# Birkhoff-von Neumann theorem for bistochastic digraphs

A weighted digraph (with loops) is bistochastic, iff

1. the weights are non-negative,
2. for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and
3. for all non-source nodes, the sum of the edge weights of the in-edges is $1$.

The Birkhoff-von Neumann theorem for a bistochastic matrix states that a bistochastic matrix is a convex combination of permutation matrices. It would be nice to characterize the bistochastic digraphs with a given underlying digraph in a similar way as a convex combination.

Attempted reduction to the Birkhoff-von Neumann theorem: If the underlying digraph has no source and sink nodes, then we can conclude from the Birkhoff-von Neumann theorem that the convex combinations of the in-degree = out-degree = 1 subdigraphs with n-nodes give all possible bistochastic digraphs (because a $n\times n$ permutation matrix corresponds to a in-degree = out-degree = 1 digraph with $n$-nodes, and only subdigraph can occur in the convex combination since no edge can be canceled out).

If the number of source nodes is equal to the number of sink nodes, then connecting each sink with exactly one source allows to reduce the problem to the previous case (because the weight of the newly added edges can only be 1). But if the number of source nodes is different from the number of sink nodes, then I guess that there exists no bistochastic digraph for that underlying digraph. The weights seem to define a flow on the digraph, so the min-cut max-flow theorem should help.

Even so this reduction seems to work, the case distinctions feel less attractive than the Birkhoff-von Neumann theorem. I would prefer to reduce it completely to the Birkhoff-von Neumann theorem (by connecting each sink with each source?), or reduce it completely to the min-cut max flow theorem (or something similar).

A matrix $Q$ is said to be doubly substochastic if its entries are nonnegative and all its row and column sums are at most one.
The doubly stochastic matrix $\begin{bmatrix} Q & I-D_r\\I-D_c & Q^T\end{bmatrix}$ is a dilation of $Q$, where $D_r$ and $D_c$ are diagonal matrices with the row and column sums of $Q$ respectively. This dilation allow to reduce the generalization of the Birkhoff-von Neumann theorem for substochastic matrices to the original theorem