# Eigenvectors of the Fourier matrix

Let $n$ be a positive integer. The $n$ by $n$ Fourier matrix may be defined as follows:

$$F^{*} = (1/\sqrt{n}) (w^{(i-1)(j-1)})$$

where

$$w = e^{2 i \pi /n}$$

is the complex $n$-th root of unity with smaller positive argument and $*$ means transpose -conjugate.

It is well known that $F$ is diagonalizable with eigenvalues $1,-1,i,-i$

where $i^2 =-1.$

It is also known that $F$ has real eigenvectors:

COMMENT: (I was unable to got this paper)

McClellan, James H.; Parks, Thomas W. Eigenvalue and eigenvector decomposition of the discrete Fourier transform. IEEE Trans. Audio Electroacoust. AU-20 (1972), no. 1, 66--74. END of COMMENT

QUESTION:

There is some simple manner to get just one of these real eigenvectors.

For example how to get a real vector with an odd number $n=2k+1$ of coordinates and such that

$$F(x) =x.$$

• I am not sure what is your question. How to obtain a paper? Through the interlibrary loan, if your university does not subscribe this journal. If you type "Fourier" and "eigenvectors" on Mathscinet, you get 49 other papers... – Alexandre Eremenko Nov 10 '12 at 21:08
• Sorry, the question is not about getting papers on internet it is in obtaining a real eigenvector of the Fourier matrix. If you have one of these eigenvectos,please answer the question – Luis H Gallardo Nov 10 '12 at 21:53

This has a little number-theoretic content, having to do with real-valued characters modulo $n=2k+1$. For example, for $n=p$ an odd prime number, there are exactly two such functions (up to scalar multiples), the function that is $1$ for non-zero-mod-$p$ inputs, and the quadratic character $\chi$ mod $p$, which is $\chi(0)=0$, $\chi(j)=+1$ for $j$ a square modulo $p$, and $\chi(j)=-1$ for $j$ a non-square mod $p$.
For odd $n=p_1...p_k$ a product of distinct primes, products of the trivial characters and/or the quadratic characters modulo the various $p_i$ are the $2^k$ real-valued eigenvectors for the Fourier matrix.
Modulo higher powers $n=p^m$ of a prime, the non-trivial character $\chi(j)$ still just depends on $j$ mod $p$ and whether it's a square or not, or is $0$, and these can be combined multiplicatively as in the previous example.
The vector $v = (1 - \sqrt{n}, 1, 1, 1, ...)$ is an eigenvector of $F(n)$ with an eigenvalue of -1 for all $n > 2$. To see this, note that the first row of $F(n)$ is $(\frac{1}{\sqrt{n}}, \frac{1}{\sqrt{n}}, \frac{1}{\sqrt{n}}, ...)$. From this is follows trivially that the first element of $F(n).v$ is $-1 + \sqrt{n}$. For all of the other rows of $F(n)$, we know that for a vector of all ones, the results of the row would sum to zero, since the row contains exactly the n roots of unity. Given this, and the fact the the first element of any row is again $\frac{1}{\sqrt{n}}$, if we were to multiply any row of $F(n)$ other than row 1, by the vector $(0,1,1,...)$, the total for a row is always $-\frac{1}{\sqrt{n}}$. Thus, for the vector $v$, we find for any row greater that zero, multiplying the row by $v$ results in $(1 - \sqrt{n})\frac{1}{\sqrt{n}} - \frac{1}{\sqrt{n}} = -1$