Extremal point in some compact and convex set is a permutation

Question

Assume that $P$ is a compact and convex set in $\mathbb{R}^N$. Then $x\in P$ is extremal point of $P$ s.t. $x=tv+(1-t)w$ for some $v,\ w\in P$ and some $t\in (0,1)$ implies $$ x=v=w$$

Problem : If $N=n^2$, define a compact and convex subset $P$ which is set of all $x$ : $$\sum_jx_{ij} =\sum_j x_{ji}=1 $$ and $$ x_{ij}\geq 0 $$ Then prove that set of all extremal point in $P$ is a set of all permutation matrices.

Proof : By considering a sphere of radius $\sqrt{n}$, note that all permutation matrices are extremal points.

However, I can not invest around a hyperplane $x_{ij}=0$. How can we prove this ?

Thank you in advance.

Answer 1

To prove other direction suppose you have extremal matrix which is not permutation! Think about a matrix which is not permutation matrix , in this matrix always you can find (at least )four entries say $a,b,c,d $ such that $ 0 <a,b,c,d <1 $ and $\min\{a,b,c,d\} = a$. Then try to rewrite this matrix in terms of mid point of two other matrices in $P$. This gives you a contradiction.

for example in $\Bbb R^{3 \times 3}$ we have

$$ \begin{bmatrix} 1 &0 &0 \\ 0& a &c \\ 0& b& d \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 &0 &0 \\ 0& 0 & c+a \\ 0& b+a & d-a \end{bmatrix} + \frac{1}{2} \begin{bmatrix} 1 &0 &0 \\ 0& a +a &c-a \\ 0& b - a & d+a \end{bmatrix} $$

You can generalize this idea to $\Bbb R^{n \times n}$

Answer 2

The permutation matrices are exactly $\mathbb{Z}^{n^2} \cap P $ so if a matrix $M$ is extremal but not a permutation matrix, there is a non-integer entry $x_{i_1, j_1}$.

Since sum of lines and of columns is integer there is another entry $x_{i_1, \sigma (j_1)}$ that is non-integer, and another entry $x_{\tau(i_1), \sigma(j_1)}$, call $i_2 = \tau(i_1) $ and $j_2 = \sigma(j_1) $, repeat the process until you repeat an entry. wlog you repeat the original entry $(i_1, j_1) = (i_{m+1}, j_{m+1})$.

Now $M = M_{-\epsilon} /2 + M_{+\epsilon }/2 $ where $M_{+\epsilon } $ is obtained from $M$ by: - adding $\epsilon $ to all the entries $(i_k, j_k)$ - subtracting $\epsilon $ to all the entries $(i_k, j_{k+1})$

And $M_{-\epsilon } $ is obtained from $M$ by: - subtracting $\epsilon $ to all the entries $(i_k, j_k)$ - adding $\epsilon $ to all the entries $(i_k, j_{k+1})$

Now choose $\epsilon $ close enough to $0$ so that both $M_{\pm \epsilon}$ lie in $P$. Hence $M$ is not extremal. Done.