V sérii statí o kombinatorice a lineární algebře se dostáváme do oblasti, kterou můžeme označit za obtížnou. Její obtížnost je hned dvojího druhu, technická a koncepční.

Technické nesnáze spojené s výpočty vlastních hodnot a vlastních vektorů matic větších rozměrů než tři jsou veliké a s opravdu velkými maticemi i počítače mají mnoho práce. Technické potíže s výpočty však vedly k objevení řady zajímavých vztahů umožňujících výpočty vlastních hodnot jednoduchými triky. Tyto triky jsou však založeny na hlubokých souvislostech.

Koncepční nesnáze jsou dány tím, že se jedná o vztahy skryté až tajemné. Podobně jako kapky deště rozkládají sluneční světlo na spektrum světel různé vlnových délek, které se nám jeví jako duha, tak vlastní hodnoty tvoří spektrum matice. Přirovnání může pokračovat. Na konci duhy se prý skrývá poklad, spektra matic jsou často klíčem pro řešení vědeckých a technických problémů. Chvění hudebních nástrojů a technických konstrukcí je příkladem, kdy vlastní hodnoty přímo vnímáme, aniž bychom je museli počítat. U hudebních nástrojů slyšíme tóny, u technických konstrukcí mohou kmity vést k destrukci staveb, třeba mostů. I naše těla jsou vlastně konstrukcemi plnými kmitů molekul.

Podobně jako se fyzikové nespoléhají na náhodný vznik duhy, ale používají k rozkladu světla hranoly, tak se i matematikové naučili rozkládat matice, nebo je upravovat na průzračný tvar

Permanent a determinant

Matice s m řádky a n sloupci obsahuje nm prvků. Na šachovnici můžeme umístit figury šachové hry podle určitých pravidel, třeba aby se koně vzájemně neohrožovali. Analogicky můžeme vybírat prvky matice, třeba aby nebyly ve stejném sloupci.

Matice má n sloupců, proto dostaneme n řad. Je zřejmé, že taková řada nemůže být delší než počet řádků matice. Vybrané prvky se násobí podobným způsobem, jako se tvořily permutace. Součet všech permutací se nazývá permanent.

Existuje celá teorie permanentů, kdy se hledají permanenty různých typů matic. V některých případech jsou výsledky shodné s klasickými kombinatorickými identitami.

Jen pro ukázku několik jednoduchých matic:

Permanent je 6. Počet členů permanentu se už proti předešlému příkladu nezvětšil. Prodloužení řetězce ze dvou prvků na tři nemá vliv na výsledek vzhledem k jednotkovým hodnotám.

S permanentem souvisí úzce determinant. Ten se počítá podobně jako permanent, pouze s tím rozdílem, že polovina permutací prvků dostane záporné znaménko podle inverzního pořadí násobení prvků. Pokud matice není čtvercová, determinant je automaticky nulový. To si můžeme vysvětlit tak, že si představíme matici rozšířenou na čtvercovou o nulové prvky. Ty se objeví v každém členu součtu tvořícího determinant, takže součet je nulový. Determinant matice (2,2) s prvky
 

a	b
c	d

je rozdíl adi + bfg + ech - afg - bci - edg. Pro jeho výpočet existuje technická úprava matice jejím rozšířením o dva řádky, aby se snadněji odečetly všechny prvky a b e
 

a	b	e
c	d	f
g	h	i
a	b	e
c	d	f

Na druhé straně nalezení determinantu matic určitého typu může být zcela snadné. Nejsnadnější je to v případě, že matice je diagonální, protože potom rozvoj determinantu má nejvýše jeden nenulový člen. To platí i v případě, že matice má trojúhelníkový tvar.

Zjistilo se, že určité operace s maticemi, jako je přičtení některého řádku či sloupce k jiným, nemění hodnotu determinantu. Taková změna mění všechny kladné i záporné prvky determinantu stejným způsobem, takže se změny vzájemně vyruší. Těmito operacemi lze převést matici na trojúhelníkový tvar v méně krocích, než při hledání všech permutací. Proto je snazší výpočet determinantu tímto způsobem.

Determinant je důležitý pro další operace s maticemi, především pro otázku existence inversní matice k dané matici. Aby existovala inversní matice, nesmí být determinant nulový. Toto tvrzení však není zcela přesné.

I když je determinant nulový, mohou existovat zobecněné inversní matice, pokud ta “nulovost” není příliš hluboká. Abychom toto tvrzení mohli vysvětlit, musíme nejprve objasnit, co determinant vlastně je.

Charakteristický polynomiál

Matice jsou operátory působící na vektory, buď sloupce, nebo řádky v závislosti na tom v jakém pořadí se operace násobení provádí. K matici M můžeme přičíst nebo odečíst jinou matici. Pokud zvolíme jako tuto matici diagonální prvky x (xI), dostane se při výpočtu determinantu matice (xI - M) výraz obsahující mocniny prvku x od 0 do n, přičemž některé z nich mohou chybět, poněvadž se vynulují.

