Adanya solusi untuk sistem linier mod 2
Membiarkan $A$ menjadi matriks simetris (skew-) berakhir $\mathbb{Z}/2$. (Sebenarnya, saya akan mengambil$A$ sebagai matriks penautan dari tautan berbingkai yang berorientasi di $S^3$atau matriks yang mewakili bentuk perpotongan pada manifol-4 halus tertutup. Namun pernyataan berikut tampaknya berlaku secara umum.) Saya tertarik pada sistem linier berikut ini$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$
Sistem ini dikenal selalu punya solusi. (cf Kuliah Saveliev tentang Topologi Manifold-3 .) Tetapi saya tidak dapat melihat mengapa ini benar kecuali$A$ adalah nonsingular berakhir $\mathbb{Z}/2$. Apakah ada metode umum untuk menangani jenis sistem linier ini?
Jawaban
Ini benar, tetapi agak rumit. Idenya hanyalah menulis matriks dalam formulir$$ A=BB^T $$ sedemikian rupa sehingga ruang kolom $B$ sama dengan $A$. Semua kolom$A$ adalah kombinasi linier dari kolom $B$, tetapi tidak jelas bagi saya bagaimana mencapai inklusi terbalik (ini jelas tidak benar untuk semua pilihan $B$).
Jadi saat ini saya tidak bisa menulis bukti yang lengkap, saya perlu merujuk ke dua artikel:
- A. Lempel, Faktorisasi matriks selesai$GF(2)$ dan basis jejak-ortogonal $GF(2^m)$, SIAM J. Comput., Vol. 4, hlm. 175-186, Juni 1975.
- G. Seroussi, A. Lempel, Penguraian Kemungkinan Maksimum Kode Reed-Muller Tertentu , Transaksi IEEE pada teori informasi, Vol. IT-29, TIDAK. 3, Mei 1983.
IIRC hanya yang pertama yang dibutuhkan. Saya memasukkan yang terakhir, karena saya menemukan yang pertama dengan membacanya.
Masalah yang Lempel (dari ketenaran Lempel-Ziv) selesaikan di artikel pertama adalah sebagai berikut. Dia ingin menulis simetris yang diberikan$n\times n$ matriks $A$ lebih $\Bbb{Z}_2$ dalam bentuk $A=BB^T$seefisien mungkin. Artinya, dia ingin meminimalkan jumlah kolom$m$ dari $B$. Jawabannya adalah itu
Biasanya $m$ sama dengan pangkat $r(A)$ dari $A$. Pengecualian muncul saat diagonal$A$ semuanya nol, bila $m=1+r(A)$ adalah yang terbaik yang bisa kami lakukan.
Hasil Lempel dapat kita terapkan untuk menjawab pertanyaan ini sebagai berikut.
- Jika diagonal $A$semuanya nol, klaimnya sepele. Kita bisa gunakan$x_i=0$ untuk semua $i$.
- Jika bukan itu masalahnya, jumlah kolom dari $B$ sama dengan pangkat $A$. Sebagai$A=BB^T$ ruang kolom $A$ kemudian sama dengan $B$.
- Jadi cukup untuk menunjukkan bahwa diagonal $A$ terdapat di ruang kolom $B$.
- Persamaannya $A=BB^T$ maksudnya $a_{ii}$ sama dengan produk dalam $(B_i,B_i)$ dari $i$baris ke-th $B_i$ dari $B$ dengan dirinya sendiri.
- Tapi $B_i$ adalah biner, jadi $(B_i,B_i)$ hanyalah jumlah dari entri itu $i$baris ke-th sebagai $x^2=x$ untuk semua $x\in\Bbb{Z}_2$.
- Oleh karena itu diagonal $A$ adalah jumlah dari kolom $B$.
- Oleh karena itu diagonal $A$ juga dalam ruang kolom $A$ dan kami selesai.
Ini terasa tidak perlu kusut. Ide menggunakan$A=BB^T$datang kepada saya secara intuitif. Saya menghitung beberapa contoh dan memperhatikan bahwa kolom$B$jumlah sampai diagonal. Waktunya bohlam!
Itu $\mathbb{Z}_2$ bentuk persimpangan pada permukaan licin tertutup $4$-manifold selalu tidak berdegenerasi oleh dualitas Poincare.