Matrix Factorization over $GF(2)$ and Trace-Orthogonal Bases of $GF(2^n )$

Abstract

The main result of this paper is a theorem showing that every binary, symmetric matrix A can be factored over $GF(2)$ into $A = BB'$, where the number of columns of B is bounded from below by either the rank $\rho (A)$ of A, or by $\rho (A) + 1$, depending on whether at least one, or none, of the main-diagonal entries of A is nonzero. An algorithm for a minimal factorization of a given matrix A and an application of this result for finding a trace-orthogonal basis of $GF(2^n )$ are presented.