Circulants, linear recurrences and codes

Abstract. We shall give some intriguing applications of the theory of circulants — the circulant matrices — and that of linear recurrence sequences (LRS). The applications of the former in §2 ranges from a simple derivation of the Blahut theorem to the energy levels of hydrogen atoms in circular hydrocarbons, where the Blahut theorem is to the effect that the Hamming weight of a code is equal to the rank of the associated Fourier matrix. The latter in §3 is connected to the understanding of an LFSR (linear feedback shift register) as an LRS, and culminates to a corollary asserting that the linear complexity of the periodically repeated sequence is equal to the rank of the DFT matrix, revealing the relationship between Blahut's and Massey's formulations. At the end of §3 we give a proof of Blahut's theorem by Massey's theorem. We also mention other relevance of circulants to the hydrocarbons and class numbers of cyclotomic fields in §4. This constitutes a companion paper to [8] and deals with more concrete cases.