Pytanie o dwie matryce: Hadamard przeciwko „magicznej” w dowodzie przypuszczenia wrażliwości

Najnowszy i niezwykle zręczny dowód domniemania wrażliwości opiera się na wyraźnej * konstrukcji macierzy $A_n\in\{-1,0,1\}^{2^n\times 2^n}$ , zdefiniowanej rekurencyjnie w następujący sposób:

$$A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix}$$ oraz dla $n\geq 2$ , n = ( n - 1 mi n - 1 mi n - 1 $$A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix}$$ W szczególności łatwo zauważyć, że$A_n^2 = n I_n$dla wszystkich$n\geq 1$.

Być może teraz czytam za dużo, ale wygląda to przynajmniej syntaktycznie w odniesieniu do innej znanej rodziny macierzy, macierzy Hadamarda, która jest również taka, że $H_n^2 \propto I_n$ i ma „podobne” spektrum:

$$H_1 = \begin{pmatrix} 1&1\\1&-1\end{pmatrix}$$ , a dla $n\geq 2$ , $$H_{n} = \begin{pmatrix} H_{n-1}&H_{n-1}\\H_{n-1}&-H_{n-1}\end{pmatrix}$$

Czy istnieje między nimi jakikolwiek związek formalny, być może użyteczny, z wyjątkiem tego, że „wyglądają nieco podobnie”?

Na przykład, n postrzegane jako zawartą matrycy przylegania hipersześcianu { 0 , 1 } n ma interpretację przyjemne (znak krawędzi ( x , B , x ' ) ∈ { 0 , 1 } n jest parzystości przedrostek x ). Czy istnieje analog dla H n ? (może to być oczywiste?)$A_n$$\{0,1\}^n$$(x,b,x')\in\{0,1\}^n$$x$$H_n$

$^*$ Ja też zastanawiałem się, czy nie-jednoznaczne budowy, np równomiernie losowo $\pm1$ matryca musiałaby pożądanych właściwości spektralne, ale to pewnie trzeba czekać na kolejne pytanie.

Obserwacja zbyt długa na komentarz (i która również dobrze pasuje do obserwacji Jasona Gaitonde'a zbyt długa na komentarz):

Jak wskazano w OQ, oba z nich można w rzeczywistości zrealizować za pomocą bardzo prostej konstrukcji rekurencyjnej. Mianowicie określamy $B_0 \in \{(0), (\pm 1)\}$ ( macierz $1 \times 1$ ), a następnie pojedynczą formułę rekurencyjną

$$B_n = \left(\begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array}\right)$$

gdzie każdy $b_{ij}$ jest jednym z $\{0, \pm 1, \pm x\}$ (gdzie tutaj „1” oznacza tożsamość odpowiedniego rozmiaru, mianowicie $2^{n-1} \times 2^{n-1}$ , i podobnie „0” oznacza zero macierz o odpowiednim rozmiarze, a $x$ oznacza $B_{n-1}$ ). W przypadku macierzy Huanga mamy $A_0 = (0)$ a formuła rekurencyjna to $\begin{bmatrix} x & 1 \\ 1 & -x \end{bmatrix}$, podczas gdy dla macierzy Hadamarda mamy $H_0 = (1)$ a wzór rekurencyjny to $\begin{bmatrix} x & x \\ x & -x \end{bmatrix}$ .

Jeśli ktoś chce, aby taka rekurencja miała właściwość, że $B_n^2$ jest proporcjonalna do $I_{2^{n}}$ , wówczas szybko stwierdza się, że albo $b_{11} + b_{22} = 0$ , albo $b_{12} = b_{21}=0$ . W tym drugim przypadku rekurencja daje tylko macierze diagonalne, co może nie jest tak interesujące. Interesujące są więc przypadki, w których $b_{11} = -b_{22}$(co jest jednym z warunków „uprzejmości” w odpowiedzi Jasona). Można to również postrzegać jako częste wytłumaczenie, dlaczego obie sekwencje macierzy są bezimienne.

Jako ostatni mały komentarz, ten rodzaj rekurencji automatycznie powoduje, że wpisy blokowe $B_n$ dojeżdżają do pracy, co było drugim warunkiem „uprzejmości” w odpowiedzi Jasona.

Nie przeprowadziłem jeszcze systematycznego dochodzenia, ale biorąc pod uwagę powyższą konfigurację, można zbadać skończenie wiele możliwości (3 opcje dla $B_0$ i technicznie $5^4$ opcje dla rekurencji, ale można to zmniejszyć za pomocą symetrii, a także z ograniczenia, które $B_n^2$ jest proporcjonalna do tożsamości). Byłoby bardzo przyjemnie dowiedzieć się, że macierze Hadamarda i Huanga są jakoś, do równoważności, jedynymi dwoma nietrywialnymi :). A jeśli nie, może czają się tam inne interesujące ...

