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 [1] 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.

**Input**: A doubly stochastic matrix .

**Output**: A Birkhoff-von Neumann decomposition of as .

**Measure**: The number of permutation matrices in the decomposition.

The NP-completeness of the decision version of this problem is shown in a recent technical report [2].

**References**

- 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).