Existencia de solución para un sistema lineal mod 2

Question

Dejar $A$ ser una matriz simétrica (sesgada) sobre $\mathbb{Z}/2$. (De hecho, tomaría$A$ como la matriz de enlace de un enlace enmarcado orientado en $S^3$o la matriz que representa la forma de intersección en un colector 4 liso cerrado. Sin embargo, la siguiente afirmación parece ser válida en general.) Estoy interesado en el siguiente sistema lineal sobre$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$

Se sabe que este sistema siempre tiene una solución. (cf. Saveliev's Lectures on the Topology of 3-Manifolds .) Pero no puedo ver por qué es esto cierto a menos que$A$ no es singular $\mathbb{Z}/2$. ¿Existe un método general para tratar este tipo de sistemas lineales?

Answer 1

Esto es cierto, pero es un poco complicado. La idea es simplemente escribir la matriz en la forma$$ A=BB^T $$ de tal manera que el espacio columna de $B$ es igual a la de $A$. Todas las columnas de$A$ son combinaciones lineales de columnas de $B$, pero no me queda claro cómo lograr la inclusión inversa (claramente no es cierto para todas las opciones de $B$).

Entonces, en este momento no puedo escribir una prueba completamente autónoma, necesito referirme a dos artículos:

• A. Lempel, factorización matricial sobre$GF(2)$ y trazas de bases ortogonales de $GF(2^m)$, SIAM J. Comput., Vol. 4, págs. 175-186, junio de 1975.
• G. Seroussi, A. Lempel, Decodificación de máxima verosimilitud de ciertos códigos Reed-Muller , Transacciones IEEE sobre teoría de la información, vol. IT-29, NO. 3, mayo de 1983.

IIRC solo se necesita el primero. Incluyo el último, porque encontré el primero al leerlo.

El problema que Lempel (de fama Lempel-Ziv) resuelve en el primer artículo es el siguiente. Quiere escribir un simétrico dado$n\times n$ matriz $A$ encima $\Bbb{Z}_2$ en la forma $A=BB^T$de la manera más eficiente posible. Es decir, quiere minimizar el número de columnas$m$ de $B$. Su respuesta es que

Normalmente $m$ es igual al rango $r(A)$ de $A$. La excepción viene cuando la diagonal de$A$ es todo ceros, cuando $m=1+r(A)$ es lo mejor que podemos hacer.

Podemos aplicar el resultado de Lempel para resolver esta cuestión de la siguiente manera.

1. Si la diagonal de $A$es todo ceros, la afirmación es trivial. Nosotros podemos usar$x_i=0$ para todos $i$.
2. Cuando ese no es el caso, el número de columnas de $B$ es igual al rango de $A$. Como$A=BB^T$ el espacio de la columna de $A$ es entonces igual a la de $B$.
3. Por tanto, basta con mostrar que la diagonal de $A$ está contenido en el espacio de columna de $B$.
4. La ecuacion $A=BB^T$ significa que $a_{ii}$ es igual al producto interno $(B_i,B_i)$ del $i$lanzar $B_i$ de $B$ consigo mismo.
5. Pero $B_i$ es binario, entonces $(B_i,B_i)$ es simplemente la suma de las entradas de ese $i$la fila como $x^2=x$ para todos $x\in\Bbb{Z}_2$.
6. Por lo tanto, la diagonal de $A$ es la suma de las columnas de $B$.
7. Por lo tanto, la diagonal de $A$ también está en el espacio de columna de $A$ y hemos terminado.

---

Esto se siente innecesariamente torpe. La idea de usar$A=BB^T$vino a mí intuitivamente. Calculé varios ejemplos y noté que las columnas de$B$resumir a la diagonal. ¡Hora de la bombilla!

Answer 2

los $\mathbb{Z}_2$ forma de intersección en un liso cerrado $4$-manifold es siempre no degenerado por la dualidad de Poincaré.