Permanents of matrix ensembles: computation, distribution,… — Begrijpelijke uitleg

De Wiskunde van het Onmogelijke: Een Reis door de "Permanent"

Stel je voor dat je een enorme, ingewikkelde puzzel hebt. Je moet alle mogelijke manieren vinden om stukjes in een rooster te leggen, en voor elke manier een getal berekenen. Dan moet je al die getallen bij elkaar optellen.

In de wiskunde heet dit het berekenen van een permanent. Het lijkt erg op een andere bekende puzzel, de determinant (die je misschien kent uit schoolwiskunde), maar met één groot verschil: bij de determinant mag je minnen en plussen, wat veel getallen tegen elkaar laat wegvallen. Bij de permanent mag dat niet. Je moet alles optellen.

Dit maakt de permanent extreem moeilijk te berekenen. Voor een klein rooster is het al lastig; voor een groot rooster is het zo complex dat zelfs de snelste supercomputers er jaren over zouden doen. Dit is een van de "heilige graal"-problemen in de informatica.

In dit paper doet de auteur, Igor Rivin, drie dingen:

Hij bouwt een supercomputer (een GPU) om deze puzzels sneller op te lossen.
Hij kijkt naar statistieken: wat gebeurt er als je willekeurige roosters gebruikt?
Hij bekijkt de geometrie: hoe verandert het antwoord als je het rooster langzaam vervormt?

Hieronder leg ik de belangrijkste ontdekkingen uit met alledaagse analogieën.

1. De Supercomputer: Het Versnellen van de Puzzel

Stel je voor dat je een enorme berg blokken moet tellen. Normaal doet iemand dit één voor één (zoals een CPU). Rivin heeft een GPU (een grafische kaart, zoals in gaming-computers) gebruikt.

De Analogie: Een CPU is als één persoon die blokken telt. Een GPU is als een leger van 10.000 mensen die tegelijkertijd werken.
Het Resultaat: Rivin kon hiermee permanenten berekenen voor roosters die 200 tot 400 keer groter waren dan wat voorheen mogelijk was. Hij kon zelfs de "Schur-matrix" (een heel specifieke, mooie wiskundige structuur) oplossen voor groottes die niemand eerder had gezien.

2. De Statistiek: Willekeurige Roosters en "De Normaal"

Rivin keek naar wat er gebeurt als je roosters maakt met willekeurige getallen. Hij deed dit voor verschillende soorten "willekeur":

A. De Unitaire Matrix (De Perfecte Dans)

Stel je een groep dansers voor die perfect synchroon bewegen. Als je hun bewegingen willekeurig maar perfect协调 (gecoördineerd) kiest, vormt het eindresultaat een cirkelvormige verdeling.

De Analogie: Het is alsof je duizenden mensen een munt laat gooien. De meeste landen komen uit in het midden, maar omdat het complex is (met een reëel en een imaginaire kant), vormt het een perfecte cirkel.
De Verrassing: De "DFT-matrix" (een heel speciale, regelmatige structuur die in de digitale wereld wordt gebruikt) is een uitzondering. Voor priemgetallen (zoals 7, 11, 13) is deze matrix een "reus" die veel groter is dan alle willekeurige dansers. Het is alsof je in een menigte van normale mensen plotseling een reus ziet staan die 10 keer zo groot is als de rest.

B. De Orthogonale Matrix (De Realistische Dans)

Hier zijn de dansers niet perfect synchroon, maar ze bewegen wel in het echt (geen imaginaire getallen).

Het Resultaat: Ook hier lijkt het resultaat op een normale verdeling, maar het is "dikker" dan normaal. Er zijn vaker extreme uitschieters (zware staarten). Het duurt langer voordat het perfect normaal wordt.

C. De Gaussische Matrix (De Chaos)

Hier zijn de getallen volledig willekeurig, zoals regen die op een dak valt.

De Verrassing: Hier werkt de "normale" wet niet. In plaats van een klokkromme, krijg je een α-stabiele verdeling.
De Analogie: Stel je voor dat je een zak met munten hebt. Bij een normale verdeling heb je veel munten van 1 euro en weinig van 100. Bij deze verdeling heb je een kans op een munt van 1 biljoen euro. Die ene enorme munt bepaalt het totaal. De "staarten" van de grafiek zijn zwaar: extreme waarden komen veel vaker voor dan je zou verwachten.

