斎藤線型の命題[3.10]の証明について

$S$が$n$個の元から成る極大線型独立系を持つとし，$S$の$m$個の元から成る部分集合$F$を$F = \{\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_m\}$と置く.
このとき，定理の主張の対偶
「$\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_m$が線型独立 $\Longrightarrow$ $n \geq m$」$\cdots \, (\ast)$
を示せばよい.
とくに，$F$も$S$の極大線型独立系であったとすれば，上の主張により$n \geq m$と$n \leq m$を得，$m = n$となり，$S$の任意の極大線型独立系は$n$個のベクトルより成ることもわかる.

$k = |S|$と置き，$k$に関する帰納法で証明する.
まず$k = 1$のときはよい.
$k > 1$とし，$k-1$に対しては$(\ast)$が成り立つと仮定して$|S| = k$のときを考える。
$E = \{\boldsymbol{e}_1，\boldsymbol{e}_2，\cdots， \boldsymbol{e}_n\}$を$S$の極大線型独立系とし，$\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_m$が線型独立であるとしよう.

もし$E \supseteq F$ならば$n \geq m$となる.
$E \nsupseteq F$ならば$F$の元で，$E$に含まれないものが存在する. このうち一つを$\boldsymbol{f}_m$とする.
$S' = S - \{\boldsymbol{f}_m\}$ とすると$|S'| = k-1$であり，極大線型独立系として$E$を持つ.
一方，$\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_{m-1}$は$S'$に含まれ，線型独立である.
帰納法の仮定によって，$n \geq m-1$となる.

$n = m-1$を仮定しよう.

このとき，$F' = \{\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_{m-1}\}$は$S'$の極大線型独立系となっている.
実際，$S'$の$F'$を含む極大線型独立系$F''$を考えると，帰納法の仮定によって$S'$の任意の極大線型独立系は$n \, (=m-1)$個の元から成るので$|F''| = m-1$.
$F' \subseteq F''$であり，$|F'| = |F''|$が成り立つので$F'' = F'$となるからである.

したがって，$\boldsymbol{e}_1，\boldsymbol{e}_2，\cdots， \boldsymbol{e}_n$は$\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_{m-1}$の線型結合で書ける.
一方，$\boldsymbol{f}_m$は$\boldsymbol{e}_1，\boldsymbol{e}_2，\cdots， \boldsymbol{e}_n$の線型結合で書けるから，結局$\boldsymbol{f}_m$は$\boldsymbol{f}_1，\boldsymbol{f}_2，\cdots， \boldsymbol{f}_{m-1}$の線型結合となり，
これらの線型独立性に反する.したがって$n > m-1$つまり$n \geq m$でなければならない.

以上によって，$(\ast)$の証明が終わった.

$Q.E.D.$