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 ${\displaystyle X=\{v_{1},\dots ,v_{n}\}}$ będzie bazą przestrzeni liniowej ${\displaystyle V}$ oraz niech ${\displaystyle Y=\{w_{1},\dots ,w_{s}\}}$ będzie układem wektorów należących do ${\displaystyle V,}$ który jest liniowo niezależny. Wówczas:

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

Dowód

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

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

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

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

Wówczas

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

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

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

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

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

Wówczas

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

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

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

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

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

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

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