Factorization of symmetric circulant matrices in finite fields (Q921087)

Conditions under which a symmetric \(n\times n\) circulant matrix C with entries from a finite field F can be factored over F as \(C=AA'\), A a circulant matrix (called a factor of C) and \(A'\) its transpose, are presented. If the first row of C is given by \((c_ 0,c_ 1,...,c_{n- 1})\), succeeding rows are given by right cyclic shifts. If \(c(x)=\sum c_ ix^ i\) then for the case \((n,p)=1\), \(char(F)=p\), it is shown that C has a circulant factor iff c(1) and, for even n also c(-1), are quadratic residues in F. For the case when \((n,p)>1\) but C nonsingular, conditions are found for C to have a circulant factor using a variation of the Galois-field Fourier transform. For the singular case a general result is established using the notion of Hasse derivatives of the polynomial c(x).