Factorization of matrices over GF$(2)$

Question

Suppose $A\in \mathbb{F}_2^{n\times n}$ is full rank non-symmetric matrix. Then, can we write $A=BB^T$ for some full-rank $B$? I know there exists a Cholesky factorization, but its not clear if that factorization works over $\mathbb{F}_2$.

Edit 1: Sorry for misleading, but I am more interested in the case where $A$ is not symmetric and has a zero diagonal!

Answer 1

The relevant theory is explained in two articles, the first is actually enough. Also, I want to point out that the author is better known for inventing the Lempel-Ziv data compression algorithm used in zip-files and such. The second article (probably behind IEEE paywall for most of you) was more relevant to me, and was the route I found my way to the first article.

• A. Lempel, Matrix factorization over $GF(2)$ and trace-orthogonal bases of $GF(2)$, 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.

The main result is the following.

Theorem. Let $A$ be a symmetric $n\times n$ matrix over $GF(2)$. Let $\rho(A)$ denote its rank, and let $\delta(A)=1$, if $A_{ii}=0$ for all $i$, and $\delta(A)=0$ otherwise. Let $B$ be an $n\times m$ matrix such that $BB^T=A$. Then $$ m\ge \rho(A)+\delta(A).\qquad(*) $$ Furthermore, there exists a matrix $B$ with $\rho(A)+\delta(A)$ columns such that $A=BB^T$, so the bound $(*)$ is tight in this sense.

Sketching the reasoning why we should expect that additive $\delta(A)$-term (explaining some of the ingredients in Lempel's result):

• The rank of $A=BB^T$ is bounded from above by the rank of $B$, because the rows of $BB^T$ are linear combinations of the rows of $B^T$.
• The matrix entry $A_{ij}$ is the inner product of rows $i$ and $j$ of $B$. So if $A_{ii}=0$ for $i$, all the rows of $B$ must have an even number of ones.
• The subspace of $GF(2)^\ell$ consisting of all the vectors with an even number of ones has dimension $\ell-1$.
• In particular if $A$ has full rank $n$ and all the diagonal elements are zero, then any matrix $B$ such that $A=BB^T$ must have at least $n+1$ columns.
• Conversely, if $A$ has at least a single non-zero entry on the diagonal, then we can find a matching $B$ with $\rho(A)$ columns. This is the harder direction in Lempel's paper. It is not too difficult though. The idea is to do simple similarity transformations to the bilinear symmetric form determined by $A$. Mostly you get away with elementary transformations, but an extra trick is needed when making use of a non-zero diagonal entry.

The conclusion is that we can write a full rank symmetric matrix $A$ in the prescribed form (with a square matrix $B$) if and only if $A$ has a non-zero diagonal entry.

Answer 2

The matrix $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ in $\mathbb{F}_2^{2 \times 2}$ does not have a decomposition as $BB^T$ for any $B \in \mathbb{F}_2^{2 \times 2}$. Otherwise, the would exist $a,b,c,d \in \mathbb{F}_2$ such that $$a^2+b^2=c^2+d^2=0,~ac+bd=1.$$ However, it follows from $a^2+b^2=c^2+d^2=0$ that $a=b$ and $c=d$ and so $ac+bd=ac+ac=0$.