正規化した DFT の固有値と重複度

正規化した DFT $F$ について、 $F^{2}$ が添字の反転 $n \mapsto - n$ であり、 $F^{4} = I$ から対角化可能であることを使える。 $tr F$ （二次ガウス和を $N$ で割ったもの）、 $tr F^{2}$ （反転の固定点の個数。 $N$ が奇数なら 1、偶数なら 2）、 $tr F^{3} = tr F$ と $m_{1} + m_{- 1} + m_{i} + m_{- i} = N$ の連立方程式を解いて、固有値 $\pm 1, \pm i$ の重複度を求められる

前提

二次ガウス和の値（大学院数学フーリエ解析）
対角化と行列の累乗（大学数学線形代数）

この技能までの道筋（73 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
極形式と積・商（数学C 複素数平面）
ド・モアブルの定理（数学C 複素数平面）
方程式 $z^{n} = a$ の解（数学C 複素数平面）
$1 + cos θ + i sin θ$ の極形式（数学C 複素数平面）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
複素数平面と絶対値・共役複素数（数学C 複素数平面）
3 次式までの展開と因数分解（数学I 数と式）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
$z^{n} = a$ の解を使った和と積（数学C 複素数平面）
（等差）×（等比）の数列の和（数学B 数列）
離散フーリエ変換の計算と逆変換（大学院数学フーリエ解析）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
二次ガウス和の値（大学院数学フーリエ解析）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）

説明

長さ $N$ の正規化した DFT は $N$ 次の行列 $F$ で表せますが、その固有値は $1, - 1, i, - i$ の 4 つしかありません。この技能では、 $F$ の固有値それぞれが何回現れるか（重複度）を、固有ベクトルを 1 本も求めずに、 $F, F^{2}, F^{3}, F^{4}$ のトレースだけから決めます。トレースは二次ガウス和と「反転の固定点の個数」で計算できるので、どんな $N$ でも連立 1 次方程式を解くだけで重複度が出ます。

なぜそうしてよいのか

添字を $0, 1, \dots, N - 1$ （ $mod N$ で考える）とし、 $ω = e^{2 π i / N}$ 、 $F_{j k} = \frac{1}{N} ω^{- j k}$ とします。 $(F^{2} x)_{j} = \sum_{l} x_{l} \cdot \frac{1}{N} \sum_{k = 0}^{N - 1} ω^{- k (j + l)}$ で、内側の和は $j + l \equiv 0 (mod N)$ のとき $N$ 、それ以外は等比数列の和で $0$ です。よって $(F^{2} x)_{j} = x_{- j}$ 、つまり $F^{2}$ は添字の反転 $n \mapsto - n$ です。反転を 2 回行えばもとに戻るので $F^{4} = I$ です。したがって $F v = λ v$ （ $v \neq = 0$ ）なら $v = F^{4} v = λ^{4} v$ から $λ^{4} = 1$ 、固有値は $1, - 1, i, - i$ のどれかです。

さらに $F$ は対角化できます。 $λ \in {1, - 1, i, - i}$ に対し $P_{λ} = \frac{1}{4} \sum_{k = 0}^{3} λ^{- k} F^{k}$ とおくと、 $F^{4} = I$ と $λ^{4} = 1$ から $F P_{λ} = λ P_{λ}$ となり、 $P_{λ}$ の像は固有値 $λ$ の固有ベクトル（と $0$ ）からなります。また $\sum_{λ} λ^{- k}$ は $k = 0$ のとき $4$ 、 $k = 1, 2, 3$ のとき $0$ （1 の 4 乗根の和）なので $\sum_{λ} P_{λ} = I$ 。つまりどんなベクトルも固有ベクトルの和に書け、固有ベクトルからなる基底がとれます。こうして $F = P D P^{- 1}$ 、 $D$ は $1, - 1, i, - i$ をそれぞれ $m_{1}, m_{- 1}, m_{i}, m_{- i}$ 個並べた対角行列になります。

トレースは $P^{- 1}$ を挟んでも変わらないので、 $tr F^{k} = tr D^{k} = m_{1} + (- 1)^{k} m_{- 1} + i^{k} m_{i} + (- i)^{k} m_{- i}$ です。 $k = 0, 1, 2, 3$ の 4 本の式が未知数 4 つの連立方程式になり、重複度が決まります。左辺は、 $tr F^{0} = N$ 、 $tr F = \frac{1}{N} \sum_{n = 0}^{N - 1} e^{- 2 π i n^{2} / N} = \frac{G ( N )}{N}$ 、 $tr F^{2}$ ＝反転の行列の対角成分の和＝ $2 n \equiv 0 (mod N)$ となる $n$ の個数（ $N$ 奇数なら $n = 0$ のみで $1$ 、偶数なら $n = 0, N /2$ で $2$ ）、 $tr F^{3} = tr (F^{2} F)$ は $F$ の行を反転したもので $e^{+ 2 π i n^{2} / N}$ の和になり $tr F$ です。

手順

