Existence of solution for a linear system mod 2

Solution 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!