Existenz einer Lösung für ein lineares System mod 2
Lassen $A$ sei eine (schief-) symmetrische Matrix über $\mathbb{Z}/2$. (In der Tat würde ich nehmen$A$ als Verknüpfungsmatrix eines orientierten gerahmten Links in $S^3$oder die Matrix, die die Schnittform auf einem geschlossenen glatten 4-Verteiler darstellt. Die folgende Aussage scheint jedoch allgemein zu gelten.) Ich interessiere mich für das folgende lineare System über$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$
Es ist bekannt, dass dieses System immer eine Lösung hat. ( Siehe Savelievs Vorlesungen über die Topologie von 3-Mannigfaltigkeiten .) Aber ich kann nicht sehen, warum dies wahr ist, es sei denn$A$ ist nicht singulär vorbei $\mathbb{Z}/2$. Gibt es eine allgemeine Methode, um mit solchen linearen Systemen umzugehen?
Antworten
Das ist wahr, aber es ist ein bisschen schwierig. Die Idee ist einfach, die Matrix in das Formular zu schreiben$$ A=BB^T $$ so, dass der Spaltenraum von $B$ ist gleich dem von $A$. Alle Spalten von$A$ sind lineare Kombinationen von Spalten von $B$, aber es ist mir nicht klar, wie man die umgekehrte Einbeziehung erreicht (es gilt eindeutig nicht für alle Entscheidungen von $B$).
Zum jetzigen Zeitpunkt kann ich keinen vollständig in sich geschlossenen Beweis schreiben. Ich muss mich auf zwei Artikel beziehen:
- A. Lempel, Matrixfaktorisierung vorbei$GF(2)$ und spurorthogonale Basen von $GF(2^m)$, SIAM J. Comput., Bd. 4, S. 175-186, Juni 1975.
- G. Seroussi, A. Lempel, Maximum-Likelihood-Decodierung bestimmter Reed-Muller-Codes , IEEE Transactions on Information Theory. IT-29, NR. 3. Mai 1983.
IIRC wird nur der erste benötigt. Ich schließe das letztere ein, weil ich das erstere durch Lesen gefunden habe.
Das Problem, das Lempel (von Lempel-Ziv) im ersten Artikel löst, ist das folgende. Er möchte eine bestimmte Symmetrie schreiben$n\times n$ Matrix $A$ Über $\Bbb{Z}_2$ in der Form $A=BB^T$so effizient wie möglich. Das heißt, er möchte die Anzahl der Spalten minimieren$m$ von $B$. Seine Antwort ist das
Normalerweise $m$ ist gleich dem Rang $r(A)$ von $A$. Die Ausnahme kommt, wenn die Diagonale von$A$ ist alles Nullen, wenn $m=1+r(A)$ ist das Beste, was wir tun können.
Wir können das Ergebnis von Lempel anwenden, um diese Frage wie folgt zu klären.
- Wenn die Diagonale von $A$Ist alles Nullen, ist die Behauptung trivial. Wir können benutzen$x_i=0$ für alle $i$.
- Ist dies nicht der Fall, wird die Anzahl der Spalten von $B$ ist gleich dem Rang von $A$. Wie$A=BB^T$ der Spaltenraum von $A$ ist dann gleich dem von $B$.
- Es genügt also zu zeigen, dass die Diagonale von $A$ ist im Spaltenraum von enthalten $B$.
- Die gleichung $A=BB^T$ bedeutet, dass $a_{ii}$ ist gleich dem inneren Produkt $(B_i,B_i)$ des $i$werfen $B_i$ von $B$ mit sich selbst.
- Aber $B_i$ ist also binär $(B_i,B_i)$ ist einfach die Summe der Einträge davon $i$th Reihe als $x^2=x$ für alle $x\in\Bbb{Z}_2$.
- Daher die Diagonale von $A$ ist die Summe der Spalten von $B$.
- Daher die Diagonale von $A$ ist auch im Spaltenraum von $A$ und wir sind fertig.
Das fühlt sich unnötig klobig an. Die Idee zu verwenden$A=BB^T$kam intuitiv zu mir. Ich berechnete mehrere Beispiele und bemerkte, dass die Spalten von$B$Summe auf die Diagonale. Glühbirnenzeit!
Das $\mathbb{Z}_2$ Schnittform auf einer geschlossenen glatten $4$-Vielfalt ist durch Poincare-Dualität immer nicht entartet.