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$ . 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<m$ , 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$ . 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$ . 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. 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. 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<n$ , 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$ . 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$ .