Birkhoff–von Neumann Decomposition

The Birkhoff–von Neumann theorem states that the polytope of n x n doubly stochastic matrices (nonnegative matrices whose every row and column sums to 1) is the convex hull of the n! permutation matrices.

Experiment

Test sparse, uniform, and circulant doubly stochastic matrices in https://riano.app/module/birkhoff-von-neumann-decomposition:

1. Set Denominator to 3 and all nine numerators N11..N33 to 1. Click Step three times to extract cyclic permutations (1,2,3), (2,3,1), and (3,1,2) with coefficients 1/3 each.
2. Set circulant numerators [3,2,1], [1,3,2], [2,1,3] with Denominator = 6 and click Finish to observe unequal weights [0.5, 1/3, 1/6] summing to 1.
3. Change N11 to 3 while keeping D = 4 in the default matrix to verify that unequal row/column sums immediately report Invalid doubly stochastic matrix.