応用線形代数演習 II ( 塩田教官 ) Frame 法の証明

【基本対称式】 λ_{1}, ⋯, λ_{n} を n 個の文字とする。 k = 0, 1, ⋯, n に対して、 λ_{1}, ⋯, λ_{n} の中

から異なる k 個を取り出して掛けた積の和 s_{k} を k 次の基本対称式と呼ぶ。すなわち、

s_{0} = 1, s_{1} = λ_{1} + ⋯ + λ_{n}, s_{2} = λ_{1}λ_{2} + λ_{1}λ_{3} + ⋯ + λ_{n−1}λ_{n},

⋯ s_{n} = λ_{1}λ_{2} ⋯ λ_{n}

【ニュートンの恒等式】 k = 1, 2, ⋯, n に対して、 λ_{1}, ⋯, λ_{n} の k 乗和を

σ_{k} = λ_{1}^{k} + ⋯ + λ_{n}^{k}

と置くと、

k s_{k} = − ∑_{j=1}^{k}(−1)^{j} σ_{j} s_{k−j} ( k = 1, 2, ⋯, n )

が成り立つ。【例】 n = 3 のときを考えよう。

s_{0} = 1, s_{1} = λ_{1} + λ_{2} + λ_{3}, s_{2} = λ_{1}λ_{2} + λ_{1}λ_{3} + λ_{2}λ_{3}, s_{3} = λ_{1}λ_{2}λ_{3}

σ_{1} = λ_{1} + λ_{2} + λ_{3}, σ_{2} = λ_{1}^{2} + λ_{2}^{2} + λ_{3}^{2}, σ_{3} = λ_{1}^{3} + λ_{2}^{3} + λ_{3}^{3}

である。 k = 1 のとき、

− ∑_{j=1}^{1}(−1)^{j} σ_{j} s_{1−j} = −(−1) σ_{1} s_{0} = σ_{1} = s_{1}

k = 2 のとき、

− ∑_{j=1}^{2}(−1)^{j} σ_{j} s_{2−j} = −(−1) σ_{1} s_{1} − (−1)^{2}σ_{2} s_{0} = σ_{1} s_{1} − σ_{2}
= (λ_{1} + λ_{2} + λ_{3})^{2} − (λ_{1}^{2} + λ_{2}^{2} + λ_{3}^{2})
= 2 (λ_{1}λ_{2} + λ_{1}λ_{3} + λ_{2}λ_{3})

k = 3 のとき、

− ∑_{j=1}^{3}(−1)^{j}σ_{j} s_{3−j} = −(−1) σ_{1} s_{2} − (−1)^{2} σ_{2}s_{1} − (−1)^{3} σ_{3}s_{0} = σ_{1} s_{2} − σ_{2} s_{1} + σ_{3}
= (λ_{1} + λ_{2} + λ_{3})(λ_{1}λ_{2} + λ_{1}λ_{3} + λ_{2}λ_{3})
− (λ_{1}^{2} + λ_{2}^{2} + λ_{3}^{2})(λ_{1} + λ_{2} + λ_{3}) + (λ_{1}^{3} + λ_{2}^{3} + λ_{3}^{3})
= 3 λ_{1}λ_{2}λ_{3}

【Frame 法の証明】 n 次行列 A の n 個の固有値を λ_{1}, ⋯, λ_{n}、 A の固有多項式を Φ_{A}(t) =

t^{n} + c_{1}t^{n−1} + ⋯ + c_{n} と置く。まず

Φ_{A}(t) = (t − λ_{1}) ⋯ (t − λ_{n})

ゆえ、根と係数の関係から

c_{k} = (−1)^{k} s_{k} ( k = 1, 2, ⋯, n )

が成り立つ。【A が上三角行列の場合】上三角行列では固有値と対角成分が一致するので、

A = ( \begin{matrix}λ_{1} & ∗ & ⋯ & ∗ \\ 0 & λ_{2} & & ∗ \\ ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{n} \end{matrix} ) である。従って A^{k} = ( \begin{matrix}λ_{1}^{k} & ∗ & ⋯ & ∗ \\ 0 & λ_{2}^{k} & & ∗ \\ ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{n}^{k} \end{matrix} ) となり

tr(A^{k}) = σ_{k} が成り立つ。第 k ステップ目の X は

X = A^{k} + c_{1}A^{k−1} + ⋯ + c_{k−1}A

なので、 k についての帰納法の仮定より

tr(X) = σ_{k} + c_{1}σ_{k−1} + ⋯ + c_{k−1}σ_{1}
= σ_{k} + (−1)^{1}s_{1}σ_{k−1} + ⋯ + (−1)^{k−1}s_{k−1}σ_{1}
= −(−1)^{k}k s_{k} = −k c_{k}

【一般の場合】三角化の定理より B = P^{−1}AP が上三角行列になるような正則行列 P を取

ることができる。 No.22 の定理から、

Φ_{B}(t) = Φ_{A}(t) = t^{n} + c_{1}t^{n−1} + ⋯ + c_{n}

である。また、 A について Frame 法を適用したときの第 k ステップ目の X を X_{A,k} と書けば、

X_{B,k} = P^{−1}X_{A,k}P

であり、再び No.22 の定理から、

tr(X_{B,k}) = tr(X_{A,k})

となる。 B については Frame 法は証明できているので、 c_{k} = −tr(X_{B,k})/k = −tr(X_{A,k})/k

【ニュートンの恒等式の証明】 f(t) = (1 + λ_{1}t) ⋯ (1 + λ_{n}t) と置くと、

f(t) = 1 + s_{1}t + s_{2}t^{2} + ⋯ + s_{n}t^{n}

ゆえ

s_{1} + 2s_{2}t+ ⋯ +ns_{n}t^{n−1}
= f′(t) = ∑_{i=1}^{n} λ_{i} \frac{f(t)}{1 + λ_{i}t} = ∑_{i=1}^{n} λ_{i} f(t) \{1 − (λ_{i}t) + (λ_{i}t)^{2} − ⋯\}
= ∑_{i=1}^{n}(1 + s_{1}t + s_{2}t^{2} + ⋯ + s_{n}t^{n}) (λ_{i} − λ_{i}^{2}t + λ_{i}^{3}t^{2} − ⋯)

両辺の t^{k−1} の係数を比べると、

k s_{k} = ∑_{i=1}^{n} ∑_{j=1}^{k} s_{k−j}(−1)^{j+1}λ_{i}^{j}
= − ∑_{j=1}^{k}(−1)^{j}s_{k−j} (∑_{i=1}^{n} λ_{i}^{j}) = − ∑_{j=1}^{k}(−1)^{j}s_{k−j} σ_{j}