シュタイニッツの交換補題

これまでに交換した $w$ の個数 $k$ に関する帰納法で議論する。$k=0$ のとき不等式 $0\leq m$ は自明であり、交換は不要である。帰納的に、$w_1,\dots,w_{k-1}$ が元の $v_i$ のうち $k-1$ 個と既に交換されており(これらを $v_1,\dots,v_{k-1}$ と番号を振り直す)、$\{w_1,\dots,w_{k-1},v_k,\dots,v_m\}$ が依然として $V$ を張ると仮定する。

$k-1$ が既に $m$ に等しいならば、すべての $v_i$ が使い尽くされているので、$\{w_1,\dots,w_{k-1}\}$ 単独で $V$ を張る。しかしそのとき $w_k\in V$ は $w_1,\dots,w_{k-1}$ の一次結合となり、$\{w_1,\dots,w_k\}$ の一次独立性に矛盾する。したがって、現在の $k$ について $k\leq m$ を示そうとしているうちに、この場合は起こり得ない——正確には、これは直ちに $k-1<m$、すなわち $k\leq m$ を示している。

そうでなければ $k-1<m$ なので、($v_k,\dots,v_m$ の中に)少なくとも 1 つの $v_j$ が残っている。$\{w_1,\dots,w_{k-1},v_k,\dots,v_m\}$ が $V$ を張るので、$w_k$ を組み合わせ $w_k=\lambda_1w_1+\cdots+\lambda_{k-1}w_{k-1}+\mu_1v_{j_1}+\cdots+\mu_{m-k+1}v_{j_{m-k+1}}$ として書く。残っている $v$ に関する係数 $\mu_1,\dots$ がすべて $0$ であれば、$w_k$ は $w_1,\dots,w_{k-1}$ だけの組み合わせとなり、再び独立性に矛盾する——したがって残っているある $v_j$ の係数はゼロでない。

その方程式を $v_j$ について解き(そのゼロでない係数で割る)、$v_j$ を $w_1,\dots,w_k$ と残りの他の $v$ の組み合わせとして表す。この表現を $v_j$ が現れるすべての箇所に代入すると、$\{w_1,\dots,w_k\}$ と残りの $v$($v_j$ を除く)を合わせたものが依然として $V$ を張ることが分かる——もう 1 つの $v$ が $w_k$ にうまく交換され、帰納的段階が完了し、$k\leq m$ が確認される。