Oto kilka uwag, których nie mogłem zmieścić w komentarzu:

0) Dodano, ponieważ pierwsza odpowiedź została usunięta: istnieje interpretacja $H_n$ , a mianowicie indeksowanie wierszy i kolumn według $\{0,1\}^n$ , pozycja odpowiadająca $(x,y)$ wynosi $1$ jeśli iloczyn Hadamarda $x\odot y=(x_1y_1,\ldots,x_n y_n)$ ma parzystą parzystość, a $-1$ jeśli ma parzystą nieparzystą.

1) Ogólnie, widmo macierzy blokowych może być bardzo skomplikowane i nie związane w oczywisty sposób z widmami poszczególnych bloków, ponieważ charakterystyczny wielomian będzie wyglądał okropnie . Ale dla symetrycznej macierzy blokowej $M=\begin{pmatrix} A & B\\ B^T & C\end{pmatrix}$ która może powstać w wyniku konstrukcji rekurencyjnej, takiej jak $A_n$ i $H_n$ powyżej, gdzie każda macierz jest kwadratowa, jedno z jedynych uproszczeń występuje, gdy $B^T$ i $C$ dojeżdżają, w którym to przypadku $\det(M)=\det(AC-BB^T)$ . Wtedy charakterystycznym wielomianem$M$ będzie

$$\det((\lambda I-A)(\lambda I-C)-BB^T)=\det(\lambda^2I-\lambda (A+C)+AC-BB^T).$$ Aby to prowadzić do dobrych rekurencyjnych wzorów dla wartości własnych, w zasadzie potrzebny jest$C=-A$$\lambda$$A$$B$ $$\det(\lambda I-M)=\det(\lambda^2 I-(A^2+B^2)),$$ from which one easily reads off the eigenvalues using the fact symmetric commuting matrices admit a common eigenbasis. This might be obvious, but all of this is to say that as far as getting good, recursive formulas for the eigenvalues, it is basically essential to require the lower right block to be $-A$$A$$A_n$$B=I$$H_n$ matrices (with $B=H_{n-1}=A$).

2) On the random sign question: the signing of the adjacency matrix given in the paper is optimal in the sense of maximizing $\lambda_{2^{n-1}}$, which is needed for the lower bound via Cauchy interlacing, and can be seen from elementary means. For an arbitrary signing $M_n$ of the adjacency matrix of the $n$-dimensional hypercube, one immediately gets

$$\text{Tr}(M_n)=\sum_{i=1}^{2^n} \lambda_i(M_n)=0,\quad \text{Tr}(M_n^2)=\sum_{i=1}^{2^n} \lambda_i(M_n)^2=\|M_n\|_F^2=n2^n,$$ where $\lambda_1(M_n)\geq \lambda_2(M_n)\geq\ldots\geq \lambda_{2^n}(M_n)$. If for some signing $M_n$ one has $\lambda_{2^{n-1}}(M_n)>\sqrt{n}$, then $$\sum_{i=1}^{2^{n-1}} \lambda_i(M_n)>\sqrt{n}2^{n-1},\quad \sum_{i=1}^{2^{n-1}} \lambda_i(M_n)^2>n2^{n-1}.$$ One can then see it is not possible to satisfy the trace equalities above: the negative eigenvalues must sum to strictly more than $\sqrt{n}2^{n-1}$ (in absolute value), and their squares must sum to strictly less than $n2^{n-1}$. Minimizing the sum of squares while keeping the sum constant happens when they are all equal, but in this case will make the sum of squares too large anyway. So for any signing, one can see via elementary means that $\lambda_{2^{n-1}}(M_n)\leq \sqrt{n}$ without knowing the magic signing in the paper, where equality holds iff the values are $\sqrt{n},\ldots,\sqrt{n},-\sqrt{n},\ldots,-\sqrt{n}$. That there actually exists such a signing attaining it is pretty amazing. The eigenvalues of the normal adjacency matrix are $-n, -n+2,\ldots,n-2,n$, where the $i$th eigenvalue has multiplicity ${n\choose i }$, so it's very interesting (to me, anyway) how the all-$+1$ signing maximizes $\lambda_1$, while this signing maximizes $\lambda_{2^{n-1}}$.

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 $\mathbb{E}[\|M_n\|_2]=\Theta(\sqrt{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.