Pergunta sobre duas matrizes: Hadamard v. “A mágica” na prova da conjectura de sensibilidade

23

A prova recente e incrivelmente clara da conjectura de sensibilidade se baseia na construção explícita * de uma matriz , definida recursivamente da seguinte forma: e, para , Em particular, é fácil ver que para todos os .An{1,0,1}2n×2n

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

Agora, talvez eu esteja lendo muito sobre isso, mas isso parece pelo menos sintaticamente relacionado a outra família famosa de matrizes, as matrizes Hadamard, que também é tal que e tem espectro 'semelhante': e, para , Hn2In

H1=(1111)
n2
Hn=(Hn1Hn1Hn1Hn1)

Existe alguma conexão formal, possivelmente útil, entre os dois, exceto que "eles parecem vagamente semelhantes"?

Por exemplo, , visto como a matriz de adjacência assinada do hipercubo tem uma boa interpretação (o sinal de uma aresta é a paridade do prefixo ). Existe um análogo para ? (isso pode ser óbvio?)An{0,1}n(x,b,x){0,1}nxHn

± 1 Também estou imaginando se uma construção não explícita, por exemplo, uma matriz uniformemente aleatória , teria as propriedades espectrais desejadas, mas isso provavelmente teria que esperar por outra pergunta.±1

Clemente C.
fonte

Respostas:

9

Uma observação muito longa para um comentário (e que também se encaixa bem na observação de Jason Gaitonde - muito tempo para comentar):

Como sugerido no OQ, esses dois podem de fato ser realizados por um tipo muito simples de construção recursiva. Ou seja, nós especificar B0{(0),(±1)} (um 1×1 matriz), e, em seguida, uma única fórmula recursiva

Bn=(b11b12b21b22)

onde cada bij é um de {0,±1,±x} (onde aqui "1" indica a identidade do tamanho apropriado, ou seja, 2n1×2n1 e da mesma forma "0" indica o zero matriz do tamanho apropriado, e x denota Bn1 ). Para as matrizes Huang, na verdade temos A0=(0) e a fórmula recursiva é [x11x], enquanto para as matrizes de Hadamard temosH0=(1)e a fórmula recursiva é[xxxx].

Se alguém deseja que tal recursão tenha a propriedade de que Bn2 é proporcional a I2n , então rapidamente descobrirá que b11+b22=0 ou b12=b21=0 . No último caso, a recursão produz apenas matrizes diagonais, o que talvez não seja tão interessante. Portanto, os casos interessantes são aqueles em que b11=b22(que é uma das condições de "gentileza" na resposta de Jason). Isso também pode ser visto como uma explicação comum para o motivo pelo qual ambas as sequências de matrizes são inexistentes.

Como último pequeno comentário, esse tipo de recursão produz automaticamente que as entradas de bloco de Bn comutadas, que era a outra condição de "gentileza" na resposta de Jason.

Ainda não fiz uma investigação sistemática, mas, dada a configuração acima, pode-se investigar as finitas possibilidades (3 opções para B0 e tecnicamente 54 opções para a recursão, mas isso pode ser reduzido usando simetrias e também de as restrições de que Bn2 é proporcional à identidade). Seria muito agradável aprender que as matrizes Hadamard e Huang são, de certa forma, até equivalência, as únicas duas não triviais :). E se não, talvez haja outros interessantes por aí ...

Joshua Grochow
fonte
E se não, talvez haja outros interessantes por aí ... parece bem interessante :)
Clement C.
9

Aqui estão apenas algumas observações que eu não poderia incluir em um comentário:

0) Adicionado porque a primeira resposta foi excluída: existe uma interpretação de Hn , ou seja, indexando as linhas e colunas por {0,1}n , a entrada correspondente a (x,y) é 1 se o produto Hadamard xy=(x1y1,,xnyn) tem paridade par e 1 se tiver paridade ímpar.

1) Em geral, o espectro de matrizes de blocos pode ser muito complicado e obviamente não relacionado aos espectros dos blocos individuais, pois o polinômio característico será horrível . Mas para uma matriz de blocos simétrica M=(ABBTC) que pode surgir através de uma construção recursiva como An e Hn acima, em que cada matriz é quadrada, uma das únicas simplificações ocorre quando BT e C comutam, neste caso, det(M)=det(ACBBT) . Em seguida, o polinómio característico deM será

det((λIA)(λIC)BBT)=det(λ2Iλ(A+C)+ACBBT).
Para que isso leve a boas fórmulas recursivas para os autovalores, basicamente é necessárioC=A para matar otermoλ linear. SeA eB são simétricos e comutados, obtemos
det(λIM)=det(λ2I(A2+B2)),
partir do qual se lê facilmente os valores próprios usando o fato de matrizes simétricas de comutação admitirem uma eigenbasis comum. Isso pode ser óbvio, mas tudo isso significa que, para obter boas fórmulas recursivas para os valores próprios, é basicamente essencial exigir que o bloco inferior direito sejaA e espero que os blocos inferior esquerdo e superior direito sejam simétricos e comutar comA , como é o caso dasmatrizesAn (comB=I ) eHn (comB=Hn1=A ).

2) Na questão do sinal aleatório: a assinatura da matriz de adjacência dada no artigo é ideal no sentido de maximizar λ2n1 , necessário para o limite inferior por meio do entrelaçamento de Cauchy, e pode ser visto de maneira elementar. Para uma assinatura arbitrária Mn da matriz de adjacência do hipercubo n dimensional, obtém-se imediatamente

Tr(Mn)=i=12nλi(Mn)=0,Tr(Mn2)=i=12nλi(Mn)2=MnF2=n2n,
ondeλ1(Mn)λ2(Mn)λ2n(Mn) . Se por algum sinalMnum tem λ2n1(Mn)>n , em seguida,
i=12n1λi(Mn)>n2n1,i=12n1λi(Mn)2>n2n1.
One can then see it is not possible to satisfy the trace equalities above: the negative eigenvalues must sum to strictly more than n2n1 (in absolute value), and their squares must sum to strictly less than n2n1. 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 λ2n1(Mn)n without knowing the magic signing in the paper, where equality holds iff the values are n,,n,n,,n. That there actually exists such a signing attaining it is pretty amazing. The eigenvalues of the normal adjacency matrix are n,n+2,,n2,n, where the ith eigenvalue has multiplicity (ni), so it's very interesting (to me, anyway) how the all-+1 signing maximizes λ1, while this signing maximizes λ2n1.

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
fonte