je výsledek (x -a)(x - d)(x - i) + bfg + ech - (x- a)fg - bc(x -i) - e(x -d)g. Po provedení všech naznačených operací se dostane charakteristický polynomiál. Pokud tento charakteristický polynomiál položíme rovný nule, lze vzniklou rovnici n-tého stupně řešit nalezením hodnot x, které rovnici vyhovují. Tyto hodnoty jsou ony hledané vlastní hodnoty matice.

Vlastní vektory jsou vektory, pro které daná matice působí jako skalár, což znamená, že při násobení určité matice jejím vlastním vektorem matice násobí každý prvek vlastního vektoru vlastní hodnotou

V našem příkladě jsou základem vlastních vektorů hodnoty (1, 1) a (-1, 1), protože 2*1 + 1*1 = 3 i 1*1 + 2*1 = 3 a 2*(-1) + 1*1 = -1 a 1*(-1) + 2*1 = 1. Použil jsem výraz základ vlastních vektorů, protože na vlastní vektory je kladena další podmínka, jejich skalární součin musí být rovný 1, takže oba vektory musíme dělit odmocninou ze dvou.

Takové normalizované vlastní vektory promění svou vlastní matici, pokud ji sevřou do skalárního součinu v diagonální matici vlastních hodnot. Lze tedy přirovnat matice vlastních vektorů ke krystalům dvojlomného vápence, které brání průchodu polarizovaného světla, ale při správném nastavení polarizovaného světlo (spektrum) propouštějí.

Pokud matice M není čtvercová, mají podobný význam jako vlastní hodnoty hodnoty singulární, což jsou vlastní hodnoty vnitřních a vnějších skalárních součinů MM^T a M^TM. Pokud matice M je symetrická, pak jsou oba skalární součiny MM^T a M^T shodné a singulární hodnoty jsou druhé mocniny vlastních hodnot matice M. Tím jsme vlastně prozradili další pravidlo, vlastní hodnoty mocnin matic jsou příslušnými mocninami vlastních hodnot. Tento vztah lze využít i pro výpočet vlastních hodnot některých matic (viz přílohy).

Vnitřní skalární součin jednotkového sloupce J je n. To je singulární hodnota tohoto sloupce a také jediná nenulová hodnota matice tvořené samými jednotkami, což je vnější skalární součin jednotkového sloupce J.

Pokud k matici přičteme nebo od ní odečteme nějaký násobek k jednotkové diagonální matice I, potom se změní všechny vlastní hodnoty o tuto hodnotu k.

Počítačové programy často vypočítají vlastní hodnoty současně s vlastními vektory.

Jak jsme se už zmínili, někdy lze vypočítat vlastní hodnoty zcela jednoduchými postupy. Zvláště v případě, kdy řešená matice je vnitřním nebo vnějším skalárním součinem incidenční matice orientovaného grafu S, pak pro výpočet vlastních hodnot lze použít celou řadu vztahů, které zdánlivě nemají s maticí nic společného.

Skalární součin S^TS je znám jako Laplace-Kirchhoffova matice. Samotné pojmenování napovídá, že takové matice nalézají uplatnění v nebeské mechanice (Laplace) a v elektrotechnice při výpočtu elektrických obvodů (Kirchhoff). A největší uplatnění nalezly v chemii, kde se ukázalo, že fyzikální vlastnosti molekul odpovídají maticím tyto molekuly popisujících, ať jsou to přímo Laplace-Kirchhoffovy matice, nebo její mimodiagonální části, matice sousedství.

Skalární součin Laplace-Kirchhoffovy matice S^TS má tvar (V - A), kde V je diagonální matice registrující počet hran sousedících s vrcholy j a A je matice sousedství, ve které nenulové prvky ukazují počet hran spojujících dva vrcholy (při tom není nutné, aby tyto prvky byla celá čísla, postačující podmínka je, aby součty prvků matice v řádcích a sloupcích byly nulové).

Charakteristický polynomiál matic sousedství acyklických grafů (bez cyklů a smyček) se počítá velmi snadno (pokud graf není příliš veliký, pak je to ovšem opět technický problém).  Najdou se všechny možné obrazce jednotlivých hran, nesousedících dvojic hran, trojic hran a tak dále. Tyto počty se střídavými znaménky plus a minus tvoří koeficienty u sudých mocnin x (v případě grafů se sudým počtem vrcholů) nebo u lichých mocnin x (v případě grafů se lichým počtem vrcholů).

Tak u lineárního řetězce se čtyřmi vrcholy a třemi hranami jsou to tři hrany a jedna dvojice, u lineárního řetězce se šesti vrcholy a pěti hranami je to pět hran, šest dvojic a jedna trojice.

U grafů s cykly se takto vypočtený acyklický polynomiál musí opravit koeficienty počítajícími dvakrát počet všech cyklů různých délek.

