Birkhoffova věta

Úkol: Nechť $ A$ je bistochastická matice, neboli matice s nezápornými elementy, jejíž všechny řádkové a sloupcové součty jsou $ 1$. Dokažte, že $ A$ je konvexní kombinací permutačních matic. Toto tvrzení se nazývá Birkhoffova věta.


Pojem konvexní kombinace vychází z geometrické představy: pro $ \vec{x}_1,\ldots, \vec{x}_n\in V$ je konvexní kombinace libovolná lineární kombinace

$\displaystyle \sum_{i=1}^n \alpha_i\vec{x}_i\,,$   kde$\displaystyle \
\alpha_1,\ldots,\alpha_n\in\langle 0;1\rangle,\ \sum_{i=1}^n \alpha_i=1\,.
$

Například pro $ V=${\bb R}$ ^2$ tvoří všechny konvexní kombinace těchto vektorů konvexní $ n$-úhelník s vrcholy v  $ \vec{x}_1,\ldots,\vec{x}_n$ (ve speciálních případech může ale být tento obrazec degenerovaný, například pokud jsou všechny vektory kolineární).

Permutační matice $ P_\pi$ je matice lineárního zobrazení {\bb R}$ ^n\to${\bb R}$ ^n$, které permutuje složky vektoru podle permutace $ \pi$, například $ P_\pi(v_1,v_2,v_3,v_4)=(v_2,v_3,v_1,v_4)$. Tato matice tedy obsahuje $ n$ jedniček na místech $ 1\pi(1),\ldots,n\pi(n)$ a zbytek jsou nuly. Jinak řečeno, v každém řádku a v každém sloupci je právě jedna jednička.

Při důkazu Birkhoffovy věty by se mohlo hodit toto tvrzení $ (\spadesuit)$:


Nechť $ G$ je bipartitní graf (viz úvod ke kapitole 7) s partitami $ V_1$ a $ V_2$ stejné velikosti. Nechť má každá množina vrcholů $ W\subseteq V_1$ alespoň $ \vert W\vert$ sousedů (v partitě $ V_2$), potom graf $ G$ obsahuje perfektní párování, tj. $ \vert V_1\vert$ různých navzájem neincidentních hran.


Řešení: Předpokládejme, že existuje bistochastická matice, která není konvexní kombinací permutačních matic. Uvažujme nějakou matici $ A$, která obsahuje mezi všemi těmito maticemi co nejméně nenulových složek. Zřejmě je počet nenulových složek matice $ A$ alespoň $ n+1$: každý řádek (a sloupec) musí obsahovat alespoň jednu nenulovou složku a bistochastická matice s $ n$ nenulovými složkami je matice permutační. Uvažujme nyní bipartitní graf, jehož jedna partita je tvořena indexy řádků matice a druhá indexy sloupců matice. Vrcholy grafu odpovídající nějakému řádkovému a sloupcovému indexu jsou spojeny hranou právě tehdy, pokud jim odpovídající prvek matice je nenulový. Nyní ukážeme, že jsou splněny předpoklady tvrzení $ (\spadesuit)$, a tedy že tento graf obsahuje perfektní párování.

Uvažujme pro matici $ A$ libovolnou množinu řádkových indexů $ I$ a označme $ J$ množinu indexů všech sloupců, v nichž se na některé řádce z $ I$ vyskytuje nenulový prvek. Součet všech prvků v řádcích s indexy z množiny $ I$ je $ \vert I\vert$ (uvažovaná matice je bistochastická) a součet všech prvků ve sloupcích s indexy z množiny $ J$ je $ \vert J\vert$. Součet prvků v těchto sloupcích na řádcích s indexy z množiny $ I$ je pak nejvýše $ \vert J\vert$, neboť na těchto řádcích jsou již v ostatních sloupcích samé nuly. Došli jsme tím k $ \vert I\vert\le\vert J\vert$, což nás opravňuje použít tvrzení $ (\spadesuit)$.

Uvažovaný bipartitní graf tedy obsahuje perfektní párování a tomu přirozeným způsobem odpovídá nějaká permutační matice, označme ji $ P$. Dále označme $ \pi$ nejmenší ze všech prvků matice $ A$ na místech nenulových prvků matice $ P$. Matici $ A$ lze zapsat jako konvexní kombinaci

$\displaystyle A=\pi P+(1-\pi) \frac{A-\pi P}{1-\pi}$ (117)

matice $ P$ a matice $ \frac{A-\pi P}{1-\pi}$. První z těchto matic je permutační, druhá je bistochastická (ověřte; proč jsou prvky $ A-\pi P$ nezáporné?) a má o alespoň jeden nenulový prvek méně než matice $ A$: o ten (ty), které jsou nejmenší na místech odpovídajících nenulovým prvkům matice $ P$. Podle předpokladu na úplném začátku řešení lze tedy matici $ \frac{A-\pi P}{1-\pi}$ vyjádřit jako konvexní kombinaci permutačních matic. Potom musí ale i matice $ A$, vyjádřená pomocí (117), být konvexní kombinací permutačních matic (lze také říci, že konvexní kombinace konvexních kombinací je opět konvexní kombinace), čímž je důkaz hotov.

$ \ast$DK$ \ast$