Rozklad degenerovaného rovnoběžnostěnu

Podívejme se na obrázek na obálce knihy Pěstujeme lineární algebru [PLA]. Vidíme projekce jednotkové krychle ve vícerozměrném prostoru {\bb R}$ ^n$ ( $ n =3,5,11,\dots$) do roviny (zde jde o velmi speciální ortogonální projekce do některého z invariantních podprostorů cyklické grupy operátorů ,,cyklická záměna souřadnic'', tedy například roviny kolmé na $ (1,1,1)$ {\bb R}$ ^3$). Zobecněme tyto obrázky následující formulací.

Úkol: Mějme $ n$ vektorů $ \vec{v}_1,\dots,\vec{v}_n$ v nějakém prostoru $ V$ dimenze $ d$ kde $ d < n$. Nechť každá $ d$-tice vybraných vektorů již tvoří nezávislý soubor vektorů (bázi $ V$). Definujeme degenerovaný rovnoběžnostěn

$\displaystyle L =$   {\Cal L}$\displaystyle (\vec{v}_1,\dots,\vec{v}_n) =\left\{
 \sum_{i =1}^n x_i \vec{v}_i\,,\ x_1,\ldots,x_n\in
 \langle 0,1\rangle\right\}.$ (17)

Dokažme, že (analogicky k obrázkům nakresleným na obálce skript [PLA]) lze každý takovýto ,,degenerovaný rovnoběžnostěn'' $ L$ rozložit na disjunktní sjednocení rovnoběžnostěnů dimenze $ d$ (speciálně pro $ d=2$ kosočtverců -- neboli rhombů -- v uvedeném příkladě).

Poznámka: Pro $ d=n$ je vztahem 17 popsán obyčejný (nedegenerovaný) rovnoběžnostěn.


Řešení: Pro zadaný bod $ \vec{u}=\sum_i x_i\vec{v}_i$ budeme $ x_i$ nazývat souřadnicemi $ \vec{u}$. Kvůli $ n>d$ nejsou tyto souřadnice jednoznačné. Pokud z  $ x_1,\ldots,x_n$ libovolně, ale pevně zvolíme $ n-d$ souřadnic a zbylých $ d$ necháme probíhat $ \langle 0;1\rangle$, potom $ \{\sum_i
x_i\vec{v}_i, x_i \in \langle 0,1\rangle \}$ popisuje nedegenerovaný $ d$-rozměrný rovnoběžnostěn (viz obrázek 7).

Budeme se zabývat rozklady, u kterých mají pevně zvolené souřadnice hodnoty 0 nebo 1. Obtíž je v tom, že pro zadané $ d$ a vektory $ \vec{v}_1,\dots,\vec{v}_n$ existuje takových rozkladů rovnoběžnostěnu $ L$ více, viz opět obrázek 7. Při důkazu potřebujeme nějak označit jeden z rozkladů, abychom s ním mohli dále pracovat.


Obrázek: Různé rozklady rovnoběžnostěnu $ L=L(\vec{v}_1,\vec{v}_2,\vec{v}_3)$, $ d=2$. Pro každou oblast ( $ A_1,B_1,C_1,$ $ A_2,B_2,C_2$) je uvedeno, jak je parametrizován její vnitřek pomocí vektorů $ \vec{v}_1,\vec{v}_2,\vec{v}_3$: pomocí $ (x_1,x_2,x_3)$ označujeme bod $ x_1\vec{v}_1+x_2\vec{v}_2+x_3\vec{v}_3$, přičemž $ 0\le x_1,x_2,x_3\le 1$.
=1mm \includegraphics[scale=0.7]{OBRAZKY/rozklad.eps} (-40,9)$ \vec{v}_1$ (-52,5)$ \vec{v}_2$ (-50.5,17.5)$ \vec{v}_3$ (-53,13)$ A_1$ (-42,13)$ B_1$ (-47,4)$ C_1$ (-4.5,9)$ \vec{v}_1$ (-16.5,5)$ \vec{v}_2$ (-15,17.5)$ \vec{v}_3$ (-8.5,6.5)$ A_2$ (-15,8)$ B_2$ (-12,14)$ C_2$

