線形システムmod2のソリューションの存在
しましょう $A$ （スキュー-）対称行列である $\mathbb{Z}/2$。（実際、私は$A$ の方向付けられたフレームリンクのリンクマトリックスとして $S^3$または、閉じた滑らかな4次元多様体上の交叉形式を表す行列。ただし、次のステートメントは一般的に当てはまるようです。）次の線形システムに興味があります。$\mathbb{Z}/2$、 $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$
このシステムには常に解決策があることが知られています。（3次元多様体のトポロジーに関するSavelievの講義を参照してください。）しかし、これが真実でない限り、なぜこれが真実であるのかわかりません。$A$ 正則です $\mathbb{Z}/2$。これらの種類の線形システムを処理する一般的な方法はありますか？
回答
これは本当ですが、少し注意が必要です。アイデアは単に行列を次の形式で書くことです$$ A=BB^T $$ の列空間が $B$ と等しい $A$。のすべての列$A$ の列の線形結合です $B$、しかし、逆包含を達成する方法は私には明確ではありません（それは明らかにすべての選択肢に当てはまるわけではありません $B$）。
したがって、現時点では完全に自己完結型の証明を書くことはできません。2つの記事を参照する必要があります。
- A. Lempel、行列の因数分解$GF(2)$ およびトレース直交基底 $GF(2^m)$、 SIAM J. Comput。、vol。4、pp。175-186、1975年6月。
- G. Seroussi、A。Lempel、特定のリードマラーコードの最大可能性復号化、情報理論に関するIEEEトランザクション、Vol。IT-29、いいえ。1983年5月3日。
IIRCは最初のものだけが必要です。前者を読んで見つけたので、後者を含めます。
Lempel（Lempel-Zivの名声）が最初の記事で解決する問題は次のとおりです。彼は与えられた対称を書きたい$n\times n$ マトリックス $A$ 以上 $\Bbb{Z}_2$ フォームで $A=BB^T$可能な限り効率的に。つまり、彼は列の数を最小限に抑えたいと考えています$m$ の $B$。彼の答えは
通常は $m$ ランクに等しい $r(A)$ の $A$。例外は、の対角線が$A$ がすべてゼロの場合 $m=1+r(A)$ 私たちができる最善のことです。
Lempelの結果を適用して、この質問を次のように解決できます。
- の対角線の場合 $A$がすべてゼロの場合、主張は取るに足らないものです。使用できます$x_i=0$ すべてのために $i$。
- そうでない場合、の列数 $B$ のランクに等しい $A$。なので$A=BB^T$ の列スペース $A$ その場合、 $B$。
- したがって、の対角線を示すだけで十分です。 $A$ の列スペースに含まれています $B$。
- 方程式 $A=BB^T$ という意味です $a_{ii}$ 内積と等しい $(B_i,B_i)$ の $i$3行目 $B_i$ の $B$ それ自体で。
- だが $B_i$ バイナリなので、 $(B_i,B_i)$ 単にそのエントリの合計です $i$3行目 $x^2=x$ すべてのために $x\in\Bbb{Z}_2$。
- したがって、の対角線 $A$ の列の合計です $B$。
- したがって、の対角線 $A$ の列スペースにもあります $A$ これで完了です。
これは不必要にぎこちなく感じます。使用するという考え$A=BB^T$直感的に来ました。私はいくつかの例を計算し、の列が$B$対角線まで合計します。電球の時間！
ザ・ $\mathbb{Z}_2$ 閉じた滑らかな交差形式 $4$-マニホールドは、ポアンカレ双対性によって常に縮退していません。