Birkhoff-von Neumann theorem for bistochastic digraphs

Question

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).

Answer 1

From Roger A. Horn "Topics in Matrix Analysis", section 3.2 page 164-165.

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

Every doubly substochastic matrix is a finite convex combination of partial permutation matrices.

The bistochastic digraphs are doubly substochastic matrices, so the generalized Birkhoff-von Neumann theorem can be applied directly for them. Or one can just apply the same reduction directly. This means taking the original digraph and a copy of the digraph where all edges are reversed, and connecting the sources and sinks to their copy by suitable oriented edges of weight 1.

However, it turned out that the notion of a doubly substochastic matrix is more suitable with respect to the original motivation for this question than the notion of a bistochastic digraph. It is a good thing that the above construction directly covers that case too.