3. De Geometrie: De Reis van het Startpunt naar het Doel

Rivin keek ook naar wat er gebeurt als je een rooster langzaam vervormt van een startpunt (de identiteit) naar een eindpunt.

De Reis naar de Cirkel: Als je van een leeg rooster naar een rooster gaat dat een cirkel vormt, daalt de "permanent" eerst heel snel, bereikt een dieptepunt halverwege, en stijgt weer.
- De Verrassing: Dit pad is universeel. Of je nu een klein of groot rooster hebt, de vorm van de daling is bijna hetzelfde. Het is alsof alle roosters, groot of klein, dezelfde "vallei" moeten doorlopen.
De Reis naar de DFT (De Priemgetallen): Als je naar de DFT-matrix reist, gebeurt er iets magisch. Als het aantal rijen een priemgetal is, daalt de waarde diep, maar komt hij aan het einde weer sterk omhoog. Als het een samengesteld getal is (zoals 9 of 15), gebeurt dit niet.
- De Analogie: Het is alsof de wiskunde een "vingerafdruk" van priemgetallen heeft. De structuur van priemgetallen zorgt ervoor dat de waarde aan het einde van de reis weer opbloeit, terwijl samengestelde getallen in de vallei blijven hangen.

4. De Grote Vraag: Is het Lognormaal?

Er was een beroemde theorie (van Aaronson) dat de grootte van deze permanenten, als je ze kwadrateert, een specifieke vorm zou hebben die "lognormaal" heet.

Het Oordeel: Rivin zegt: "Niet altijd."
- Voor sommige soorten willekeurige roosters klopt het wel.
- Voor andere (zoals de "GUE" en "Real Ginibre") klopt het niet. De "zware staarten" (die enorme, zeldzame getallen die we eerder noemden) voorkomen dat het lognormaal wordt. Het is alsof je probeert de gemiddelde lengte van mensen te berekenen, maar er zit een reus tussen die de hele statistiek verpest.

Waarom is dit belangrijk?

Dit onderzoek is niet alleen leuk wiskundig puzzelen. Het heeft directe gevolgen voor de kwantumcomputers.

Boson Sampling: Dit is een manier om te laten zien dat kwantumcomputers sneller zijn dan gewone computers. Ze gebruiken lichtdeeltjes (fotonen) die door een netwerk van spiegels gaan. Het berekenen van de kans dat de deeltjes op een bepaalde plek uitkomen, vereist het berekenen van een permanent.
De Conclusie: Omdat deze permanenten zo moeilijk te voorspellen zijn (en vaak extreem grote waarden kunnen hebben), is het voor een gewone computer bijna onmogelijk om het resultaat na te bootsen. Dit bewijst dat kwantumcomputers een echt voordeel hebben.

Kortom: Rivin heeft met een supercomputer bewezen dat willekeurige kwantum-systemen een heel specifiek, voorspelbaar patroon volgen (een cirkel), maar dat specifieke, regelmatige systemen (zoals de DFT) en andere soorten willekeur (Gaussisch) heel anders gedragen. Het is een reis door de grenzen van wat we kunnen berekenen en hoe de natuur op kwantumschaal "willekeurig" is.

Titel: Permanents van Matrix Ensembles: Berekening, Distributie en Geometrie

Auteur: Igor Rivin
Datum: 17 februari 2026

1. Probleemstelling

De permanente van een $n \times n$ matrix $A$ is gedefinieerd als:
$\text{perm}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i,\sigma(i)}$
In tegenstelling tot de determinant is het berekenen van de permanente voor een algemene matrix een #P-compleet probleem; er is geen polynomiale tijd-algoritme bekend (de snelste algemene methode, Ryser's algoritme, heeft een complexiteit van $O(n 2^n)$ ).

Ondanks deze computationele moeilijkheid speelt de permanente een cruciale rol in de kwantum-informatiewetenschap, specifiek bij Boson Sampling. De uitkomsten van een lineair optisch netwerk worden bepaald door $|\text{perm}(U_S)|^2$ , waarbij $U_S$ een submatrix is van een unitaire transmissiematrix. Een centrale aanname voor de bewijslast van kwantumvoordeel is de Permanent Anti-Concentration Conjecture (PACC), die stelt dat de permanente van willekeurige unitaire matrices niet te vaak dicht bij nul ligt.

