# On 2D Inverse Problems/Fourier coordinates

For an integer N, let $\omega$ be the N'th root of unity, that is not equal to 1.

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

We consider the following symmetric Vandermonde matrix:

$\mathbf{F_N} = \frac{1}{\sqrt{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} = \frac{1}{\sqrt{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} = \frac{1}{\sqrt{5}} \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 forth power of the Fourier transform is the identity:

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

Exercise (**). Proof that if N is a prime number than for any 0 < k < N

$\mathbf{F(\omega^k)} = \mathbf{P}\mathbf{F(\omega)}\mathbf{P}^T$,

where P is a cyclic permutation matrix.

Exercise (*). If a network is rotation invariant then its Dirichlet-to-Neumann operator is diagonal in Fourier coordinates. (Hint) The harmonic functions commute w/rotation.