Michele Benzi, Alex Pothen and I have been making use of the celebrated Birkhoff-von Neumann theorem on doubly stochastic matrices. The theorem says that any doubly stochastic matrix can be written as a convex combination of a finitely many permutation matrices. Formally, let be a doubly stochastic matrix. Then,
where and each is a permutation matrix.
Given this formulation, one wonders if the decomposition is unique. Well, the answer is “No”. Then, one asks what can be said about the number . And this is the main topic of this post.
Richard A. Brualdi  discusses many things among which a lower bound and an upper bound on . The minimum number of permutation matrices is equal to the maximum cardinality of a set of nonzeros positions of no two of which could appear together in a single permutation matrix in the pattern of . An easy lower bound is then equal to the maximum number of nonzeros in a row or a column of . The upper bound is , for a fully indecomposable matrix with nonzeros; more generally if there are fully indecomposable blocks, then the upper bound is .
What about the minimum number of permutation matrices? It turns out that this is an NP-complete problem. Let’s state it in the form of a standard NP-completeness result.
The NP-completeness of the decision version of this problem is shown in a recent technical report .
- Richard A. Brualdi, Notes on the Birkhoff algorithm for doubly stochastic matrices, Canadian Mathematical Bulletin, 25(2), 191–199, 1982 (doi).
- Fanny Dufossé and Bora Uçar, Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices, Technical Report, RR-8852, Inria Grenoble Rhône-Alpes, 2016 (link).