Steinitzova věta o výměně

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Steinitzova věta o výměně je důležitá při důkazech mnoha tvrzení, například, že všechny báze vektorového prostoru mají stejnou mohutnost (a prostor má tedy jen jednu dimenzi), nebo že pokud má prostor konečnou bázi, pak lze libovolnou lineárně nezávislou množinu doplnit na bázi.

Znění věty[editovat | editovat zdroj]

Nechť je dán vektorový prostor V, lineárně nezávislá X \subseteq V a jeho konečný systém generátorů Y. Potom platí, že |X| \leq |Y| a dokonce \exists Z \subseteq V, pro kterou platí:

  • |Z| = |Y|
  • Z generuje V
  • X \subseteq Z
  • Z \setminus X \subseteq Y

Důkaz[editovat | editovat zdroj]

Označme \{u_1, ..., u_n\} := X \setminus Y, a Z_0 := Y. Dále postupujme matematickou indukcí pro i \in (1, n):

  • předpoklad: Z_{i-1} generuje V - vyjádřeme u_i vůči Z_{i-1}:

\sum_{w_j \in Z_{i-1}}{a_j w_j}

  • protože X je lineárně nezávislá, a_j \neq 0 pro nějaké w_j \notin X, použijme lemma o výměně a položme Z_i := (Z_{i-1} \setminus \{w_j\}) \cup \{u_i\}

Toto iterujme pro \forall i, na konci máme Z_n = Z.

První pravidlo platí, protože při iteraci neměníme počet prvků, druhé z lemmatu o výměně, třetí - X \cap Y \subseteq Z_0 i ostatních Z_i a X \setminus Y \subseteq Z_n, čtvrté vyplývá z algoritmu.

Důkaz by se dal shrnout tak, že pokud je Y množina generátorů, každý prvek z X se dá vyjádřit jako lin. kombinace prvků z Y. Vezmeme první prvek z X, ten se rovná lin. kombinaci prvků z Y, vezmeme tedy z Y ten prvek, jehož koeficient v lin. kombinaci je nenulový a vyměníme ho s prvním prvkem z X (dle lematu o výměně). To samé provedeme pro zbývající prvky X. Z Y dostaneme množinu Z, jejíž mohutnost se zachová, navíc bude obsahovat všechny prvky z X a stále bude množinou generátorů.

Související články[editovat | editovat zdroj]