Eigenvectors of the Fourier matrix

Question

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. $$

Answer 1

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.

Answer 2

There is full and simple description of all eigenvectors in the article

Morton, P. On the eigenvectors of Schur's matrix. J. Number Theory, 1980, 12, 122-127 http://deepblue.lib.umich.edu/bitstream/2027.42/23371/1/0000315.pdf

Answer 3

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$

Answer 4

There are several known eigenvector basis for the DFT using matrices that commute with the DFT matrix:

1. Alberto Grunbaum (Tridiagonal Commuting matrix), Journal of Mathematical Analysis and Applications, 1982.
2. B. Santhanam and T. S. Santhanam (quantum mechanics in finite dimensions)(Symmetric matrix), Signal Processing, Elsevier, 2008.
3. Steiglitz and Dickinson (S matrix approach) (Almost tridiagonal), IEEE Transactions on Signal Processing, Feb. 1982.