On 2D Inverse Problems/Fourier coordinates

From Wikibooks, open books for an open world
Jump to: navigation, search
Let \omega be a not unit N'th root of unity, i.e. \omega^N = 1, \omega \ne 1.

The discrete Fourier transform 's given by the symmetric Vandermonde matrix:
F_\omega =
\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,
F_{e^{2\pi i/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}.
Exercise (*). The square of the Fourier transform is the identity transform:
F_N^2 = Id.
Exercise (*). If an e-network is rotation invariant, then so 's the conductivity equation and the Dirichlet-to-Neumann map is diagonal in the Fourier coordinates (the column vectors of the matrix.