Twierdzenie Steinitza o wymianie

Twierdzenie Steinitza o wymianie – twierdzenie algebry liniowej mówiące, że dowolny układ wektorów liniowo niezależnych skończenie wymiarowej przestrzeni liniowej można dopełnić do bazy tej przestrzeni wektorami wybranymi ze z góry zadanej bazy. Twierdzenie nazwane imieniem matematyka, Ernsta Steinitza.

Twierdzenie

Niech $X=\{v_{1},\dots ,v_{n}\}$ rozpina przestrzeń liniową $V$ oraz niech $Y=\{w_{1},\dots ,w_{s}\}$ będzie układem wektorów należących do $V,$ który jest liniowo niezależny. Wówczas:

1. $s\leqslant n,$
2. Spośród wektorów $v_{1},\dots ,v_{n}$ można wybrać taki podzbiór $X'$ złożony z $n-s$ wektorów, które wraz z wektorami $w_{1},\dots ,w_{s}$ tworzą bazę $V.$

Dowód

Ustalmy $n.$ Dowód przebiega indukcyjnie ze względu na $t=|Y|.$

Dla $t=0,$ $Y$ jest zbiorem pustym, więc wystarczy wziąć $X'=X.$

Załóżmy, że twierdzenie jest prawdziwe dla wszystkich takich zbiorów $Y,$ że $|Y|=t-1.$ Pokażemy prawdziwość twierdzenia dla $|Y|=t.$

Ustalmy zbiór $Y=\{w_{1},\dots ,w_{s}\},$ będący liniowo niezależnym układem wektorów należących do V. Niech $|Y|=s=t$ oraz $Y_{1}=\{w_{1},\dots ,w_{s-1}\}.$ Z założenia indukcyjnego wynika, że $s-1\leqslant n$ oraz istnieje taki zbiór $X'_{1}\subset X,$ że $|X'_{1}|=n-(s-1)$ oraz $(X'_{1}\cup Y_{1})=V.$ Aby uprościć zapis, przyjmijmy, że $X'_{1}=\{v_{1},\dots ,v_{n-s+1}\}.$

Wówczas

$\langle X'_{1}\cup Y_{1}\rangle =\langle v_{1},\dots ,v_{n-s+1},w_{1},\dots ,w_{s-1}\rangle .$

Ponieważ $\langle X'_{1}\cup Y_{1}\rangle =V$ i $w_{s}\in V,$ więc

$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}$

dla pewnych $\alpha _{i},\beta _{i}.$

Zauważmy, że istnieje takie $i,$ że $\alpha _{i}\neq 0,$ gdyż w przeciwnym razie mielibyśmy $w_{s}=\beta _{1}w_{1}+\ldots \beta _{s-1}w_{s-1},$ co przeczyłoby liniowej niezależności $Y.$ Bez straty ogólności, załóżmy, że $\alpha _{n-s+1}\neq 0.$

Wówczas

$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}).$

Stąd $V=\langle v_{1},\dots ,v_{n-s},w_{1},\dots ,w_{s}\rangle ,$ gdyż dla każdego $v\in V$ istnieją takie $\alpha _{i}',\beta _{i}',$ że

$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},$

a podstawiając pod $v_{n-s+1}$ z poprzedniej równości odpowiednią kombinację liniową otrzymujemy, że istnieją takie $\alpha _{i}'',\beta _{i}'',$ że

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

Wystarczy wziąć $X'=\{v_{1},\dots ,v_{n-s}\}.$ Wówczas $\langle X'\cup Y\rangle =V.$

Zauważmy, że $s-1<n.$ W przeciwnym razie, tj. gdyby $s-1=n,$ zbiór $X'_{1}$ byłby pusty, więc $\langle Y_{1}\rangle =V,$ skąd $w_{s}\in \langle Y_{1}\rangle ,$ co przeczyłoby liniowej niezależności $Y.$ Skoro $s-1$<$n$ to $s\leqslant n.$