<p><strong>Summary.</strong> 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.)</p>

<p><strong>Details.</strong> 
The following proof of the Birkhoff&ndash;von Neumann theorem can be found e.g. in [1], and leads to an efficient algorithm for decomposing doubly-stochastic matrices.</p>

<p>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.</p>

<ul>
<li>Set $t \gets 0$.</li>
<li><p>While $N &gt; 0$:</p>

<ol>
<li>Set $t \gets t + 1$.</li>
<li>For each $i \in [n]$: let $S_i = \bigl\{ j \in [n]: A_{ij} &gt; 0 \bigr\}$.</li>
<li>Find a bijection $\sigma: [n] \to [n]$ such that $\sigma(i) \in S_i$<br>(such a bijection exists, and can be found efficiently, by Hall's Marriage criterion).</li>
<li>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]$. </li>
<li>Update $A \gets \bigl(A - u^{(t)} P^{(t)}\bigr)$, and update $N$ to the number of non-zero elements of $A$<br>(which is smaller by at least $1$).</li>
</ol></li>
<li><p>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.</p></li>
</ul>

<p>[1] <a href="https://books.google.co.uk/books?id=8-ipCAAAQBAJ&amp;lpg=PA58&amp;ots=aoNEzv1fh_&amp;dq=decomposing%20doubly%20stochastic%20matrices&amp;pg=PA58#v=onepage&amp;q=decomposing%20doubly%20stochastic%20matrices&amp;f=false" rel="nofollow">Extremal Combinatorics: With Applications in Computer Science</a> by Stasys Jukna</p>

CC BY-SA 3.0
2015-10-13T09:39:31.193Z
2015-10-13T13:46:15.733Z
2015-10-13T13:46:15.733Z
Niel de Beaudrap
<p>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.</p>

<p>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$ ?</p>

CC BY-SA 3.0
2015-10-13T09:40:30.143Z
A good chestnut, but this question should be migrated to CS.SE.
Niel de Beaudrap
<ds.algorithms><co.combinatorics><approximation-algorithms><permutations><permanent>
The complexity of decomposing a bi-stochastic matrix
Lior Eldar
# The complexity of decomposing a bi-stochastic matrix

(Asked by: username_0 on 2015-10-12)

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$ ?

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms, permutations, permanent

> **Comments:**
> **username_1**: A good chestnut, but this question should be migrated to CS.SE.  

---

## 1 answers

### Answer by username_1 on 2015-10-13. Score: 6 | Accepted answer

**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](https://books.google.co.uk/books?id=8-ipCAAAQBAJ&lpg=PA58&ots=aoNEzv1fh_&dq=decomposing%20doubly%20stochastic%20matrices&pg=PA58#v=onepage&q=decomposing%20doubly%20stochastic%20matrices&f=false) by Stasys Jukna


---

