実離散フーリエ変換(中編)-離散三角関数の直交性-

$0<\left|{\displaystyle \frac{m}{N}}\right|<1$より$\exp \left(i{\displaystyle \frac{m}{N}}\tau \right)\ne 1$となるから
$$\begin{array}{rl}\sum _{n=0}^{N-1}\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right)& ={\displaystyle \frac{1-\exp \left(i{\displaystyle \frac{1}{N}}N\tau \right)}{1-\exp \left(i{\displaystyle \frac{m}{N}}\tau \right)}}\\ & ={\displaystyle \frac{1-1}{1-\exp \left(i{\displaystyle \frac{m}{N}}\tau \right)}}\\ & =0\\ \sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{m}{N}}n\tau \right)& =\mathrm{Re}(\sum _{n=0}^{N-1}\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right))\\ & =0\\ \sum _{n=0}^{N-1}\sin \left({\displaystyle \frac{m}{N}}n\tau \right)& =\mathrm{Im}(\sum _{n=0}^{N-1}\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right))\\ & =0\end{array}$$

行列$A$を角度${\displaystyle \frac{m}{N}}\tau$の2次元回転行列とする。
$$\begin{array}{r}A=\left[\begin{array}{cc}\cos \left({\displaystyle \frac{m}{N}}\tau \right)& -\sin \left({\displaystyle \frac{m}{N}}\tau \right)\\ \sin \left({\displaystyle \frac{m}{N}}\tau \right)& \cos \left({\displaystyle \frac{m}{N}}\tau \right)\end{array}\right]\end{array}$$
行列を$n$回かけることは${\displaystyle \frac{m}{N}}n\tau$回転することを意味するから
$$\begin{array}{r}{A}^n=\left[\begin{array}{cc}\cos \left({\displaystyle \frac{m}{N}}n\tau \right)& -\sin \left({\displaystyle \frac{m}{N}}n\tau \right)\\ \sin \left({\displaystyle \frac{m}{N}}n\tau \right)& \cos \left({\displaystyle \frac{m}{N}}n\tau \right)\end{array}\right]\end{array}$$
(数学的帰納法によって示すこともできる。)
また、
$$\begin{array}{rl}\det (I-A)& ={(1-\cos \left({\displaystyle \frac{m}{N}}\tau \right))}^2+{\sin }^2({\displaystyle \frac{m}{N}}\tau )\\ & =1-2\cos \left({\displaystyle \frac{m}{N}}\tau \right)+{\cos }^2({\displaystyle \frac{m}{N}}n\tau )+{\sin }^2({\displaystyle \frac{m}{N}}\tau )\\ & =2-2\cos \left({\displaystyle \frac{m}{N}}\tau \right)\end{array}$$
$0<\left|{\displaystyle \frac{m}{N}}\right|<1$より$\cos \left({\displaystyle \frac{m}{N}}\tau \right)\ne 1$となるから$\det (I-A)\ne 0$
つまり$(I-A{)}^{-1}$が存在する。よって、
$$\begin{array}{rl}\sum _{n=0}^{N-1}{A}^n& =(1-A^N)(1-A{)}^{-1}\\ & =\left[\begin{array}{cc}1-\cos \left(n\tau \right)& -\sin \left(n\tau \right)\\ \sin \left(n\tau \right)& 1-\cos \left(n\tau \right)\end{array}\right](1-A{)}^{-1}\\ & =\left[\begin{array}{cc}1-1& 0\\ 0& 1-1\end{array}\right](1-A{)}^{-1}\\ & =\left[\begin{array}{cc}0& 0\\ 0& 0\end{array}\right]\\ \sum _{n=0}^{N-1}{A}^n& =\left[\begin{array}{cc}{\displaystyle \sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{m}{N}}n\tau \right)}& {\displaystyle -\sum _{n=0}^{N-1}\sin \left({\displaystyle \frac{m}{N}}n\tau \right)}\\ {\displaystyle \sum _{n=0}^{N-1}\sin \left({\displaystyle \frac{m}{N}}n\tau \right)}& {\displaystyle \sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{m}{N}}n\tau \right)}\end{array}\right]\end{array}$$
したがって、
$$\begin{array}{r}\sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{m}{N}}n\tau \right)=\sum _{n=0}^{N-1}\sin \left({\displaystyle \frac{m}{N}}n\tau \right)=0\end{array}$$

