Istnienie rozwiązania dla systemu liniowego mod 2
Pozwolić $A$ być (skośną-) symetryczną macierzą nad $\mathbb{Z}/2$. (W rzeczywistości wziąłbym$A$ jako macierz łącząca zorientowanego linku w ramce w $S^3$lub macierz reprezentująca formę przecięcia na zamkniętej, gładkiej 4-kolektorze. Jednak poniższe stwierdzenie wydaje się być ogólnie przyjęte.) Interesuje mnie następujący układ liniowy$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$
Wiadomo, że ten system zawsze ma rozwiązanie. (por . Wykłady Savelieva o topologii trzech rozmaitości ). Ale nie rozumiem, dlaczego jest to prawdą, chyba że$A$ jest bezosobowa $\mathbb{Z}/2$. Czy istnieje ogólna metoda radzenia sobie z tego rodzaju systemami liniowymi?
Odpowiedzi
To prawda, ale jest to trochę trudne. Chodzi o to, aby po prostu napisać macierz w formularzu$$ A=BB^T $$ w taki sposób, że przestrzeń kolumn $B$ jest równa temu z $A$. Wszystkie kolumny$A$ są liniowymi kombinacjami kolumn $B$, ale nie jest dla mnie jasne, jak osiągnąć odwrotną integrację (nie jest to oczywiście prawdą w przypadku wszystkich wyborów $B$).
Więc w tej chwili nie mogę napisać całkowicie samodzielnego dowodu, muszę odnieść się do dwóch artykułów:
- A. Lempel, Koniec faktoryzacji macierzy$GF(2)$ i śladowo-ortogonalne bazy $GF(2^m)$, SIAM J. Comput., Tom. 4, 175-186, czerwiec 1975.
- G. Seroussi, A. Lempel, Maximum Likelihood Decoding of Some Reed-Muller Codes , IEEE Transactions on information Teoria, Vol. IT-29, NIE. 3 maja 1983.
IIRC jest potrzebny tylko pierwszy. Uwzględniam to drugie, bo to pierwsze znalazłem, czytając.
Problem, który Lempel (znany z Lempel-Ziv) rozwiązuje w pierwszym artykule, jest następujący. Chce napisać daną symetrię$n\times n$ matryca $A$ nad $\Bbb{Z}_2$ w formie $A=BB^T$tak wydajnie, jak to możliwe. Oznacza to, że chce zminimalizować liczbę kolumn$m$ z $B$. Jego odpowiedź brzmi:
Normalnie $m$ jest równa rangi $r(A)$ z $A$. Wyjątkiem jest przekątna$A$ to same zera, kiedy $m=1+r(A)$ to najlepsze, co możemy zrobić.
Możemy zastosować wynik Lempela do rozwiązania tego problemu w następujący sposób.
- Jeśli przekątna $A$to same zera, twierdzenie jest trywialne. Możemy użyć$x_i=0$ dla wszystkich $i$.
- Jeśli tak nie jest, liczba kolumn $B$ jest równa randze $A$. Tak jak$A=BB^T$ przestrzeń kolumn $A$ jest wtedy równa temu z $B$.
- Wystarczy więc pokazać, że przekątna $A$ znajduje się w przestrzeni kolumn $B$.
- Równanie $A=BB^T$ oznacza, że $a_{ii}$ jest równy iloczynowi wewnętrznemu $(B_i,B_i)$ z $i$rzucać $B_i$ z $B$ samym sobą.
- Ale $B_i$ jest binarny, więc $(B_i,B_i)$ jest po prostu sumą wpisów tego $i$wiersz jako $x^2=x$ dla wszystkich $x\in\Bbb{Z}_2$.
- Dlatego przekątna $A$ jest sumą kolumn $B$.
- Dlatego przekątna $A$ znajduje się również w przestrzeni kolumn $A$ i gotowe.
Wydaje się to niepotrzebnie niezdarne. Pomysł użycia$A=BB^T$przyszedł do mnie intuicyjnie. Obliczyłem kilka przykładów i zauważyłem, że kolumny$B$podsumuj do przekątnej. Czas na żarówkę!
Plik $\mathbb{Z}_2$ forma przecięcia na zamkniętej gładkiej $4$-rozmaitość jest zawsze nieodgenerowana przez dualność Poincarego.