Hledání ztracených podprostorů

Počet podprostorů prostoru $T^n$ pro $T \in \{\mathbb{Q}, \mathbb{R}, \mathbb{C}\}$

V těchto případech je situace poměrně jednoduchá. Podprostory dimenze $0$ a $n$ jsou v $T^n$ jediné (to platí pro jakékoli těleso $T$), podprostorů dimenze $1$ až $n-1$ je nekonečně mnoho (aby existovaly, musíme předpokládat, že $n \geq 2$). Připomeňme, že podprostor dimenze nula je množina obsahující pouze nulový vektor $\{\theta\}$ a podprostor dimenze $n$ je vektorový prostor $T^n$, který je dle definice sám sobě podprostorem.

Předpokládejme, že $n \geq 2$. Ukážeme, že v takovém případě obsahuje $T^n$, kde $T$ je nekonečné těleso, nekonečně podprostorů dimenze $1$. Stačí uvažobvat vektory $(1,0,\ldots,0,\alpha), \alpha \in T$. Když vezmeme dva takové s různou hodnotou parametru $\alpha$, tvoří dvoučlenný lineárně nezávislý soubor a jimi generované dva podprostory dimenze jedna jsou různé: \[ \langle (1,0,\ldots,0,\alpha_1) \rangle \neq \langle (1,0,\ldots,0,\alpha_2) \rangle \quad \text{pro} \quad \alpha_1 \neq \alpha_2. \] Takto tedy můžeme vždy zkonstruovat nekonečně mnoho různých podprostorů dimenze 1. V případě $\mathbb{R}^2$ by to byly dokonce všechny podprostory (až na osu $y$ generovanou vektorem $(0,1)$), ve vyšších dimenzích je ještě mnoho jiných jednodimenzionálních podprostorů.

Pro vyšší dimenze by se dal důkaz konstruovat podobně, ale s tím tu nebudeme zdržovat. Situace v prostorech $T^n$ s konečým tělesem $T = \mathbb{Z}_p$ je totiž daleko zajímavější, jak se zvídavý čtenář hned vzápětí přesvědčí.

Počet podprostorů prostoru $T^n$ pro konečné těleso $T$

Mějme konečné těleso $T$ mající $p$ prvků a uvažme $V = T^n$, vektorový prostor dimenze $n$. Kolik podprostorů zadané dimenze $k \in \hat n$ tento prostor má?

Na tuto otázku lze odpovědět relativně jednoduchou kombinatorickou úvahou. Každý $k$-dimenzionální podprostor prostoru $V$ je lineárním obalem lineárně nezávislého souboru vektorů délky $k$ (báze daného podprostoru). Musíme si tedy uvědomit dvě věci:

1. Kolik v našem prostoru $V$ existuje lineárně nezávislých souborů s $k$ vektory?
2. Kolika způsoby lze vybrat bázi podprostoru dimenze $k$?

Nejprve odpovězme na první otázku. Ve vektorovém prostoru $V = T^n$ je právě $p^n$ vektorů, právě jeden z nich je nulový. Vybíráme-li tedy první vektor našeho souboru, pak máme na výběr z $p^n - 1$ vektorů. Jako druhý člen souboru nyní můžeme vybrat libovolný vektor, který není násobkem prvního vektoru (těchto násobků je $p$, včetně nulového vektoru). Tudíž pro druhý vektor máme na výběr $p^n - p$ možností. Třetí vektor nemůže být lineární kombinací prvních dvou vektorů, kterých je $p^2$ a proto na výběr pro třetí vektor našeho souboru máme $p^n - p^2$ vektorů. Takto pokračujeme ve výběru až ke $k$-tému vektoru souboru, který nesmí být lineární kombinací předchozích $k-1$ vektorů, čili ho můžeme vybrat $p^n - p^{k-1}$ způsoby.

Možných $k$-prvkových lineárně nezávislých souborů v prostoru $V = T^n$ je proto $$ (p^n - 1)(p^n - p) \cdots (p^n - p^{k-1}). $$

Prakticky totožnou úvahu lze nyní použít k zodpovězení druhé otázky. V podprostoru dimenze $k$ je $p^k$ vektorů. Opět se ptáme, kolika způsoby z nich lze vybrat lineárně nezávislý soubor s $k$ členy. Podobně jako výše dostaneme $$ (p^k - 1)(p^k - p) \cdots (p^k - p^{k-1}). $$

To tedy znamená, že počet podprostorů s dimenzí $k$ prostoru $T^n$ je přesně (po jednoduchém pokrácení) $$ \frac{(p^n - 1)(p^n - p) \cdots (p^n - p^{k-1})}{(p^k - 1)(p^k - p) \cdots (p^k - p^{k-1})} = \boxed{\frac{(p^n - 1)(p^{n-1} - 1) \cdots (p^{n-k+1} - 1)}{(p^k - 1)(p^{k-1} - 1) \cdots (p - 1)}.} $$

