Вопрос о двух матрицах: Адамар против «магического» в доказательстве гипотезы чувствительности

23

Недавнее и невероятно приятное доказательство гипотезы о чувствительности основано на явном * построении матрицы An{1,0,1}2n×2n , определенной рекурсивно следующим образом:

A1=(0110)
и, для, В частности, легко видеть, чтодля всех.n2
An=(An1In1In1An1)
An2=nInn1

Теперь, может быть, я читаю слишком много в этом, но это выглядит как минимум синтаксически связанным с другим известным семейством матриц, матрицами Адамара, которое также таково, что Hn2In и имеет «похожий» спектр:

H1=(1111)
и, для n2 ,
Hn=(Hn1Hn1Hn1Hn1)

Есть ли какая-то формальная связь, возможно, полезная, между этими двумя, кроме того, что «они выглядят неопределенно похожими»?

Например, An рассматриваемая как матрица смежности со знаком гиперкуба {0,1}n имеет хорошую интерпретацию (знак ребра (x,b,x){0,1}n является четностью префикс x ). Есть ли аналог для Hn ? (это может быть очевидно?)

Мне также интересно, если бы неявная конструкция, например, равномерно случайнаяматрица±1 , имела бы желаемые спектральные свойства, но, вероятно, пришлось бы ждать другого вопроса.

Климент С.
источник

Ответы:

9

Наблюдение, слишком длинное для комментария (и которое также хорошо согласуется с наблюдением Джейсона Гайтонда, слишком длинным для комментария):

Как намекается в OQ, оба они могут быть реализованы с помощью очень простой рекурсивной конструкции. А именно, мы указываем B0{(0),(±1)} ( матрица 1×1 ), а затем одну рекурсивную формулу

Bn=(b11b12b21b22)

где каждый bij является одним из {0,±1,±x} (где здесь «1» обозначает единицу соответствующего размера, а именно 2n1×2n1 , и аналогично «0» обозначает ноль матрица соответствующего размера, а x обозначает Bn1 ). Для матриц Хуанга мы фактически имеем A0=(0) а рекурсивная формула имеет вид [x11x], тогда как для матриц АдамараH0=(1)и рекурсивная формула[xxxx].

Если кто -то хочет такой рекурсию , чтобы обладать свойством , что Bn2 пропорциональна I2n , то один быстро находит , что либо b11+b22=0 , или b12=b21=0 . В последнем случае рекурсия дает только диагональные матрицы, что, возможно, не так интересно. Итак, интересные случаи, в которых b11=b22(что является одним из условий "милости" в ответе Джейсона). Это также можно рассматривать как общее объяснение того, почему обе последовательности матриц не имеют следов.

В качестве последнего небольшого комментария этот тип рекурсии автоматически приводит к тому, что записи блока Bn коммутируют, что было другим условием «любезности» в ответе Джейсона.

Я еще не проводил систематического исследования, но, учитывая вышеописанную схему, можно исследовать конечное число возможностей (3 варианта для B0 и технически 54 вариантов для рекурсии, но это можно сократить с помощью симметрий, а также из ограничения, что Bn2 пропорциональна идентичности). Было бы очень приятно узнать, что матрицы Адамара и Хуанга как-то, вплоть до эквивалентности, единственные две нетривиальные :). А если нет, может быть, есть еще какие-то интересные, скрывающиеся там ...

Джошуа Грохов
источник
А если нет, может быть, есть еще какие-то интересные, скрывающиеся там ... звучит довольно интересно :)
Клемент С.
9

Вот только пара замечаний, которые я не смог уместить в комментарии:

0) Добавлено потому, что первый ответ был удален: существует интерпретация Hn , а именно, индексация строк и столбцов по {0,1}n , запись, соответствующая (x,y) равна 1 если произведение Адамара xy=(x1y1,,xnyn) имеет четную четность и 1 если она имеет нечетную четность.

1) Как правило, спектр блочных матриц может быть очень сложным и явно не связан со спектрами отдельных блоков, поскольку характеристический полином будет выглядеть ужасно . Но для симметричной блочной матрицы M=(ABBTC) которая может возникнуть через рекурсивную конструкцию, подобную вышеприведенным An и Hn , где каждая матрица является квадратной, одно из единственных упрощений происходит, когда BT и C коммутируют, в этом случае каждый имеет det(M)=det(ACBBT) . Тогда характеристическим многочленомM будет

det((λIA)(λIC)BBT)=det(λ2Iλ(A+C)+ACBBT).
Чтобы это привело к хорошим рекурсивным формулам для собственных значений, в основном требуетсяC=A чтобы убить линейныйчленλ . Если далееA иB симметричны и коммутируют, мы получаем
det(λIM)=det(λ2I(A2+B2)),
из которого легко считывать собственные значения, используя факт, что симметричные коммутирующие матрицы допускают общее собственное основание. Это может быть очевидно, но все это означает, что для получения хороших рекурсивных формул для собственных значений в основном необходимо требовать, чтобы нижний правый блок былA and hope that lower left and upper right blocks are symmetric and commute with A, which is the case for the An (with B=I) and Hn matrices (with B=Hn1=A).

λ2n1, which is needed for the lower bound via Cauchy interlacing, and can be seen from elementary means. For an arbitrary signing Mn of the adjacency matrix of the n-dimensional hypercube, one immediately gets

Tr(Mn)=i=12nλi(Mn)=0,Tr(Mn2)=i=12nλi(Mn)2=MnF2=n2n,
where λ1(Mn)λ2(Mn)λ2n(Mn). If for some signing Mn one has λ2n1(Mn)>n, then
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
источник