Jedna exponenciální formule pro determinant

Úkol: Nechť $ {A} =\mathbbm{1}-{W}$ je diagonálně dominantní matice $ n\times n$, tj. matice $ {W}$ je ,,malá'' ve smyslu, že pro každý index $ i=1,\ldots,n$ je $ \sum_j \vert w_{i,j}\vert< 1$. Předpokládáme navíc pro jednoduchost, že $ W$ je matice s nulovými prvky na diagonále. Pak platí formule

$\displaystyle \mathop{\rm det}\nolimits {A} \equiv \mathop{\rm det}\nolimits (\...
...W})
 = \exp \left(\sum_{S\mbox{ \footnotesize prostá}} \log (1 -w_S) \right)\,,$ (88)

kde váhy smyček $ w_S$ (cyklů, které se mohou i protínat) jsou definovány analogicky jako váhy cyklů $ w_C$, viz podrobněji formuli níže. Symbol $ \mathbbm{1}$ značí jednotkovou matici, jak je to v této knize obvyklé.


Poznámka: Podmínka ,,malosti'' $ {W}$ zaručuje, že se uvedenou formuli nesnažíme aplikovat například v situacích, kdy determinant reálné matice je záporný. (Na druhé straně formule platí i pro komplexní matice $ {W}$ splňující podmínku nahoře.) Není totiž těžké si uvědomit, že podmínka nahoře implikuje kladnost determinantu (srovnejte s Gershgorinovou větou, příklad 9.2), tzn. souhlasnou orientaci $ {A}$ a $ \mathbbm{1}$ (pro reálné matice samozřejmě).


Řešení: Tato formule je, jak uvidíme, důsledek věty o vyjádření $ \mathop{\rm det}\nolimits \exp {A}$ pomocí $ \mathop{\rm Tr}\nolimits {A}$. Také se nám budou hodit vyjádření $ \mathop{\rm Tr}\nolimits {W}^k$ jako sumy přes všemožné smyčky délky $ k$, viz konec příkladu 6.8.

Zobecněme v teorii permutací již dříve zavedený pojem cyklu $ C$ (na indexové množině $ 1, \dots,n $) na obecnější pojem smyčky $ S$ takto: Symbolem $ (S, i_1)$ označujme smyčku s vybraným počátkem $ i_1$, definovanou jako libovolná posloupnost tvaru $ (i_1,i_2, \dots, i_k, i_1)$, se žebry $ (i_1,i_2),
\dots , (i_k,i_1)$ splňujícími podmínky $ i_1 \ne i_2 $ atd. Vícenásobné návštěvy jednoho indexu $ i$ jsou tedy u smyčky $ S$, narozdíl od cyklu $ C$, povoleny (vylučujeme pouze existenci žeber typu $ (i,i)$) a smyčka může tedy mít (na rozdíl od cyklu) libovolně velkou délku $ \vert S\vert=k$. Délka smyčky je totéž co počet jejích žeber.

Index $ i_1$ nazveme počátečním bodem smyčky $ S$. Tento počáteční bod můžeme nyní ,,zapomenout'' -- a mluvíme pak pouze o smyčce $ S$ (bez počátečního bodu). V tomto případě tedy ztotožňujeme objekty jako $ (i_1,\dots,i_n,i_1)$ a $ (i_2,\dots, i_n, i_1, i_2)$. Pro každou smyčku definujme v souvislosti s maticí $ {W}=(w_{i,j})_{i,j=1}^n$ její váhu předpisem (všimněte si znaménka minus, máme totiž matici $ {A} =\mathbbm{1}-{W}$)

$\displaystyle w_S = \prod_{(i,j)\in S} (-w_{i,j})\,,$

kde součin se bere přes všechna žebra smyčky $ S$.

