Math challenge (99% fail) Let S C R^n. Prove that every point in conv(S), the convex…
- User
Math challenge (99% fail) Let S C R^n. Prove that every point in conv(S), the convex hull of S, is a convex combination of at most n + 1 points of S
- Assistant
Certainly! This statement is a version of Carathéodory's Theorem, a fundamental result in convex geometry. Let's delve into the theorem and provide a detailed proof.
Carathéodory's Theorem
Theorem:
Let ( S \subset \mathbb{R}^n ). Then, any point ( x ) in the convex hull of ( S ), denoted ( \text{conv}(S) ), can be expressed as a convex combination of at most ( n + 1 ) points from ( S ).In other words: For every ( x \in \text{conv}(S) ), there exist points ( x_1, x_2, \dots, x_{n+1} \in S ) and non-negative scalars ( \lambda_1, \lambda_2, \dots, \lambda_{n+1} ) such that [ x = \lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_{n+1} x_{n+1}, ] with [ \lambda_1 + \lambda_2 + \dots + \lambda_{n+1} = 1. ]
Proof of Carathéodory's Theorem
We will prove the theorem using induction on the dimension ( n ).
Base Case: ( n = 1 )
In ( \mathbb{R}^1 ), any convex hull of a set ( S ) is just the interval between the minimum and maximum points in ( S ). Any point ( x ) in this interval can be expressed as a convex combination of at most two points (the endpoints) from ( S ).
Thus, the base case holds.
Inductive Step
Assume that the theorem holds for ( \mathbb{R}^{n-1} ). We need to show it holds for ( \mathbb{R}^n ).
-
Express ( x ) as a Convex Combination:
Let ( x \in \text{conv}(S) ). By definition, there exist finitely many points ( y_1, y_2, \dots, y_m ) in ( S ) and scalars ( \alpha_1, \alpha_2, \dots, \alpha_m ) with ( \alpha_i \geq 0 ) and ( \sum_{i=1}^m \alpha_i = 1 ) such that [ x = \sum_{i=1}^m \alpha_i y_i. ]
-
Affine Independence Check:
If the set ( {y_1, y_2, \dots, y_m} ) contains a subset of ( n+1 ) points that are affinely independent and still represent ( x ), then we are done. If not, there exists a linear dependence among these ( n+1 ) points.
-
Find a Redundant Point:
Suppose ( m > n + 1 ). Among the ( n + 2 ) points ( y_1, y_2, \dots, y_{n+2} ) (if ( m \geq n + 2 )), at least one point is a convex combination of the others because they lie in ( \mathbb{R}^n ).
Specifically, there exist coefficients ( \beta_1, \beta_2, \dots, \beta_{n+2} ), not all zero, such that [ \sum_{i=1}^{n+2} \beta_i y_i = 0, ] and [ \sum_{i=1}^{n+2} \beta_i = 0. ]
Without loss of generality, assume ( \beta_{n+2} \neq 0 ). Then, [ y_{n+2} = \sum_{i=1}^{n+1} \left( -\frac{\beta_i}{\beta_{n+2}} \right) y_i. ]
Let ( \lambda_i = \alpha_i \left( 1 + \frac{\beta_i}{\beta_{n+2}} \right) ) for ( i = 1, 2, \dots, n+1 ). By adjusting the coefficients, we can express ( x ) without ( y_{n+2} ).
-
Reducing the Number of Points:
By removing ( y_{n+2} ) and appropriately adjusting the coefficients ( \alpha_i ), we have expressed ( x ) as a convex combination of ( n + 1 ) points. This follows because the existence of an affine dependence allows us to write one point as a combination of others, effectively reducing the number of points needed.
-
Applying the Inductive Hypothesis:
After reducing the number of points to ( n + 1 ), the point ( x ) lies in the convex hull of these ( n + 1 ) points. If among these there are still more than ( n + 1 ), repeat the process. Eventually, this process must terminate with ( x ) expressed as a convex combination of at most ( n + 1 ) affinely independent points.
Conclusion
By induction, Carathéodory's Theorem holds for all ( \mathbb{R}^n ). Therefore, every point in the convex hull of a set ( S ) in ( \mathbb{R}^n ) is a convex combination of at most ( n + 1 ) points from ( S ).
Example
Consider ( \mathbb{R}^2 ) (so ( n = 2 )). Suppose ( S ) consists of five points in the plane, and let ( x ) be a point in the convex hull of ( S ). According to Carathéodory's Theorem, ( x ) can be expressed as a convex combination of at most ( 3 ) points from ( S ).
Even if ( S ) has many points, any point within its convex hull doesn't require all of them for its representation, just a minimal subset of ( n + 1 = 3 ) points.
This completes the proof of Carathéodory's Theorem, confirming that every point in the convex hull of a set ( S \subset \mathbb{R}^n ) can indeed be expressed as a convex combination of at most ( n + 1 ) points from ( S ).
-