まずコサインの総和を示す。

積和の公式
$$\begin{array}{rl}\cos \alpha \sin \beta & =\frac{1}{2}(\sin (\alpha +\beta )-\sin (\alpha -\beta ))\end{array}$$
より、
$\theta ={\displaystyle \frac{m}{N}}\tau ,\alpha =n\theta ,\beta ={\displaystyle \frac{\theta }{2}},I_n=\cos \left(n\theta \right)\sin \left({\displaystyle \frac{\theta }{2}}\right)$とすると、

$$\begin{array}{rl}{I}_n& =\cos \left(n\theta \right)\sin \left({\displaystyle \frac{\theta }{2}}\right)\\ & =\frac{1}{2}(\sin (n\theta +\frac{\theta }{2})-\sin (n\theta -\frac{\theta }{2}))\end{array}$$
よって、
$$\begin{array}{rl}2\sum _{n=0}^{N-1}{I}_n& =\sum _{n=0}^{N-1}(\sin (n\theta +\frac{\theta }{2})-\sin (n\theta -\frac{\theta }{2}))\\ & =-\sin (-\frac{\theta }{2})+\sum _{n=1}^{N-1}(\sin ((n-1)\theta +\frac{\theta }{2})-\sin (n\theta -\frac{\theta }{2}))\\ & +\sin ((N-1)\theta +\frac{\theta }{2})\\ & =\sin (N\theta -\frac{\theta }{2})+\sin \left(\frac{\theta }{2}\right)\\ & =\sin (N{\displaystyle \frac{m}{N}}\tau -\frac{\theta }{2})+\sin \left(\frac{\theta }{2}\right)\\ & =-\sin \left(\frac{\theta }{2}\right)+\sin \left(\frac{\theta }{2}\right)\\ & =0\end{array}$$
一方で
$$\begin{array}{rl}\sum _{n=0}^{N-1}{I}_n& =\sin \left({\displaystyle \frac{\theta }{2}}\right)\sum _{n=0}^{N-1}\cos \left(n\theta \right)\end{array}$$
仮定$1\le \left|m\right|<N$より$0<\left|{\displaystyle \frac{\theta }{2}}\right|=\left|{\displaystyle \frac{m}{2N}}\tau \right|<{\displaystyle \frac{\tau }{2}}$となるから$\sin \left({\displaystyle \frac{\theta }{2}}\right)\ne 0$
よって、
$$\begin{array}{r}\sum _{n=0}^{N-1}\cos \left(n\theta \right)=\sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{m}{N}}n\tau \right)=0\end{array}$$

次にサインの総和を示す。

積和の公式
$$\begin{array}{rl}\sin \alpha \sin \beta & =\frac{1}{2}(-\cos (\alpha +\beta )+\cos (\alpha -\beta ))\end{array}$$
より、
$\theta ={\displaystyle \frac{m}{N}}\tau ,\alpha =n\theta ,\beta ={\displaystyle \frac{\theta }{2}},J_n=\sin \left(n\theta \right)\sin \left({\displaystyle \frac{\theta }{2}}\right)$とすると、

