# Proof that the set of doubly-stochastic matrices forms a convex polytope?

Does the set of all doubly-stochastic matrices form a convex polytope? In general, I wonder how the proofs of convexity and geometry can be established for sets of matrices of this kind? Anything to do with the birkhoff's theorem!? Am not sure, if I am thinking in the right direction and hence the post.

• I'm confused. Dense in what? It seems that the permutation matrices are contained in $\text{GL}_n(\mathbb{Z})$ which isn't dense in anything (it's discrete?)! – Alex Youcis Mar 10 '13 at 2:11
• There are only finitely many permutation matrices (and generally more than one). You might be confusing this with permutation matrices being in convex position. But this is trivial to prove once you write down the definition. – Erick Wong Mar 10 '13 at 2:13
• Ok...well you are right, as any doubly-stochastic matrix can be written as a convex combination of permutation matrices (finite number). Do all the doubly stochastic matrices form a convex set? I wonder , if there is a well known strategy/theorem that proves/disproves these sets of matrices as forming convex polytopes? – qlinck Mar 10 '13 at 2:19
• @qlinck The definition of a convex set is very easy to verify for doubly-stochastic matrices, no strategy required. Should your real question be how to prove that a given convex set is a polytope? – Erick Wong Mar 10 '13 at 2:31
• Let $\mathbf a = \mathrm{vec}(\mathbf A)$ where the vectorization stacks columns from left to right. Then, $0 \leq a_{ij} \leq 1$ must be satisfied and there are two matrices, $\mathbf C$ and $\mathbf R$ in $\mathbb R^{n \times n^2}$ such that $\mathbf C \mathbf a = \mathbf 1$ and $\mathbf R \mathbf a = \mathbf 1$. This is already enough since there is, then, a matrix $\mathbf B$ and vector $\mathbf c$ such that $\mathbf A$ is doubly stochastic iff $\mathbf B \mathbf a \leq \mathbf c$ where the inequality is interpreted coordinatewise. – cardinal Mar 10 '13 at 3:08

We identify the space of matrix $\mathbb{R}^{n\times n}$ with $\mathbb{R}^{n^2}$. A matrix $(a_{i,j})_{i,j\leq n}$ is doubly stochastic if

1. $0\leq a_{i,j}\leq 1\ \forall i,j$
2. $\sum_i a_{i,j}=1 \ \forall j$
3. $\sum_j a_{i,j}=1 \ \forall i$

It is direct to check that if $(a_{i,j})_{i,j\leq n}$ and $(b_{i,j})_{i,j\leq n}$ are doubly stochastic then $(t a_{i,j}+ (1-t) b_{i,j})_{i,j\leq n}$ is doubly stochastic for any $0\leq t\leq1$ (the conditions above are clearly fulfilled). This gives the convexity.

To observe that the set of doubly stochastic matrices is a polytope in $\mathbb{R}^{n^2}$ we just need to have in mind that a polytope can be defined as a finite intersection of half-spaces. The conditions above are actually $2n^2+4$ inequalities (have in mind that $a=b\iff (a\leq b \text{ and } b\leq a)$ ).

I think it is usual to consider that a polytope is bounded, here this is clear because of condition $1$.

Edit: As you suggested in your question, this is a direct corollary of Birkhoff-Von Neumann theorem which is much stronger. The Birkhoff–von Neumann theorem states that the set of doubly stochastic matrices is the convex hull of the set of permutation matrices. Their is a finite number of permutations and the convex hull of a finite number of points is a convex body, so the corollary is immediate. But if you just want to see that this is a convex polytope without beeing more precise you don't need to use this theorem, the elementary arguments used above are sufficients.