$\displaystyle \begin{array}{rlrl}
A_1:\ & (0,x_2,x_3) &\qquad A_2:\ & (1,x_2,x...
...2:\ & (x_1,1,x_3) \\
C_1:\ & (x_1,x_2,0) & C_2:\ & (x_1,x_2,1)
\end{array}
$

Obrázek 7 nás může svést k tomu, abychom zvolili ,,rozklad'', kde oněch $ n-d$ extremálních souřadnic budou samé nuly. V následujícím příkladě ale žádný rozklad nesplňuje tuto podmínku

$\displaystyle \vec{w}_1=(1,0)\,,\ \vec{w}_2=(0,1)\,,\ \vec{w}_3=(1,1)\,.$ (18)

Možným rozkladem je například $ (0,x_2,x_3)$, $ (x_1,0,x_3)$, $ (x_1,x_2,1)$. ,,Rozkladem'', kde by všechny extremální souřadnice (tedy ona jedna v tomto případě) byly nula, bychom ,,nedosáhli'' do všech rohů $ L$.

První způsob ,,označení jednoho rozkladu'' je založen na klíčové ideji ,,optimalizace souřadnic'' $ x_i$ zvoleného bodu (vektoru) $ \vec{v} = \sum_{i} x_i \vec{v}_i \in L $, $ x_i \in (0,1)$. Optimalizací zde přesněji míníme minimalizaci sumy $ s=\sum_i x_i$ při zachování podmínky $ x_i \in \langle 0,1\rangle$. Hodláme tedy tvrdit:

Tvrzení: Optimalizujeme-li souřadnice bodu (vektoru) $ \vec{v} \in L$, tak výsledná $ n$-tice koeficientů $ (x_1,\dots,x_n)$ je určena jednoznačně, a nejméně $ n-d$ z těchto čísel $ x_i$ má extremální hodnoty (tedy $ x_i \in
\{0,1\}$).

Toto tvrzení ovšem platí pouze tehdy, když je splněn

Předpoklad $ \char93 $: Píšeme-li vztah lineární závislosti jakékoliv vybrané $ (d+1)$-tice vektorů $ \vec{v}_{i_1},\dots,\vec{v}_{i_{d+1}}$ ve tvaru $ \sum_{j=1,\dots,
d+1} \alpha_j \vec{v}_{i_j} = 0$, tak $ \sum_j \alpha_j \ne 0$.

Jinými slovy chceme pouze, aby jakákoliv $ (d+1)$-tice vybraná z vektorů $ \vec{v}_1,\dots,\vec{v}_n$ byla už lineárně nezávislá, pokud ke každému vektoru $ \vec{v}_i =(v^1_i,\dots,v^d_i)$ přidáme ještě jednu souřadnici $ v^{d+1}_i =1$. Všechny $ d$-tice takovýchto vektorů jsou už nezávislé podle předpokladu na začátku.

Příklad takové ,,optimální'' volby souřadnic je na obrázku 7 vlevo.

Není těžké pochopit, že výše uvedené tvrzení je skutečně již klíčem k hledané dekompozici $ L$ na disjunktní bloky rovnoběžnostěnů; tyto bloky budou prostě zadány specifikací pořadových indexů a hodnot (0 či 1) příslušných $ n-d$ extremálních souřadnic. Volba zbylých $ d$ proměnných z intervalu $ (0,1)$ pak dává parametrický popis uvedeného bloku. Je ovšem možné, že některé z takto vytvořených bloků budou totožné.

Důkaz tvrzení: Nechť $ \vec{v} = \sum_i x_i \vec{v}_i$ je vyjádření vektoru s nejmenším možným součtem $ s=\sum_i x_i$. Předpokládejme například, že to jsou souřadnice $ x_1, x_2,
\dots x_{d+1}$, které mají neextremální hodnoty, tzn. z otevřeného intervalu $ (0,1)$, a odvodíme spor. Vskutku, platí-li $ \alpha_1 \vec{v}_1
+ \dots +\alpha_{d+1} \vec{v}_{d+1} = 0$ a je-li přitom $ \alpha_1 +\dots+ \alpha_{d+1} \ne 0$, jak předpokládáme, můžeme souřadnice $ x_1,x_2, \dots, x_{d+1}$ ,,zlepšit'' (z hlediska zmenšení jejich sumy) tím, že vezmeme nové souřadnice, pro $ i =1,2,\dots,d+1$

$\displaystyle \tilde x_i = x_i + \alpha \alpha_i $

tak, aby nové souřadnice stále ještě náležely intervalu $ (0,1)$ (stačí vzít $ \alpha$ dostatečně malé a vhodného znaménka). To ale je spor s předpokládanou optimalitou $ x_i$. Tedy víc než $ d$ hodnot optimální volby souřadnic $ x_i$ prostě nemůže nabývat hodnot z otevřeného intervalu $ (0,1)$.


Je třeba ještě ukázat, že takto vytvořené bloky jsou skutečně disjunktní, přesněji řečeno, že není možno najít dvě různá optimální vyjádření $ \vec{v} = \sum_i x_i \vec{v}_i$ a $ \vec{v} =\sum_i y_i
\vec{v}_i$ taková, u nichž by bylo nejvýše $ d$ indexů $ i$ s neextremálními hodnotami, tj. $ x_i \in (0,1)$ nebo $ y_i \in (0,1)$. Zkoumejme nyní výraz $ \sum_{i}(x_i-y_i)\vec{v}_i=0$. Pokud je $ x_i\not=y_i$ pro nejvýše $ d$ indexů, dostáváme spor s lineární nezávislostí (libovolné $ d$-tice vektorů). Pokud je $ x_i\not=y_i$ pro více než $ d$ indexů, pak je

$\displaystyle \vec{v}=\frac{1}{2}(\vec{v}+\vec{v})=\sum_i \frac{1}{2}(x_i+y_i)\vec{v}_i
$

rovněž optimální vyjádření vektoru $ \vec{v}$, které ovšem má více než $ d$ souřadnic s neextremálními hodnotami, což je spor.

Touto cestou jsme ovšem dokázali rozložitelnost $ L$ pouze za předpokladu $ \char93 $. Případy, kdy zadaná dimenze $ d$ spolu s  vektory $ \vec{v}_1,\dots,\vec{v}_n$ tento předpoklad nesplňuje, mají ,,míru nula'', tedy stačí vektory (téměř) libovolně málo pozměnit a předpoklad $ \char93 $ již bude splněn. Jako příklad si vezměme vektory $ \vec{w}_1,\vec{w}_2,\frac{1}{2}\vec{w}_3$, viz vztah (18). Lze tedy očekávat, že i pro vektory, které nesplňují podmínku $ \char93 $, bude možné rozklad provést, i když onen ,,optimální rozklad'' nebude jednoznačně určen. V našem příkladě jsou optimální rozklady

$\displaystyle \begin{array}{rlrl}
X_1:\ & (x_1,x_2,0) &\qquad X_2:\ & (0,x_2,x...
...2:\ & (x_1,0,x_3) \\
Z_1:\ & (x_1,1,x_3) & Z_2:\ & (x_1,x_2,1)
\end{array}
$

Přesvědčte se, že například bod $ \vec{w}_1+\vec{w}_2$ lze pomocí rozkladu vlevo zapsat jako $ (1,1,0)$ a pomocí rozkladu vpravo jako $ (\frac{1}{2},\frac{1}{2},1)$. Tato dvě vyjádření dávají stejný součet $ s=2$.

Druhý způsob důkazu rozložitelnosti pouze načrtneme, zkuste provést podrobně. Máme-li konvexní $ (d+1)$-dimensionální těleso, můžeme ho (ortogonálně) promítnout na nějaký $ d$-rozměrný podprostor (vraťte se k obrázku 7; tam jsme promítali na rovinu kolmou na tělesovou úhlopříčku $ (1,1,1)$). Bylo-li těleso složeno z kvádrů či obecněji rovnoběžnostěnů, máme na povrchu tohoto tělesa viditelné $ d$ rozměrné hrany (tedy rovnoběžnostěny opět, ale v nižší dimenzi; na obrázku 7 jsou to tedy tři kosočtverce) těch bloků, které vystupují na povrch. Při uvedeném promítání jsou tyto hrany buď celé ,,osvětlené'' nebo naopak celé ve stínu (rozmyslete si, co tím asi míníme pro obecné $ d$; je možné například pomocí skalárního součinu srovnávat normály ke stěnám mířící ven z tělesa s normálou k nadrovině, na níž promítáme). Takže projekci daného tělesa můžeme rozložit na $ d$-rozměrné rovnoběžnostěny dokonce dvěma způsoby: nakreslením projekce ,,osvětlené'' či naopak ,,zastíněné'' části povrchu.

Nyní je tento postup třeba iterovat. Začneme s rovnoběžnostěnem vybudovaným v  {\bb R}$ ^n$ nad vhodnými vektory $ \vec{w}_1, \dots,
\vec{w}_n$ a postupně projektujeme vzniklé konvexní útvary do nižších dimenzí $ k = n-1,\dots, d$, rozkládajíce vždy vzniklý $ k$-rozměrný konvexní útvar do rovnoběžníkových bloků podle výše uvedeného argumentu.

Zde vidíme, že (pokud jsou všechny podprostory, na které promítáme, pevně zvoleny) máme celkem $ 2^{n-d}$ možností rozkladu (zkuste si rozmyslet, zda jsou vzájemně různé). Jak souvisí tyto rozklady s tím, který jsme dostali první metodou (optimalizací souřadnic)? Polohy nadrovin, na které postupně promítáme, je třeba zvolit tak, abychom z vektorů $ \vec{w}_1,\ldots,\vec{w}_n\in${\bb R}$ ^n$ dostali správné vektory $ \vec{v}_1,\ldots,\vec{v}_n\in${\bb R}$ ^d$. Směr osvětlení pak souvisí s volbou nul a jedniček v extremálních souřadnicích.

$ \ast$MZ$ \ast$