Spektrum matice incidence součinu grafů

Úkol: Znáte-li spektrum matice incidence grafů $ G$ a $ H$, určete, jak vypadá spektrum matice incidence jejich součinu. Prozkoumejte různé typy součinů grafů (viz obrázek 13):

Obrázek: Různé typy součinů grafů.
=1mm \includegraphics[scale=0.7]{OBRAZKY/soucgraf.eps} (-101,20)$ G$ (-101,0)$ H$ (-71,5)$ G\times H$ (-42,5) $ G\mathop{\vbox{\hrule\hbox{\vrule height 5pt\hskip4.2pt\vrule}\hrule }}\nolimits H$ (-15,5) $ G\otimes H$


Řešení: Označme $ \vec{v}^i$ a $ \lambda^i$ vlastní vektory a vlastní čísla matice incidence grafu $ G$ a $ \vec{w}^j$ a $ \sigma^j$ vlastní vektory a vlastní čísla matice incidence grafu $ H$. Uvažme nyní vektory $ \vec{u}^{i,j}$ definované jako $ (\vec{u}^{i,j})_{[k,l]}=(\vec{v}^i)_k (\vec{w}^j)_l$, $ [k,l]$ jsou vrcholy součinu grafů, tedy indexy složek $ \vec{u}$. Všimněme si podobnosti s tenzorovým součinem dvou vektorů.

Nejprve nahlédneme, že vektory $ \vec{u}^{i,j}$ jsou lineárně nezávislé. Nechť jsou lineárně závislé, tedy nechť existují nenulové koeficienty $ \alpha^{i,j}$ takové, že $ \sum\limits_{i,j}\alpha^{i,j}\vec{u}^{i,j}=0$. Pro každé $ k$ a $ l$ pak platí:

$\displaystyle \sum\limits_{i,j}\alpha^{i,j} (\vec{v}^i)_k
(\vec{w}^j)_l=\sum\limits_{i} \bigg(\sum\limits_{j}\alpha^{i,j}
(\vec{w}^j)_l\bigg) (\vec{v}^i)_k=0\,.$

Protože $ \vec{v}^i$ jsou lineárně nezávislé vektory, musí být $ \sum_{j}\alpha^{i,j} (\vec{w}^j)_l=0$ pro všechna $ i$. Avšak alespoň jedna z těchto lineárních kombinací je netriviální (alespoň jedno z  $ \alpha^{i,j}$ je nenulové), tedy jsou vektory $ \vec{w}^j$ lineárně závislé. Obdrželi jsme spor, a proto jsou vektory $ \vec{u}^{i,j}$ lineárně nezávislé.

Nyní přistupme k určení spektra příslušných matic incidence:

$ \ast$DK$ \ast$