# Doubly stochastic matrices as linear combinations of permutation matrices

For a doubly stochastic matrix ($n \times n$) that is a linear combination of $N$ permutation matrices, how do we prove that $N = (n - 1)^2 + 1$ suffices?

• @ Vijay , have you bothered to read my answer ? – loup blanc Sep 29 '16 at 10:06

Let $DS_n$ be the set of doubly stochastic matrices.; $DS_n$ is a compact convex set of dimension $(n-1)^2$. According to the Minkowski-Caratheodory theorem, any point of $DS_n$ is a convex combination of at most $(n-1)^2+1$ extreme points of $DS_n$. The conclusion comes from the fact that the extreme points of $DS_n$ are the permutation matrices.