Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/StackCSTheory/status/659516139148550144
It seems allowed to give any such decomposition, so I clarified that (I think you can encode some hard problems if the permutation matrices need be of certain types). I erased "succinct" because it could create confusion: https://en.wikipedia.org/wiki/Succinct_data_structure
Source Link
edit approved Oct 13, 2015 at 12:28
Juan Bermejo Vega
edit approved Oct 13, 2015 at 12:28
Juan Bermejo Vega
  • 1.4k
  • 1
  • 14
  • 30

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 a succinctpermutation-matrix decomposition of A? Is itthis 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$ ?

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 such a succinct decomposition? Is it 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$ ?

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

Source Link
Lior Eldar
Lior Eldar
  • 1.2k
  • 6
  • 15

The complexity of decomposing a bi-stochastic matrix

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 such a succinct decomposition? Is it 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$ ?