Pertanyaan tentang dua matriks: Hadamard v. "Yang ajaib" sebagai bukti dugaan sensitivitas

Bukti dugaan sensitivitas baru-baru ini dan sangat apik bergantung pada konstruksi * eksplisit dari matriks , didefinisikan secara rekursif sebagai berikut: dan, untuk , Secara khusus, mudah untuk melihat bahwa untuk semua .$A_n\in\{-1,0,1\}^{2^n\times 2^n}$

$$A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix}$$ $n\geq 2$ $$A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix}$$ $A_n^2 = n I_n$$n\geq 1$

Sekarang, mungkin saya membaca terlalu banyak tentang ini, tetapi ini terlihat setidaknya secara sintaksis berhubungan dengan keluarga matriks terkenal lainnya, matriks Hadamard, yang juga sedemikian rupa sehingga dan memiliki spektrum 'mirip': dan, untuk , $H_n^2 \propto I_n$

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

Apakah ada hubungan formal, mungkin bermanfaat, di antara keduanya, kecuali bahwa "mereka terlihat agak mirip"?

Sebagai contoh, dilihat sebagai matriks adjacency yang ditandatangani dari hypercube memiliki interpretasi yang bagus (tanda tepi adalah paritas dari awalan ). Apakah ada analog untuk ? (ini mungkin jelas?)$A_n$$\{0,1\}^n$$(x,b,x')\in\{0,1\}^n$$x$$H_n$

$^*$ Saya juga bertanya-tanya apakah konstruksi non-eksplisit, misalnya, matriks acak seragam , akan memiliki sifat spektral yang diinginkan, tetapi itu mungkin harus menunggu pertanyaan lain.$\pm1$

Pengamatan terlalu lama untuk komentar (dan yang juga cocok dengan pengamatan Jason Gaitonde-terlalu-lama-untuk-komentar):

Seperti yang diisyaratkan dalam OQ, kedua hal ini sebenarnya dapat diwujudkan dengan konstruksi rekursif yang sangat sederhana. Yaitu, kami menetapkan ( matriks ), dan kemudian satu rumus rekursif tunggal$B_0 \in \{(0), (\pm 1)\}$$1 \times 1$

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

di mana setiap adalah salah satu dari (di sini di sini "1" menunjukkan identitas dengan ukuran yang sesuai, yaitu , dan demikian pula "0" menunjukkan matriks nol dari ukuran yang sesuai, dan menunjukkan ). Untuk matriks Huang, kita sebenarnya memiliki dan rumus rekursif adalah , sedangkan untuk matriks Hadamard kita memiliki dan rumus rekursif adalah .$b_{ij}$$\{0, \pm 1, \pm x\}$$2^{n-1} \times 2^{n-1}$$x$$B_{n-1}$$A_0 = (0)$$\begin{bmatrix} x & 1 \\ 1 & -x \end{bmatrix}$$H_0 = (1)$$\begin{bmatrix} x & x \\ x & -x \end{bmatrix}$

Jika seseorang menginginkan rekursi seperti itu memiliki properti yang sebanding dengan , maka orang dengan cepat menemukan bahwa , atau . Dalam kasus terakhir, rekursi hanya menghasilkan matriks diagonal, yang mungkin tidak begitu menarik. Jadi kasus-kasus menarik adalah kasus-kasus di mana (yang merupakan salah satu kondisi "kebaikan" dalam jawaban Jason). Ini juga dapat dilihat sebagai penjelasan umum mengapa kedua urutan matriks tidak dapat ditemukan.$B_n^2$$I_{2^{n}}$$b_{11} + b_{22} = 0$$b_{12} = b_{21}=0$$b_{11} = -b_{22}$

Sebagai komentar kecil terakhir, jenis rekursi ini secara otomatis menghasilkan bahwa entri blok bolak-balik, yang merupakan kondisi "kebaikan" lain dalam jawaban Jason.$B_n$

Saya belum melakukan penyelidikan sistematis, tetapi mengingat pengaturan di atas, orang dapat menyelidiki banyak kemungkinan (3 pilihan untuk , dan secara teknis pilihan untuk rekursi, tetapi ini dapat dikurangi menggunakan simetri dan juga dari pembatasan bahwa sebanding dengan identitas). Akan sangat menyenangkan untuk mengetahui bahwa matriks Hadamard dan Huang entah bagaimana, sampai dengan kesetaraan, hanya dua yang nontrivial :). Dan jika tidak, mungkin ada beberapa yang menarik yang bersembunyi di luar sana ...$B_0$$5^4$$B_n^2$

Ini beberapa pengamatan yang tidak bisa saya masukkan dalam komentar:

0) Ditambahkan karena jawaban pertama telah dihapus: ada interpretasi , yaitu, mengindeks baris dan kolom dengan , entri yang sesuai dengan adalah jika produk Hadamard memiliki paritas genap, dan jika paritas ganjil.$H_n$$\{0,1\}^n$$(x,y)$$1$$x\odot y=(x_1y_1,\ldots,x_n y_n)$$-1$

