Is it possible to link the eigenvalues of a matrix to the Fourier transform of the matrix? I'm trying to get insight into the eigenvalue spectrum of a square matrix (large N, symmetric, positive semi-definite matrix) using Fourier transforms (I've tried transforming a bunch of things: the diagonal, the skew diagonal, the entire matrix, each eigenvector, etc. . Is there anything I should be looking at specifically?
 A: I know of a couple of results for certain special types of matrices.
1) If you have a circulant matrix, the eigenvalues of that matrix will be the discrete Fourier transform of the first row of the circulant matrix.
2) For the second one I don't remember all the technical details. Suppose you have a symmetric Toeplitz matrix whose size goes to infinity, certain functions of the eigenvalues can be written in terms of the Fourier transform of the first row of the matrix. In fact, the expression is written as a Riemann sum, which becomes a Riemann integral in the Fourier domain. In other words, you can write an unwieldy expression involving the eigenvalues of this growing matrix in terms of an integral which is usually much easier to evaluate.
If you want to learn more, check out Robert Gray's notes at http://ee.stanford.edu/~gray/toeplitz.pdf for an introduction to these kinds of results. 
There is also the book by Grenander and Szego which gives a lot more detail and proves some more general results here 
http://books.google.com/books?id=CFhVdL78wGcC&printsec=frontcover&dq=toeplitz+forms&hl=en&ei=CudxTf_XFtL1gAfH9qRV&sa=X&oi=book_result&ct=result&resnum=1&ved=0CDQQ6AEwAA#v=onepage&q&f=false
