Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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