U jednoduchých cyklů charakteristický polynomiál matic sousedství má jednoduchý tvar x^n -1 = 0. Hledání vlastních hodnot se změní na problém řešení tohoto typu rovnic pomocí substitucí, vedoucí k součtu sinu a kosinu.

Matice sousedství prostých grafů mají nulovou diagonálu. Na diagonále se však může zaznamenávat existence smyček. Charakteristický polynomiál matic sousedství grafů se smyčkami se dá vypočítat podobně jako u prostých grafů. Smyčky tvoří obrazce samostatně jako hrany, avšak také obrazce v kombinaci s hranami. Počet jednoduchých smyček se objeví jako koeficient u vynechané mocniny x, kombinace smyčky s jednou hranou u další vynechané mocniny x.

Vzhledem k tomu, že Laplace-Kirchhoffova matice S^TS má tvar (V - A) a jak jsme řekli, pokud diagonální matice V má všechny hodnoty stejné, existuje vztah mezi vlastními hodnotami této matice a vlastními hodnotami matice sousedství. Vztah je jednoduchý v případě pravidelných grafů, kde všechny vrcholy mají stejnou hodnotu incidence.

Laplace-Kirchhoffovy matice S^TS úplných grafů mají hodnotu diagonální matice V (n - 1). Mimodiagonální prvky jsou -1. To je stejné, jako kdyby hodnota diagonální matice V byla n a od této matice se odečetla čtvercová jednotková matice. To dá (n-1) vlastních hodnot rovných n a jednu nulovou vlastní hodnotu. A podobně jako se úplný graf rozštěpí na dvojici komplementárních grafů, tak se rozštěpí spektrum úplného grafu.

Jednoduchý příklad:

Matice
 

1	-1	0
-1	2	-1
0	-1	1

Důkaz tohoto tvrzení je založen na vlastnostech zobecněných inverzních matic. Matici komplementárního grafu lze získat snadno ze znalosti zobecněné inverzní matice.

Roubování stromů a rekonstrukce charakteristického polynomiálu

U matic sousedství stromů lze při hledání charakteristického polynomiálu použít techniku roubování. Při přidání nového listu je charakteristický polynomiál součtem součinu charakteristického polynomiálu původního stromu násobeného členem x a charakteristického polynomiálu původního stromu osekaného o všechny větve sousedící s vrcholem, ke kterému byl list přidán (viz přílohu). Takové osekání odstraní z matice grafu i-tý sloupec a řádek (sloupec z matice incidence), což lze považovat za diferenci příslušného grafu a jeho matice.

Takové diference grafu jsou známy jako Ulamovy podgrafy. Ulam vyslovil domněnku, že ze znalosti všech takových podgrafů lze rekonstruovat původní graf. Pokud nejsou vrcholy označeny, tak to není u velkých grafů snadná záležitost. Velkým problémem je identifikace vrcholů v různých podgrafech.

Rekonstrukce charakteristického polynomiálu ze znalostí charakteristických polynomiálů všech Ulamových podgrafů je však snadná operace. Charakteristické polynomiály všech Ulamových podgrafů se jednoduše sečtou a výsledek se považuje za diferenciál charakteristického polynomiálu vytvořený podle pravidel diferenciace. Člen nx^(n-1) diference odpovídá původnímu členu x^n atd.

U stromů lze provést rekonstrukci polynomiálů i pro diferenciaci podle hran.

Existuje ještě řada dalších pravidel a vztahů, které lze využít pro výpočet nebo odhad charakteristických polynomiálů. Tak třeba matice sousedství linkových cyklických grafů (graf tvořený mimodiagonálními prvky matice SS^T) obsahují vlastní hodnoty -2, aby se eliminovalo (m - n) diagonálních prvků matice SS^T s hodnotou 2 (viz přílohu).

Nejobecnější metodou výpočtu charakteristických polynomiálů je technika, jejímiž autory jsou La Verrier, Frame a Fadějev. Tito pánové žili v různých dobách. To svědčí o tom, že tato technika byla znovu objevena, zapomenuta a znovu objevena několikrát.

Metoda spočívá v opakujícím se odečítání stopy matice nebo jejích násobků a násobení takto získaných matic původní maticí. Stopa matice se rovná součtu vlastních hodnot a v násobcích se násobí každá vlastní hodnota těmito součty. Postupně se tak dostávají součiny dvojic, trojic a obecně n-tic vlastních hodnot a rekonstruuje se charakteristický polynomiál.

Literatura

K. Balasubramanian, Computer generation of distance polynomials of graphs, J. Comput. Chem., 11 (1990) 829-836.

D. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs, Deutcher Verlag der Wissenshaften, Berlin, 1980.

Trinajstic, N. The Characteristic Polynomial of a Graph. J. Math. Chem., 1988, 2, 197-215.
 

časopis o přírodě, vědě a civilizaci