$$\begin{array}{rl}{J}_n& =\sin \left(n\theta \right)\sin \left({\displaystyle \frac{\theta }{2}}\right)\\ & =\frac{1}{2}(-\cos (n\theta +\frac{\theta }{2})+\cos (n\theta -\frac{\theta }{2}))\end{array}$$
よって、
$$\begin{array}{rl}2\sum _{n=0}^{N-1}{J}_n& =\sum _{n=0}^{N-1}(-\cos (n\theta +\frac{\theta }{2})+\cos (n\theta -\frac{\theta }{2}))\\ & =\cos (-\frac{\theta }{2})+\sum _{n=1}^{N-1}(\cos ((n-1)\theta +\frac{\theta }{2})-\cos (n\theta -\frac{\theta }{2}))\\ & -\cos ((N-1)\theta +\frac{\theta }{2})\\ & =\cos \left(\frac{\theta }{2}\right)-\cos (N\theta -\frac{\theta }{2})\\ & =\cos \left(\frac{\theta }{2}\right)-\cos (N{\displaystyle \frac{m}{N}}\tau -\frac{\theta }{2})\\ & =\cos \left(\frac{\theta }{2}\right)-\cos \left(\frac{\theta }{2}\right)\\ & =0\end{array}$$
一方で
$$\begin{array}{rl}\sum _{n=0}^{N-1}{J}_n& =\sin \left({\displaystyle \frac{\theta }{2}}\right)\sum _{n=0}^{N-1}\sin \left(n\theta \right)\end{array}$$
仮定$1\le \left|m\right|<N$より$0<\left|{\displaystyle \frac{\theta }{2}}\right|=\left|{\displaystyle \frac{m}{2N}}\tau \right|<{\displaystyle \frac{\tau }{2}}$となるから$\sin \left({\displaystyle \frac{\theta }{2}}\right)\ne 0$
よって、
$$\begin{array}{r}\sum _{n=0}^{N-1}\sin \left(n\theta \right)=\sum _{n=0}^{N-1}\sin \left({\displaystyle \frac{m}{N}}n\tau \right)=0\end{array}$$

• $\cos$どうしの内積
  $j,k$を$0\le j,k\le {\displaystyle \frac{N}{2}}$となる整数とする。
  $$\begin{array}{rl}{\mathbf{c}}_j\cdot {\mathbf{c}}_k& =\sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{j}{N}}n\tau \right)\cos \left({\displaystyle \frac{k}{N}}n\tau \right)\\ & =\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}(\cos \left({\displaystyle \frac{j+k}{N}}n\tau \right)+\cos \left({\displaystyle \frac{j-k}{N}}n\tau \right))\end{array}$$
  • $j\ne k$のとき
    $1\le |j+k|\le N-2,1\le |j-k|\le {\displaystyle \frac{N-1}{2}}$より前編の補題3から
    $$\begin{array}{rl}{\mathbf{c}}_j\cdot {\mathbf{c}}_k& =0\end{array}$$
  • $j=k$のとき
    $j-k=0$より
    $$\begin{array}{rl}{\mathbf{c}}_j\cdot {\mathbf{c}}_k& =\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}(\cos \left({\displaystyle \frac{j+k}{N}}n\tau \right)+\cos 0)\\ & ={\displaystyle \frac{N}{2}}+\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}\cos \left({\displaystyle \frac{j+k}{N}}n\tau \right)\end{array}$$
    • $j=k=0$のとき
      $j+k=0$より
      $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{c}}_k={\displaystyle \frac{N}{2}}+\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}\cos 0=N\end{array}$$
    • $0<j=k<\frac{N}{2}$のとき
      $0<|j+k|<N$より補題3から
      $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{c}}_k={\displaystyle \frac{N}{2}}\end{array}$$
    • $j=k=\frac{N}{2}$のとき
      $j+k=N$より
      $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{c}}_k={\displaystyle \frac{N}{2}}+\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}\cos \left(n\tau \right)=N\end{array}$$

• $\sin$どうしの内積
  $j,k$を$1\le j,k\le {\displaystyle \frac{N-1}{2}}$となる整数とする。
  $$\begin{array}{rl}{\mathbf{s}}_j\cdot {\mathbf{s}}_k& =\sum _{n=0}^{N-1}\sin \left({\displaystyle \frac{j}{N}}n\tau \right)\sin \left({\displaystyle \frac{k}{N}}n\tau \right)\\ & =-\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}(\cos \left({\displaystyle \frac{j+k}{N}}n\tau \right)-\cos \left({\displaystyle \frac{j-k}{N}}n\tau \right))\end{array}$$
  • $j\ne k$のとき
    $1\le |j+k|\le N-2,1\le |j-k|\le {\displaystyle \frac{N-1}{2}}-1$より補題3から
    ${\mathbf{s}}_j\cdot {\mathbf{s}}_k=0$
  • $j=k$のとき
    $2\le |j+k|\le N-1,j-k=0$より補題3から
    $$\begin{array}{r}{\mathbf{s}}_j\cdot {\mathbf{s}}_k=-\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}(-\cos 0)={\displaystyle \frac{N}{2}}\end{array}$$

