大学の線形代数で扱う帰納法

帰納法は証明手法として極めて重要なものです。特に証明する途中、証明する目標となる命題と似たような形の子問題がでる時帰納法は定番化される。帰納法は特に自然数などの構造で役立つけど、線形代数の場合はそう簡単ではない。行列や線形変換や線形空間などは自明的な帰納的構造を持たないため、帰納法を適用しようとしてもなかなか難しいだろう。これから自分が見かけたいくつかの帰納法の考え方を紹介する。

掃出しを使った帰納法

こちらの帰納法は一番簡単で、やり方としてまず行と列の足し引きによって一行と一列の要素を一つ以外全部0にする。その後残りの部分に対して帰納法を適用。典型として任意の行列は標準形に移せることの証明に使われる。標準形はつまり1が対角線上にだけ並ぶ形です。行列 $A$ の一行目と一列目を掃き出すと以下の形になる。

$\begin{pmatrix} 1 & 0 \\ 0 & A_{m,n} \\ \end{pmatrix}$

つまり $(1,1)$ にのみ1が存在してそれ以外の一列目と一行目の要素は全部0になる。この時右下の $A_{m,n}$ はサイズが $A$ より小さいがため帰納法の仮定を適用できる。この方法は主に正則変換の影響を受けない性質持つ命題の証明に使われる。

正値エルミートの場合

正値エルミート行列の場合、正値行列を $H$ とする。

$H= \begin{pmatrix} A_{n-1} & b \\ b^t & c \\ \end{pmatrix} P= \begin{pmatrix} E_{n-1} & A_{n-1}^{-1}b \\ 0^t & 1 \\ \end{pmatrix}$

この時 $B=P^t A P$ が以下の形になる。

$B=\begin{pmatrix} A_{n-1} & 0 \\ 0^t & c-A_{n-1}^{-1}[b] \\ \end{pmatrix}$

この変換は行列式に影響が出ない上掃き出すことができる。これを使って二次形式やアダマールの不等式などを証明することが楽です。

部分集合に関する帰納法

名前通りにベクトル集合の要素に対して帰納する。なおこの時集合のすべての要素を表せるベクトルの組は基底ではなく、極大線形独立系と呼ばれる。簡単で理解しやすい反面に行列や変換に対してあまり効かないので一回だけ見たことある。では次の命題を考えましょう。

集合Sがn個のベクトルからなる極大線形独立系を持つときn個より多いベクトルは必ず線形従属

集合Sに対して $E_1$ と $E_2$ の二つの極大線形独立系がある時。 $E_1$ はn個のベクトルがある。 $E_2$ はm-1個のベクトルがある。 $E_1$ にない $E_2$ にあるベクトル $v$ を考える。Sから $v$ を取り除いてS'を得る。集合は線形空間の効率を満たさなくでもいいのでとても便利です。この時 $E_1$ はまたn個のベクトルを有する。でも $E_2$ はm-1個の線形独立なベクトルしかない。 S'に対して帰納法の仮定を適用すると $n \geq m-1$ はすぐに分かる。イコールの場合に対して証明すれば大丈夫です。