Twierdzenie Steinitza o wymianie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.