Het doel van dit artikel is om een computationeel en experimenteel onderzoek te doen naar:

De efficiënte berekening van permanenten voor grote matrices.
De statistische verdeling van permanenten over verschillende matrix-ensembles (Haar-random unitair, orthogonaal, en Gaussisch).
Het gedrag van de permanente langs geodeten op de unitaire groep.
Het testen van de conjecture van Aaronson dat $|\text{perm}(X)|^2$ asymptotisch lognormaal is voor Gaussische matrices.

2. Methodologie

Computationele Versnelling

De auteur ontwikkelt een geavanceerde pijplijn om permanenten tot $n=43$ exact te berekenen en statistische steekproeven te nemen voor grotere $n$ :

GPU-versnelling: Implementatie van Ryser's algoritme op NVIDIA H100/GH200 GPU's.
Gray-code Parallelisatie: De $2^n$ subsets worden gepartitioneerd in blokken die parallel worden verwerkt door GPU-threads, waarbij Gray-codes worden gebruikt om de berekening van rij-sommen te minimaliseren ( $O(1)$ werk per subset).
Chinese Reststelling (CRT): Voor exacte berekening van de permanente van de Schur-matrix (DFT-matrix) wordt de berekening modulo verschillende priemgetallen uitgevoerd en vervolgens gecombineerd via CRT.
Numerieke Stabiliteit: Toepassing van Kahan-compenserende sommatie om cumulatieve afrondingsfouten te elimineren.

Deze methode levert een snelheidswinst van 200–400x op ten opzichte van single-threaded CPU-berekeningen.

Statistische Analyse

Steekproeven: Generatie van 50.000 Haar-random unitaire en orthogonale matrices, en 20.000–50.000 matrices uit Gaussische ensembles (GUE, GOE, Ginibre).
Tests: Toepassing van Kolmogorov-Smirnov, Shapiro-Wilk, en Q-Q-plots om de verdelingen te vergelijken met theoretische modellen (Gaussisch, Rayleigh, $\alpha$ -stabiel, Lognormaal).
Geodetische Analyse: Studie van de evolutie van de permanente langs geodeten op de unitaire groep $U(n)$ , specifiek van de identiteit naar de $n$ -cyclus permutatiematrix en de DFT-matrix.

3. Belangrijkste Bijdragen en Resultaten

A. Computationele Uitbreiding

De exacte waarden van de permanente van de Schur-matrix ( $S_n$ ) zijn uitgebreid van $n=35$ tot $n=43$ .
De berekeningstijden voor $n=43$ bedragen ongeveer 424 minuten op één GPU, wat vergelijkbaar is met cluster-berekeningen die duizenden CPU-kernen vereisten.

B. Distributie van Permanentes

Haar-random Unitair Matrices ( $U \in U(n)$ ):
- De permanente $\text{perm}(U)$ volgt een cirkelsymmetrische complexe Gaussische verdeling $CN(0, \sigma^2)$ .
- De grootte $|\text{perm}(U)|$ volgt een Rayleigh-verdeling, en het kwadraat $|\text{perm}(U)|^2$ volgt een exponentiële verdeling (Porter-Thomas statistieken).
- Uitzondering: De DFT-matrix (Schur-matrix) is een extreme outlier voor priemgetallen $n \geq 7$ . De magnitude van de permanente ligt ver buiten de 100e percentiel van de verdeling van willekeurige matrices. Voor samengestelde getallen valt de DFT binnen de bulk.
Haar-random Orthogonale Matrices ( $O \in O(n)$ ):
- De permanente is ongeveer reëel Gaussisch, maar vertoont een positieve excess kurtosis (dikke staarten) die afneemt als $O(1/n)$ .
- De convergentie naar een Gaussische verdeling is aanzienlijk trager dan bij unitaire matrices.
Gaussische Ensembles (GUE, GOE, Ginibre):
- In tegenstelling tot unitaire matrices, volgen de permanenten hier $\alpha$ -stabiele verdelingen met een stabiliteitsindex $\alpha \approx 1.0 - 1.4$ (ver beneden de Gaussische waarde $\alpha=2$ ).
- Dit impliceert oneindige variantie en zware staarten.
- Hiërarchie van $\alpha$ : GOE ( $\approx 1.0$ , Cauchy-achtig) < GUE/Real Ginibre ( $\approx 1.2$ ) < Complex Ginibre ( $\approx 1.4$ ).

