Question

Show that \(C\) is a convex set in a vector space if and only if \(\sum \lambda_{i} x_{i} \in C\) whenever \(x_{1}, \ldots, x_{n} \in C\) and \(\lambda_{1}, \ldots, \lambda_{n} \geq 0\) satisfy \(\sum \lambda_{i}=1\) Hint: (a) \(\lambda_{1} x_{1}+\lambda_{2} x_{2}+\lambda_{3} x_{3}=\left(\lambda_{1}+\lambda_{2}\right)\left(\frac{\lambda_{1}}{\lambda_{1}+\lambda_{2}} x_{1}+\frac{\lambda_{2}}{\lambda_{1}+\lambda_{2}} x_{2}\right)+\lambda_{3} x_{3}\) and induction.

Short answer

A set C is convex if and only if any convex combination of points in C, with non-negative coefficients summing to 1, is also in C.

Step-by-step solution

Understand the Definition of a Convex Set

A set C is convex if, for any two points x and y in C, the line segment connecting these points is also in C. Mathematically, this means that for any x, y ∈ C and for any λ such that 0 ≤ λ ≤ 1, the point λx + (1 - λ)y is also in C.

Given Property of the Convex Set

According to the problem, we need to prove that C is convex if and only if for any finite set of points x_{1}, x_{2}, ..., x_{n} in C, and any non-negative real coefficients λ_{1}, λ_{2}, ..., λ_{n} satisfying \(\sum_{i=1}^n \lambda_i = 1\), it holds that \(\sum_{i=1}^n \lambda_i x_i \in C\).

Prove the 'Only If' Direction

Assume C is a convex set. By definition, this means that for any x, y ∈ C and λ such that 0 ≤ λ ≤ 1, the combination \(\lambda x + (1 - \lambda)y \in C\). To extend this to more points, use induction. Start by considering three points x_{1}, x_{2}, and x_{3} in C. Using the hint: \(\lambda_{1} x_{1} + \lambda_{2} x_{2} + \lambda_{3} x_{3} = (\lambda_{1} + \lambda_{2})(\frac{\lambda_{1}}{\lambda_{1} + \lambda_{2}} x_{1} + \frac{\lambda_{2}}{\lambda_{1} + \lambda_{2}} x_{2}) + \lambda_{3} x_{3}\). Since C is convex, the term inside the parentheses is in C, thus the sum is in C. The same argument can be applied iteratively for any number of points and corresponding coefficients.

Prove the 'If' Direction

Assume instead that for any finite set of points x_{1}, x_{2}, ..., x_{n} in C and any non-negative real coefficients λ_{1}, λ_{2}, ..., λ_{n} satisfying \(\sum_{i=1}^n \lambda_i = 1\), it holds that \(\sum_{i=1}^n \lambda_i x_i \in C\). To show that C is convex, take any two points x and y in C. Use the given assumption with n=2, λ_{1}=λ, λ_{2}=1-λ, where 0 ≤ λ ≤ 1, and see that \(\lambda x + (1-\lambda)y \in C\). Hence, C is convex.

Key concepts

Vector Space

Understanding a vector space is crucial for working with convex sets. A vector space is a collection of vectors, where vectors can be added together and scaled by numbers, called scalars, to produce another vector within the same space. Imagine vectors as arrows that can point in any direction, and their length can be changed.

For example, vectors in a 2-dimensional space can be represented as pairs like (x, y). You can add two vectors (x1, y1) and (x2, y2) to get a new vector (x1 + x2, y1 + y2). You can also scale a vector by multiplying it by a scalar, so scaling (x, y) by a factor α results in (αx, αy).

This concept is more abstract in higher dimensions, but the principles remain the same. In the context of the problem, we need to understand that any operations performed on the given vectors should remain within the vector space.

Convex Combination

A convex combination is a specific way to combine a set of points where the coefficients (called weights) used to combine them are all non-negative and sum to 1. In simpler terms, if you have points x1, x2, ..., xn, a convex combination would look like \(\lambda_{1} x_{1} + \lambda_{2} x_{2} + ... + \lambda_{n} x_{n} \) where \(\lambda_{1} + \lambda_{2} + ... + \lambda_{n} = 1 \).

The concept of convex combinations is essential when dealing with convex sets. A convex set is defined such that for any two points in the set, the line segment connecting them lies entirely within the set. By extending this idea, if a set is convex, any convex combination of points from the set will also lie within the set. Think of a convex combination as a 'weighted average' where the sum of all weights is 1, ensuring that the resultant point lies within the limits defined by the original points.

Proof by Induction

Proof by induction is a method to prove statements for all natural numbers. It is a powerful technique frequently used in mathematics. The idea is to show that if a statement is true for some base case, and if assuming it's true for some case 'k' implies it is true for the next case 'k+1', then the statement is true for all cases.

Let's break it down with an example:

• Base Case: Show that the statement is true for the first natural number (usually 1).
• Induction Hypothesis: Assume the statement is true for an arbitrary natural number k.
• Inductive Step: Show that if the statement is true for k, it must be true for k+1.

In the context of our convex set problem, we start by proving the statement for a small, manageable number of points. Then, using the induction hypothesis, we assume it's true for a certain number of points and then prove it's true for one more point. This method allows us to generalize the proof to any finite number of points. By using the hint given in the exercise, we apply the principle of induction to extend from combinations of three points to any number of points, reaffirming the set's convexity.