Smyčku $ S$ nazveme prostou pokud ji není možno rozdělit na několik stejných smyček $ S'$ tak, aby $ S = (S')^m$ kde $ m$-tou mocninou smyčky $ S'$ rozumíme tuto smyčku probíhanou $ m$-krát za sebou. (Neznamená to samozřejmě, že bychom prostou smyčkou nemohli některé indexy navštívit vícekrát!) Je vcelku jasné (oduvodněte podrobněji), že každá smyčka $ S$ je vhodnou mocninou $ S = (S')^m$ (častěji bude ovšem $ m =1$) nějaké prosté smyčky $ S'$ a přitom takováto prostá smyčka $ S'$ je určena jednoznačně až na počáteční bod. Ten potom mužeme zvolit celkem $ \vert S'\vert$ zpusoby.

Dokažme nyní konecne vztah (88). Použijme formule $ \mathop{\rm det}\nolimits \exp M=\exp\mathop{\rm Tr}\nolimits M$

$\displaystyle \mathop{\rm det}\nolimits {A} \equiv
\mathop{\rm det}\nolimits (...
...ight] = \exp
\sum_{k =2}^{\infty} -\mathop{\rm Tr}\nolimits \frac{1}{k} {W}^k.$

Všimněme si, že faktor $ 1/k$ v rozvoji $ \log (\mathbbm{1}-{W}) =
\sum_k -(1/k) {W}^k$ (připomeňme, že pro $ k=1$ máme předpoklad $ w_{i,i} =0$) je právě kompenzován možnou volbou $ k$ různých "počátků" ve smyčce $ S$ délky $ k$ (srovnejte s příkladem 6.8). Připomeňme dále, že stopa matice $ W^k$ je dána sumou přes všechny smyčky43 $ S$ délky $ \vert S\vert=k$ s počátečním bodem

$\displaystyle \mathop{\rm Tr}\nolimits {W}^k =\sum_{(S,i_1);\ \vert S\vert = k} w_S\,.
$

Bylo by teď pěkné, kdybychom mohli říci, že se tato suma rovná $ \sum_{S;\, \vert S\vert=k} \vert S\vert w_S$, kde sčítáme pouze přes smyčky s nespecifikovaným počátečním bodem. Toto pozorování platí ale pouze pro prosté smyčky $ S$. Obecněji, příspěvek smyčky $ S^n$, kde $ S$ je prostá a má délku $ m$, najdeme ve výrazu $ \mathop{\rm Tr}\nolimits \log(\mathbbm{1}-{W})
=\sum_k (1/k) \mathop{\rm Tr}\nolimits \
{W}^k$ s koeficientem $ 1/mn$ (u členu s pořadím $ k =mn$). Na druhé straně, objevíme ho tam (při různých posunech té smyčky $ S$) celkem $ m$-krát -- což dává při sumaci přes všechny $ k =mn$ celkový příspěvek

$\displaystyle \sum_{n=1}^{\infty} \frac{m}{mn} \ (w_S)^n = - \log(1 -w_S)\,.$

Výraz $ \sum_k (1/k) \mathop{\rm Tr}\nolimits \ {W}^k$ tedy můžeme přepsat pomocí sumy přes všechny prosté smyčky a tím je důkaz skončen:

$\displaystyle \sum_{k=2}^\infty \frac{1}{k} \mathop{\rm Tr}\nolimits W^k=
\sum_{S\mbox{ \footnotesize prostá}} -\log (1-w_S)\,.
$

Tento príklad má dulezité aplikace ve statistické fyzice: Připomeňme si definici determinantu a uvědomme si, že každou permutaci na množině $ \{1,\dots,n\}$ lze ekvivalentně popsat jako soubor navzájem se neprotínajících cyklů. Sumace přes všechny permutace na množině indexů $ \{1,\dots,n\}$ je tedy sumací přes všechny možné soubory $ \{C_j\}$ vzájemně se neprotínajících cyklů $ C_j$ na $ \{1,\dots,n\}$. Můžeme tedy napsat $ \mathop{\rm det}\nolimits {A} = \mathop{\rm det}\nolimits (\mathbbm{1}-{W})$ jako44

$\displaystyle Z = \sum_{\{C_i\}} \prod_i (-w_{C_i}),$

kde sčítáme přes všechny možné kolekce navzájem se neprotínajících cyklů (nikoliv obecných smyček!) na množině indexů $ \{1,\dots,n\}$. Připomínáme, že $ a_{i,i}=1$, resp. $ w_{i,i} =0$.

