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⩽n,$
2. Spośród wektorów $v_1,\dots ,v_n$ można wybrać taki podzbiór $X^{\prime }$ 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^{\prime }=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⩽n$ oraz istnieje taki zbiór $X{\text{'}}_1\subset X,$ że $|X{\text{'}}_1|=n-(s-1)$ oraz $(X{\text{'}}_1\cup Y_1)=V.$ Aby uprościć zapis, przyjmijmy, że $X{\text{'}}_1=\{v_1,\dots ,v_{n-s+1}\}.$

Wówczas

$⟨X{\text{'}}_1\cup Y_1⟩=⟨v_1,\dots ,v_{n-s+1},w_1,\dots ,w_{s-1}⟩.$

Ponieważ $⟨X{\text{'}}_1\cup Y_1⟩=V$ i $w_s\in V,$ więc

$w_s={\alpha }_1{v}_1+\dots +{\alpha }_{n-s+1}{v}_{n-s+1}+{\beta }_1{w}_1+\dots {\beta }_{s-1}{w}_{s-1}$

dla pewnych ${\alpha }_i,{\beta }_i.$

Zauważmy, że istnieje takie $i,$ że ${\alpha }_i\ne 0,$ gdyż w przeciwnym razie mielibyśmy $w_s={\beta }_1{w}_1+\dots {\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}\ne 0.$

Wówczas

$v_{n-s+1}={\alpha }_{n-s+1}^{-1}(w_s-{\alpha }_1{v}_1-\dots -{\alpha }_{n-s}{v}_{n-s}-{\beta }_1{w}_1-\dots {\beta }_{s-1}{w}_{s-1}).$

Stąd $V=⟨v_1,\dots ,v_{n-s},w_1,\dots ,w_s⟩,$ gdyż dla każdego $v\in V$ istnieją takie ${{\alpha }_i}^{\prime },{{\beta }_i}^{\prime },$ że

$v={{\alpha }_1}^{\prime }{v}_1+\dots +{\alpha }_{n^{\prime }-s+1}{v}_{n-s+1}+{{\beta }_1}^{\prime }{w}_1+\dots {\beta }_{s^{\prime }-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+\dots +{\alpha }_{n^{″}-s}{v}_{n-s}+{{\beta }_1}^{″}{w}_1+\dots {{\beta }_s}^{″}{w}_s.$

Wystarczy wziąć $X^{\prime }=\{v_1,\dots ,v_{n-s}\}.$ Wówczas $⟨X^{\prime }\cup Y⟩=V.$

Zauważmy, że $s-1<n.$ W przeciwnym razie, tj. gdyby $s-1=n,$ zbiór $X{\text{'}}_1$ byłby pusty, więc $⟨Y_1⟩=V,$ skąd $w_s\in ⟨Y_1⟩,$ co przeczyłoby liniowej niezależności $Y.$ Skoro $s-1$<$n$ to $s⩽n.$