circulant matrix

A square matrix $M:A\\times A\\to C$ is said to be $g$ -circulant for an integer $g$ if each row other than the first is obtainedfrom the preceding row by shifting the elements cyclically g columns to the right (g¿0) or -g columns to the left (g ¡ 0).

That is, if $A=[a_{ij}]$ then $a_{i,j}=a_{i+1,j+g}$ where the subscripts are computed modulo d.A 1-circulant is commonly called a circulantand a -1-circulant is called a back circulant.

More explicitly, a matrix of the form

\\left[\\begin{array}[]{ccccc}M_{1}&M_{2}&M_{3}&\\ldots&M_{d}\\\\M_{d}&M_{1}&M_{2}&\\ldots&M_{d-1}\\\\M_{d-1}&M_{d}&M_{1}&\\ldots&M_{d-2}\\\\\\vdots&\\vdots&\\vdots&\\ddots&\\vdots\\\\M_{2}&M_{3}&M_{4}&\\ldots&M_{1}\\end{array}\\right]

is called circulant.

Because the Jordan decomposition (http://planetmath.org/JordanCanonicalFormTheorem) of acirculant matrix is rather simple, circulant matrices have someinterest in connection with the approximation of eigenvalues ofmore general matrices. In particular, they have become part of thestandard apparatus in the computerized analysis of signals and images.