Birkhoff–von Neumann Decomposition

Birkhoff Polytope and Hall's Marriage Theorem

Any nonnegative matrix R whose rows and columns all sum to a common positive scalar c > 0 has at least one strictly positive permutation transversal (a perfect matching in its support bipartite graph) by Hall's marriage theorem. Subtracting the bottleneck entry along that transversal preserves equal row and column sums while zeroing out at least one positive entry.

Greedy Lexicographic Extraction

Given a 3x3 matrix M = N / D with integer numerators N_i,j in [0, 6] whose rows and columns each sum to D, each step selects the lexicographically smallest 1-based permutation π = (π₁, π₂, π₃) with N_1,π1 > 0, N_2,π2 > 0, and N_3,π3 > 0. Letting m = min_i N_i,πi, we extract coefficient c_k = m / D and subtract m from those three positions in the unnormalized residual numerator matrix until the residual reaches 0.

Worked Example

Decompose the 3x3 doubly stochastic matrix with denominator D = 4 and numerator rows [2, 2, 0], [0, 2, 2], [2, 0, 2]:

1. Step 1: The lexicographically smallest supported permutation is the main diagonal (1, 2, 3) with bottleneck entry min(2/4, 2/4, 2/4) = 0.5. Subtracting 0.5 · P_(1,2,3) leaves residual numerators [0, 2, 0], [0, 0, 2], [2, 0, 0].
2. Step 2: The remaining positive entries support permutation (2, 3, 1) with bottleneck 2/4 = 0.5. Subtracting 0.5 · P_(2,3,1) reduces the residual matrix to 0, completing the 2-term convex combination with coefficients [0.5, 0.5] summing to 1.

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.

Limitations

The convex decomposition of an interior doubly stochastic matrix into permutation vertices is generally nonunique (for example, the uniform 1/3 matrix can be written as 1/3 of the three even permutations or 1/3 of the three odd permutations). The greedy lexicographic rule selects one canonical decomposition with at most n² - 2n + 2 = 5 terms.

Common Pitfalls

After subtracting a permutation matrix with weight c₁ < 1, the residual matrix has row and column sums equal to 1 - c₁ rather than 1; calling the unnormalized residual doubly stochastic without dividing by 1 - c₁ is incorrect.

References

The Birkhoff polytope and constructive permutation extraction algorithm follow standard combinatorial geometry references:

• SageMath Polytopes Library: Birkhoff Polytope and Doubly Stochastic Matrices