Last modified on 27 October 2012, at 22:20

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.