# Fourier matrix - multiplicity of eigenvalues?

This question is Miscellaneous Exercise M.10 in Chapter 8 (Bilinear Forms) of Artin's Algebra. (The sentences in italics are due to me.)

The row and column indices in the $n \times n$ Fourier matrix $A$ run from $0$ to $n-1$, and the $i, j$ entry is $n^{-1/2}\;\zeta^{ij}$, with $\zeta = e^{2 \pi i / n} \;$. (The author defined the matrix as $[\zeta^{ij}]$; I added the $n^{-1/2}$ factor for normalisation purposes.) This matrix solves the following interpolation problem: Given complex numbers $b_0, \ldots, b_{n-1}$, find a complex polynomial $f(t) = c_0 + c_1 t + \cdots + c_{n-1} t^{n-1}$ such that $f(\zeta^{\nu}) = b_{\nu}$.

(a) Explain how the matrix solves the problem.

(b) Prove that $A$ is symmetric and normal, and compute $A^2$.

(c) (This part is marked with a star.) Determine the eigenvalues of $A$. (I presume that we are required to determine the multiplicity of eigenvalues as well.)

My work:

(a) The interpolation problem boils down to solving a linear system $n^{1/2}Ac = b$ with $c = [c_\nu]$ and $b = [b_{\nu}]$. Since $A$ is unitary, the solution is given by $c = n^{-1/2} A^{\ast} b$.

(b) Symmetry is obvious. A routine calculation shows that $A$ is unitary (hence normal). Also, $$A^2_{ij} = \frac{1}{n} \sum_{k} \zeta^{k(i+j)} = \begin{cases} 1, &\text{if } i+j=0 \pmod n, \\ 0, &\text{otherwise.} \end{cases}$$ Thus $A^2$ is a permutation matrix, the permutation corresponding to which sends any index $i$ to the unique index $j$ such that $i + j \equiv 0 \pmod n$. This is a product of disjoint transpositions.

(c) From the above description, it is easy to determine the spectrum of $A^2$: its eigenvalues are $\pm 1$, and the multiplicity of $-1$ is $$\begin{cases} \frac{n-1}{2}, &\text{odd } n, \\ \frac{n}{2} - 1, &\text{even } n. \end{cases}$$ (The corresponding eigenvectors are of the form $e_i + e_j$ and $e_i - e_j$, where $i + j = 0 \pmod n$.)

Now, the eigenvalues of $A$ are in the set $\{ \pm 1, \pm i \}$, but I cannot determine the individual multiplicities. I appreciate any hints.

-
Wikipedia has good info: en.wikipedia.org/wiki/… – leonbloy Apr 10 '12 at 19:53
Thanks for pointing it out, @leonbloy. (I had seen the page, but somehow I had missed this particular section before.) Apparently the solution is not entirely trivial. Unfortunately the cited papers are behind paywall.. – Srivatsan Apr 12 '12 at 10:10
a) sounds about right; note that the Fourier matrix is in fact a special case of a Vandermonde matrix, where you are essentially constructing an interpolating polynomial at the roots of unity. – J. M. Apr 19 '12 at 5:40
– joriki Apr 19 '12 at 5:52