Лема Стейніца про заміну

Доведення здійснюється методом математичної індукції за величиною ${\displaystyle s=|Y|}$.

Для ${\displaystyle s=0}$, ${\displaystyle Y}$ є пустою множиною і тоді ${\displaystyle X'=X}$.

Припустимо твердження є справедливим для всіх множин ${\displaystyle Y}$, для яких ${\displaystyle |Y|=s-1}$. Покажемо справедливість для ${\displaystyle |Y|=s}$.

Визначимо множину ${\displaystyle Y=\{w_{1},\ldots w_{s}\}}$ і ${\displaystyle Y_{1}=\{w_{1},\ldots w_{s-1}\}}$. З припущення індукції ${\displaystyle s-1\leqslant n}$ і існує підмножина ${\displaystyle X'_{1}\subset X}$, така що ${\displaystyle |X'_{1}|=n-(s-1)}$ і ${\displaystyle \langle X'_{1}\cup Y_{1}\rangle =V}$. Для визначеності припустимо що ${\displaystyle X'_{1}=\lbrace v_{1},\ldots ,v_{n-s+1}\rbrace }$.

Оскільки множина ${\displaystyle \langle X'_{1}\cup Y_{1}\rangle =\langle v_{1},\ldots ,v_{n-s+1},w_{1},\ldots w_{s-1}\rangle }$ є базисом лінійного простору то:

${\displaystyle w_{s}=\alpha _{1}v_{1}+\ldots +\alpha _{n-s+1}v_{n-s+1}+\beta _{1}w_{1}+\ldots \beta _{s-1}w_{s-1}}$

для деяких скалярів ${\displaystyle \alpha _{i},\beta _{i}}$.

Для деякого ${\displaystyle i}$, виконується ${\displaystyle \alpha _{i}\neq 0}$, бо в іншому разі ${\displaystyle w_{s}=\beta _{1}w_{1}+\ldots \beta _{s-1}w_{s-1}}$, що суперечить лінійній незалежності векторів з ${\displaystyle Y}$. Без втрати загальності нехай ${\displaystyle \alpha _{n-s+1}\neq 0}$.

Тоді

${\displaystyle v_{n-s+1}=\alpha _{n-s+1}^{-1}(w_{s}-\alpha _{1}v_{1}-\ldots -\alpha _{n-s}v_{n-s}-\beta _{1}w_{1}-\ldots \beta _{s-1}w_{s-1})}$.

Тоді ${\displaystyle V=\langle v_{1},\ldots ,v_{n-s},w_{1},\ldots w_{s}\rangle }$, тобто для кожного ${\displaystyle v\in V}$ визначені скаляри ${\displaystyle \alpha _{i}',\beta _{i}'}$, для яких

${\displaystyle v=\alpha _{1}'v_{1}+\ldots +\alpha _{n-s+1}'v_{n-s+1}+\beta _{1}'w_{1}+\ldots \beta _{s-1}'w_{s-1}}$.

Достатньо взяти ${\displaystyle X'=\{v_{1},\ldots ,v_{n-s}\}}$. Тоді ${\displaystyle \langle X'\cup Y\rangle =V}$.

Також ${\displaystyle s-1<n}$. Якщо б було ${\displaystyle s-1=n}$, то ${\displaystyle \langle Y_{1}\rangle =V}$ і відповідно ${\displaystyle w_{s}\in \langle Y_{1}\rangle }$, що суперечило б лінійній незалежності ${\displaystyle Y}$. Оскільки ${\displaystyle s-1}$< ${\displaystyle n}$ то ${\displaystyle s\leqslant n}$.