Steinitzova věta o výmě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

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

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

• Vektorový prostor
• Báze (algebra)
• Lineární algebra