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ť ${\displaystyle \scriptstyle X\equiv \{{\vec {x}}_{1},\ldots ,{\vec {x}}_{n}\}}$ a ${\displaystyle \scriptstyle Y\equiv \{{\vec {y}}_{1},\ldots ,{\vec {y}}_{m}\}}$ jsou dvě množiny vektorů z vektorového prostoru ${\displaystyle \scriptstyle V}$. Nechť jsou dále vektory z množiny ${\displaystyle \scriptstyle X}$ lineárně nezávislé a každý z nich lze vyjádřit jako lineární kombinaci vektorů z množiny ${\displaystyle \scriptstyle Y}$. Pak platí, že ${\displaystyle \scriptstyle n\leq m}$. Pokud ${\displaystyle \scriptstyle n=m}$, tak je lineární obal množiny ${\displaystyle \scriptstyle X}$ nutně roven lineárnímu obalu množiny ${\displaystyle \scriptstyle Y}$. Neboli ${\displaystyle \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 ${\displaystyle \scriptstyle \{X\}_{\text{lin}}}$ značí lineární obal množiny ${\displaystyle \scriptstyle X}$ atd.). Dále, pokud platí ostrá nerovnost ${\displaystyle \scriptstyle n<m}$, tak existují navzájem různé indexy ${\displaystyle \scriptstyle i_{1},\ldots ,i_{m-n}\in \{1,\ldots ,m\}}$ takové, že

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

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

Nechť ${\displaystyle \scriptstyle V\equiv \{{\vec {y}}_{1},\ldots ,{\vec {y}}_{m}\}_{\text{lin}}}$ je konečněrozměrný vektorový prostor dimenze ${\displaystyle \scriptstyle m>0}$ a ${\displaystyle \scriptstyle X\equiv \{{\vec {x}}_{1},\ldots ,{\vec {x}}_{n}\}}$ jeho podmnožina tvořená ${\displaystyle \scriptstyle n}$ lineárně nezávislými vektory. Pak ${\displaystyle \scriptstyle n\leq m}$ a prostor ${\displaystyle \scriptstyle V}$ je generován vektory ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \scriptstyle n\leq m}$, poté ukážeme, že předpoklad ${\displaystyle \scriptstyle n>m}$ vede ke sporu. Pro počáteční krok matematické indukce uvažujme množinu ${\displaystyle \scriptstyle \{{\vec {x}}_{1},{\vec {y}}_{1},\ldots ,{\vec {y}}_{m}\}}$ vzniklou tak, že k vektorům z množiny ${\displaystyle \scriptstyle Y}$ přidáme jeden ("první") vektor z množiny ${\displaystyle \scriptstyle X}$. O vektorech z množiny ${\displaystyle \scriptstyle X}$ ovšem víme, že je lze vyjádřit pomocí vektorů z ${\displaystyle \scriptstyle Y}$ a námi sestrojená množina je tak lineárně závislá. Existuje v ní tedy vektor ${\displaystyle \scriptstyle {\vec {y}}_{i_{1}}}$ pro jistý index ${\displaystyle \scriptstyle i_{1}\in \{1,\ldots ,m\}}$, který lze nakombinovat ze zbylých vektorů této množiny. Neboli

