Fourier coordinates

From Wikipedia, the free encyclopedia
Jump to: navigation, search

If the given directed graph with boundary is rotation invariant then its hitting matrix is diagonal in Fourier coordinates. Let

\omega = e^{2 \pi i/N}

be the N'th root of unity or any other root of unity not equal to 1.

\omega^N = 1,\quad \omega \ne 1.

We consider the following symmetric Vandermonde matrix:

\mathbf{F}_N =
\begin{bmatrix}
 1     & 1     & 1   & \ldots & 1 \\
 1     & \omega & \omega^2 & \ldots & \omega^{(N-1)} \\
 1     & \omega^2  & \vdots   & \ldots & \omega^{2(N-1)}     \\
 \vdots          & \vdots         & \vdots                   & \ddots & \vdots                       \\
 1 & \omega^{(N-1) } & \omega^{2(N-1)} & \ldots & \omega^{(N-1)^2} \\
\end{bmatrix}

For example,

\mathbf{F}_5 =
\begin{bmatrix}
 1     & 1         & 1        & 1 & 1 \\
 1     & \omega    & \omega^2 & \omega^3 & \omega^4 \\
 1     & \omega^2  & \omega^4 & \omega^6 & \omega^8 \\
 1     & \omega^3  & \omega^6 & \omega^9 & \omega^{12} \\
 1     & \omega^4  & \omega^8 & \omega^{12} & \omega^{16} \\
\end{bmatrix}
 = 
\begin{bmatrix}
 1     & 1         & 1        & 1 & 1 \\
 1     & \omega    & \omega^2 & \omega^3 & \omega^4 \\
 1     & \omega^2  & \omega^4 & \omega & \omega^3 \\
 1     & \omega^3  & \omega & \omega^4 & \omega^2 \\
 1     & \omega^4  & \omega^3 & \omega^2 & \omega \\
\end{bmatrix}.

The square of the Fourier transform is the flip permutation matrix:

\mathbf{F}^2 = \mathbf{P}.

The fourth power of the Fourier transform is the identity:

\mathbf{F}^4 = \mathbf{I}.

Exercise: Proof that for any :1 \le k \le N-1

\mathbf{F(\omega^k)} = \mathbf{P}\mathbf{F(\omega)}.