The complexity of decomposing a bi-stochastic matrix

Question

A bistochastic matrix $A$ is a matrix with positive entries in which each row/column sums to $1$. By the Birkhoff von-Neumann theorem $A$ is a convex combination of permutation matrices. Further, by the Caratheodory theorem, $A$ can be written as a convex combination of at most $n^2 +1$ such matrices.

What is known about the complexity of finding any such permutation-matrix decomposition of A? Is this problem known to be NP-hard ? Furthermore, suppose we are provided with such a succinct description of $A$, i.e. $$ A = \sum_{i=1}^{n^2+1} c_i P_i, \ \ \sum_i c_i = 1, c_i \geq 0, $$ where each $P_i$ is a permutation matrix. Are there problems related to bi-stochastic matrices that become easier, say computing the permanent of $A$ ?

Answer 1

Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using $O(\max\{n^{d+2},n^4\})$ operations over the reals for decomposing doubly-stochastic matrices. The run-time bound comes from $O(n^2)$ iterations of a procedure in which each iteration involves finding a matching, and modifying coefficients of an $n \times n$ matrix. (There are undoubtedly ways of streamlining these operations, at least in the case of the time required to modify the matrix coefficients.)

Details. The following proof of the Birkhoff–von Neumann theorem can be found e.g. in [1], and leads to an efficient algorithm for decomposing doubly-stochastic matrices.

We consider matrices $A$ whose rows and columns all sum to the same value (which for a doubly-stochastic input is initially 1). Let $N$ be the number of non-zero entries in your $n \times n$ doubly-stochastic matrix: in decomposing the matrix, we will reduce the number of non-zero entries while keeping the invariant of having constant line-sums. Thus at each stage, we have either $N \geqslant n$ or $N = 0$, by the invariant of having equal line-sums.

• Set $t \gets 0$.

• While $N > 0$:

  1. Set $t \gets t + 1$.
  2. For each $i \in [n]$: let $S_i = \bigl\{ j \in [n]: A_{ij} > 0 \bigr\}$.
  3. Find a bijection $\sigma: [n] \to [n]$ such that $\sigma(i) \in S_i$
     (such a bijection exists, and can be found efficiently, by Hall's Marriage criterion).
  4. Let $u^{(t)} = \min\,\bigl\{A_{i,\sigma(i)} : i \in [n]\bigr\}$, and let $P^{(t)}$ be the permutation matrix for which $P^{(t)}_{i,\sigma(i)} = 1$ for each $i \in [n]$.
  5. Update $A \gets \bigl(A - u^{(t)} P^{(t)}\bigr)$, and update $N$ to the number of non-zero elements of $A$
     (which is smaller by at least $1$).

• Return $\bigl(u^{(1)},P^{(1)}\bigr)$, ... $\bigl(u^{(t)},P^{(t)}\bigr)$, representing the decomposition $\sum_{i\in[t]} u^{(i)} P^{(i)}$ of the input.

[1] Extremal Combinatorics: With Applications in Computer Science by Stasys Jukna