${\displaystyle {\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 ${\displaystyle \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 ${\displaystyle \scriptstyle Y}$ a ne opět vektor ${\displaystyle \scriptstyle {\vec {x}}_{1}}$. To, že je množina ${\displaystyle \scriptstyle \{{\vec {x}}_{1},{\vec {y}}_{1},\ldots ,{\vec {y}}_{m}\}}$ lineárně závislá totiž znamená, že existuje netriviální lineární kombinace ${\displaystyle \scriptstyle \alpha _{0}{\vec {x}}_{1}+\sum _{i=1}^{m}\alpha _{i}{\vec {y}}_{i}}$ rovná nulovému vektoru. Kdyby ${\displaystyle \scriptstyle \alpha _{0}\neq 0}$ a všechny ostatní koeficienty byly nulové, byl by to spor s lineární nezávislostí množiny ${\displaystyle \scriptstyle X.}$ Existuje tedy nenulový koeficient ${\displaystyle \scriptstyle \alpha _{i_{1}}}$, kde ${\displaystyle \scriptstyle i_{1}\in \{1,\ldots ,m\}}$ je jistý index vektoru z ${\displaystyle \scriptstyle Y}$. Tímto koeficientem můžeme dělit a vyjádřit dané ${\displaystyle \scriptstyle {\vec {y}}_{i_{1}}}$ pomocí zbylých vektorů způsobem

${\displaystyle {\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 ${\displaystyle \scriptstyle {\vec {x}}_{1}}$ lze nakombinovat z vektorů z ${\displaystyle \scriptstyle Y}$, je ${\displaystyle \scriptstyle \{Y\}_{\text{lin}}=\{{\vec {x}}_{1},{\vec {y}}_{1},\ldots ,{\vec {y}}_{m}\}_{\text{lin}}}$. Obdobně pro ${\displaystyle \scriptstyle {\vec {y}}_{i_{1}}}$ a máme tedy

${\displaystyle \{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á ${\displaystyle \scriptstyle k\geq 1}$, kde ${\displaystyle \scriptstyle k<n}$, existují navzájem různé indexy ${\displaystyle \scriptstyle i_{1},\ldots ,i_{m-k}\in \{1,\ldots ,m\}}$ tak, že

${\displaystyle \{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 ${\displaystyle \scriptstyle {\vec {x}}_{k+1}\in \{Y\}_{\text{lin}}}$, je množina ${\displaystyle \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 ${\displaystyle \scriptstyle \{{\vec {x}}_{1},\ldots ,{\vec {x}}_{k+1}\}}$ je lineárně nezávislá. V první jmenované množině tedy existuje vektor ${\displaystyle \scriptstyle {\vec {y}}_{i_{p}}}$ pro jisté ${\displaystyle \scriptstyle i_{p}\in \{1,\ldots ,m\}}$ (kde ${\displaystyle \scriptstyle p\in \{1,\ldots ,m-k\}}$), který lze vyjádřit pomocí zbylých vektorů. Postupem obdobným tomu pro ${\displaystyle \scriptstyle {\vec {y}}_{i_{1}}}$ dospíváme k rovnosti

${\displaystyle \{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

${\displaystyle \{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 ${\displaystyle \scriptstyle n\leq m}$ máme tedy větu dokázánu. Předpokládejme nyní, že ${\displaystyle \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 ${\displaystyle \scriptstyle {\vec {x}}_{m+1}}$, nemáme už ale žádný zbylý vektor z ${\displaystyle \scriptstyle Y}$, za který bychom ho mohli vyměnit. Neboli bychom měli

${\displaystyle \{Y\}_{\text{lin}}=\{{\vec {x}}_{1},\ldots ,{\vec {x}}_{m}\}_{\text{lin}}.}$

Z předpokladů věty ale ${\displaystyle \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 ${\displaystyle \scriptstyle X}$. To je ale spor s lineární nezávislostí množiny ${\displaystyle \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 ${\displaystyle \scriptstyle V}$ konečné (nenulové) dimenze ${\displaystyle \scriptstyle m}$. Existuje v něm tedy ${\displaystyle \scriptstyle m}$-členná báze, označme si ji ${\displaystyle \scriptstyle Y\equiv \{{\vec {y}}_{1},\ldots ,{\vec {y}}_{m}\}}$. Dále mějme podmnožinu prostoru ${\displaystyle \scriptstyle V}$, kterou si označíme ${\displaystyle \scriptstyle X\equiv \{{\vec {x}}_{1},\ldots ,{\vec {x}}_{n}\}}$, tvořenou ${\displaystyle \scriptstyle n}$ lineárně nezávislými vektory. Steinitzova věta nám říká, že ${\displaystyle \scriptstyle n\leq m}$, a navíc, že existují navzájem různé indexy ${\displaystyle \scriptstyle i_{1},\ldots ,i_{m-n}\in {\hat {m}}}$ tak, že

${\displaystyle 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ů ${\displaystyle \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 ${\displaystyle \scriptstyle V}$. Tato množina by měla nejvýše ${\displaystyle \scriptstyle m-1}$ prvků, což je ve sporu s tím, že dimenze prostoru ${\displaystyle \scriptstyle V}$ je ${\displaystyle \scriptstyle m}$.

Literatura

• PYTLÍČEK, Jiří. Lineární algebra a geometrie. Praha: Česká technika - nakladatelství ČVUT, 2008. ISBN 978-80-01-04063-8.  – skripta FJFI ČVUT

Související články

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