Editing Carathéodory's theorem (convex hull) (section)

==Proof== 
'''Note:''' We will only use the fact that <math>\R</math> is an [[ordered field]], so the theorem and proof works even when <math>\R</math> is replaced by any field <math>\mathbb F</math>, together with a total order.


We first formally state Carathéodory's theorem:<ref>{{Cite book |last=Leonard |first=I. Ed |title=Geometry of convex sets |last2=Lewis |first2=J. E. |date=2016 |publisher=Wiley Blackwell |isbn=978-1-119-02266-4 |location=Hoboken, New Jersey |chapter=3.3 Convex Hulls}}</ref>
{{Math theorem
| name = Carathéodory's theorem
| note = 
| math_statement = If <math>x \in \mathrm{Cone}(S) \subset \R^d</math>, then <math>x</math> is the nonnegative sum of at most <math>d</math> points of <math>S</math>.  

If <math>x \in \mathrm{Conv}(S) \subset \R^d</math>, then <math>x</math> is the convex sum of at most <math>d+1</math> points of <math>S</math>.
}}
The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because <math>\mathrm{Conv}(S)</math> is the set of ''finite'' convex combination of elements of <math>S</math> (see the [[convex hull]] page for details).

{{Math theorem
| name = Lemma
| note = 
| math_statement = If <math>q_1, ..., q_N \in \R^d</math> then <math>\forall x \in \mathrm{Conv}(\{q_1, ..., q_N\})</math>, exists <math>w_1, ..., w_N \geq 0</math> such that <math>x = \sum_n w_n q_n</math>, and at most <math>d</math> of them are nonzero.
}}With the lemma, Carathéodory's theorem is a simple extension:
{{Math proof|title=Proof of Carathéodory's theorem|proof=  

For any <math>x\in \mathrm{Conv}(S)</math>, represent <math>x=\sum_{n=1}^N w_n q_n</math> for some <math>q_1, ..., q_N\in S</math>, then <math>x\in \mathrm{Conv}(\{q_1, ..., q_N\})</math>, and we use the lemma.

The second part{{Clarify|date=April 2024|reason=In the proof, there is a mention of two parts. The first part, which concerns the "Cone", has not been treated. The connection between the two parts ("Cone" and "Conv") is not clear.}} 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 <math>S\subset \R^d</math>, then identify <math>\R^d</math> with the subset <math>\{w \in \R^{d+1}: w_{d+1} = 1\}</math>. This induces an embedding of <math>S</math> into <math>S \times \{1\}\subset \R^{d+1}</math>.  

Any <math>x\in S</math>, by first part, has a "lifted" representation <math>(x, 1) = \sum_{n=1}^N w_n (q_n, 1)</math> where at most <math>d+1</math> of <math>w_n</math> are nonzero. That is, <math>x = \sum_{n=1}^N w_n q_n</math>, and <math>1 =\sum_{n=1}^N w_n</math>, which completes the proof.  

}}

{{Math proof|title=Proof of lemma|proof=  

This is trivial when <math>N \leq d</math>. If we can prove it for all <math>N = d+1</math>, then by induction we have proved it for all <math>N \geq d+1</math>. Thus it remains to prove it for <math>N = d+1</math>. This we prove by induction on <math>d</math>.  

Base case: <math>d=1, N = 2</math>, trivial.  

Induction case. Represent <math>x = \sum_{n=1}^{d+1} w_n q_n</math>. If some <math> w_n = 0</math>, then the proof is finished. So assume all <math>w_n > 0</math>

If <math>\{q_1, ..., q_{d}\}</math> is linearly dependent, then we can use induction on its linear span to eliminate one nonzero term in <math>\sum_{n=1}^d \frac{w_n}{w_1 + \cdots + w_d}q_n</math>, and thus eliminate it in  <math>x = \sum_{n=1}^{d+1} w_n q_n</math> as well.

Else, there exists <math>(u_1, ..., u_{d}) \in \R^{d}</math>, such that <math>\sum_{n=1}^{d} u_n q_n = q_{d+1}</math>. Then we can interpolate a full interval of representations:  

<math display="block">x = \sum_{n=1}^{d} (w_n+ \theta w_{d+1}u_n) q_n + (1-\theta) w_{d+1} q_{d+1}; \quad \theta\in[0, 1]</math>

If <math>w_n + w_{d+1} u_n \geq 0</math> for all <math>n=1, ..., d</math>, then set <math>\theta = 1</math>. Otherwise, let <math>\theta</math> be the smallest <math>\theta</math> such that one of <math>w_n + \theta w_{d+1} u_n = 0</math>. Then we obtain a convex representation of <math>x</math> with <math>\leq d</math> nonzero terms.  
}}

Alternative proofs use [[Helly's theorem]] or the [[Perron–Frobenius theorem]].<ref>{{Cite book|url=http://ebooks.cambridge.org/ref/id/CBO9780511566172|title=Convexity|last=Eggleston|first=H. G.|publisher=Cambridge University Press|year=1958|doi=10.1017/cbo9780511566172|isbn=9780511566172}} See pages 40–41.</ref><ref>{{Cite journal|arxiv=1901.00540|first1=Márton|last1=Naszódi|first2=Alexandr|last2=Polyanskii|title=Perron and Frobenius Meet Carathéodory|journal=The Electronic Journal of Combinatorics|year=2021|volume=28|issue=3|doi=10.37236/9996|s2cid=119656227}}</ref>