離散フーリエ変換 (一般)
離散フーリエ変換は線形写像であるから、行列積で表現できる。行列表現では、離散フーリエ変換は以下のように書ける。
[ f 0 f 1 ⋮ f n − 1 ] = [ 1 1 1 ⋯ 1 1 α α 2 ⋯ α n − 1 1 α 2 α 4 ⋯ α 2 ( n − 1 ) ⋮ ⋮ ⋮ ⋮ 1 α n − 1 α 2 ( n − 1 ) ⋯ α ( n − 1 ) ( n − 1 ) ] [ v 0 v 1 ⋮ v n − 1 ] {\displaystyle {\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &&\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}}
この行列は、DFT行列と呼ばれる。
R {\displaystyle R} を任意の環、 n ≥ 1 {\displaystyle n\geq 1} を自然数とする。 α ∈ R {\displaystyle \alpha \in R} を、 R {\displaystyle R} の単位元の主 n {\displaystyle n} 乗根(principal root)であり次式を満たす要素とする
α n = 1 ∑ j = 0 n − 1 α j k = 0 for 1 ≤ k < n ( 1 ) {\displaystyle {\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\qquad (1)\end{aligned}}}
離散フーリエ変換は、 R {\displaystyle R} の要素のn個組 ( v 0 , ... , v n − 1 ) {\displaystyle (v_{0},\ldots ,v_{n-1})} を、次の計算式により R {\displaystyle R} の要素のn個組 ( f 0 , ... , f n − 1 ) {\displaystyle (f_{0},\ldots ,f_{n-1})} へ写像する。
f k = ∑ j = 0 n − 1 v j α j k .