Steinitzova věta o výměně

Steinitzova věta o výměně je důležité tvrzení z oblasti lineární algebry pojmenované po německém matematikovi Ernstu Steinitzovi. Hraje významnou roli v důkazech mnoha dalších tvrzení, například, že všechny báze vektorového prostoru mají stejnou mohutnost, a prostor má tedy jednoznačně určenou dimenzi. Dalším příkladem může být důkaz věty, ž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ť \scriptstyle X \equiv \{ \vec{x}_1, \ldots, \vec{x}_n \} a \scriptstyle Y \equiv \{ \vec{y}_1, \ldots, \vec{y}_m \} jsou dvě množiny vektorů z vektorového prostoru \scriptstyle V. Nechť jsou dále vektory z množiny \scriptstyle X lineárně nezávislé a každý z nich lze vyjádřit jako lineární kombinaci vektorů z množiny \scriptstyle Y. +more Pak platí, že \scriptstyle n \leq m. Pokud \scriptstyle n = m, tak je lineární obal množiny \scriptstyle X nutně roven lineárnímu obalu množiny \scriptstyle Y. Neboli \scriptstyle \{ X \}_\text{lin} = \{ \vec{x}_1, \ldots, \vec{x}_n \}_\text{lin} = \{ \vec{y}_1, \ldots, \vec{y}_m \}_\text{lin} = \{ Y \}_\text{lin}. (Výraz \scriptstyle \{ X \}_\text{lin} značí lineární obal množiny \scriptstyle X atd. ). Dále, pokud platí ostrá nerovnost \scriptstyle n , tak existují navzájem různé indexy \scriptstyle i_1, \ldots, i_{m-n} \in \{1, \ldots, m\} takové, že : \{ \vec{y}_1, \ldots, \vec{y}_m \}_\text{lin} = \{ \vec{x}_1, \ldots, \vec{x}_n, \vec{y}_{i_1}, \ldots, \vec{y}_{i_{m-n}} \}_\text{lin}.

Jinými slovy, mějme množinu \scriptstyle n lineárně nezávislých vektorů \scriptstyle X a dále množinu \scriptstyle m vektorů \scriptstyle Y. Nechť lze navíc libovolný vektor z množiny \scriptstyle X vyjádřit jako lineární kombinaci vektorů z množiny \scriptstyle Y. +more Pak platí, že vektorů v množině \scriptstyle X nemůže být víc než vektorů v množině \scriptstyle Y. Pokud jich je stejně, tak se lineární obaly množin \scriptstyle X a \scriptstyle Y rovnají. Pokud je vektorů v množině \scriptstyle Y více než vektorů v \scriptstyle X, tak lze ke generátorům lineárního obalu množiny \scriptstyle X přidat vhodných \scriptstyle m-n dodatečných vektorů z množiny \scriptstyle Y tak, že tyto vektory dohromady generují lineární obal množiny \scriptstyle Y.

Protože se v daném vektorovém prostoru \scriptstyle V můžeme omezit na jeho podprostor \scriptstyle \{ Y \}_\text{lin}, který je současně vektorový prostor, lze Steinitzovu větu vyjádřit v kratší podobě. Vezměme rovnou \scriptstyle \{ Y \}_\text{lin} = V. +more Pak:.

Nechť \scriptstyle V \equiv \{ \vec{y}_1, \ldots, \vec{y}_m \}_\text{lin} je konečněrozměrný vektorový prostor dimenze \scriptstyle m > 0 a \scriptstyle X \equiv \{ \vec{x}_1, \ldots, \vec{x}_n \} jeho podmnožina tvořená \scriptstyle n lineárně nezávislými vektory. Pak \scriptstyle n \leq m a prostor \scriptstyle V je generován vektory \scriptstyle \{ \vec{x}_1, \ldots, \vec{x}_n, \vec{y}_{i_1}, \ldots, \vec{y}_{i_{m-n}} \} pro jisté, navzájem různé, indexy \scriptstyle i_1, \ldots, i_{m-n} \in \{ 1, \ldots, m \}.

Důkaz

