Existenz einer Lösung für ein lineares System mod 2

Dec 09 2020

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

1 JyrkiLahtonen Dec 10 2020 at 04:21

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.

  1. Wenn die Diagonale von $A$Ist alles Nullen, ist die Behauptung trivial. Wir können benutzen$x_i=0$ für alle $i$.
  2. 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$.
  3. Es genügt also zu zeigen, dass die Diagonale von $A$ ist im Spaltenraum von enthalten $B$.
  4. 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.
  5. 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$.
  6. Daher die Diagonale von $A$ ist die Summe der Spalten von $B$.
  7. 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!

QiaochuYuan Dec 09 2020 at 14:15

Das $\mathbb{Z}_2$ Schnittform auf einer geschlossenen glatten $4$-Vielfalt ist durch Poincare-Dualität immer nicht entartet.