Technische Samenvatting: Wiskundige en Computationele Perspectieven op Booleaanse en Binaire Rang

1. Probleemdefinitie en Omvang

Deze survey biedt een uitgebreid overzicht van de Booleaanse rang ($rank_B(M)$) en de binaire rang ($rank_{bin}(M)$) van 0,1-matrices, waarbij ze zowel vanuit een wiskundig als een computationeel perspectief worden geanalyseerd. De primaire focus ligt op hun relatie tot de reële rang ($rank_R(M)$).

Hoewel de reële rang goed begrepen en efficiënt berekenbaar is via Gaussische eliminatie, zijn de Booleaanse en binaire rangen gedefinieerd over semiringen (Booleaanse rekenkunde en gehele rekenkunde, respectievelijk) in plaats van velden. Dit onderscheid leidt tot significante verschillen in gedrag:

• Definities:
  • Reële Rang: Minimale $d$ waarvoor $M = A \cdot B$ over $\mathbb{R}$.
  • Binaire Rang: Minimale $d$ waarvoor $M = A \cdot B$ over $\mathbb{Z}$ (gehele getallen) met 0,1-elementen.
  • Booleaanse Rang: Minimale $d$ waarvoor $M = A \cdot B$ over Booleaanse rekenkunde ($1+1=1$).
• Relaties: Het geldt altijd dat $rank_R(M) \leq rank_{bin}(M)$ en $rank_B(M) \leq rank_{bin}(M)$. Echter, de relatie tussen $rank_B(M)$ en $rank_R(M)$ is complex; $rank_B(M)$ kan exponentieel kleiner of quasi-polynomiaal groter zijn dan $rank_R(M)$.
• Computationele Complexiteit: In tegen Tang van de reële rang, is het berekenen van zowel de Booleaanse als de binaire rang NP-volledig. Bovendien is het benaderen van de Booleaanse rang binnen een factor $n^{1-\epsilon}$ ook NP-hard.

2. Methodologie en Alternatieve Formuleringen

Het artikel synthetiseert technieken uit de lineaire algebra, combinatoriek, grafentheorie en communicatiecomplexiteit. Een centraal thema is de equivalentie van rangfuncties aan diverse combinatorische problemen:

• Monochromatische Rechthoeken:
  • $rank_{bin}(M)$ is gelijk aan het minimum aantal monochromatische rechthoeken dat nodig is om de enen van $M$ te partitioneren ($Partition_1(M)$).
  • $rank_B(M)$ is gelijk aan het minimum aantal monochromatische rechthoeken dat nodig is om de enen van $M$ te dekken ($Cover_1(M)$).
• Grafentheorie: Deze rangen komen overeen met het minimum aantal bicliques dat nodig is om de randen van een bipartiete graaf te partitioneren of te dekken, waarvan de adjacentiematrix $M$ is.
• Set Basis Problemen: De rangen zijn gerelateerd aan het vinden van minimale verzamelingen bases (normale set bases voor binaire rang) voor families van verzamelingen afgeleid van matrixkolommen.
• Communicatiecomplexiteit: De rangen zijn nauw verbonden met communicatiecomplexiteitsmaten:
  • $rank_B(M)$ bepaalt de niet-deterministische communicatiecomplexiteit ($N_1(M) = \lceil \log_2 rank_B(M) \rceil$).
  • $rank_{bin}(M)$ bepaalt de unambigue niet-deterministische communicatiecomplexiteit ($U(M) = \lceil \log_2 rank_{bin}(M) \rceil$).
  • De deterministische communicatiecomplexiteit ($D(M)$) wordt begrensd door $O(\log_2 rank_{bin}(M))$.

3. Belangrijkste Bijdragen en Resultaten

A. Onderbouw- en Bovengrenstechnieken

De survey beschrijft diverse methoden voor het vaststellen van grenzen aan deze rangen:

• Lineaire Algebra: Gebruik van eigenwaarden (Graham-Pollack stelling) en de reële rang als ondergrens. Voor specifieke families zoals circulant matrices $D_{n,k}$, bewijst lineaire algebra dat $rank_{bin}(D_{n,k}) \geq rank_R(D_{n,k}) + 1$ in bepaalde gevallen.
• Isolatie (Fooling) Sets: Het vinden van een verzameling enen waar geen twee dezelfde rij, kolom of 2x2 sub-matrix van enen delen. De grootte van de maximale isolatieset $i(M)$ vormt een ondergrens voor beide rangen.
• Combinatoriek: Het gebruik van de stelling van Sperner om de Booleaanse rang van matrices met anti-chain rijen te begrenzen (bijv. $rank_B(C_n) = \Theta(\log n)$ voor het complement van de identiteitsmatrix).
• Probabilistische Methode: Het bewijzen van bovengrenzen voor matrices met beperkte nullen (bijv. $rank_B(M) \leq O(k \log n)$ voor matrices met $k$ nullen per kolom).
• Kernalisatie: Het verkleinen van de matrixgrootte door dubbele rijen/kolommen en rijen/kolommen met alleen nullen te verwijderen. De kern-grootte wordt begrensd door $2^{rank}$, wat fixed-parameter tractable algoritmen mogelijk maakt.
• Lifting Techniek: Een krachtige methode uit de communicatiecomplexiteit die query complexiteit ondergrenzen naar communicatiecomplexiteit "lift", wat resulteert in quasi-polynomiale gaten tussen $rank_{bin}(M)$ en $rank_B(M)$ (en hun complementen).

