Theorem 13.1.18: Caratheodory

Theorem 13.1.18 (Caratheodory).label Let $A\suf\R^{n}$ then $\fall x\in Conv(A)$, $\exists \curl{\lam_i}_{1}^{n+1}\geq 0,\sums{n+1 }{i=1}\lam_{i}=1$ and $\curl{x_i}_{1}^{n+1}\in A$ such that $x=\sums{n+1}{i=1}\lam_{i}x_{i}$.

Proof. Suppose $\exists x\in Conv(A)$ such that $x=\sums{m}{i=1}\lam_{i}x_{i},m=n+2,\sums{m }{i=1}\lam_{i}=1,x_{i}\in A,i=\cl{i,m}$. WLOG $\lam_{i}\neq 0,i=\cl{1,m}$. Consider $x_{1}-x_{m},...,x_{m-1}-x_{m}\implies \exists a_{i}\in \R$ such that $\sums{m-1}{i=1}a_{i}(x_{i}-x_{m})=\vec{0}$. Let $a_{m}\define -\sums{m-1}{i=1}a_{i}$ then

$\sums{m }{i=1}a_{i}=0$
$\sums{m }{i=1}a_{i}x_{i}=\vec{0}$
$\sums{m-1}{i=1}a_{i}x_{i}-\parens{\sums{m-1}{i=1}a_i}x_{m}=\vec{0}$

We can assume that at least one of $a_{i}$ is positive and define

\begin{align*}t&\define \MIN{i:a_i>0}\frac{\lam_{i}}{a_{i}}>0\\ \mu_{i}&\define \lam_{i}-ta_{i}&&i=\cl{1,m}\end{align*}

Observe $\mu_{i}\geq 0,i=\cl{1,m}$ since $a_{i}t<\lam_{i}$ for all $i$ such that $a_{i}>0$. Furthermore

\begin{align*}\sums{m}{i=1}\mu_{i}=\sums{m }{i=1}\lam_{i}-t \sums{m }{i=1}a_{i}=1-0=1\end{align*}

Consider

\begin{align*}\sums{m }{i=1}\mu_{i}x_{i}=\sums{m}{i=1}\lam_{i}x_{i}-t \sums{m}{i=1}a_{i}x_{i}=x-0\end{align*}

Hence $x$ can be written as the convex combination of $n+1$ points.$\square$

The Eigenspace

Post a Comment

The Eigenspace