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!

  • 1
    $\begingroup$ I'm a bit curious as to what you want to do with this :-) I used the Seroussi&Lempel algorithm as a step in a decoding algorithm I cooked up for the self-dual McGuire-Calderbank code of length $32$ over $\Bbb{Z}_4$. The algorithm wasn't too hot, so I never bothered publishing it in forms other than a symposium abstract. It earned me a trip to Southern Italy though :-) $\endgroup$ – Jyrki Lahtonen Aug 22 '18 at 11:05

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.

  • $\begingroup$ Dear @Jyrki, Thanks for the detailed response. I did come across the paper by Lempel, but it seems like I am more interested in the case where $A$ is non-symmetric and has a zero diagonal. Do you have any refernces for this case? $\endgroup$ – wwjohnsmith Aug 23 '18 at 10:05
  • 1
    $\begingroup$ @wwjohnsmith Any matrix of the form $BB^T$ is automatically symmetric. Recall that the transpose of a product is the product of transposes in reverse order: $(CD)^T=D^TC^T$ for all matrices $C,D$ of compatible types. Consequently $(BB^T)^T=(B^T)^TB^T=BB^T$, so $BB^T$ is equal to its own transpose irrespective of what $B$ was. $\endgroup$ – Jyrki Lahtonen Aug 23 '18 at 12:20

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$.

  • $\begingroup$ If we enforce $A$ is non-symmetric with zero diagonal, could you come up with counterexamples for a factorization of the form $A=BB^T$? I'll accept your answer after that. Thanks! $\endgroup$ – wwjohnsmith Aug 21 '18 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.