You are not logged in.
#1 2009-04-24 21:55:17
- dannyv
- Member
Offline
Discrete Fourier Transform
Can somebody tell me what is the process to calculate the eigenvalues of the discrete fourier transform matrix? Or a reference would be good also. thanks!!
#2 2009-04-25 10:17:13
- bobbym
- Administrator
Offline
Re: Discrete Fourier Transform
Hi dannyv;
As far as I can remember the eigenvalues for those matrices are taken from the set of the roots of unity, solutions of z^n-1=0 where n is the size of the matrix. I think there is an easy way to determine how many of each by n modulo 4. I might be mistaken, its been a long time since I have worked with a DFT or FFT. Google will probably provide what you need.
Last edited by bobbym (2009-04-25 10:18:20)
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#3 2009-04-25 13:13:13
- dannyv
- Member
Offline
Re: Discrete Fourier Transform
I found this wikipedia page http://en.wikipedia.org/wiki/Discrete_Fourier_transform that gives a really good and correct definitions and properties of the DFT. It also gives the eigenvalues but doesn't tell exactly how to find them. This is a quote from the page:
Consider the unitary form
This can be seen from the inverse properties above: operating twice gives the original data in reverse order, so operating four times gives back the original data and is thus the identity matrix. This means that the eigenvalues satisfy a characteristic equation:
Therefore, the eigenvalues of are the four roots of unity: is +1, -1, +i, -i
What is not clear form me is why is the characteristic equation . How can I derive this algebraically? Also, how do I calculate the multiplicity of these eigenvalues? The calculation of the multiplicities is given in this paper "J. H. McClellan and T. W. Parks (1972). "Eigenvalues and eigenvectors of the discrete Fourier transformation". IEEE Trans. Audio Electroacoust. 20 (1): 66–74" (http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1162342), but my university doesn't have access to this paper, so I haven't read this yet.
In summary my questions are as follows:
1) How to derive algebraically the characteristic equation
2) How to calculate the multiplicity of the eigenvalues
3) What is a good alternate reference for this paper
Thanks in advanced!!!
#4 2009-04-25 18:06:07
- bobbym
- Administrator
Offline
Re: Discrete Fourier Transform
Hi dannyv;
From my notes I can answer question 2:
If n is of the form 4m then the eigenvalues are:
m+1 eigenvalues that equal 1
m eigenvalues that equal -1
m eigenvalues that equal -i
m-1 eigenvalues that equal i
If n is of the form 4m+1 then the eigenvalues are:
m+1 eigenvalues that equal 1
m eigenvalues that equal -1
m eigenvalues that equal -i
m eigenvalues that equal i
If n is of the form 4m+2 then the eigenvalues are:
m+1 eigenvalues that equal 1
m+1 eigenvalues that equal -1
m eigenvalues that equal -i
m eigenvalues that equal i
If n is of the form 4m+3 then the eigenvalues are:
m+1 eigenvalues that equal 1
m+1 eigenvalues that equal -1
m+1 eigenvalues that equal -i
m eigenvalues that equal i
Unfortunately my notes are sketchy on deriving the characteristic eqtn (your question #1). So do yourself a favor and keep good notes, don't be like me. Try google for DFT and eigenvalues that may turn up an alternate reference.
In mathematics, you don't understand things. You just get used to them.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.