Proveďme důkaz neúplnou matematickou indukcí. Předpokládejme nejprve \scriptstyle n \leq m, poté ukážeme, že předpoklad \scriptstyle n > m vede ke sporu. +more Pro počáteční krok matematické indukce uvažujme množinu \scriptstyle \{ \vec{x}_1, \vec{y}_1, \ldots, \vec{y}_m \} vzniklou tak, že k vektorům z množiny \scriptstyle Y přidáme jeden ("první") vektor z množiny \scriptstyle X. O vektorech z množiny \scriptstyle X ovšem víme, že je lze vyjádřit pomocí vektorů z \scriptstyle Y a námi sestrojená množina je tak lineárně závislá. Existuje v ní tedy vektor \scriptstyle \vec{y}_{i_1} pro jistý index \scriptstyle i_1 \in \{1, \ldots, m\}, který lze nakombinovat ze zbylých vektorů této množiny. Neboli : \vec{y}_{i_1} \in \{ \vec{x}_1, \vec{y}_1, \ldots, \vec{y}_{i_1 - 1}, \vec{y}_{i_1 + 1}, \ldots, \vec{y}_m \}_\text{lin}, kde symbol \scriptstyle \{ \ldots \}_\text{lin} značí lineární obal. Ačkoliv nám lineární závislost množiny vektorů zajišťuje, že v ní existuje vektor, který lze nakombinovat pomocí ostatních, mohli jsme s klidem vzít za tento vektor jeden z vektorů množiny \scriptstyle Y a ne opět vektor \scriptstyle \vec{x}_1. To, že je množina \scriptstyle \{ \vec{x}_1, \vec{y}_1, \ldots, \vec{y}_m \} lineárně závislá totiž znamená, že existuje netriviální lineární kombinace \scriptstyle \alpha_0 \vec{x}_1 + \sum_{i=1}^m \alpha_i \vec{y}_i rovná nulovému vektoru. Kdyby \scriptstyle \alpha_0 \neq 0 a všechny ostatní koeficienty byly nulové, byl by to spor s lineární nezávislostí množiny \scriptstyle X. Existuje tedy nenulový koeficient \scriptstyle \alpha_{i_1}, kde \scriptstyle i_1 \in \{1, \ldots, m \} je jistý index vektoru z \scriptstyle Y. Tímto koeficientem můžeme dělit a vyjádřit dané \scriptstyle \vec{y}_{i_1} pomocí zbylých vektorů způsobem : \vec{y}_{i_1} = \frac{1}{\alpha_{i_1}} \left( -\alpha_0 \vec{x}_1 - \sum_{i=1,i \neq i_1}^m \alpha_i \vec{y}_i \right).

