Let C be the n by n circulant matrix whose first row is (2, -1, 0, ..., 0, -1). Give all of its eigenvalues in closed form, and evaluate the smallest nonzero eigenvalue when n = 6.

Let C be the n by n circulant matrix whose first row is (2, -1, 0, ..., 0, -1). Give all of its eigenvalues in closed form, and evaluate the smallest nonzero eigenvalue when n = 6.

Approach: Every circulant matrix is diagonalised by the discrete Fourier basis, so test the vector with entries omega^{jk} where omega is an n-th root of unity and read off the multiplier.

1. The eigenvalues are lambda_k = 2 - 2 cos(2 pi k / n) for k = 0, 1, ..., n-1. A circulant matrix acts as convolution with its first row, so the vector v_k with entries omega^{jk}, omega = e^{2 pi i / n} an n-th root of unity, is an eigenvector in the discrete Fourier basis with multiplier 2 - omega^{k} - omega^{-k} = 2 - 2 cos(2 pi k / n). At n = 6 the eigenvalues are 0, 1, 3, 4, 3, 1, so the smallest nonzero one is 2 - 2 cos(pi/3) = 2 - 1 = 1. The zero at k = 0 is the constant vector, which this discrete Laplacian annihilates.

Follow-up: How does the smallest nonzero eigenvalue behave as n grows, and what does that say about the condition number of this matrix?

Key concepts: circulant matrix, roots of unity, discrete fourier basis, eigenvalues.