Frage zu zwei Matrizen: Hadamard v. "Der Magische" im Beweis der Sensitivitätsvermutung

23

Der kürzliche und unglaublich glatte Beweis der Sensitivitätsvermutung beruht auf der expliziten * Konstruktion einer Matrix , die rekursiv wie folgt definiert wird: , und für , Insbesondere ist leicht zu erkennen, dass für alle .An{1,0,1}2n×2n

A1=(0110)
n2
An=(An1In1In1An1)
An2=nInn1

Vielleicht lese ich zu viel darüber, aber dies scheint zumindest syntaktisch mit einer anderen berühmten Matrizenfamilie zu verwandt zu sein, den Hadamard-Matrizen, die ebenfalls so ist, dass und ein 'ähnliches' Spektrum aufweist: , und für , Hn2In

H1=(1111)
n2
Hn=(Hn1Hn1Hn1Hn1)

Gibt es irgendeine formale Verbindung, die möglicherweise nützlich ist, mit der Ausnahme, dass "sie vage ähnlich aussehen"?

Zum Beispiel hat als vorzeichenbehaftete Adjazenzmatrix des Hyperwürfels eine schöne Interpretation (das Vorzeichen einer Kante ist die Parität des Präfixes ). Gibt es ein Analogon für ? (Dies kann offensichtlich sein?)An{0,1}n(x,b,x){0,1}nxHn

Ich frage mich auch, ob eine nicht explizite Konstruktion, z. B. eine gleichmäßig zufällige Matrix, die gewünschten spektralen Eigenschaften hätte, aber das müsste wahrscheinlich auf eine andere Frage warten.±1

Clement C.
quelle

Antworten:

9

Eine Beobachtung, die zu lang für einen Kommentar ist (und die auch gut zu Jason Gaitondes Beobachtung passt, die zu lang für einen Kommentar ist):

Wie in der OQ angedeutet, können beide tatsächlich durch eine sehr einfache Art von rekursiver Konstruktion realisiert werden. Wir spezifizieren nämlich B0{(0),(±1)} (eine 1×1 Matrix) und dann eine einzelne rekursive Formel

Bn=(b11b12b21b22)

wobei jedes bij eines von {0,±1,±x} (wobei "1" hier die Identität der geeigneten Größe bezeichnet, nämlich 2n1×2n1 und in ähnlicher Weise "0" die Null Matrix der geeigneten Größe und x bezeichnet Bn1 ). Für die Huang-Matrizen haben wir tatsächlich A0=(0) und die rekursive Formel ist [x11x], während für die Hadamard-MatrizenH0=(1)und die rekursive Formel[xxxx].

Wenn man möchte, dass eine solche Rekursion die Eigenschaft hat, dass Bn2 proportional zu I2n , dann findet man schnell, dass entweder b11+b22=0 oder b12=b21=0 . Im letzteren Fall liefert die Rekursion nur diagonale Matrizen, was vielleicht nicht so interessant ist. Die interessanten Fälle sind also diejenigen, in denen b11=b22(Das ist eine der "Nizza" Bedingungen in Jasons Antwort). Dies kann auch als allgemeine Erklärung dafür angesehen werden, warum beide Matrizenfolgen spurenlos sind.

Als letzten kleinen Kommentar liefert diese Art der Rekursion automatisch, dass die Blockeinträge von Bn pendeln, was die andere Bedingung für die "Freundlichkeit" in Jasons Antwort war.

Ich habe noch keine systematische Untersuchung durchgeführt, aber angesichts des obigen Aufbaus könnte man die endlich vielen Möglichkeiten untersuchen (3 Auswahlmöglichkeiten für B0 und technisch 54 Auswahlmöglichkeiten für die Rekursion, aber dies kann unter Verwendung von Symmetrien und auch von abgeschnitten werden die Einschränkungen, dass Bn2 proportional zur Identität ist). Es wäre sehr erfreulich zu erfahren, dass die Hadamard- und die Huang-Matrix in gewisser Weise bis zur Äquivalenz die einzigen beiden nichttrivialen sind :). Und wenn nicht, vielleicht lauern da draußen noch einige andere interessante ...

Joshua Grochow
quelle
Und wenn nicht, vielleicht lauern da draußen noch andere interessante ... hört sich ganz interessant an :)
Clement C.
9

Hier sind nur ein paar Beobachtungen, die ich nicht in einen Kommentar einfügen konnte:

0) Hinzugefügt, weil die erste Antwort gelöscht wurde: Es gibt eine Interpretation von Hn , nämlich Indizieren der Zeilen und Spalten durch {0,1}n , der Eintrag entsprechend (x,y) ist 1 wenn das Hadamard-Produkt xy=(x1y1,,xnyn) hat gerade Parität und 1 wenn es ungerade Parität hat.

1) Im Allgemeinen kann das Spektrum der Blockmatrizen sehr kompliziert sein und hängt nicht offensichtlich mit den Spektren der einzelnen Blöcke zusammen, da das charakteristische Polynom schrecklich aussehen wird . Aber für einen symmetrischen Blockmatrix M=(ABBTC) , die über eine rekursive Konstruktion wie die entstehen könnte , An und Hn oben, wobei jede Matrix quadratisch ist, eine der nur Vereinfachungen tritt auf, wenn BT und C pendeln, in diesem Fall hat man det(M)=det(ACBBT) . Danndas charakteristische PolynomM wird

det((λIA)(λIC)BBT)=det(λ2Iλ(A+C)+ACBBT).
Damit dies zu schönen rekursiven Formeln für die Eigenwerte führt, braucht man grundsätzlichC=A , um den linearenλ Termzu töten. Sind weiterhinA undB symmetrisch und pendeln, so erhalten wir
det(λIM)=det(λ2I(A2+B2)),
woraus man leicht die Eigenwerte mit Hilfe der Tatsache abliest, dass symmetrische Pendelmatrizen gelten eine gemeinsame eigenbasis. Dies mag offensichtlich sein, aber all dies bedeutet, dass es für das Erhalten guter rekursiver Formeln für die Eigenwerte im Grunde genommen wesentlich ist, dass der untere rechte Block vorhanden istA und hoffe, dass der untere linke und der obere rechte Block symmetrisch sind und mitA pendeln, was für dieMatrizenAn (mitB=I ) undHn (mitB=Hn1=A )der Fall ist.

2) Zur Frage des Zufallszeichens: Die Signierung der in der Arbeit angegebenen Adjazenzmatrix ist optimal im Sinne einer Maximierung von λ2n1 , die für die Untergrenze über Cauchy-Interlacing benötigt wird und sich aus elementaren Mitteln ergibt. Für ein beliebiges Vorzeichen Mn der Adjazenzmatrix des n dimensionalen Hyperwürfels erhält man sofort

Tr(Mn)=i=12nλi(Mn)=0,Tr(Mn2)=i=12nλi(Mn)2=MnF2=n2n,
wobeiλ1(Mn)λ2(Mn)λ2n(Mn) . Wenn für einige UnterzeichnungMnman hat λ2n1(Mn)>n , dann
i=12n1λi(Mn)>n2n1,i=12n1λi(Mn)2>n2n1.
Man kann dann sehen, dass es nicht möglich ist, die obigen Gleichungen der Spuren zu erfüllen: Die negativen Eigenwerte müssen sich zu genau mehr alssummierenn2n1 (in absoluten Werten) und ihre Quadrate müssen sich zu genau weniger alsn2n1 summieren. Das Minimieren der Quadratsumme bei konstanter Summe geschieht, wenn alle gleich sind. In diesem Fall wird die Quadratsumme jedoch ohnehin zu groß. Für jede Signatur kann man also mit elementaren Mitteln sehen, dassλ2n1(Mn)n ohne die magische Signatur im Papier zu kennen, wobei Gleichheit gilt, wenn die Werten,,n,n,,n . Dass es tatsächlich eine solche Unterzeichnung gibt, ist ziemlich erstaunlich. Die Eigenwerte der normalen Adjazenzmatrix sindn,n+2,,n2,n, wobei deriEigenwert die Multiplizität(ni) , also ist es (für mich) sehr interessant, wie die all-+1Signaturλ1maximiert, während diese Signaturλ2n1maximiert.

As far as would a random signing work, it's harder to say because I think most non-asymptotic bounds on eigenvalues focus on spectral norm. One expects random signings to smooth out the extreme usual eigenvalues, and indeed, using the noncommutative Khintchine inequality and/or recent tighter bounds like in here, a uniformly random signing has E[Mn2]=Θ(n). It's hard for me to imagine the middle eigenvalues would be on a similar polynomial order as the leading one in expectation (and asymptotic results like the semi-circular law for different matrix ensembles suggest similarly, I think), but maybe it's possible.

J.G
quelle