Protože vektor \scriptstyle \vec{x}_1 lze nakombinovat z vektorů z \scriptstyle Y, je \scriptstyle \{ Y \}_\text{lin} = \{ \vec{x}_1, \vec{y}_1, \ldots, \vec{y}_m \}_\text{lin}. Obdobně pro \scriptstyle \vec{y}_{i_1} a máme tedy : \{ Y \}_\text{lin} = \{ \vec{x}_1, \vec{y}_1, \ldots, \vec{y}_{i_1 - 1}, \vec{y}_{i_1 + 1}, \ldots, \vec{y}_m \}_\text{lin}, viz (druhé) tvrzení v oddíle Ostatní v článku Lineární obal. +more Přikročme nyní k důkazu indukčního kroku. Předpokládejme, že pro všechna přirozená \scriptstyle k \geq 1, kde \scriptstyle k , existují navzájem různé indexy \scriptstyle i_1, \ldots, i_{m-k} \in \{1, \ldots, m \} tak, že : \{ Y \}_\text{lin} = \{ \vec{x}_1, \ldots, \vec{x}_k, \vec{y}_{i_1}, \ldots, \vec{y}_{i_{m-k}} \}_\text{lin}. Neboť z předpokladů věty platí, že \scriptstyle \vec{x}_{k+1} \in \{ Y \}_\text{lin}, je množina \scriptstyle \{ \vec{x}_1, \ldots, \vec{x}_k, \vec{x}_{k+1}, \vec{y}_{i_1}, \ldots, \vec{y}_{i_{m-k}} \} lineárně závislá, přičemž množina \scriptstyle \{ \vec{x}_1, \ldots, \vec{x}_{k+1} \} je lineárně nezávislá. V první jmenované množině tedy existuje vektor \scriptstyle \vec{y}_{i_p} pro jisté \scriptstyle i_p \in \{1, \ldots, m \} (kde \scriptstyle p \in \{1, \ldots, m-k \}), který lze vyjádřit pomocí zbylých vektorů. Postupem obdobným tomu pro \scriptstyle \vec{y}_{i_1} dospíváme k rovnosti : \{ Y \}_\text{lin} = \{ \vec{x}_1, \ldots, \vec{x}_k, \vec{x}_{k+1}, \vec{y}_{i_1}, \ldots, \vec{y}_{i_p-1}, \vec{y}_{i_p+1}, \ldots, \vec{y}_{i_{m-k}} \}_\text{lin}. Přeznačíme-li indexy u vektorů v předchozím vzorci, dostáváme vztah : \{ Y \}_\text{lin} = \{ \vec{x}_1, \ldots, \vec{x}_k, \vec{x}_{k+1}, \vec{y}_{j_1}, \ldots, \vec{y}_{j_{m-k-1}} \}_\text{lin}, který dokončuje indukční krok. Pro případ \scriptstyle n \leq m máme tedy větu dokázánu. Předpokládejme nyní, že \scriptstyle n > m. Kdybychom postupovali postupem stejným jako výše, tak bychom se dostali postupným přidáváním vektorů k původnímu lineárnímu obalu do stavu, kdy chceme přidat vektor \scriptstyle \vec{x}_{m+1}, nemáme už ale žádný zbylý vektor z \scriptstyle Y, za který bychom ho mohli vyměnit. Neboli bychom měli : \{ Y \}_\text{lin} = \{ \vec{x}_1, \ldots, \vec{x}_m \}_\text{lin}. Z předpokladů věty ale \scriptstyle \vec{x}_{m+1} \in \{ Y \}_\text{lin} a podle rovnosti výše můžeme tento vektor vyjádřit pomocí zbylých vektorů z množiny \scriptstyle X. To je ale spor s lineární nezávislostí množiny \scriptstyle X, což dokončuje důkaz věty.

Aplikace věty

Jako příklad užití Steinitzovy věty si dokažme následující tvrzení: Každou lineárně nezávislou podmnožinu konečně rozměrného vektorového prostoru lze doplnit na bázi tohoto prostoru. Mějme tedy vektorový prostor \scriptstyle V konečné (nenulové) dimenze \scriptstyle m. +more Existuje v něm tedy \scriptstyle m-členná báze, označme si ji \scriptstyle Y \equiv \{ \vec{y}_1, \ldots, \vec{y}_m \}. Dále mějme podmnožinu prostoru \scriptstyle V, kterou si označíme \scriptstyle X \equiv \{ \vec{x}_1, \ldots, \vec{x}_n \}, tvořenou \scriptstyle n lineárně nezávislými vektory. Steinitzova věta nám říká, že \scriptstyle n \leq m, a navíc, že existují navzájem různé indexy \scriptstyle i_1, \ldots, i_{m-n} \in \hat{m} tak, že : V = \{ \vec{x}_1, \ldots, \vec{x}_n, \vec{y}_{i_1}, \ldots, \vec{y}_{i_{m-n}} \}_\text{lin}. Abychom dokončili důkaz, musíme ještě ukázat, že soubor vektorů \scriptstyle \{ \vec{x}_1, \ldots, \vec{x}_n, \vec{y}_{i_1}, \ldots, \vec{y}_{i_{m-n}} \} je lineárně nezávislý. Kdyby ale byl lineárně závislý, tak z něj můžeme vybrat lineárně nezávislou podmnožinu generující prostor \scriptstyle V. Tato množina by měla nejvýše \scriptstyle m-1 prvků, což je ve sporu s tím, že dimenze prostoru \scriptstyle V je \scriptstyle m.

Literatura

- skripta FJFI ČVUT

Související články

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

Kategorie:Matematické věty a důkazy Kategorie:Lineární algebra