Remember the examples, where you had to find the eigenvalues and eigenvectors of a circular
matrix like
A= 0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0

This matrix has as the eigenvalues the roots of the characteristic polynomial det(Ax) = x^{10}1. These roots
are called roots of unity.
We have computed also the eigenvectors. If e(k) = exp(2Pi i k/10) are the eigenvalues, then the eigenvectors
the columns of the matrix (remember the multiplication table)

The matrix S diagonalizing a circular matrix. Click for a larger picture.

S = 1 1 1 1 1 1 1 1 1 1
e(1) e(2) e(3) e(4) e(5) e(6) e(7) e(8) e(9) e(10)
e(2) e(4) e(6) e(8) e(10) e(12) e(14) e(16) e(18) e(20)
e(3) e(6) e(9) e(12) e(15) e(18) e(21) e(24) e(27) e(30)
e(4) e(8) e(12) e(16) e(20) e(24) e(28) e(32) e(36) e(40)
e(5) e(10) e(15) e(20) e(25) e(30) e(35) e(40) e(45) e(50)
e(6) e(12) e(18) e(24) e(30) e(36) e(42) e(48) e(54) e(60)
e(7) e(14) e(21) e(28) e(35) e(42) e(49) e(56) e(63) e(70)
e(8) e(16) e(24) e(32) e(40) e(48) e(56) e(64) e(72) e(80)
e(9) e(18) e(27) e(36) e(45) e(60) e(63) e(72) e(81) e(90)
/sqrt(10)

We divided by sqrt(10) so that each column has length one and so that they form an orthonormal eigen basis
of the matrix A. The matrix S produces a transformation which is called the
discrete Fourier transform
here in the case n=10.
It is important in signal processing, sound and image manipulation and compression. Note as in midterm practice problems
or homework used frequently that because A is orthogonal, S also diagonalizes A
^{T} = A
^{1} and
so L = A+A
^{T}2 which is a discretization of the second derivative D
^{2}.
In the same way as Fourier series diagonalized D
^{2}, the discrete Fourier transform diagonalizes the discrete
second derivative L. The eigenvalues are e(k) + e(k)  2 = 2 cos(2Pi k/10)  2.
A[n_]:= Table[ If[Mod[ji,n]==1,1,0],{i,n},{j,n}]
S[n_]:= Table[ Exp[ 2Pi I (i1) (j1)/n],{i,n},{j,n}]/Sqrt[n];
Chop[N[Conjugate[Transpose[S[10]]].A[10].S[10]]]