# Fourier coordinates

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