2
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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