Spektrum matice incidence grafu

Úkol: Nechť $ I_G$ je matice incidence grafu $ G$$ n$ vrcholech, tj. $ {(I_G)}_{ij}=1$ právě tehdy, když vrchol $ i$ je spojený hranou s vrcholem $ j$; prvky na její diagonále jsou nulové. Určete vlastní čísla a vlastní vektory matice incidence pro následující grafy:

  1. Matice úplného grafu (na $ n$ vrcholech).
  2. Matice úplného bipartitního grafu s partitami o velikostech $ m$ a $ k$ (samozřejmě musí být $ m+k=n$).
  3. Matice cyklu na $ n$ vrcholech. Matici $ I_{C_n}$ vyjádřete jako součet matic $ A$ a $ B$ (viz níže) a povšimněte si, že $ A^{n-1}=B$.

    $\displaystyle A=\left(\begin{array}{ccccc}
0 & 1 & 0 & \ldots & 0 \\
0 & 0 & 1...
...& & \vdots \\
\vdots & & & 0 & 0 \\
0 & \ldots & 0 & 1 & 0
\end{array}\right)$


Řešení: Především si povšimněme, že matice incidence grafu jsou matice symetrické, a tedy jejich vlastní čísla jsou reálná a z jejich vlastních vektorů lze sestavit ortogonální bázi. Protože je stopa těchto matic nulová, sčítají se vlastní čísla matic incidence na nulu. Rozeberme nyní matice incidence ze zadání příkladu:


1. K nalezení vlastních čísel matice lze použít výsledků příkladu 9.3 (o determinantu matice $ x\mathbbm{1}+yJ$; zde $ x=-1$, $ y=1$). Nalezení vlastních čísel a vektorů této matice je však snadné i bez tohoto příkladu: matice má jednoduché vlastní číslo $ n-1$, kterému odpovídá vlastní vektor $ (1,\ldots,1)$, a $ (n-1)$-násobné vlastní číslo $ -1$, kterému odpovídá libovolný vektor kolmý na vektor $ (1,\ldots,1)$, tj. např. vektory tvaru $ (0,\ldots,0,1,-1,0,\ldots,0)$.


2. Pro větší názornost očíslujeme vrcholy tak, aby bylo za sebou nejprve všech $ m$ vrcholů z první partity a pak následovalo zbývajících $ k$ vrcholů z druhé partity. Matice incidence pak má blokový tvar

$\displaystyle I_G=\left(\begin{array}{ccccccccccccc} 0\ (m\times m) & 1\ (m\times k)\cr 1\ (k\times m) & 0\ (k\times k)\end{array}\right)\,,$ (42)

bloky mají velikost uvedenou vždy v závorkách a jsou v nich buď samé nuly, nebo samé jedničky. Tato matice incidence má $ (n-2)$-násobné vlastní číslo nula, kterému odpovídají vlastní vektory tvaru $ (0,\ldots,0,1,-1,0,\ldots,0)$ s dvěma nenulovými složkami na místech odpovídajících dvěma vrcholům v téže partitě.

Zbývající dvě vlastní čísla jsou potom $ \sqrt{mk}$ a $ -\sqrt{mk}$ a k nim přísluší vlastní vektory $ (\sqrt{k},\ldots,\sqrt{k},\sqrt{m},\ldots,\sqrt{m})$ a $ (\sqrt{k},\ldots,\sqrt{k},\allowbreak -\sqrt{m},\ldots,-\sqrt{m})$.


3. Povšimněme si nejprve, že $ A^n$ je jednotková matice -- pokud se vám nechce násobit matice, rozmyslete si, co se stane, když za sebou $ n$-krát posuneme složky $ n$-složkového vektoru o jednu nahoru. Vlastní čísla matice $ A$ mohou být tedy pouze $ n$-té komplexní odmocniny jedničky; ukážeme, že mezi vlastními čísly žádná nechybí. Existují totiž následující vlastní vektory (a k nim příslušná vlastní čísla)

$\displaystyle \varepsilon _k=\exp{(2\pi{\rm i}k/n)}\,,\ k=0,\ldots, n-1,\qquad
\vec{v}_k=(1,\varepsilon _k,\ldots,\varepsilon _k^{n-1})\,.\hskip-2pt$

Vektor $ A\vec{v}_k$ je totiž vektor, v němž cyklicky posuneme všechny složky o jednu nahoru. Vlastní čísla matice $ B$ jsou $ (n-1)$-té mocniny vlastních čísel matice $ A$ (jelikož $ A^{n-1}=B$), vlastní vektory se shodují. Vlastní čísla matice $ A+B$ jsou pak součtem příslušných vlastních čísel matic $ A$ a $ B$ a mají tedy hodnotu $ \lambda_k=2\cos{2\pi k/n}$, $ k=0,\ldots, n-1$.

Všimněte si, že mezi $ \lambda_k$ je kromě jedničky ($ \lambda_0$) -- a pro $ n$ sudé také kromě $ \lambda_{n/2}=-1$ -- každé číslo dvakrát ( $ \lambda_k=\lambda_{n-k}$). To znamená, že všechna tato vlastní čísla budou dvojnásobná. Za bázi vlastního podprostoru k $ \lambda_k$ lze zvolit například vektory $ \vec{v}_{k},\vec{v}_{n-k}$. Symetrie (reálné) matice $ A+B$ nám ale zaručuje, že lze zvolit bázi z reálných vektorů. Když si všimneme, že $ \lambda_k=\overline{\lambda_{n-k}}$, víme automaticky, že $ \vec{v}_{k}=\overline{\vec{v}_{n-k}}$ a pak už není těžké vymyslet

$\displaystyle \frac{1}{2}(\vec{v}_k+\overline{\vec{v}_{k}})=\big(1,\cos{2\pi k/n},\ldots,
\cos{2\pi (n-1) k/n}\big)\,,
$

$\displaystyle \frac{1}{2{i}}(\vec{v}_k-\overline{\vec{v}_{k}})=\big(0,\sin{2\pi k/n},\ldots,
\sin{2\pi (n-1) k/n}\big)\,.
$

$ \ast$DK$ \ast$