# Polytopes and matrices

How can one show that the vertices of a polytope are the matrices contains 2 ones on each row and col? and if $M \in P$ is not a $Z_2$ matrix then $M$ is a derived from two other matrices in $P$?

Number of $(0,1)-$matrices with exactly two $1$'s in each row and column

-
Do I understand correctly that you're assuming as given that the set of real $m\times m$ matrices with entries bounded between $0$ and $1$ and all row and column sums $2$ is a polytope? –  joriki Feb 11 '13 at 20:39
That wasn't my question; I know it is. I was asking whether you're assuming this as given. –  joriki Feb 11 '13 at 20:43
Can you modify the proofs of the Birkhoff-von Neumann theorem, like this one? –  user1551 Feb 12 '13 at 0:39

A point is a vertex of a closed convex polytope iff it's not expressible as a nontrivial convex combination of other points in the polytope. It's clear that the $0$-$1$ matrices with $2$ ones in each row and column are not expressible as nontrivial convex combinations of other points in the polytope $P$. Therefore resolving question $2$ also solves question $1$.
For a matrix $M=(m_{k\ell})\in P$ which is not a $0$-$1$ matrix, construct a graph whose vertices are all $(k,\ell)$ such that $m_{k\ell}\notin\{0,1\}$. Join each pair of vertices in the same row with a red edge and each pair of vertices in the same column with a green edge.
Since the sum of each column is $2$, which is an integer, for each $(k,\ell)$ such that $m_{k\ell}\notin\{0,1\}$, there must be some $k'\ne k$ such that $m_{k'\ell}\notin\{0,1\}$. Therefore, each vertex must have at least one green edge incident to it. Similarly, since the sum of each row is integral, each vertex must have at least one red edge incident to it. Therefore, we can start at any vertex $v_0$, and then follow a red edge from $v_0$ to $v_1\ne v_0$, a green edge from $v_1$ to $v_2\ne v_1$, and so on, alternating red and green edges. Let $j$ be minimal with $v_j\in\{v_0,\ldots,v_{j-1}\}$, and let $i\in\{0,\ldots,j-1\}$ satisfy $v_i=v_j$. The chain of edges from $v_i$ to $v_j$ is then a cycle, and, by construction, $i<j-1$, so it has at least one red and one green edge. Collapsing adjacent red edges and adjacent green edges gives a cycle of distinct vertices connected by alternating red and green edges. Write down alternating $+1$s and $-1$s next to the vertices in the cycle, and let $s(v)$ be the number written next to vertex $v$.
For each vertex $v=(k,\ell)$ in the cycle, let $\phi(v):=\min(m_{k\ell},1-m_{k\ell})$, and let $\epsilon>0$ be the minimum of the $\phi(v)$s. Then, construct the matrix $M_+$ from $M$ by, for each $v=(k,\ell)$ in the cycle, adding $s(v)\epsilon$ to $m_{k\ell}$. Similarly, construct $M_-$ by, for each $v=(k,\ell)$ in the cycle, subtracting $s(v)\epsilon$ from $m_{k\ell}$. Then $M_-$ and $M_+$ are both in $P$ but $M=(M_-+M_+)/2$. Therefore, $M$ is a convex combination of two other matrices in $P$.