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

$\{{\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_m{\}}_{\text{lin}}=\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_n,{\overrightarrow{y}}_{i_1},\dots ,{\overrightarrow{y}}_{i_{m-n}}{\}}_{\text{lin}}.$

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

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

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

Důkaz

Proveďme důkaz neúplnou matematickou indukcí. Předpokládejme nejprve $n\le m$, poté ukážeme, že předpoklad $n>m$ vede ke sporu. Pro počáteční krok matematické indukce uvažujme množinu $\{{\overrightarrow{x}}_1,{\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_m\}$ vzniklou tak, že k vektorům z množiny $Y$ přidáme jeden ("první") vektor z množiny $X$. O vektorech z množiny $X$ ovšem víme, že je lze vyjádřit pomocí vektorů z $Y$ a námi sestrojená množina je tak lineárně závislá. Existuje v ní tedy vektor ${\overrightarrow{y}}_{i_1}$ pro jistý index $i_1\in \{1,\dots ,m\}$, který lze nakombinovat ze zbylých vektorů této množiny. Neboli

${\overrightarrow{y}}_{i_1}\in \{{\overrightarrow{x}}_1,{\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_{i_1-1},{\overrightarrow{y}}_{i_1+1},\dots ,{\overrightarrow{y}}_m{\}}_{\text{lin}},$

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

${\overrightarrow{y}}_{i_1}=\frac{1}{{\alpha }_{i_1}}(-{\alpha }_0{\overrightarrow{x}}_1-\sum _{i=1,i\ne i_1}^m{\alpha }_i{\overrightarrow{y}}_i).$

Protože vektor ${\overrightarrow{x}}_1$ lze nakombinovat z vektorů z $Y$, je $\{Y{\}}_{\text{lin}}=\{{\overrightarrow{x}}_1,{\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_m{\}}_{\text{lin}}$. Obdobně pro ${\overrightarrow{y}}_{i_1}$ a máme tedy

$\{Y{\}}_{\text{lin}}=\{{\overrightarrow{x}}_1,{\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_{i_1-1},{\overrightarrow{y}}_{i_1+1},\dots ,{\overrightarrow{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á $k\ge 1$, kde $k<n$, existují navzájem různé indexy $i_1,\dots ,i_{m-k}\in \{1,\dots ,m\}$ tak, že

$\{Y{\}}_{\text{lin}}=\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_k,{\overrightarrow{y}}_{i_1},\dots ,{\overrightarrow{y}}_{i_{m-k}}{\}}_{\text{lin}}.$

Neboť z předpokladů věty platí, že ${\overrightarrow{x}}_{k+1}\in \{Y{\}}_{\text{lin}}$, je množina $\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_k,{\overrightarrow{x}}_{k+1},{\overrightarrow{y}}_{i_1},\dots ,{\overrightarrow{y}}_{i_{m-k}}\}$ lineárně závislá, přičemž množina $\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_{k+1}\}$ je lineárně nezávislá. V první jmenované množině tedy existuje vektor ${\overrightarrow{y}}_{i_p}$ pro jisté $i_p\in \{1,\dots ,m\}$ (kde $p\in \{1,\dots ,m-k\}$), který lze vyjádřit pomocí zbylých vektorů. Postupem obdobným tomu pro ${\overrightarrow{y}}_{i_1}$ dospíváme k rovnosti

$\{Y{\}}_{\text{lin}}=\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_k,{\overrightarrow{x}}_{k+1},{\overrightarrow{y}}_{i_1},\dots ,{\overrightarrow{y}}_{i_p-1},{\overrightarrow{y}}_{i_p+1},\dots ,{\overrightarrow{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}}=\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_k,{\overrightarrow{x}}_{k+1},{\overrightarrow{y}}_{j_1},\dots ,{\overrightarrow{y}}_{j_{m-k-1}}{\}}_{\text{lin}},$

který dokončuje indukční krok. Pro případ $n\le m$ máme tedy větu dokázánu. Předpokládejme nyní, že $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 ${\overrightarrow{x}}_{m+1}$, nemáme už ale žádný zbylý vektor z $Y$, za který bychom ho mohli vyměnit. Neboli bychom měli

$\{Y{\}}_{\text{lin}}=\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_m{\}}_{\text{lin}}.$

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

$V=\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_n,{\overrightarrow{y}}_{i_1},\dots ,{\overrightarrow{y}}_{i_{m-n}}{\}}_{\text{lin}}.$

Abychom dokončili důkaz, musíme ještě ukázat, že soubor vektorů $\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_n,{\overrightarrow{y}}_{i_1},\dots ,{\overrightarrow{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 $V$. Tato množina by měla nejvýše $m-1$ prvků, což je ve sporu s tím, že dimenze prostoru $V$ je $m$.

Literatura

• Šablona:Citace monografie – skripta FJFI ČVUT

Související články

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