Existência de solução para um sistema linear mod 2

Question

Deixei $A$ ser uma matriz simétrica (enviesada) sobre $\mathbb{Z}/2$. (Na verdade, eu levaria$A$ como a matriz de ligação de um link enquadrado orientado em $S^3$ou a matriz que representa a forma de interseção em um coletor de 4 linhas fechado. A declaração a seguir, entretanto, parece ser válida em geral.) Estou interessado no seguinte sistema linear$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$

Este sistema é conhecido por ter sempre uma solução. (cf Saveliev's Lectures on the Topology of 3-Manifolds .) Mas eu não posso ver porque isso é verdade$A$ é não singular sobre $\mathbb{Z}/2$. Existe um método geral para lidar com esses tipos de sistemas lineares?

Answer 1

Isso é verdade, mas é um pouco complicado. A ideia é simplesmente escrever a matriz no formulário$$ A=BB^T $$ de tal forma que o espaço da coluna de $B$ é igual ao de $A$. Todas as colunas de$A$ são combinações lineares de colunas de $B$, mas não está claro para mim como conseguir a inclusão reversa (claramente não é verdade para todas as opções de $B$)

Portanto, no momento não posso escrever uma prova totalmente independente, preciso referir-me a dois artigos:

• A. Lempel, Matrix factorization over$GF(2)$ e bases traço ortogonais de $GF(2^m)$, SIAM J. Comput., Vol. 4, pp. 175-186, junho de 1975.
• G. Seroussi, A. Lempel, Decodificação de Máxima Verossimilhança de Certos Códigos Reed-Muller , IEEE Transactions on information theory, Vol. IT-29, NO. 3, maio de 1983.

IIRC apenas o primeiro é necessário. Incluo o último porque descobri o primeiro lendo-o.

O problema que Lempel (famoso por Lempel-Ziv) resolve no primeiro artigo é o seguinte. Ele quer escrever um dado simétrico$n\times n$ matriz $A$ sobre $\Bbb{Z}_2$ na forma $A=BB^T$tão eficientemente quanto possível. Ou seja, ele quer minimizar o número de colunas$m$ do $B$. A resposta dele é que

Normalmente $m$ é igual à classificação $r(A)$ do $A$. A exceção vem quando a diagonal de$A$ são todos zeros, quando $m=1+r(A)$ é o melhor que podemos fazer.

Podemos aplicar o resultado de Lempel para resolver essa questão da seguinte maneira.

1. Se a diagonal de $A$é tudo zeros, a afirmação é trivial. Podemos usar$x_i=0$ para todos $i$.
2. Quando esse não é o caso, o número de colunas de $B$ é igual à classificação de $A$. Como$A=BB^T$ o espaço da coluna de $A$ é então igual ao de $B$.
3. Portanto, é suficiente mostrar que a diagonal de $A$ está contido no espaço da coluna de $B$.
4. A equação $A=BB^T$ significa que $a_{ii}$ é igual ao produto interno $(B_i,B_i)$ do $i$lançar $B_i$ do $B$ consigo mesmo.
5. Mas $B_i$ é binário, então $(B_i,B_i)$ é simplesmente a soma das entradas desse $i$a linha como $x^2=x$ para todos $x\in\Bbb{Z}_2$.
6. Portanto, a diagonal de $A$ é a soma das colunas de $B$.
7. Portanto, a diagonal de $A$ também está no espaço da coluna de $A$ e nós terminamos.

---

Isso parece desnecessariamente desajeitado. A ideia de usar$A=BB^T$veio a mim intuitivamente. Calculei vários exemplos e percebi que as colunas de$B$soma até a diagonal. Hora da lâmpada!

Answer 2

o $\mathbb{Z}_2$ forma de interseção em um plano fechado $4$-variedade é sempre não degenerada pela dualidade de Poincaré.