Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 5 down vote accepted

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$.

Addendum: This is more or less the same proof as the proof of the Birkhoff-von Neumann theorem that user1551 mentioned.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.