# On the Birkhoff-von Neumann decomposition

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 $\mathbf{A}$ be a doubly stochastic matrix. Then,

$\mathbf{A}=\sum_{j=1}^k \alpha_j \mathbf{P}_j\;,$

where $\alpha_j>0, \sum_j \alpha_j=1$ and each $\mathbf{P}_j$ 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 $k$. 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 $k$. The minimum number of permutation matrices is equal to the maximum cardinality of a set of nonzeros positions of $\mathbf{A}$ no two of which could appear together in a single permutation matrix in the pattern of $\mathbf{A}$. An easy lower bound is then equal to the maximum number of nonzeros in a row or a column of $\mathbf{A}$. The upper bound is $\mathrm{nnz}(\mathbf{A})-2n+2$, for a fully indecomposable matrix $\mathbf{A}$ with $\mathrm{nnz}(\mathbf{A})$ nonzeros; more generally if there are $b$ fully indecomposable blocks, then the upper bound is $\mathrm{nnz}(\mathbf{A})-2n+b+1$.

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 $\mathbf{A}$.
Output: A Birkhoff-von Neumann decomposition of $\mathbf{A}$ as $\mathbf{A} = \alpha_1\mathbf{P}_1 + \alpha_2\mathbf{P}_2 + \cdots +\alpha_k\mathbf{P}_k$.
Measure: The number $k$ 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

1. Richard A. Brualdi, Notes on the Birkhoff algorithm for doubly stochastic matrices, Canadian Mathematical Bulletin, 25(2), 191–199, 1982 (doi).
2. 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).