Spektrum matice incidence Petersenova grafu

Úkol: Najděte vlastní čísla matice incidence Petersenova grafu. Petersenův graf je graf na deseti vrcholech, které ztotožňujeme s dvouprvkovými podmnožinami množiny $ \{1,2,3,4,5\}$. Dva vrcholy jsou v tomto grafu spojeny hranou právě tehdy, když jim přiřazené množiny jsou disjunktní. (Návod: Zkoumejte druhou mocninu matice incidence tohoto grafu.)


Řešení: Označme matici incidence Petersenova grafu $ I_P$. Petersenův graf je 3-regulární (každý vrchol má stupeň 3). Tedy podle příkladu 7.6 je největší vlastní číslo $ I_P$ tři a je jednonásobné, protože Petersenův graf je souvislý. Dva sousední vrcholy v Petersenově grafu nemají žádného společného souseda a dva nesousední vrcholy mají právě jednoho. Odtud plyne (stačí si rozmyslet, jak se matice násobí), že platí $ I_P^2=J+2\mathbbm{1}-I_P$, kde $ J$ je matice tvořená samými jedničkami. Přepišme výše uvedenou rovnost do tvaru

$\displaystyle I_P^2+I_P-2\mathbbm{1}=J\,.$

Matice $ J$ má vlastní vektor ze samých jedniček (k jednonásobnému vlastnímu číslu 10), ten je vlastním vektorem i $ I_P$ a $ \mathbbm{1}$. Tento vektor má u $ I_P$ vlastní číslo 3. Všimněte si, že poslední rovnice odpovídá po násobení tímto vlastním vektorem zprava rovnici $ 9+3-2=10$.

Ostatní vlastní vektory všech zkoumaných matic jsou na něj kolmé (všechny tyto matice jsou symetrické) a tedy leží ve vlastním podprostoru matice $ J$ (viz příklad 9.3) odpovídajícímu vlastnímu číslu 0 (v něm leží právě vektory, které jsou kolmé na vektor tvořený samými jedničkami). Tedy pro vlastní číslo $ \lambda$ matice $ I_P$ musí platit: $ \lambda^2+\lambda-2=0$ a tedy $ \lambda\in\{1,-2\}$.

Nyní si uvědomíme, že stopa matice $ I_P$ je nulová, a tedy součet všech jejích vlastních čísel (braných v násobnostech) je nula. Zároveň musí být součet násobností deset. Těmto dvěma podmínkám vyhovíme jen tehdy, pokud má matice $ I_P$ jednoduché vlastní číslo $ 3$, pětinásobné $ 1$ a čtyřnásobné $ -2$.

$ \ast$DK$ \ast$