5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$ Nov 10, 2012 at 21:08
  • $\begingroup$ 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 $\endgroup$ Nov 10, 2012 at 21:53

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
0
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.