施泰尼茨交换引理

对目前已交换的 $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$ 中)至少还剩一个 $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$——又成功地用 $w_k$ 换掉了一个 $v$,归纳步骤完成,$k\leq m$ 得到确认。