Označením veličiny $ \mathop{\rm det}\nolimits {A}$ symbolem $ Z$ chceme upozornit na fakt, že takovýto objekt se ve statistické fyzice nazývá partiční sumou (a bývá označován symbolem $ Z$). Zde potom jde o partiční sumu jakéhosi abstraktního ,,plynu'', jehož ,,molekuly'' jsou právě cykly $ C$. ,,Váha'' či ,,aktivita'' $ w_C$ molekuly $ C$ se pak často píše v exponenciálním tvaru $ w_C = \exp \bigl(-E(C)\bigr),$ kde veličina $ E(C)$ je ,,energie'' molekuly (cyklu) $ C$ vynásobená Boltzmannovým faktorem $ 1/ k T$.

V našem případě (výpočet determinantu) mají ovšem váhy lichých smyček znaménko minus, a to je fyzikálně jistě neobvyklé. Uvedená analogie není tedy vubec triviální, poznamenejme, že slavné Onsagerovo řešení Isingova modelu, tedy přesný výpočet jeho volné energie (další technický termín převzatý ze statistické fyziky) muže být motivováno právě takovýmto zpusobem tzn. snahou převést výpočet příslušné partiční sumy $ Z$ na výpočet jistého determinantu. To dodatečné znaménko minus se potom ovšem musí ,,uměle vytvořit'' a právě zpusob jak to udělat tvoří jeden z hlavních triků Onsagerova řešení. (Lev D. Landau kdysi prohásil něco ve smyslu, že si celou teoretickou fyziku promyslel a osvojil znovu a od začátku sám, až měl pocit, že by to všechno vlastně mohl vytvorit sám... S výjimkou Onsagerova řešení, zduraznil.)

Zdurazněme ještě jednou, že výše uvedená formule (88) je v zásadě použitelná jen pro matice $ {W}$ s ,,malými'' členy, kdy příspěvky smyček velké délky jsou nevýznamné. Hledáme-li pak přibližnou hodnotu $ \log \mathop{\rm det}\nolimits {A}$ (po vydělení objemem jde právě o volnou energii), můžeme se omezit na sumaci přes smyčky předem omezené délky $ 2$, $ 3$ atd.

Nechť je matice $ A$ například tvaru cirkulant o rozměrech $ n\times n$ tzn. nechť je její množina indexů cyklickou grupou $ G=\{0,\ldots,n-1\}$ a její prvky mají ,,translačně invariantní'' tvar $ w_{i,j} = w(i-j\mathop{\rm mod}\nolimits n)$, kde $ w(0),\ldots,w(n-1)$ jsou pevně zadaná čísla. Skutečně zajímavý případ pro aplikace v teoretické fyzice ale nastává, až vezmeme-li jako množinu indexů nějakou vícerozměrnou Abelovu grupu jako třeba $ G\times G$ (či $ G^3$); taková grupa se nazývá též torus. $ G^2$ si znázorníme v rovině jako čtverec. Jeho protější strany ale musíme slepit (jelikož po $ n-1$ následuje 0), čímž vznikne onen torus (či též anuloid nebo duše od pneumatiky). Zatím ale berme například $ i
\in \{1,\ldots,n\}$, tj. jednorozmerný torus $ G^1$.

Definujme nyní ,,volnou energii'' naší matice $ A$

$\displaystyle h_i = -\sum_{S;\ S\owns i} \vert\mathop{\rm supp}\nolimits S\vert^{-1} (1 - \log w_S)\,, $

kde suma je přes všechny prosté smyčky obsahující index $ i$ a $ \vert\mathop{\rm supp}\nolimits S\vert$ označuje počet prvků ,,nosiče'' $ \mathop{\rm supp}\nolimits S$ smyčky $ S$, tedy množiny indexů alespoň jednou navštívených smyčkou $ S$. (Vícenásobné návštěvy se zde nepočítají.)