規約を確認する: $F_{j k} = \frac{1}{N} e^{- 2 π ij k / N}$ なら $tr F = G (N) / N$ （指数の符号が $+$ の規約なら $tr F = G (N) / N$ ）
二次ガウス和の値から $tr F = a + bi$ （ $a, b$ は実数）を求める
$tr F^{2}$ を求める: $N$ が奇数なら $1$ 、偶数なら $2$
連立方程式を立てる: $m_{1} - m_{- 1} = a$ 、 $m_{i} - m_{- i} = b$ （ $tr F$ と $tr F^{3} = tr F$ の実部・虚部）、 $m_{1} + m_{- 1} - m_{i} - m_{- i} = tr F^{2}$ 、 $m_{1} + m_{- 1} + m_{i} + m_{- i} = N$
後ろ 2 式から $m_{1} + m_{- 1}$ と $m_{i} + m_{- i}$ を出し、前 2 式と合わせて 4 つの重複度を求め、すべて 0 以上の整数で和が $N$ になることを確かめる

例題

$N = 7$ とし、 $7$ 次正方行列 $F$ を $F_{j k} = \frac{1}{7} e^{- 2 π ij k /7}$ （ $0 \leq j, k \leq 6$ ）で定める。 $F$ の固有値 $1, - 1, i, - i$ の重複度をそれぞれ $m_{1}, m_{- 1}, m_{i}, m_{- i}$ とするとき、組 $(m_{1}, m_{- 1}, m_{i}, m_{- i})$ を求めよ。

例題の解答

【手順 1】指数の符号は $-$ なので、 $tr F = \frac{1}{7} \sum_{n = 0}^{6} e^{- 2 π i n^{2} /7} = G (7) / 7$ 。

【手順 2】 $7 \equiv 3 (mod 4)$ なので $G (7) = i 7$ 、共役は $- i 7$ 。よって $tr F = - i$ 、すなわち $a = 0$ 、 $b = - 1$ 。

【手順 3】 $N = 7$ は奇数なので $tr F^{2} = 1$ 。

【手順 4】連立方程式は
$m_{1} - m_{- 1} = 0, m_{i} - m_{- i} = - 1, m_{1} + m_{- 1} - m_{i} - m_{- i} = 1, m_{1} + m_{- 1} + m_{i} + m_{- i} = 7.$

【手順 5】後ろ 2 式を足して 2 で割ると $m_{1} + m_{- 1} = 4$ 、引いて 2 で割ると $m_{i} + m_{- i} = 3$ 。第 1 式と合わせて $m_{1} = m_{- 1} = 2$ 、第 2 式と合わせて $m_{i} = 1$ 、 $m_{- i} = 2$ 。どれも 0 以上の整数で、和は $2 + 2 + 1 + 2 = 7$ となり確かに $N$ に一致する。

答え: $(2, 2, 1, 2)$

よくある誤り

$tr F = G (N) / N$ としてしまう誤り。 $F_{j k} = \frac{1}{N} e^{- 2 π ij k / N}$ では対角成分が $e^{- 2 π i j^{2} / N} / N$ なので、正しくは $tr F = G (N) / N$ 。たとえば $N = 7$ で取り違えると $m_{i}$ と $m_{- i}$ が入れ替わり $(2, 2, 2, 1)$ になってしまう
$tr F^{2} = N$ や $0$ としてしまう誤り。 $F^{2}$ は反転 $n \mapsto - n$ の置換行列なので、正しくはトレースは固定点 $2 n \equiv 0 (mod N)$ の個数で、 $N$ 奇数なら $1$ 、偶数なら $2$
$tr F^{3} = tr F$ としてしまう誤り。 $tr F^{3} = m_{1} - m_{- 1} - i (m_{i} - m_{- i})$ なので、正しくは $tr F^{3} = tr F$ 。 $tr F$ と同じとみなすと $m_{i} - m_{- i}$ の情報が失われ、方程式が足りなくなる
固有値の重複度とトレースの関係を対角化できるか確かめずに使ってしまう誤り。正しくは $F^{4} = I$ から $P_{λ} = \frac{1}{4} \sum_{k = 0}^{3} λ^{- k} F^{k}$ の和が $I$ になることで対角化可能性を保証してから $tr F^{k} = m_{1} + (- 1)^{k} m_{- 1} + i^{k} m_{i} + (- i)^{k} m_{- i}$ を使う

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$N = 8$ とし、 $ω = e^{2 π i / N}$ とおく。 $C^{N}$ 上の線形写像 $F$ を、 $x = (x_{0}, x_{1}, \dots, x_{N - 1})$ に対して
$(F x)_{k} = \frac{1}{N} n = 0 \sum N - 1 x_{n} ω^{nk} (k = 0, 1, \dots, N - 1)$
で定める（指数の符号が正であることに注意）。 $F$ の固有値 $1, - 1, i, - i$ の重複度をそれぞれ $m_{1}, m_{- 1}, m_{i}, m_{- i}$ とするとき、組 $(m_{1}, m_{- 1}, m_{i}, m_{- i})$ をこの順に求めよ。ただし重複度は代数的重複度とし、二次ガウス和 $G (N) = \sum_{n = 0}^{N - 1} e^{2 π i n^{2} / N}$ の値（ $N \equiv 0 (mod 4)$ なら $G (N) = (1 + i) N$ ）は用いてよい。

正規化した DFT の固有値と重複度

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題