• $\cos$と$\sin$の内積
  $j$を$0\le j\le {\displaystyle \frac{N}{2}}$、$k$を$1\le k\le {\displaystyle \frac{N-1}{2}}$となる整数とする。
  $$\begin{array}{rl}{\mathbf{c}}_j\cdot {\mathbf{s}}_k& =\sum _{n=0}^{N-1}\cos \left({\displaystyle \frac{j}{N}}n\tau \right)\sin \left({\displaystyle \frac{k}{N}}n\tau \right)\\ & =\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}(\sin \left({\displaystyle \frac{j+k}{N}}n\tau \right)-\sin \left({\displaystyle \frac{j-k}{N}}n\tau \right))\end{array}$$
  • $j\ne k$のとき
    $1\le |j+k|\le N-{\displaystyle \frac{1}{2}},1\le |j-k|\le {\displaystyle \frac{N}{2}}$より補題3から
    $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{s}}_k=0\end{array}$$
  • $j=k$のとき
    $1\le |j+k|\le N-1,j-k=0$より補題3から
    $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{s}}_k=\sum _{n=0}^{N-1}{\displaystyle \frac{1}{2}}\sin 0=0\end{array}$$
    内積は可換であるため、${\mathbf{s}}_j\cdot {\mathbf{c}}_k={\mathbf{c}}_k\cdot {\mathbf{s}}_j=0$

• まとめ
  • $j$を$0\le j\le {\displaystyle \frac{N}{2}}$、$k$を$0\le k\le {\displaystyle \frac{N}{2}}$となる整数とすると
    $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{c}}_k=\{\begin{array}{ll}0& (j\ne k)\\ N& (j=k=0,j=k={\displaystyle \frac{N}{2}})\\ {\displaystyle \frac{N}{2}}& (0<j=k<{\displaystyle \frac{N}{2}})\end{array}\end{array}$$
  • $j$を$1\le j\le {\displaystyle \frac{N-1}{2}}$、$k$を$1\le k\le {\displaystyle \frac{N-1}{2}}$となる整数とすると
    $$\begin{array}{r}{\mathbf{s}}_j\cdot {\mathbf{s}}_k=\{\begin{array}{ll}0& (j\ne k)\\ {\displaystyle \frac{N}{2}}& (j=k=0)\end{array}\end{array}$$
  • $j$を$0\le j\le {\displaystyle \frac{N}{2}}$、$k$を$1\le k\le {\displaystyle \frac{N-1}{2}}$となる整数とすると
    $$\begin{array}{r}{\mathbf{c}}_j\cdot {\mathbf{s}}_k=0\end{array}$$

$N$が奇数の時
$$\begin{array}{r}{E}^{\prime }=\{{\mathbf{c}}_0,{\mathbf{c}}_1,{\mathbf{s}}_1,\cdots ,{\mathbf{c}}_{(N-1)/2},{\mathbf{s}}_{(N-1)/2}\}\end{array}$$
はそれぞれ自身以外との内積が0となるため直交系となる。

$N$が偶数の時
$$\begin{array}{r}{E}^{\prime }=\{{\mathbf{c}}_0,{\mathbf{c}}_1,{\mathbf{s}}_1,\cdots ,{\mathbf{c}}_{N/2-1},{\mathbf{s}}_{N/2-1},{\mathbf{c}}_{N/2}\}\end{array}$$
はそれぞれ自身以外との内積が0となるため直交系となる。

つまり$E^{\prime }$ は直交系となる。
また、$E$ はそれに加えて各ノルムが$1$となるため正規直交系となる。

命題2より$E^{\prime }$は直交系であり、$E$は正規直交系である。
また前編の命題7「$N$個の$N$次ベクトルは互いに直交するなら$N$次ベクトル空間の基底になる。」より、$E^{\prime }$は直交系かつ基底であり、$E$は正規直交系かつ基底である。