Circulant Matrix

An  matrix whose rows are composed of cyclically shifted versions of a length- list . For example, the  circulant matrix on the list  is given by

(1)

Circulant matrices are very useful in digital image processing, and the  circulant matrix is implemented as CirculantMatrix[l, n] in the Mathematica application package Digital Image Processing.

Circulant matrices can be implemented in the Wolfram Language as follows.

  CirculantMatrix[l_List?VectorQ] :=
    NestList[RotateRight, RotateRight[l],
      Length[l] - 1]
  CirculantMatrix[l_List?VectorQ, n_Integer] :=
    NestList[RotateRight,
      RotateRight[Join[Table[0, {n - Length[l]}],
        l]], n - 1] /; n >= Length[l]

where the first input creates a matrix with dimensions equal to the length of  and the second pads with zeros to give an  matrix. A special type of circulant matrix is defined as

(2)

where  is a binomial coefficient. The determinant of  is given by the beautiful formula

(3)

where , , ...,  are the th roots of unity. The determinants for , 2, ..., are given by 1, , 28, , 3751, 0, 6835648, , 364668913756, ... (OEIS A048954), which is 0 when .

Circulant matrices are examples of Latin squares.

REFERENCES:

Davis, P. J. Circulant Matrices, 2nd ed. New York: Chelsea, 1994.

Sloane, N. J. A. Sequences A048954 and A049287 in "The On-Line Encyclopedia of Integer Sequences."

Stroeker, R. J. "Brocard Points, Circulant Matrices, and Descartes' Folium." Math. Mag. 61, 172-187, 1988.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, p. 114, 1991.