Carathéodory's_theorem_(convex_hull) (original) (raw)

If , then is the nonnegative sum of at most points of . If , then is the convex sum of at most points of . (en)
If then , exists such that , and at most of them are nonzero. (en)

This is trivial when . If we can prove it for all , then by induction we have proved it for all . Thus it remains to prove it for . This we prove by induction on . Base case: , trivial. Induction case. Represent . If some , then the proof is finished. So assume all If is linearly dependent, then we can use induction on its linear span to eliminate one nonzero term in , and thus eliminate it in as well. Else, there exists , such that . Then we can interpolate a full interval of representations: If for all , then set . Otherwise, let be the smallest such that one of . Then we obtain a convex representation of with nonzero terms. (en)
For any , represent for some , then , and we use the lemma. The second part reduces to the first part by "lifting up one dimension", a common trick used to reduce affine geometry to linear algebra, and reduce convex bodies to convex cones. Explicitly, let , then identify with the subset . This induces an embedding of into . Any , by first part, has a "lifted" representation where at most of are nonzero. That is, , and , which completes the proof. (en)