Steinitzovo lemma o výměně

Steinitzovo lemma o výměně, někdy též 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.

Tento článek potřebuje úpravy.

---

Tento článek není dostatečně ozdrojován, a může tedy obsahovat informace, které je třeba ověřit.

Znění lemmatu

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