C. Geodetische Analyse

Naar de $n$ -cyclus: De permanente langs de geodeet van de identiteit naar de $n$ $n$ -cyclus toont een universele schaalfunctie $f(t) = -\frac{1}{n} \ln |\text{perm}(\gamma(t))|$ $f (t) = - \frac{1}{n} ln ∣ perm (γ (t)) ∣$ die onafhankelijk is van $n$ $n$ voor grote $n$ $n$ .
- Op het middenpunt ( $t=1/2$ ) geldt voor oneven $n$ : $\text{perm}(\gamma(1/2)) \approx (-1)^{(n-1)/2} \cdot 2e^{-n}$ .
- Voor even $n$ is de waarde exact 0.
Naar de DFT-matrix: Het gedrag aan het einde van de geodeet ( $t=1$ ) onderscheidt priemgetallen van samengestelde getallen. Voor priemgetallen is er een sterke "herstel" (recovery) van de permanente boven het dal, terwijl dit voor samengestelde getallen verwaarloosbaar is.

D. Test van Aaronson's Lognormale Conjecture

Aaronson conjectureerde dat $|\text{perm}(X)|^2$ lognormaal is voor Gaussische $X$ .

Complex Ginibre en GOE: De conjecture is plausibel; de verdeling van $\log|\text{perm}|$ convergeert naar normaal.
GUE en Real Ginibre: De conjecture faalt. De verdeling vertoont aanhoudende negatieve scheefheid en hoge kurtosis, veroorzaakt door de zware staarten van de onderliggende $\alpha$ -stabiele verdeling.
Anti-concentratie: Ondanks het falen van de lognormale hypothese voor sommige ensembles, geldt anti-concentratie (de kans dat de waarde dicht bij nul ligt is klein) voor alle Gaussische ensembles en is zelfs robuuster dan voor Haar-unitaires.

4. Betekenis en Implicaties

Kwantumvoordeel en Boson Sampling:
- De bevestiging dat Haar-random unitaire permanenten een exponentiële verdeling volgen (Porter-Thomas) ondersteunt sterk de hardheid van Boson Sampling. Het impliceert dat de PACC (Permanent Anti-Concentration Conjecture) waar is en dat bijna alle willekeurige unitaire matrices een uitkomst boven de drempelwaarde genereren.
- De ontdekking dat de DFT-matrix een extreme outlier is voor priemgetallen heeft implicaties voor experimenten met Fourier-interferometers, waar bepaalde overgangsamplitudes anomal groot kunnen zijn.
Statistische Fysica en Wiskunde:
- Het artikel onthult een fundamenteel onderscheid tussen de verdeling van permanenten op de unitaire groep (beperkte entries $\to$ Gaussisch) en Gaussische ensembles (onbeperkte entries $\to$ $\alpha$ -stabiel). Dit suggereert dat de "Gaussianiteit" van de unitaire permanente een delicaat gevolg is van de begrenzing van de matrix-elementen.
- De identificatie van $\alpha$ -stabiele verdelingen voor Gaussische ensembles is een nieuwe inzichten in de wiskundige structuur van deze objecten.
Computationele Grenzen:
- De studie toont aan dat exacte berekening van permanenten tot $n \approx 43$ nu haalbaar is op enkele GPU's, wat overlapt met het regime van huidige fotonische experimenten. Dit maakt directe vergelijking tussen theorie en experiment mogelijk.

Conclusie

Dit werk combineert geavanceerde computationele technieken met diepgaande statistische analyse om de aard van matrix-permanenten te onthullen. Het bevestigt de Gaussische aard voor willekeurige unitaire matrices, onthult zware staarten voor Gaussische matrices, en biedt nieuwe inzichten in de meetkunde van de unitaire groep. De resultaten hebben directe relevantie voor de validatie van kwantumvoordeel en het begrijpen van de statistische eigenschappen van complexe systemen.

Permanents of matrix ensembles: computation, distribution, and geometry