An n × n circulant matrix has the form

in which the entries of each succeeding row are obtained by moving all the previous row's entries one slot to the right, the last entry moving to the front.
(a) Check that the shift matrix S of Exercise 8.2.13, the difference matrix ˆ†, and its symmetric product K of Exercise 8.4.12 are all circulant matrices.
(b) Prove that the sampled exponential vectors w0, ...,wn-1, (5.90) are eigenvectors of C. Thus, all circulant matrices have the same eigenvectors! What are the eigenvalues?
(c) Prove that Fn-1C Fn = Λ where Fn is the Fourier matrix in Exercise 5.7.9 and A is the diagonal matrix with the eigenvalues of C along the diagonal.
(d) Find the eigenvalues and eigenvectors of the following circulant matrices:

(e) Find the eigenvalues of the tricirculant matrices in Exercise 1.7.13. Can you find a general formula for the n × n version? Explain why the eigenvalues must be real and positive. Does your formula reflect this fact?
(f) Which of the preceding matrices are invertible? Write down a general criterion for checking the invertibility of circulant matrices.

Cn-l Co Cl C2 C3 Cn-1 Co C C CO Ci CzC3C4 321 213 132 11-11012 1111 0121 2 11112101 2