Laplaceova matice

Úkol: Nechť $ G$ je orientovaný graf s $ n$ vrcholy a $ m$ hranami. Nechť $ B$ označuje matici typu $ n\times m$ takovou, že $ B_{ij}=-1$, pokud hrana $ j$ vychází z vrcholu $ i$, $ B_{ij}=1$, pokud hrana $ j$ vchází do vrcholu $ i$, $ B_{ij}=0$ jinak.

Označme dále $ Q$ matici typu $ n\times n$ takovou, že $ Q_{ii}$ je rovno stupni vrcholu $ i$, $ Q_{ij}=-1$ pokud je vrchol $ i$ spojený hranou s vrcholem $ j$ a $ Q_{ij}=0$ jinak. Tato matice se nazývá Laplaceova.

Dokažte, že $ Q$ je singulární a $ Q=BB^T$. Označme $ Q'$ matici, která vznikne vynecháním prvního řádku a sloupce z matice $ Q$ a $ B'$ matici, která vznikne vynecháním prvního řádku z matice $ B$. Potom platí $ Q'=B'{B'}^T$.


Řešení: Vztah $ Q=BB^T$ je zřejmý, pokud si uvědomíme, že $ Q_{ij}=\vec{b}_i\cdot \vec{b}_j$, kde $ \vec{b}_i$ je $ i$-tý řádek matice $ B$. Uvažme vektor $ \vec{w}^T=
(1,\ldots,1)$. Potom $ Q\vec{w}$ je nulový vektor, a matice $ Q$ je tedy singulární. Vztah $ Q'=B'B'^T$ je též zřejmý.

$ \ast$DK$ \ast$