Skip to main content
1 of 2
bobuhito
  • 1.5k
  • 11
  • 19

The Discrete Fourier Transform's Gaussian-Like Eigenvector

I have the $N$x$N$ matrix below where $N$ is a power of 2 (usually 64 or 256) and $\omega = 2\pi/N$. What is its largest eigenvalue?

$\begin{bmatrix} 2 & 1 & 0 & 0 & \cdots & 0 & 0 & 1\\ 1 & 2cos(\omega) & 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 & 2cos(2\omega) & 1 & \cdots & 0 & 0 & 0\\ 0 & 0 & 1 & 2cos(3\omega) & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 2cos((N-3)\omega) & 1 & 0\\ 0 & 0 & 0 & 0 & \cdots & 1 & 2cos((N-2)\omega) & 1\\ 1 & 0 & 0 & 0 & \cdots & 0 & 1 & 2cos((N-1)\omega) \end{bmatrix}$

This is exactly the $S$ matrix here (which explains how this eigenvector is also the simplest eigenvector of the Discrete Fourier Transform); I am wondering if our analysis of this eigenvector has improved since 1982.

For large $N$, I know this eigenvalue tends to 4 and its eigenvector tends to a Gaussian, and I can numerically find the roots of the characteristic polynomial for more precision (e.g., this eigenvalue is 3.903025 for $N$=64), but is there a faster more-accurate method? Is there a closed-form solution?

To reiterate, the helpful points here are that $N$ is a power of 2 and I am only concerned with the highest eigenvalue.

bobuhito
  • 1.5k
  • 11
  • 19