THE FOLD / CO-OP / SHARED MEMORY / THE BIRKHOFF–VON NEUMANN
THE BIRKHOFF–VON NEUMANN
a fair blend that splits into perfect assignments
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Birkhoff–von Neumann theorem says every doubly stochastic matrix — a square matrix of non-negative entries whose every row and column sums to 1 — is a convex combination of permutation matrices. A fair, fractional assignment (each agent split across jobs, each job split across agents) is always a weighted average of whole, one-to-one assignments. Birkhoff’s algorithm peels them off: find a permutation sitting entirely on positive entries (a perfect matching always exists), subtract as much of it as possible, and repeat — the weights sum to exactly 1.
LIT verified live: hundreds of random doubly stochastic matrices are decomposed into permutation matrices whose coefficients sum to 1 and whose weighted sum reconstructs the original exactly (window.__bvn). FIG no framing; the Birkhoff peeling with perfect-matching extraction, checked by reconstruction.
LIT verified live: hundreds of random doubly stochastic matrices are decomposed into permutation matrices whose coefficients sum to 1 and whose weighted sum reconstructs the original exactly (window.__bvn). FIG no framing; the Birkhoff peeling with perfect-matching extraction, checked by reconstruction.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — a fractional assignment shared across agents is really a blend of whole one-to-one assignments, peeled apart one permutation at a time. That shared blend is the structure. AVAN (AI) built the instrument: the perfect-matching extractor (augmenting paths on the positive support), the Birkhoff peeling loop, the coefficient sum, and the reconstruction check.
Credit as content: Garrett Birkhoff (1946) & John von Neumann; the underlying matching is Kőnig–Hall. The weave: David names shared-memory; I repeatedly find a permutation lying on positive entries, subtract its smallest weight, and confirm the weights total 1 and rebuild the matrix — a fair blend split into perfect assignments.
Credit as content: Garrett Birkhoff (1946) & John von Neumann; the underlying matching is Kőnig–Hall. The weave: David names shared-memory; I repeatedly find a permutation lying on positive entries, subtract its smallest weight, and confirm the weights total 1 and rebuild the matrix — a fair blend split into perfect assignments.
3 ONE DIMENSION
A doubly stochastic matrix (rows and columns sum to 1) = Σ θk Pk, permutation matrices Pk, weights θk ≥ 0 summing to 1. Peel: a permutation on positive cells, subtract its min, repeat.
4 TWO DIMENSIONS · INTERACTIVE
A doubly stochastic matrix and its Birkhoff decomposition into weighted permutations; the reconstruction checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a fair blend of whole assignments.
AVAN’s addition (the inverse-companion): read a fractional, doubly-balanced assignment not as a blur but as a weighted mix of exact one-to-one matchings. The inverse of ‘average many permutations into a matrix’ is ‘peel any doubly stochastic matrix back into permutations.’ Magenta is the blurred fractional matrix; green is the set of crisp permutation matrices it decomposes into. A blend, unmixed.
LIT Genuine Birkhoff–von Neumann theorem (Garrett Birkhoff, 1946; also von Neumann). Verified live: 500 random doubly stochastic matrices (built by Sinkhorn normalization) are decomposed by Birkhoff peeling — perfect matchings extracted from the positive support by augmenting paths — into permutation matrices whose weights sum to 1 (window.__bvn.sumOne) and whose weighted sum reconstructs the matrix exactly (window.__bvn.reconstructs).
FIG No framing: the perfect-matching extractor (augmenting paths on the positive support), the Birkhoff peeling loop, the coefficient sum, and the reconstruction check all run in-browser. The AVAN inverse is honest — reading a fractional doubly-balanced matrix as a weighted mix of exact one-to-one matchings (rather than averaging permutations into a matrix) genuinely inverts the blend; magenta is the blurred fractional matrix, green the crisp permutation matrices it splits into. A blend, unmixed.
FIG No framing: the perfect-matching extractor (augmenting paths on the positive support), the Birkhoff peeling loop, the coefficient sum, and the reconstruction check all run in-browser. The AVAN inverse is honest — reading a fractional doubly-balanced matrix as a weighted mix of exact one-to-one matchings (rather than averaging permutations into a matrix) genuinely inverts the blend; magenta is the blurred fractional matrix, green the crisp permutation matrices it splits into. A blend, unmixed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN