Differences

This shows you the differences between two versions of the page.

--- world:choquet [2026/04/10 14:55]
rdouc
+++ world:choquet [2026/04/10 15:48] (current)
rdouc [Krein-Milman, Choquet and Birkhoff-Von Neuman Theorems]
@@ Line 3: / Line 3: @@
 ====== Krein-Milman, Choquet and Birkhoff-Von Neuman Theorems ======
-<WRAP center round todo 80%>
+<WRAP center round todo>
 **Definition:** Let $K$ be convex. We say that $x \in K$ is an extreme point if
 $$
@@ Line 9: / Line 9: @@
 $$
 We denote by $\mathrm{Extr}(K)$ the set of extreme points.
 </WRAP>
-<WRAP center round tip 80%>
+<WRAP center round tip>
 **Theorem (Krein–Milman).** Let $E$ be a Euclidean space of dimension $n$ and $K \subset E$ convex, compact, non-empty. Then
 $$
 K = \mathrm{conv}(\mathrm{Extr}(K)).
 $$
+where the notation $\mathrm{conv}(G)$ stands for the convex enveloppe of the set $G$.
 </WRAP>
-**Proof.**
+<hidden **Proof.**>
 It suffices to show $K \subset \mathrm{conv}(\mathrm{Extr}(K))$, the reverse inclusion being clear by convexity of $K$.
 The proof proceeds by induction on $n$, the dimension of $E$. We assume the property is true for every Euclidean subspace of dimension $n-1$. Without loss of generality, we assume that $K$ is not reduced to a singleton.
-Let $x \in K$. Choose $y \in K \setminus \{x\}$ arbitrarily. Consider $[a,b]$ the maximal segment contained in $K$ and containing $[x,y]$. Since $a,b \in K$ and $x$ is a convex combination of $a,b$, it suffices to show that $a,b \in \mathrm{conv}(E)$. We prove that $a \in \mathrm{conv}(E)$ (the case $b \in \mathrm{conv}(E)$ is similar). Since $a \in \partial K$, there exists a sequence $a_k \notin K$ converging to $a$ and for each $k$, we choose $u_k$ unitary such that for all $y \in K$, $\langle y-a_k,u_k \rangle \geq 0$. We can extract from $(u_k)$ a convergent subsequence on the unit sphere, and let $u$ be its limit. Passing to the limit yields $\langle y-a,u \rangle \geq 0$. Thus, defining $f(y)=\langle y-a,u \rangle$, we obtain that $a \in H_a=f^{-1}(0) \cap K=\mathrm{argmin}_{y\in K} f(y)$. The set $H_a$ is convex, compact, non-empty in a space of dimension $n-1$, and the induction hypothesis shows that $a \in \mathrm{conv}(\mathrm{Extr}(H_a))$. It remains to show that $\mathrm{Extr}(H_a) \subset \mathrm{Extr}(K)$. Indeed, since $K$ is convex and $f$ is linear, if $z \in \mathrm{Extr}(H_a)$ can be written $z=\lambda x + (1-\lambda) y$ with $x,y \in K$, then $f(z)=0=\lambda f(x) + (1-\lambda) f(y)$, hence $f(x)=f(y)=0$, which implies $x,y \in H_a$ and thus $\lambda \in \{0,1\}$ since $z \in \mathrm{Extr}(H_a)$.
+Let $x \in K$. Choose $y \in K \setminus \{x\}$ arbitrarily. Consider $[a,b]$ the maximal segment contained in $K$ and containing $[x,y]$. Since $a,b \in K$ and $x$ is a convex combination of $a,b$, it suffices to show that $a,b \in \mathrm{conv}(\mathrm{Extr}(K))$. We prove that $a \in \mathrm{conv}(\mathrm{Extr}(K))$ (the case $b \in \mathrm{conv}(\mathrm{Extr}(K))$ is similar). Since $a \in \partial K$, there exists a sequence $a_k \notin K$ converging to $a$ and for each $k$, we choose $u_k$ unitary such that for all $y \in K$, $\langle y-a_k,u_k \rangle \geq 0$. We can extract from $(u_k)$ a convergent subsequence on the unit sphere, and let $u$ be its limit. Passing to the limit yields $\langle y-a,u \rangle \geq 0$. Thus, defining $f(y)=\langle y-a,u \rangle$, we obtain that $a \in H_a=f^{-1}(0) \cap K=\mathrm{argmin}_{y\in K} f(y)$. The set $H_a$ is convex, compact, non-empty in a space of dimension $n-1$, and the induction hypothesis shows that $a \in \mathrm{conv}(\mathrm{Extr}(H_a))$. It remains to show that $\mathrm{Extr}(H_a) \subset \mathrm{Extr}(K)$. Indeed, since  $f$ is linear, if $z \in \mathrm{Extr}(H_a)$ and $z=\lambda x + (1-\lambda) y$ with $x,y \in K$, then $f(z)=0=\lambda f(x) + (1-\lambda) f(y)$, hence $f(x)=f(y)=0$ (since $f\geq 0$ on $K$), which implies $x,y \in H_a$ and thus $\lambda \in \{0,1\}$ since $z \in \mathrm{Extr}(H_a)$. This shows that $z \in \mathrm{Extr}(K)$ and the proof is concluded.
+</hidden>
+<WRAP center round todo>
 **Theorem (Choquet).** Let $E$ be a Euclidean space and $K \subset E$ convex compact such that $\mathrm{Extr}(K)$ is compact. Let $f : E \to \mathbb{R}$ be linear and continuous. Then $f$ attains its minimum on $K$ at a point of $\mathrm{Extr}(K)$.