1) Secara umum, spektrum matriks blok dapat sangat rumit dan tidak jelas terkait dengan spektrum masing-masing blok, karena karakteristik polinomialnya akan terlihat mengerikan . Tapi untuk blok matriks simetris yang mungkin timbul melalui konstruksi rekursif seperti dan di atas, di mana setiap matriks persegi, salah satu satu-satunya penyederhanaan terjadi ketika dan bepergian, dalam hal ini seseorang memiliki . Maka polinomial karakteristik adalah$M=\begin{pmatrix} A & B\\ B^T & C\end{pmatrix}$$A_n$$H_n$$B^T$$C$$\det(M)=\det(AC-BB^T)$$M$

$$\det((\lambda I-A)(\lambda I-C)-BB^T)=\det(\lambda^2I-\lambda (A+C)+AC-BB^T).$$ Agar hal ini mengarah pada rumus rekursif yang bagus untuk nilai eigen, yang pada dasarnya membutuhkan untuk membunuh istilah linear . Jika lebih lanjut dan simetris dan bolak-balik, kita mendapatkan yang darinya seseorang dengan mudah membaca nilai eigen menggunakan Bahkan matriks komuter simetris mengakui eigenbasis umum. Ini mungkin jelas, tetapi semua ini adalah untuk mengatakan bahwa sejauh mendapatkan formula rekursif yang baik untuk nilai-nilai eigen, pada dasarnya penting untuk mengharuskan blok kanan bawah menjadi dan berharap bahwa blok kiri bawah dan kanan atas simetris dan bepergian dengan , yang merupakan kasus untuk$C=-A$$\lambda$$A$$B$ $$\det(\lambda I-M)=\det(\lambda^2 I-(A^2+B^2)),$$ $-A$$A$$A_n$(dengan ) dan matriks (dengan ).$B=I$$H_n$$B=H_{n-1}=A$

2) Pada pertanyaan tanda acak: penandatanganan matriks adjacency yang diberikan dalam makalah adalah optimal dalam arti memaksimalkan , yang diperlukan untuk batas bawah melalui interlacing Cauchy, dan dapat dilihat dari sarana dasar. Untuk penandatanganan dari adjacency matrix dari -dimensional hypercube, seseorang segera mendapatkan mana . Jika untuk beberapa penandatanganan seseorang memiliki , maka $\lambda_{2^{n-1}}$$M_n$$n$

$$\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,$$ $\lambda_1(M_n)\geq \lambda_2(M_n)\geq\ldots\geq \lambda_{2^n}(M_n)$$M_n$$\lambda_{2^{n-1}}(M_n)>\sqrt{n}$ $$\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}.$$ Satu kemudian dapat melihat itu tidak mungkin untuk memenuhi jejak persamaan di atas: nilai eigen negatif harus berjumlah lebih dari (dalam nilai absolut), dan kotak mereka harus dijumlahkan dengan sangat kurang dari pada . Meminimalkan jumlah kuadrat sambil menjaga jumlah konstan terjadi ketika mereka semua sama, tetapi dalam hal ini akan membuat jumlah kuadrat terlalu besar. Jadi untuk penandatanganan apa pun, orang dapat melihat melalui sarana dasar bahwa tanpa mengetahui penandatanganan ajaib di kertas, di mana kesetaraan berlaku jika nilainya adalah$\sqrt{n}2^{n-1}$$n2^{n-1}$$\lambda_{2^{n-1}}(M_n)\leq \sqrt{n}$$\sqrt{n},\ldots,\sqrt{n},-\sqrt{n},\ldots,-\sqrt{n}$. Bahwa benar-benar ada penandatanganan seperti itu, itu sangat menakjubkan. Nilai eigen dari matriks adjacency normal , di mana th eigen memiliki keragaman , sehingga sangat menarik (bagi saya, anyway) bagaimana semua- penandatanganan memaksimalkan , sementara penandatanganan ini memaksimalkan .$-n, -n+2,\ldots,n-2,n$$i$${n\choose i }$$+1$$\lambda_1$$\lambda_{2^{n-1}}$

Sejauh penandatanganan acak bekerja, lebih sulit untuk mengatakan karena saya pikir sebagian besar batas non-asimptotik pada nilai eigen fokus pada norma spektral. Seseorang mengharapkan penandatanganan acak untuk memuluskan nilai eigen biasa yang ekstrem, dan memang, menggunakan ketidaksetaraan Khintchine nonkomutatif dan / atau batas yang lebih ketat baru-baru ini seperti di sini , penandatanganan acak yang seragam memiliki . Sulit bagi saya untuk membayangkan nilai eigen tengah akan berada pada urutan polinomial yang sama dengan yang terkemuka dalam harapan (dan hasil asimptotik seperti hukum setengah lingkaran untuk ansambel matriks yang berbeda menyarankan dengan cara yang sama, saya pikir), tetapi mungkin itu mungkin.$\mathbb{E}[\|M_n\|_2]=\Theta(\sqrt{n})$