B. Wiskundige Eigenschappen

Het artikel belicht fundamentele verschillen tussen deze rangen en de reële rang:

• Spannende Verzamelingen en Augmentatie: Terwijl de reële rang de augmentatie-eigenschap bezit (het toevoegen van een vector die de rang niet verhoogt, behoudt de afhankelijkheden), faalt dit voor de Booleaanse en binaire rangen. Een noodzakelijke en voldoende voorwaarde voor augmentatie is de aanwezigheid van een unieke basis die alle andere basisen spant.
• Full Rank Sub-matrices: De reële rang garandeert een $d \times d$ sub-matrix met rang $d$. Dit geldt niet voor Booleaanse of binaire rangen. Er bestaan voorbeelden waarbij een matrix rang $d$ heeft, maar alle eigenlijke sub-matrices een strikt lagere rang dan $d$ hebben.
• Kronecker Producten: De reële rang is multiplicatief ($rank(A \otimes B) = rank(A)rank(B)$). De Booleaanse rang is sub-multiplicatief, en een strikte ongelijkheid ($rank_B(A \otimes B) < rank_B(A)rank_B(B)$) is bewezen voor specifieke matrices (bijv. $C_n \otimes C_n$). De multiplicativiteit van de binaire rang onder Kronecker producten blijft een open vraag.
• Matrix vs. Complement: Het gat tussen $rank(M)$ en $rank(\bar{M})$ is maximaal 1 voor de reële rang. Voor Booleaanse en binaire rangen kan het gat exponentieel of quasi-polynomial zijn. Recente resultaten met lifting-technieken tonen aan dat $rank_B(M)$ de orde $d^{e^{\Omega(\log d)}}$ kan bereiken terwijl $rank_{bin}(M) = d$.

C. Algoritmische Resultaten

Gezien de NP-hardheid behandelt de survey relaxatiestrategieën:

• Geparametriseerde Algoritmen: Beide rangen zijn Fixed-Parameter Tractable (FPT) met betrekking tot de rang-parameter $d$. Er bestaan algoritmen met een complexiteit van ongeveer $O(2^{2^d} \cdot poly(n))$, gebruikmakend van kernalisatie om de probleemgrootte te reduceren.
• Benaderingsalgoritmen:
  • Simpele greed-benaderingen bereiken ratio's van $O(n/\log n)$ voor de binaire rang en $O(n/\log^2 n)$ onder specifieke condities.
  • Hardheidsresultaten sluiten benadering binnen $n^{1-\epsilon}$ uit.
  • Reducties naar vertex coloring en set cover bieden alternatieve benaderingsgrenzen voor specifieke matrixklassen.
• Property Testing: Er bestaan non-adaptieve en adaptieve testing algoritmen met een query complexiteit die onafhankelijk is van de matrixgrootte maar exponentieel in $d$ (bijv. $O(2^{2d}/\epsilon^2)$ voor de binaire rang). Een belangrijke uitdaging is het bestaan van matrices waar elke kleine sub-matrix een lage rang heeft, terwijl de volledige matrix een hoge rang heeft (hoewel dergelijke matrices dicht bij low-rank matrices liggen).
• Boolean Matrix Factorization (BMF): De survey vermeldt kort praktische algoritmen voor benaderde factorisatie, hoewel de theoretische garanties beperkt zijn.

4. Betekenis en Openstaande Problemen

De survey betoogt dat de Booleaanse en binaire rangen dienen als een verenigende taal die algebra, combinatoriek, grafentheorie en communicatiecomplexiteit verbindt. De interactie tussen deze velden heeft langlopende open problemen opgelost (bijv. het weerleggen van de Alon-Saks-Seymour conjectuur via communicatiecomplexiteit lifting) terwijl het diepe structurele verschillen met de reële rang heeft onthuld.

Het artikel concludeert door verschillende kritieke openstaande problemen te schetsen:

1. Sub-matrix Eigenschap: Het vinden van een 0,1-matrix waarbij de binaire rang $d < n$ is, maar elke $d \times d$ sub-matrix een aanzienlijk kleinere binaire rang heeft.
2. Kronecker Multiplicativiteit: Bepalen of er matrices $A, B$ bestaan zodanig dat $rank_{bin}(A \otimes B) < rank_{bin}(A) \cdot rank_{bin}(B)$.
3. Gap Optimalisatie: Onderzoeken of de quasi-polynomiale kloof tussen de reële rang en de binaire/Booleaanse rang optimaal is of dat er grotere gaten bestaan.
4. Vereenvoudigde Bewijzen: Het vinden van combinatorische of algebraïsche bewijzen voor de quasi-polynomiale gap-resultaten die momenteel steunen op complexe lifting-technieken.
5. Benadering: Het ontwikkelen van betere benaderingsalgoritmen voor specifieke matrixfamilies.
6. Property Testing: Het vinden van een property testing algoritme voor de binaire rang met een query complexiteit die polynomiaal is in $d$ en $\epsilon$, of bewijzen dat een dergelijk algoritme niet bestaat.

De survey benadrukt dat hoewel er aanzienlijke vooruitgang is geboekt, het structurele begrip van deze rangen minder compleet is dan dat van de reële rang, wat rijke richtingen biedt voor toekomstig onderzoek in zowel de wiskunde als de theoretische informatica.