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.

Znění lemmatu

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$.

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