Existence of solution for a linear system mod 2

Question

Let $A$ be a (skew-) symmetric matrix over $\mathbb{Z}/2$. (In fact, I would take $A$ as the linking matrix of an oriented framed link in $S^3$ or the matrix representing the intersection form on a closed smooth 4-manifold. The following statement however does seem to hold in general.) I am interested in the following linear system over $\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$

This system is known to always have a solution. (c.f. Saveliev's Lectures on the Topology of 3-Manifolds.) But I cannot see why is this true unless $A$ is nonsingular over $\mathbb{Z}/2$. Is there a general method to deal with these kinds of linear systems?

Answer 1

This is true, but it is a bit tricky. The idea is simply to write the matrix in the form $$ A=BB^T $$ in such a way that the column space of $B$ is equal to that of $A$. All the columns of $A$ are linear combinations of columns of $B$, but it is not clear to me how to achieve the reverse inclusion (it is clearly not true for all choices of $B$).

So at this time I cannot write a completely self-contained proof, I need to refer to two articles:

• A. Lempel, Matrix factorization over $GF(2)$ and trace-orthogonal bases of $GF(2^m)$, SIAM J. Comput., vol. 4, pp. 175-186, June 1975.
• G. Seroussi, A. Lempel, Maximum Likelihood Decoding of Certain Reed-Muller Codes, IEEE Transactions on information theory, Vol. IT-29, NO. 3, May 1983.

IIRC only the first is needed. I include the latter, because I found the former by reading it.

The problem Lempel (of Lempel-Ziv fame) solves in the first article is the following. He wants to write a given symmetric $n\times n$ matrix $A$ over $\Bbb{Z}_2$ in the form $A=BB^T$ as efficiently as possible. That is, he wants to minimize the number of columns $m$ of $B$. His answer is that

Normally $m$ is equal to the rank $r(A)$ of $A$. The exception comes when the diagonal of $A$ is all zeros, when $m=1+r(A)$ is the best we can do.

We can apply Lempel's result to settle this question as follows.

1. If the diagonal of $A$ is all zeros, the claim is trivial. We can use $x_i=0$ for all $i$.
2. When that is not the case, the number of columns of $B$ is equal to the rank of $A$. As $A=BB^T$ the column space of $A$ is then equal to that of $B$.
3. So it suffices to show that the diagonal of $A$ is contained in the column space of $B$.
4. The equation $A=BB^T$ means that $a_{ii}$ is equal to the inner product $(B_i,B_i)$ of the $i$th row $B_i$ of $B$ with itself.
5. But $B_i$ is binary, so $(B_i,B_i)$ is simply the sum of the entries of that $i$th row as $x^2=x$ for all $x\in\Bbb{Z}_2$.
6. Therefore the diagonal of $A$ is the sum of the columns of $B$.
7. Therefore the diagonal of $A$ is also in the column space of $A$ and we are done.

---

This feels unnecessarily kludgy. The idea of using $A=BB^T$ came to me intuitively. I calculated several examples and noticed that the columns of $B$ sum up to the diagonal. Light bulb time!

Answer 2

The $\mathbb{Z}_2$ intersection form on a closed smooth $4$-manifold is always nondegenerate by Poincare duality.

Answer 3

Let $G$ be the undirected graph possibly with loops which has adjacency matrix $A$ in which vertices can be black or white. Initially they are all white. A valid move is to select a vertex and change the color of its neighbors. Our problem is equivalent to showing there is is a sequence of moves that can change the color of all the vertices with loops but no other vertex.

The proof is by induction on the number of vertices. For each vertex of $v$ consider the graph $G-v$. By the inductive hypothesis there a sequence of moves that works in $G-v$, if any of these sequences of moves also does what we want it to do to $v$ in the original graph then we are done, so we assume it always does the incorrect thing on $v$. We call this sequence a supermove on $v$.

If the number of loops is even we just have to do a supermove over all vertices with a loop and we are done.

If the number of loops is odd then the sum of degrees is odd and so there is an odd number of vertices of odd degree. We can do a supermove over all vertices with odd degree, the incorrect vertices will then be exactly the vertices with odd degree, and we can fix it by making a regular move over all of the vertices.