+</WRAP>
-**Proof.**
+<hidden **Proof.**>
 Let $x \in \mathrm{argmin}_{y\in K} f(y)$. By Krein–Milman, there exist $y_1,\ldots,y_n \in \mathrm{Extr}(K)$ such that $x$ is a convex combination of the $(y_i)$, and since $f$ is linear and $f(x)=\min_{y\in K} f(y)$, we obtain $f(x)=f(y_1)=\cdots=f(y_n)$, which completes the proof.
+</hidden>
-**Theorem (Birkhoff–Von Neumann).** Let $B_n$ be the set of bistochastic matrices, i.e. defined by
+<WRAP center round tip>
+**Theorem (Birkhoff–Von Neumann).** Let $B_n$ be the set of bistochastic matrices (of size $n\times n$), i.e. defined by
 $$
-B_n = \left\{ A = (a_{ij}) \in \mathcal{M}_n([0,1]) \mid \sum_j a_{ij} = 1,\ \sum_i a_{ij} = 1 \right\}.
+B_n = \left\{ A = (a_{ij}) \in \mathcal{M}_n([0,1]) \mid \sum_{j=1}^n a_{ij} = 1,\ \sum_{i=1}^n a_{ij} = 1 \right\}.
 $$
 Then $\mathrm{Extr}(B_n) = P_n$, the set of permutation matrices (i.e. matrices having exactly one $1$ in each row and each column).
+</WRAP>
-**Proof.**
+<hidden **Proof.**>
 A permutation matrix is clearly extreme. We prove by induction on the dimension that any extreme matrix is a permutation matrix. Assume it is true for $n-1$. Now take $A \in \mathrm{Extr}(B_n)$.
@@ Line 47: / Line 58: @@
 Thus $A$ has at most $2n-1$ nonzero entries. Therefore one of its $n$ rows contains only one nonzero entry, which must be equal to $1$. The other entries in the corresponding column must be $0$. Removing this row and column, we obtain a matrix of size $n-1$ which is still bistochastic and still extreme. By the induction hypothesis, it is a permutation matrix. Therefore $A$ is a permutation matrix, which concludes the induction.
+</hidden>

Welcome to Randal Douc's wiki

User Tools

Site Tools

Differences

Page Tools