これは何？

ちょっとやってみたら離散フーリエ変換（以下DFT）を代数的に定義できたので嬉しくなって書いただけの記事です。Sageを触って１時間くらいで書いた記事なのでSage自体には詳しく無いです。

Sageの処理系

ソースコード

NthRootOfOne(n) = (-1)^(2/n)
T = 16
w = NthRootOfOne(T)
dft_matrix = Matrix([[w^(f*t) for t in range(0, T)] for f in range(0, T)])
dft_matrix # 表示用の値の評価

NthRootOfOne

$1$の$N$乗根を求める関数です。$1$の$N$乗根とは、ここでは複素数平面上の単位円を$N$分割し、$(1,0i)$を起点として左に進んでいった時の1ピース目の複素数（代数的数）の事です。これを何度も掛けると単位円上を回転して進んでいき、$N$乗した時点で元の場所$(1,0i)$に戻ってきます。

dft_matrixの計算

$w$は$0$を除いた最低の角速度です。ここでは$T=16$と定義しているので、$T$乗すると$(1,0i)$に戻ってきます。例えば$w^2$を$0 \cdots T-1$乗すると単位円をほぼ2回転します。$w^3$の場合はほぼ3回転、$w^4$の場合はほぼ4回転となり、$w^f$の$f$を周波数、$w^f$をその周波数の角速度とみなす事ができます。

DFT行列は単に、周波数毎に角速度$w^f$の$0 \cdots T-1$乗までの点列で$T$次元のベクトルを作り、それを並べて行列にしただけです。

T=4の結果を見てみる

T=16を記事に載せるのはスペース的に無理があったので、わかりやすくT=4の結果を載せます。

[ 1  1  1  1]
[ 1  I -1 -I]
[ 1 -1  1 -1]
[ 1 -I -1  I]

ちゃんと上から直流基底、周波数$1$の基底、周波数$2$の基底、周波数$3$の基底になっています。周波数$3$の基底は一度に$-i$進むので、ちゃんと角速度$i$で逆回転（右回転）している波に見えますね。

結論

多くのDFTの説明はフーリエ変換を周期化、離散化する過程でオイラーの公式なり$\cos$関数や$\sin$関数を導入しますし、δ関数の畳み込みなんかが登場して数学的議論がめちゃくちゃ難しいですが、代数的定義であれば非常にシンプルです。

DFTを代数的に定義すると、$\cos$関数や$\sin$関数は出てきませんし、$\cos$関数や$\sin$関数の超越性がオーバースペックだという事がわかります。

というか、DFTは代数的に定義可能なはずなので、とりあえず理論計算が不要で計算機上で扱えさえすれば良いという人は代数的定義から入るとわかりやすいんじゃないでしょうか？

とりあえずDFTを代数的に定義できたはずですが、代数計算のプロでは無いのでいろいろ教えていただけるとありがたいです。

Sageで離散フーリエ変換を代数的に定義してみた