Vlastní čísla nerozložitelných matic

Úkol: Matice $ A$ typu $ n\times n$ je nerozložitelná, pokud ji nelze permutací řádků a symetrickou permutací sloupců převést do následujícího tvaru:

$\displaystyle \left(\begin{array}{cc}B&C\\ O&D\end{array}\right)$

($ B$,$ C$,$ D$ jsou matice vhodných typů, $ B$ a $ D$ matice čtvercové, matice $ O$ je nulová matice)
Nechť $ A$ je nerozložitelná reálná matice a $ \lambda$ je její reálné vlastní číslo, které leží na hranici Gershgorinovy množiny matice $ A$ (viz příklad 9.2).

  1. Dokažte, že takové vlastní číslo musí být obsaženo ve všech Gershgorinových kruzích matice $ A$.
  2. Nechť $ A$ je libovolná symetrická diagonálně dominantní matice s kladnými prvky na diagonále. Předpokládejme, že je $ A$ nerozložitelná a že v alespoň jednom řádku platí $ A_{ii}>\sum_{i\not=j} \vert A_{ij}\vert$. Potom je $ A$ pozitivně definitní.


Řešení:


1. Nechť $ \vec{x}$ je (reálný) vlastní vektor matice $ A$ příslušný vlastnímu číslu $ \lambda$. Násobme jej vhodným číslem tak, aby $ \vert\vec{x}\vert _\infty=\max_i \vert x_i\vert=1$, a označme $ k$ některý z indexů, pro které platí $ \vert x_k\vert=1$. Stejně jako při důkazu Gershgorinovy věty (v příkladu 9.2) odvodíme, že platí (druhá rovnost je pouze jedna z rovnic $ (A-\lambda\mathbbm{1})\vec{x}=0$ zapsaná ve složkách)

$\displaystyle \vert\lambda-A_{kk}\vert=\vert\lambda-A_{kk}\vert\vert x_k\vert=
...
...=k}\vert A_{ki}\vert\vert x_i\vert\le
\sum\limits_{i\not=k}\vert A_{ki}\vert\,.$

Tedy $ \lambda$ leží v $ k$-tém z Gershgorinových kruhů, a protože leží na hranici Gershgorinovy množiny, musí ležet na hranici tohoto kruhu.

Označme nyní $ I$ množinu těch indexů $ i$, pro které platí $ \vert x_i\vert=1$. Zřejmě leží $ \lambda$ na hranici všech Gershgorinových kruhů $ K_i$ pro $ i\in I$. Je-li $ \lambda$ na hranici příslušného Gershgorinova kruhu ($ k\in I$), platí $ \vert\lambda-A_{kk}\vert=\sum_{i\not=k}\vert A_{ki}\vert$ a všechny výše uvedené nerovnosti jsou tedy rovnosti. Díky $ \sum_{k\not=i}
\vert A_{ki}\vert\vert x_i\vert=\sum_{k\not=i} \vert A_{ki}\vert$ musí být $ \vert x_i\vert$ rovno jedné, kdykoliv je $ A_{ki}$ nenulové.

Ukážeme, že množina $ I$ obsahuje všechny indexy. Předpokládejme, že existuje index, který v této množině obsažen není. Proveďme permutaci řádků a stejnou permutaci sloupců matice $ A$ tak, aby se řádky a sloupce s indexy z $ I$ staly posledními řádky a sloupci matice $ A$. Jako $ D$ označme podmatici tvořenou posledními $ \vert I\vert$ řádky a sloupci, jako $ B$, $ C$ a $ O$ označme podmatice podle zadání z příkladu. Podmatice $ O$ je nenulová (neboť $ A$ je nerozložitelná), obsahuje tedy nějaký nenulový prvek $ A_{ij}$, kde $ i\in I$ a $ j\not\in I$. Podle úvah na konci minulého odstavce by ale muselo nutně platit $ \vert x_j\vert=1$ a tedy $ j\in I$, což je spor. Tedy neexistuje index, který by nebyl v $ I$, a stejně tak ani Gershgorinův kruh, na jehož hranici by nebylo $ \lambda$.


2. Díky diagonální dominanci a symetrii je matice pozitivně semidefinitní (viz příklad 9.2) a nula může ležet na hranici její Gershgorinovy množiny. Zároveň ale podle předpokladu existuje alespoň jeden Gershgorinův kruh, ve kterém nula neleží. Podle předchozího bodu tedy nula nemůže být vlastním číslem této matice, a matice je proto dokonce pozitivně definitní. Nerozložitelnost matice nám umožnila předpokládat ,,ostrou diagonální dominanci pouze v jednom řádku''.

$ \ast$DK$ \ast$