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,\ldots ,v_n \}$ będzie bazą przestrzeni liniowej $V$ oraz niech $Y=\{w_1,\ldots w_s \}$ będzie układem wektorów, który jest liniowo niezależny. Wówczas:

1. $s\leqslant n$
2. Spośród wektorów $v_1,\ldots ,v_n$ można wybrać taki podzbiór $X'$ złożony z $n-s$ wektorów, które wraz z wektorami $w_1,\ldots 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,\ldots w_s\}$. Niech $|Y|=s=t$ oraz $Y_1=\{ w_1, \ldots 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 $\langle X'_1 \cup Y_1 \rangle = V$. Aby uprościć zapis, przyjmijmy, że $X'_1=\lbrace v_1,\ldots ,v_{n-s+1} \rbrace$.

Wówczas

$\langle X'_1 \cup Y_1 \rangle = \langle v_1,\ldots,v_{n-s+1}, w_1, \ldots w_{s-1} \rangle$.

Stąd

$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,\ldots,v_{n-s}, w_1, \ldots 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}$.

Wystarczy wziąć $X'=\{ v_1, \ldots, 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'_1$. Skoro $s-1$<$n$ to $s\leqslant n$.