Všimněme si, že $ h_{i+1}$ dostaneme z $ h_i$ právě akcí výše zmíněné cyklické grupy: touto akcí se žebro $ (i,j)$ zobrazí na $ (i+1,j+1)$ (sčítání modulo $ n$), a tedy ze smyčky obsahující $ i$ vznikne smyčka obsahující $ i+1$. Pro jednu pevně zvolenou smyčku $ S$ existuje právě $ \mathop{\rm supp}\nolimits S$ různých $ h_k$, do kterých tato smyčka přispívá. Pomocí výšeuvedené akce můžeme z $ S$ získat celkem $ \mathop{\rm supp}\nolimits S$ různých smyček (,,stejného tvaru'', jen různě ,,posunuté''), které všechny obsahují index $ i$. Jelikož je ale pro cirkulant $ w_{i,j}=w_{i+1,j+1}$, je $ w_S$ invariantní vůči působení uvedené cyklické grupy, a tedy se v $ h_i$ objeví pro každý ,,tvar'' smyčky $ S$ celkem $ \mathop{\rm supp}\nolimits S$ stejných příspěvků; odtud faktor $ (\mathop{\rm supp}\nolimits S)^{-1}$.

Platí potom vztah $ \sum_{i=1}^n h_i= - \sum_S \log(1 - w_S)$ Pro cirkulant $ A$ je $ h_i\equiv h$, pročež $ \sum_i h_i=nh$, a tedy $ \mathop{\rm det}\nolimits {A} = \exp(hn) $. Uznejte, že toto je mnohem užitečnější formule, zvláště pro veliká $ n$ rádu $ 10^{27}$, než tradiční výsledek pro cirkulant uvedený např. ve skriptech [PLA] na str. 105.

Námi dokázaný vzorec (88) dává zajímavé důsledky např. i v kombinaci s Cramerovým pravidlem. V podílu příslušných dvou determinantů (vyjádřených námi pomocí exponenciál) se totiž velká většina příspěvků $ w_S$ vyruší; pro výpočet neznámé $ x_i$ pomocí Cramerova pravidla takto zbudou jen ty smyčky, které obsahují index $ i$ (zkuste si to nejprve pro pravou stranu $ \vec{b}$ rovnice $ {A}\vec{x} =
\vec{b}$ složenou ze samých jedniček, ať vidíte, jak to funguje). Tímto způsobem získáme vyjádření $ x_i$ formulemi typu

$\displaystyle x_i = \exp\left[ -\sum_S \big(\log(1-w_S) - \log(1 -{\tilde
w}_S)\big)\right],
$

kde sumace je přes všechny smyčky obsahující $ i$ a $ w_S$ resp. $ \tilde w_S$ jsou váhy smyčky $ S$ vzaté pro matici $ {A} =\mathbbm{1}-{W}$, resp. pro matici $ A$$ i$-tým sloupcem nahrazeným pravou stranou $ \vec{b}$. Pro obecnou pravou stranu $ \vec{b}$ je ovšem třeba podrobněji ověřit konvergenci příslušné sumy v exponenciále, která se objeví v čitateli Cramerova pravidla.


Poznámky: Zdá se, že přímý kombinatorický důkaz našeho základního tvrzení $ \mathop{\rm det}\nolimits (\mathbbm{1}-{W}) = \exp \big(\sum_S - \log (1
-w_S) \big)$ neexistuje resp. nebude vůbec jednoduchý. Přinejmenším autorovi tohoto cvičení není znám, a oceníme jakýkoliv úspěšný pokus v tomto směru.

Podmínka jednotek na diagonále $ A$ se dá odstranit, ovšem za cenu relativně méně hezké formulace výsledku -- promyslete.

K podmínce ,,malosti'' $ {W}$. Případ $ \sum_j \vert w_{i,j}\vert = 1$ je hraniční; podmínku pro $ {W}$ lze sice ještě asi dále trochu zeslabit (třeba jen pro některé indexy $ i$) ale dostáváme se tak už rozhodně dosti blízko oblasti, kdy řada $ \sum_S \log( 1-w_S)$ v exponenciále buď již vůbec nekonverguje nebo přinejmenším nad její případnou konvergencí (absolutní, neabsolutní či jinou) ztrácíme kontrolu.

$ \ast$MZ$ \ast$