Tento výraz má dokonce jméno, jde o tzv. Gaussův binomický koeficient. Obecně pro nezáporná celá čísla $m$ a $r$, $r \leq m$, a přípustná reálná $q$ klademe $$ \binom{m}{r}_q := \frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r+1})}{(1-q)(1-q^2)\cdots(1-q^r)}. $$ V limitě $q \to 1_-$ z tohoto výrazu dostaneme známý binomický koeficient.

Pojďme nyní tento abstraktní výsledek explicitně prozkoumat v případě prostorů $\mathbb{Z}_2^n$ a $\mathbb{Z}_3^n$. Jak uvidíme, podprostorů je opravdu hodně.

Počty podprostorů prostoru $\mathbb{Z}_2^n$

V následující tabulce uvádíme počty podprostorů dimenze $k$ v prostoru $\mathbb{Z}_2^n$ pro $n=1,2,\ldots,10$.

Počty podprostorů prostoru $\mathbb{Z}_3^n$

V následující tabulce uvádíme počty podprostorů dimenze $k$ v prostoru $\mathbb{Z}_3^n$ pro $n=1,2,\ldots,10$.

Jak najít všechny podprostory zadané dimenze?

V předchozím textu jsme si ukázali, kolik podprostorů v daném prostoru je. Jak je ale explicitně najít? Na tuto otázku už není zcela jednoduchá odpověď a budeme muset vyvinout jisté úsilí k jejímu zodpovězení.

Uvažujme opět konkrétní situaci, kdy se bavíme o prostoru $T^n$ a jeho podprostorech $P$ dimenze $k$. Z Frobeniovy věty víme, že každý takovýto podprostor můžeme popsat pomocí matice $\mathbf{A} \in T^{n-k,n}$ s hodností $n-k$ rovností $$ P = \{ x \in T^n \mid \mathbf{A} x = \theta \}. $$ Přesný tvar matice $\mathbf{A}$ ale neznáme, dokonce víme, že může existovat více matic, které nám dají stejný podprostor $P$ (stačí prostě provést jednu z ekvivalentních úprav GEM). Než se pustíme dále, tak se této nejednoznačnosti musíme zbavit. Proto nyní následuje malá teoretická vsuvka.

Redukovaný horní stupňovitý tvar matice (rHST)

Budeme potřebovat jeden z konceptů, který se v BI-LA1 (ani BI-LIN dříve) neprobírá, konkrétně redukovaný horní stupňovitý tvar matice (reduced echelon form).

---

Definice: Matice $\mathbf{A} \in T^{m,n}$ je v redukované horním stupňovitém tvaru (rHST), právě když je v horním stupňovitém tvaru a v hlavních sloupcích má vždy právě jednu jedničku a jinak samé nuly.

---

Tj. rHST získáme například tak, že standardně vypočteme HST a pak pouze doeliminujeme všechny nenulové prvky v hlavních sloupcích vyjma pivotů (nenulových prvků nejníže v hlavním sloupci). Ty poté podělením řádku vhodným nenulovým číslem převedeme na jedničky. Například v $\mathbb{Z}_3^{3, 4}$ bychom tento převod provedli takto: $$ \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{pmatrix} \sim \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$ Tato matice má hlavní sloupce první, druhý a poslední. Třetí sloupec je vedlejší. Matice napravo je v rHST.

Dobře, k čemu nám takovýto nový pojem je? O co je lepší, než obyčejný HST? Důvody pro důležitost tohoto pojmu jsou dva:

• praktický: je daleko snazší napsat řešení soustavy lineárních rovnic, pokud je příslušná matice soustavy v rHST. Zpětné dopočítávání hodnot vázaných proměnných (těch odpovídajících hlavním sloupcům) je triviální, výsledek píšeme hned.
• teoretický (s praktickými důsledky; důležitý i pro téma tohoto blogu!): pro zadanou homogenní soustavu lineárních rovnic je rHST kanonický, či unikátní, přesněji toto vyjádříme v následujícím tvrzení.

---

Tvrzení: Mějme podprostor $P \subset T^n$ dimenze $k \in \hat n$. Potom existuje právě jedna matice $\mathbf{A}$ hodnosti $n - k$, která je v rHST a platí $P = \{ x \in T^n \mid \mathbf{A} x = \theta \}$.

---

Důkaz: Že takováto matice skutečně existuje by mělo být zřejmé, ovládáme-li Gaussovu eliminaci a známe Frobeniovu větu. Zbývá ukázat, že je opravdu pouze jedna. To dokážeme sporem. Předpokládejme proto, že máme dvě matice $\mathbf{A}$ a $\mathbf{B}$ hodnosti $n - k$, které jsou v rHST, splňuji $$ P = \{ x \in T^n \mid \mathbf{A} x = \theta \} = \{ x \in T^n \mid \mathbf{B} x = \theta \}, $$ a jsou různé, tedy $\mathbf{A} \neq \mathbf{B}$.

Uvědomme si, že obě matice mají stejný počet hlavních ($n - k$) a vedlejších ($k$) sloupců. Musíme nyní prozkoumat dva způsoby rozdílnosti těchto matic:

