Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields

Abstract

It is shown that every symmetric matrix A, with entries from a finite field F, can be factored over F into $A = BB'$, where the number of columns of B is bounded from below by either the rank $\rho (A)$ of A, or by $1 + \rho (A)$, depending on A and on the characteristic of F This result is applied to show that every finite extension $\Phi $ of a finite field F has a trace-orthogonal basis over F. Necessary and sufficient conditions for the existence of a trace-orthonormal basis are also given. All proofs are constructive, and can be utilized to formulate procedures for minimal factorization and basis construction.