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