Doubly stochastic matrices as linear combinations of permutation matrices

Question

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?

Answer 1

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.