en>ChrisGualtieri: Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB

2013-12-27T03:15:49Z

Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB

New page

{{technical|date=August 2012}}
{{expert|mathematics|date=March 2013}}

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

:<math>\omega = e^{2 \pi i/N}</math>

be the ''N'''th [[root of unity]] or any other root of unity not equal to 1.
:<math>\omega^N = 1,\quad \omega \ne 1</math>.
We consider the following symmetric '''[[Vandermonde matrix]]''':

:<math>\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}
</math>

For example,

:<math>\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}.
</math>

The square of the Fourier transform is the flip permutation matrix:
:<math>\mathbf{F}^2 = \mathbf{P}.</math>

The fourth power of the Fourier transform is the identity:
:<math>\mathbf{F}^4 = \mathbf{I}.</math>

''Exercise'': Proof that for any :<math>1 \le k \le N-1 </math>
:<math>\mathbf{F(\omega^k)} = \mathbf{P}\mathbf{F(\omega)}.</math>

[[Category:Fourier analysis]]

Conditional dependence - Revision history

en>ChrisGualtieri: Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB