|
|
Inverzní matice
Milan Kunz
Moebiusova inverze
O německém matematikovi Moebiusovi jste asi slyšeli jako objeviteli plochy, která má jen jednu stranu. Vezměte dostatečně dlouhý proužek papíru, zkruťte jej o 180 stupňů a slepte jeho konce, takže dostanete jakousi obruč.
Proužek měl původně dvě strany. Zkuste si označit jednu stranu slepeného proužku čarou jdoucí středem pásku a zjistíte, že se čára uzavře, Moebiusův pás má jedinou stranu. Když proužek podél čáry rozstřihněte, dostanete dva spletené kruhy.
Dá s
e dlouho spekulovat, co by se třeba mohlo stát, kdyby Vesmír, ve kterém žijeme, měl topologii podobnou Moebiusovu pásu.My se teď nebudeme zabývat tímto problémem, ale dalším Moebiusůvým objevem, který má velmi podobné vlastnosti. Jsou to dvě funkce, z nichž jedna je inverzí druhé, takže je vlastně nelze oddělit protože existují současně. Podobnost existuje i v tom, že se také dostanou "rozstřižením", i když se tohle rozstřižení technicky provádí jinak, "rozstřižené" části se naopak spojují, v tomto případě se dvě maticové funkce se spojují v diagonální pás, ve kterém jsou samé jednotky.
Nejprve trochu impertinentní otázku: Víte co je to Erastothenovo síto?
To síto je primitivní zařízení na rýžování prvočísel. Na Erastothenovo síto se vysypou přirozená čísla a když číslo sítem propadne na dno, jedná se o prvočíslo.
Technicky je konstrukce Erastothenova síta velmi jednoduchá.
Je to matice E
, jejíž prvky e(ij) jsou 1, pokud číslo i dělí číslo j a 0, jestliže j není beze zbytku dělitelné číslem i.Prvý řádek síta jsou samé jednotky a samé jednotky jsou také na diagonále matice, která představuje dno síta. Tak tedy
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Čísla 1, 2, 3, 5 a 7 propadnou ze základní čáry na diagonálu, jsou to tedy prvočísla. Mezi jednotkami v prvém řádku není žádná nula, v druhém řádku je mezi jednotlivými jednotkami jedna nula, v třetím řádku jsou mezi jednotlivými jednotkami nuly dvě, v dalším řádku tři nuly a tak jsou mezery stále širší.
Teď najdeme matici, která při vynásobení s Erastothenovým sítem dá jednotkovou diagonální matici.
Tato matice má tvar
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
-1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
-1 |
-1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
-1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
Na diagonále Moebiusovy matice jsou vždy jednotky, m(i=j) = 1. Dovedete odhalit způsob, jakým jsou v Moebiusově matici rozdělena čísla 1, -1 a 0 mimo diagonálu? Záporný jednotkový prvek musí být v prvém sloupci u prvočísel, aby se v prvém sloupci součinu vynulovaly dva jednotkové prvky v příslušném sloupci Erastothen
ova síta. Pokud je číslo j mocnina i, pak m(i1) = 0. Dále platí, že m(ij) = -1 pro prostý dělitel čísla i. Pro čísla, která jsou součinem dělitelů čísla i platí pravidla násobení, takže mohou mít obě znaménka podle toho, kolik dělitelů čísla i -1 se násobí.Inverzní funkce
Připomenme si, že existují dva typy inverzních funkcí, additivní, kdy se jedná o součet dvou prvků
a + (-a) = 0
a multiplikativní, kdy se jedná o součin dvou prvků
a x (-a) = 1
Prvky mohou být i matice. Additivní inverzní matice je daná ma
tice, jejíž všechny prvky mají opačné znaménko. Na našem příkladě Moebiusovy inverze jsme viděli, že u multiplikativní inverzní matice jsou vztahy složitější. Při násobení matic se prvky obou matic nejen násobí, ale současně sečítají, proto se většinou v inverzní matici matice, jejíž všechny prvky jsou kladné, objeví prvky záporné.V některých případech může být inverzní matice totožná s danou maticí, pokud platí vztah
MM-1
= Ikde I
je jednotková diagonální matice. To znamená, že když násobíme matici stejnou maticí, najdeme její druhou mocninu a tato mocnina je jednotkovou diagonální maticí, potom jsou je inverzní matice totožná s danou maticí. Jsou to předevšímjednotkové permutační matice konvolucí (symetrické permutační matice), například:|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
0 |
0 |
1 |
Velmi zajímavými příklady samoinverzních matic je matice Pascalova trojúhelníku se střídavě kladnými a zápornými sloupci
|
1 |
0 |
0 |
0 |
|
1 |
-1 |
0 |
0 |
|
1 |
-2 |
1 |
0 |
|
1 |
-3 |
3 |
-1 |
případně se střídavě kladnými a zápornými řádky
|
1 |
0 |
0 |
0 |
|
-1 |
-1 |
0 |
0 |
|
1 |
2 |
1 |
0 |
|
-1 |
-3 |
-3 |
-1 |
Inverzní matice Pascalova trojúhelníku
|
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
2 |
1 |
0 |
|
1 |
3 |
3 |
1 |
má stejné hodnoty, pouze znaménka jsou rozdělena jinak
|
1 |
0 |
0 |
0 |
|
-1 |
1 |
0 |
0 |
|
1 |
-2 |
1 |
0 |
|
-1 |
3 |
-3 |
1 |
Pascalův trojúhelník je vhodným objektem i pro vysvětlení problému hledání inverzní
ch matic u matic, které nemají trojúhelníkový tvar.Pokud napíšeme Pascalův trojúhelník ve tvaru
|
1 |
1 |
1 |
1 |
|
1 |
2 |
3 |
4 |
|
1 |
3 |
6 |
10 |
|
1 |
4 |
10 |
20 |
víme, že se jedná o součin Pascalova trojúhelníka s transponovaným Pascalovým trojúhelníkem. Matici rozložíme na součin matic v trojúhelníkovém tvaru, k oběma členům najdeme inverzní matici a obě částečné inverzní matice vynásobíme. Jenom si musíme dát pozor na pořadí násobení. Podobně se dají rozkládat a obracet i některé jiné matice.
Pokud není matice symetrická, má odli
šnou inverzní matici při násobení zprava od inverzní matice při násobení zleva.Ne ke každé matici lze najít inversní matici. Základní podmínkou existence inverzní matice je existence nenulového determinantu. Ve spektru matice nesmí být nulové vlastní hodnoty, protože vlastní hodnoty inverzní matice jsou inverzemi vlastních hodnot původní matice a inverze nuly je nekonečno.
Nebudeme se zabývat technickými problémy řešení problému hledání inverzních matic, od toho přece máme počítače, ale budeme se zabývat některými zajímavými problémy, které pomáhají pochopit význam inverzních matic, protože mají zcela konkretní význam.
Matice cest
Kvadratická forma STS incidenční matice orientovaného grafu S je známa jako Laplace-Kirchhoffova matice. O těchto maticích je známo, že mají jednu nulovou vlastní hodnotu.
Protože obě kvadratické formy STS i SST mají shodná spektra, potom kvadratická forma SST stromů s (n-1) sloupci a řádky nemá žádnou nulovou vlastní hodnotu a má tedy inverzní matici.
Abychom si zjednodušili práci
a mohli pracovat s celými čísly, nebudeme hledat inverzní matici, ale její n-násobek.Diagonální prvky kvadratická formy incidenční matice orientovaného grafu
SST jsou vždy 2, mimodiagonální prvky jsou 0, pokud dvě orientované hrany nemají společný vrchol, 1, když orientované hrany se společným vrcholem mají opačnou orientaci nebo obě vycházejí ze společného vrcholu a -1, když orientované hrany na sebe navazují.Diagonální prvky inverzních matic W
počítají, kolikrát se orientovaná hrana objevila ve všech cestách ve stromu, mimodiagonální prvky inverzních matic W počítají, kolikrát se orientovaná hrana i objevila ve všech cestách ve stromu společně s diagonální hranou j.Pro lineární řetězce L(n) jsou inverzní matice postupně
pro n = 4
|
3 |
2 |
1 |
|
2 |
4 |
2 |
|
1 |
2 |
3 |
pro n = 5
|
4 |
3 |
2 |
1 |
|
3 |
6 |
4 |
2 |
|
2 |
4 |
6 |
3 |
|
1 |
2 |
3 |
4 |
pro n = 6
|
5 |
4 |
3 |
2 |
1 |
|
4 |
8 |
6 |
4 |
2 |
|
3 |
6 |
9 |
6 |
3 |
|
2 |
4 |
6 |
8 |
4 |
|
1 |
2 |
3 |
4 |
5 |
Stopy matic (součty diagonálních prvků) jsou postupně(4), 10, 20, 35. Tato čísla jsou v chemii známa jako Wienerova čísla (záměrně jsem zvolil označení matic
W). Harry Wiener byl skromný jmenovec známého Norberta Wienera. Ještě před druhou světovou válkou zjistil, že body varů alkanů (methan, ethan, propan, atd.) korelují se součtem všech vzdáleností (počty vazeb) mezi uhlíky alkanů.Tento objev n
ejprve zapadl, později se však zjistilo, že má obecnější platnost. Wienerovo číslo bylo formálně spojeno se součtem prvků matice vzdáleností (o těchto maticích až příště). Tady se však objevilo jako stopa matice a tedy součet jejích vlastních hodnot.Vyvra
cení matic z kořenůU některých matic důležitých pro techniku s jednou nulovou vlastní hodnotou neexistují inversní matice. Patří k nim Laplace-Kirchhoffovy matice. Laplace je spojil s mechanikou nebeských těles a Kirchhoff s elektrickými obvody, odpory v sítích a hledáním proudů protékajících mezi jednotlivými uzly sítě. Nevím, jak se dnes učí řešení tohoto problému na školách, ale za mých mladých let se hledaly počty stromů, na které je možné síť rozdělit.
Při tom existují dvě řešení problému.
Prvé bylo z
námo z teorie kódování, bez aplikace na teorii grafů, a platí přesně jen pro stromy. Je spojené s pojmem kořenu a u cyklických grafů se jedná o jakési náhradní a dílčí řešení.U každého grafu můžeme si zvolit jeden jeho vrchol a posadit jej na tento vrchol. Pak můžeme značit cesty od kořene ke všem ostatním vrcholům v matici cest, jejímiž prvky budou 1, pokud vrchol leží v cestě mezi kořenem a vrcholem i a 0 jindy. Samotný kořen ještě označíme v matici osamělou jednotkou.
Pro lineární řetězce bude příslušná
matice W mít tvar|
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
Invezní matice se najde velmi snadno, protože má méně nenulových prvků:
|
1 |
0 |
0 |
0 |
0 |
|
-1 |
1 |
0 |
0 |
0 |
|
0 |
-1 |
1 |
0 |
0 |
|
0 |
0 |
-1 |
1 |
0 |
|
0 |
0 |
0 |
-1 |
1 |
Pomineme-li prvý řádek, pak je to incidenční mati
ce S orientovaného lineární řetězce L(5). Když k této matici přidáme další hranu jiným způsobem|
1 |
0 |
0 |
0 |
|
-1 |
1 |
0 |
0 |
|
0 |
-1 |
1 |
0 |
|
0 |
0 |
-1 |
1 |
|
1 |
0 |
0 |
-1 |
dostaneme jako kvadratickou formu S
TS zakořeněnou incidenční matici S orientovaného cyklu C(4).|
3 |
-1 |
0 |
-1 |
|
-1 |
2 |
-1 |
0 |
|
0 |
-1 |
2 |
-1 |
|
-1 |
0 |
-1 |
2 |
Při hledání invezní matice si úkol rozdělíme na dvě části. Nejprve si uvědomíme, že jednotkový vektor sloupec je vlastní vektor pro nulovou vlastní hodnotu nezakořeněné kvadratické formy
STS cyklu C(4). Když shora uvedenou matici vynásobíme čtvercovou jednotkovou maticí, dostaneme jako produkt jednotkový prvý řádek, ostatní řádky budou samé nuly. K nim můžeme přidat inverzi podmatice, kterou jsme už řešili shora L(n) pro n = 4. Násobíme všechny hodnoty 4x:|
4 |
4 |
4 |
4 |
|
4 |
7 |
6 |
5 |
|
4 |
6 |
8 |
6 |
|
4 |
5 |
6 |
7 |
Jednotkový řádek je zbytek kořenu, ale další tři řádky mimo prvý nulový sloupec jsou kvadratická forma
SST lineárního řetězce L(4). Zbyla by nám po odstranění zakořeněného vrcholu.Jedná se o tak zvaný Ulamův subgraf. Ulam vyslovil hypotézu, že ze všech n podgrafů vzniklých z grafu odstraněním jednoho vrcholu a s ním incidentních hran se dá rekonstruovat původní graf. Důkaz tohoto tvrzení je obtížný, ale bylo dokázáno, že součet charakteristických polynomiálů kvadratických forem
STS všech n podgrafů je diferencí charakteristického polynomiálu původního grafu, takže se z nich dá původní polynomiál rekonstruovat podle pravidel integrace.No a součet inverzních matic všech Ulamových podgrafů (příslušně upravený) dá pseudoinverzní matici původního grafu. Pseudoinverzní matice je to proto, že po vynásobení s původní maticí se nedostane jednotková diagonální matice
I, ale součet této matice s maticí -1/nJJT, kde J je jednotkový sloupec.V našem příkladě pro cykl C(4) je to 1/16 matice
|
10 |
4 |
2 |
4 |
|
4 |
10 |
4 |
2 |
|
2 |
4 |
10 |
4 |
|
4 |
2 |
4 |
10 |
Vraťme se ještě k matici diference cyklu C(4) 1/4
|
3 |
2 |
1 |
|
2 |
4 |
2 |
|
1 |
2 |
3 |
U elektrických obvodů diagonální prvky prvky můžeme interpretovat jako vodivosti sítě vzhledem k vrcholu 1. Za předpokladu jednotkových odporů mezi vrcholy sítě je odpor cesty 1-2 roven 1, odpor cesty 1-4-3-2 je roven 3, součet proudů je 1 + 1/3 = 4/3 a vodivost mezi vrcholy 1-2 je 3/4. Mezi vrcholy 1-3 je to 1/2 + 1/2 = 1.
Závěrečné poznámky
Existence pseudoinverzních matic sítí má velmi závažné důsledky nejen pro techniku, ale také pro řadu vědeckých oborů.
Laplace je znám jako zastánce determinizmu. Jestliže si představíme, že Vesmír přechází v každém okamžiku z jednoho stavu do druhého, pak lze tento přechod vyjádřit incidenční maticí
S. K této matici si lze představit kvadratické formy. Laplace-Kirchhoffovy matice má zobecněnou inverzi. Otázkou je, jak rychle se tato inverze vytváří a jak rychle působí vzdálené změny.Literatura
M. Kunz: Path and walk matrices of trees, Coll. Czech. Chem. Commun., 54 (1989) 2148- 2155.
M. Kunz: A Moebius inversion of the Ulam subgraphs conjecture, J. Math. Chem., 9 (1992) 297-305.
M. Kunz: Inverting Laplace-Kirchhoff matrices from their roots, J. Chem. Inform. Comput. Sci., 1996, 36, 822-824.
Trinajstic,N. The Characteristic Polynomial of a Graph. J.Math.Chem., 1988,2,197-215.