Algorytm Lagrange'a

Algorytm Lagrange'a jest użyteczną procedurą, którą wykorzystamy do dowodu następującego głównego wyniku w tej części.

Twierdzenie (#) Każda macierz symetryczna $ A=A^T\in\M{n}{n}{\K} $ jest kongruentna z macierzą diagonalną, tzn.\ istnieje macierz odwracalna $ C\in\M{n}{n}{\K} $ taka, że

$$C^TAC=\mk{ccc}  {d_1&&\0\vspace{-2pt}\\  &\ddots&\vspace{-2pt}\\  \0&&d_n} ,$$

przy czym wyrazy niezerowe na przekątnej poprzedzają wyrazy zerowe

Zanim przystąpimy do dowodu tego twierdzenia, podamy jego interpretację w języku form kwadratowych na $ \K^n $.

Stwierdzenie (#) Dla każdej niezerowej formy kwadratowej $ Q:\K^n\to\K $ istnieje izomorfizm $ \ps:\K^n\to\K^n $ taki, że $ Q\circ S(Y)=\sum_{j=1}^r d_jy_j^2 $, dla $ Y=[y_1,\ldots,y_n]^T $, gdzie $ d_j\neq 0 $, $ j\leq r=\r(Q) $.

W dowodzie twierdzenia będziemy wykonywać operacje elementarne na wierszach i kolumnach $ A $. Zauważmy, że jeśli macierz elementarna $ M $ jest macierzą operacji elementarnej $ \E $ na wierszach (czyli zgodnie z Uwagą [link], iloczyn $ MA $ jest macierzą otrzymaną z $ A $ przez wykonanie operacji $ \E $ na jej wierszach)

to iloczyn $ AM^T=(MA^T)^T $ powstaje z $ A $ przez wykonanie odpowiedniej operacji na jej kolumnach.

{\bf Dowód Twierdzenia [link] (algorytm Lagrange'a).} Niech $ A=[a_{ij}]_{i,j=1}^n\in\M{n}{n}{\K} $ będzie niezerową macierzą symetryczną.

(I) Załóżmy, że $ a_{11}\neq 0 $. Wówczas odejmując pierwszy wiersz pomnożony przez $ \frac{a_{i1}}{a_{11}} $ od $ i $-tego, dla $ i\geq 2 $, wyzerujemy wszystkie wyrazy pierwszej kolumny pod $ a_{11} $. Jeśli $ M $ jest iloczynem odpowiednich macierzy elementarnych, to z $ A=A^T $ wynika, że $ (MAM^T)^T=(M^T)^TA^TM^T= MAM^T $, więc iloczyn $ MAM^T $ jest symetryczną macierzą postaci

$$MAM^T=\mk{c|ccc}{ a_{11}&0&\cdots&0\\\hline 0&&&\\ \vdots&&B&\\ 0&&&},$$

(operowanie pierwszą kolumną $ MA $ na kolejnych kolumnach zeruje wyrazy $ a_{12}=a_{21},\ldots,a_{1n}= a_{n1} $ pierwszego wiersza na prawo od $ a_{11} $). W szczególności, macierz $ B $ jest symetryczna.

(II) Jeśli $ a_{11}=0 $ ale $ a_{ii}\neq 0 $ dla pewnego $ i>1 $, to dla macierzy $ M $ operacji elementarnej zamieniającej pierwszy wiersz z $ i $-tym macierz symetryczna $ MAM^T $ ma w lewym górnym rogu wyraz $ a_{ii} $, a więc spełnia warunek w (I).

(III) Jeśli $ a_{ii}=0 $ dla $ i=1,\ldots,n $, to z $ A\neq\0 $ i $ A=A^T $ wynika, że istnieją $ i>j $ takie, że $ a_{ij}\neq 0 $. Wzorujemy się wtedy na kongruencji z Przykładu [link] (a) przyjmując $ M=[m_{kl}]_{k,l=1}^n $, gdzie wyrazy na przekątnej $ M $ są jedynkami, $ m_{ij}=1, m_{ji}=-1 $, a pozostałe wyrazy $ M $ są zerowe. Macierz symetryczna $ MAM^T $ ma na przekątnej niezerowe wyrazy $ \mp 2a_{ij} $, a więc spełnia warunek w (II) (lub w (I), jeśli $ j=1 $).

Tak więc, mnożąc odpowiednie macierze opisane w (I),(II),(III) otrzymamy macierz odwracalną $ M_1\in\M{n}{n}{\K} $ taką, że

$$M_1AM_1^T=\mk{c|ccc}{ d_{1}&0&\cdots&0\\\hline 0&&&\\ \vdots&&A_1&\\ 0&&&}, \ A_1=A_1^T, \ d_1\neq 0.$$

Jeśli macierz $ A_1\neq \0 $, to powtarzając tę procedurę dla $ A_1 $ otrzymamy macierz odwracalną $ M_2\in\M{n}{n}{\K} $ (postaci $ MM_1 $) taką, że

$$ M_2AM_2^T=\mk{cc|cc}{ d_{1}&0&\cdots&0\\ 0&d_2&\cdots&0\\\hline \vdots&\vdots&\ \ A_2&\\ 0&0&&}, \ A_2=A_2^T, \ d_1,d_2\neq 0.$$

Po $ r=\r A $ takich krokach znajdziemy macierz odwracalną $ M_r\in\M{n}{n}{\K} $ taką, że

$$M_rAM_r^T=\mk{ccc|c}{ d_{1}&&0&\0\\ &\ddots&&\\ 0&&d_r&\0\\\hline \0&&\0&\0}, \ d_1,\ldots,d_r\neq 0$$

i przyjmujemy $ C=M_r^T $. \null
\null$ \blacksquare $    

Uwaga (#) Macierz $ M_r=C^T $ występującą w dowodzie twierdzenia można otrzymać, podobnie jak przy odwracaniu macierzy, z macierzy jednostkowej $ I_n $ wykonując na jej wierszach operacje takie same jak wykonywane w trakcie redukcji operacje na wierszach macierzy $ A $ (mnożenie z lewej strony przez macierz $ M $ opisaną w (III) odpowiada zastąpieniu $ j $-tego wiersza przez różnicę $ j $-tego i $ i $-tego wiersza, zaś $ i $-tego wiersza przez sumę tych wierszy, zob.\ Przykład [link] (a)).

Twierdzenie [link] można sformułować równoważnie w następujący sposób.

Twierdzenie (#) Dla każdego symetrycznego funkcjonału dwuliniowego $ h:V\times V\to \K $ istnieje baza $ (\be_1,\ldots,\be_n) $ w $ V $ taka, że $ h(\be_i,\be_j)=0 $ dla $ i\neq j $ oraz $ h(\be_j,\be_j)=0 $ dla $ j>\r(h) $.

Niezależnie od wyprowadzenia Twierdzenia [link] z [link], warto też podać bezpośrednie uzasadnienie, które jest interpretacją algorytmu Lagrange'a w języku funkcjonałów dwuliniowych, podkreślającą związek tego algorytmu z procedurą wykorzystaną przy ortogonalizacji Grama-Schmidta.

{\bf Dowód Twierdzenia [link].} Załóżmy, że $ h $ jest funkcjonałem niezerowym i ustalmy dowolną bazę $ (\al_1,\ldots,\al_n) $ w przestrzeni $ V $.

(I) Jeśli $ h(\al_1,\al_1)\neq 0 $, to przyjmujemy

$$\be_1=\al_1 \mbox{ i } \al'_i=\al_i-\frac{h(\al_i,\al_1)}{h(\al_1,\al_1)}\al_1\ , \ i=2,\ldots,n.$$

Wówczas dla $ i\geq 2 $ mamy $ h(\al'_i,\be_1)= h(\al_i-\frac{h(\al_i,\al_1)}{h(\al_1,\al_1)}\al_1,\al_1)= h(\al_i,\al_1)-h(\al_i,\al_1)=0 $.

(II) Jeśli $ h(\al_1,\al_1)=0 $ ale $ h(\al_i,\al_i)\neq 0 $ dla pewnego $ i>0 $, to zamieniamy w bazie $ \al_1 $ z $ \al_i $ miejscami i jesteśmy w sytuacji takiej jak w (I).

(III) Jeśli $ h(\al_i,\al_i)=0 $ dla $ i=1,\ldots,n $, to istnieją $ i>j $ takie, że $ h(\al_i,\al_j)=c\neq 0 $. Wówczas, podobnie jak w Przykładzie [link] (a), $ h(\al_j-\al_i,\al_j-\al_i)=-2c $ (a także $ h(\al_j+\al_i,\al_j+\al_i)=2c $ i $ h(\al_j-\al_i,\al_j+\al_i)=0 $). Zastępując w bazie $ (\al_1,\ldots,\al_n) $ wektor $ \al_j $ przez $ \al_j-\al_i $, a wektor $ \al_i $ przez $ \al_j+\al_i $ doprowadzamy do sytuacji takiej jak w (II) (lub (I), jeśli $ j=1 $).

Tak więc, operacje opisane w (I),(II),(III) pozwalają przejść od bazy $ (\al_1,\ldots,\al_n) $ do bazy $ (\be_1,\al'_2,\ldots,\al'_n) $ takiej, że $ h(\al'_i,\be_1)= 0 $ dla $ i\geq 2 $.

Stosując tę samą procedurę do bazy $ (\al'_2,\ldots,\al'_n) $ przestrzeni $ \lin(\al'_2,\ldots,\al'_n) $ dostajemy bazę $ (\be_1,\be_2,\al''_3\ldots,\al''_n) $ przestrzeni $ V $ taką, że $ h(\be_i,\be_j)=0 $ dla $ i<j\leq 2 $ oraz $ h(\al''_i,\be_j)=0 $ dla $ j=1,2 $, $ i\geq 3 $.

Po $ r=\r(h) $ krokach dostaniemy bazę $ (\be_1,\ldots,\be_n) $ przestrzeni $ V $ taką, że $ h(\be_i,\be_j)=0 $ dla $ i<j\leq n $ oraz $ h(\al,\be)=0 $ dla $ \al,\be\in\lin (\be_{r+1},\ldots,\be_n) $. \null
\null$ \blacksquare $    

Uwaga (#)

  • [(a)] Opisanym w dowodzie operacjom prowadzącym od bazy $ (\al_1,\ldots,\al_n) $ do bazy $ (\be_1,\ldots,\be_n) $ odpowiadają opisane w dowodzie Twierdzenia [link] operacje na wierszach i kolumnach macierzy Grama $ A=[a_{ij}]_{i,j=1}^n= [h(\al_i,\al_j)]_{i,j=1}^n $ funkcjonału $ h $ w bazie $ (\al_1,\ldots,\al_n) $.
  • [(b)] Etapy (II) i (III) algorytmu można zastąpić operacją elementarną odpowiadającą macierzy elementarnej użytej w Przykładzie [link] (b). Jeśli $ a_{11}=0 $ i $ a_{i1}= 0 $ dla $ i>1 $, to w macierzy $ A $ pierwsza kolumna (i wiersz) są zerowe. Przechodzimy wtedy do redukcji macierzy Grama układu $ (\al_2,\ldots,\al_n) $ (oznaczanej przez $ A_1 $ w dowodzie [link]). Jeśli $ a_{11}=0 $ i $ a_{i1}\neq 0 $ dla pewnego $ i>1 $, to zastępujemy wektor $ \al_1 $ przez $ \al_1+\al_i $ (do pierwszego wiersza $ A $ dodajemy $ i $-ty i symetrycznie, do pierwszej kolumny dodajemy $ i $-tą), co prowadzi do sytuacji takiej jak w (I). Po nie więcej niż $ n $ takich krokach dostajemy nową bazę (macierz diagonalną), która po zmianie kolejności wektorów (wierszy i kolumn) spełnia tezę Twierdzenia [link] ( [link]).