• matice nemají totožné pořadí hlavních a vedlejších sloupců: tj., bez újmy na obecnosti, nechť pro $i < j$ má matice $\mathbf{A}$ $i$tý sloupec jako hlavní a $j$ jako vedlejší a matice $\mathbf{B}$ má $i$tý sloupec jako vedlejší a $j$tý jako hlavní. Potom má soustava $\mathbf{B} x = \theta$ jistě nějaké řešení, pro které je $x_i \neq 0$ a $x_{i+1} = x_{i+2} = x_n = 0$. Naopak je-li $x$ řešení $\mathbf{A} x = \theta$ splňující $x_{i+1} = x_{i+2} = x_n = 0$ pak nutně i $x_i = 0$. Množiny řešení obou soustav jsou tedy rozdílné, to je spor.
• matice mají co do pořadí totožné hlavní a vedlejší sloupce: protože se ale dle předpokladu jedná o různé matice, musí se lišit alespoň jednou hodnotou v alespoň jednom řádku. V takovémto řádku musí obě matice mít pivot na stejném místě (první nenulový prvek, jednička). Označme tento sloupec jako $i$tý. V tomto řádku se pak musí lišit hodnotou v $j$tém, $j > i$, sloupci. Položme $a := \mathbf{A}_{i,j} \neq \mathbf{B}_{i,j} =: b$. $j$tý sloupec je vedlejší sloupec matice $\mathbf{A}$ i $\mathbf{B}$ (hodnota v hlavních sloupcích se nemůže lišit, jsou tam buď nuly nebo jedničky). Soustava $\mathbf{A} x = \theta$ má jistě jako řešení $x$, pro které $x_i = -a$, $x_j = 1$ a $x_k = 0$ určitě pro $k > i$ a $k \neq j$. Pro tento vektor ale platí $\mathbf{B} x = -a + b \neq 0$ a proto není řešením homogenní soustavy s maticí $\mathbf{B}$. Opět dostáváme, že obě soustavy mají různé množiny řešení.

Tím je důkaz dokončen.

Hledání všech $k$-dimenzionálních podprostorů prostoru $T^n$

Z předchozího textu vyplývá následující pozorování: chceme-li systematicky sestrojit všechny podprostory dimenze $k$ prostoru $T^n$, tak stačí nalézt všechny matice $\mathbf{A} \in T^{n-k, n}$ v redukovaném horním stupňovitém tvaru a vyřešit příslušnou homogenní soustavu lineárních rovnic.

Pojďme si tento postup vyzkoušet například na dvoudimenzionálních ($k = 2$) podprostorech prostoru $\mathbb{Z}_3^4$ ($n = 4$). Podle textu a tabulky výše by takovýchto podprostorů mělo být $130$. Možné tvary redukovaných horních stupňovitých matic s hodností $2$ a a čtyřmi sloupci jsou

$$ \begin{aligned} \mathbf{A}_1 &= \begin{pmatrix} 1 & 0 & \alpha & \beta \\ 0 & 1 & \gamma & \delta \end{pmatrix}, & \alpha,\beta,\gamma,\delta &\in \mathbb{Z}_3, & &3^4 \ \text{možností}, \\ \mathbf{A}_2 &= \begin{pmatrix} 1 & \alpha & 0 & \beta \\ 0 & 0 & 1 & \gamma \end{pmatrix}, & \alpha,\beta,\gamma &\in \mathbb{Z}_3, & &3^3 \ \text{možností}, \\ \mathbf{A}_3 &= \begin{pmatrix} 1 & \alpha & \beta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}, & \alpha,\beta &\in \mathbb{Z}_3, & &3^2 \ \text{možností}, \\ \mathbf{A}_4 &= \begin{pmatrix} 0 & 1 & 0 & \alpha \\ 0 & 0 & 1 & \beta \end{pmatrix}, & \alpha,\beta &\in \mathbb{Z}_3, & &3^2 \ \text{možností}, \\ \mathbf{A}_5 &= \begin{pmatrix} 0 & 1 & \alpha & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}, & \alpha &\in \mathbb{Z}_3, & &3 \ \text{možnosti}, \\ \mathbf{A}_6 &= \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}, & & & &1 \ \text{možnost}. \end{aligned} $$

Pokud sečteme všechny možnosti, dostaneme očekávaně $$ 3^4 + 3^3 + 2\cdot3^2 + 3 + 1 = 130. $$ Každé z matic $\mathbf{A}_1,\ldots,\mathbf{A}_6$ a každé volbě uvedených konstant $\alpha,\beta,\gamma,\delta\in\mathbb{Z}_3$ odpovídá právě jeden podprostor, který je množinou řešení homogenní soustavy s uvažovanou maticí.

Sestrojit tyto podprostory je už snadné, například pro $\mathbf{A}_4$ a daná $\alpha, \beta \in \mathbb{Z}_3$ se jedná o následující lineární obal $$ \langle (1, 0, 0, 0),\ (0, -\alpha, -\beta, 1) \rangle. $$