dekompozicija vlastitih vrijednosti

CS-dekompozicija J-ortogonalnih matrica malog reda

Vjeran Hari   i  Vida Zadelj-Martić
Matematički odsjek PMFa Sveučilišta u Zagrebu, Bijenička cesta 30, 10000 Zagreb, Hrvatska
Geodetski fakultet Sveučilišta u Zagrebu, Kačićeva 26, 10000 Zagreb, Hrvatska



 

Sažetak
U radu se izvodi CS dekompozicija J-ortogonalnih matrica reda 2, 3 i 4. U izvodu se koriste samo osnovni pojmovi iz teorije matrica, te singularna dekompozicija matrica reda 2 i 3. Pokazuje se da se J-ortogonalna matrica reda 4 (3) može faktorizirati u produkt od 4 (2) “trigonometrijske” ravninske rotacije i 2 (1) “hiperbolne” ravninske rotacije. To otvara zanimljiv i važan problem: kako odrediti sve te ravninske rotacije, direktno iz simetrične matrice A reda 4 (3), koje kroz transformacije kongruencije dijagonaliziraju A. Rješenje tog problema ima direktnu primjenu u ubrzanju blok J-Jacobijeve metode za računanje vlastitih vrijednosti i vektora indefinitne simetrične matrice reda n.

1Uvod u CSD J-ortogonalne matrice

Ovaj rad nastavak je istraživanja o CS dekompoziciji ortogonalnih matrica malog reda [3]. Umjesto s ortogonalnim, radit ćemo sa J-ortogonalnim matricama. Matrice malog reda su jednostavnnije za proučiti, pa je namjera ovog članka dokazati rezultate na novi i jednostavniji način. Stoga je rad napisan tako da zahtijeva minimalno znanje iz teorije matrica. Ipak, zaključak ovog istraživanja upućuje na otvoren, zanimljiv i netrivijalan matematički problem: kako dijagonalizirati indefinitnu simetričnu matricu reda 4 (3) koristeći tek nekoliko ravninskih (trigonometrijskih i hiperbolnih) rotacija. Rješenje tog problema povećalo bi efikasnost postojećih vrlo točnih algoritama [5, 2] za računanje vlastitih vrijednosti simetrične indefinitne matrice reda n.

Neka je J dijagonalna matrica predznaka reda n oblika

J=\begin{bmatrix}I_{l} & 0 \\\ 0&-I_{n-l}\end{bmatrix} ,\quad 1\leq l\leq n-1,

pri čemu su I_{l} i I_{n-l} jedinične matrice reda l i n-l, respektivno. Matrici J možemo pridružiti grupu J-ortogonalnih matrica reda n.

Definicija 1. Matrica F naziva se J-ortogonalna matrica ako vrijedi
(1)
F^{\tau}JF=J.


Iz definicije odmah slijedi da F mora biti kvadratna i nesingularna. Doista, jer je na desnoj strani jednakosti (1) kvadratna matrica J reda n, mora i lijeva strana dati kvadratnu matricu. Stoga F kao zadnja matrica u produktu mora imati n stupaca, a da bi produkt JF bio definiran mora F imati n redaka. Dakle sve su matrice na lijevoj strani kvadratne reda n. Njihov produkt je J koja je nesingularna, pa sve matrice na lijevoj strani moraju biti nesingularne. To se također vidi i ako primijenimo na lijevu i desnu stranu jednakosti (1) determinantu i iskoristimo Binet-Cauchyjev teorem.

Propozicija 2.J-ortogonalne matrice reda n čine grupu s obzirom na operaciju matričnog množenja. Ona je podgrupa grupe nesingularnih matrica reda n i zatvorena je u odnosu na matrično transponiranje.

Dokaz. Pokažimo prvo da je produkt dviju J-ortogonalnih matrica također J-ortogonalna matrica. Neka su F i GJ-ortogonalne tako da vrijedi F^{\tau} JF=J i G^{\tau} JG=J. Tada je

(FG)^{\tau}J(FG)=(G^{\tau}F^{\tau} )\; JFG=G^{\tau}(F^{\tau}JF)G=G^{\tau}JG=J,

što pokazuje da je i produkt FG jedna J- ortogonalna matrica.

Ulogu jediničnog elementa igra jedinična matrica I_{n} koja zadovoljava relaciju (1). Grupna operacija je matrično množenje koje je asocijativno, pa preostaje pokazati da je inverz J-ortogonalne matrice također J-ortogonalna.

Neka je FJ-ortogonalna. Tada je ona nesingularna, pa postoji inverzna matrica F^{-1}. Pokažimo da je F^{-1}J-ortogonalna. Ako pomnožimo lijevu i desnu stranu jednadžbe (1) prvo sa F^{-1} zdesna, a zatim s J slijeva, dobijemo ekvivalentu jednadžbu

(2)
F^{-1}= JF^{\tau}J.

Ako invertiramo lijevu i desnu stranu i iskoristimo činjenicu da operacije transponiranja i invertiranja komutiraju, dobijemo

[F^{-1}]^{-1} = J [F^{-1}]^{\tau}J.

To pokazuje da i F^{-1} zadovoljava uvjet (2), pa je J-ortogonalna matrica.

Preostaje još pokazati da J-ortogonalnost od F povlači J-ortogonalnost od F^{T}. Doista, ako transponiramo izraze na lijevoj i desnoj strani jednadžbe (2), dobijemo

[F^{T}]^{-1} = J [F^{T}]^{T}J.

pa je propozicija dokazana. Q.E.D.
Koje uvjete zadovoljavaju elementi proizvoljne J-ortogonalne matrice F?

Napomena 3. Da bismo na to odgovorili, podijelimo matricu F u četiri bloka
(3)
F=\left[\begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array}\right] \begin{array}{l} l\\ n-l \end{array}
pri čemu su F_{11} i F_{22} kvadratni. Tada se jednadžba J=F^{T}JF može zapisati u obliku
(4)
\begin{eqnarray} \left[ \begin{array}{cc} I_{l} & 0 \\ 0 & -I_{n-l} \end{array}\right] &=& \left[\begin{array}{cc} F_{11}^{T} & F_{21}^{T} \\ F_{12}^{T} & F_{22}^{T} \end{array}\right] \left[ \begin{array}{cc} I_{l} & 0 \\ 0 & -I_{n-l} \end{array}\right] \left[\begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array}\right] \\ &=& \left[\begin{array}{cc} F_{11}^{T} & -F_{21}^{T} \\ F_{12}^{T} &- F_{22}^{T} \end{array}\right] \left[\begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array}\right] \nonumber\\ &=& \left[\begin{array}{cc} F_{11}^{T} F_{11}-F_{21}^{T} F_{21} & F_{11}^{T}F_{12}-F_{21}^{T}F_{22} \\ F_{12}^{T} F_{11}-F_{22}^{T} F_{21}& F_{12}^{T} F_{12}-F_{22}^{T} F_{22} \end{array}\right] \end{eqnarray}
Izjednačavajući blokove na lijevoj i desnoj strani, dobivamo
(5)
\begin{eqnarray} F_{11}^{T} F_{11}-F_{21}^{T} F_{21} = I_{l}\quad &&\quad F_{12}^{T} F_{12}-F_{22}^{T} F_{22}=-I_{n-l} \\[3pt] F_{11}^{T} F_{12}-F_{21}^{T} F_{22}=0 \quad\ &&\quad\ \ F_{12}^{T} F_{11}-F_{22}^{T} F_{21}=0. \end{eqnarray}

Ako pišemo F=(f_{ij}), i izračunamo elemente na diagonalnom mjestu (i,i) odnosno nedijagonalnom mjestu (i,j), na lijevoj i desnoj strani u relaciji (1), lako dobijemo

(6)
\sum_{k=1}^{l} f_{ki}^{2}-\sum_{k=l+1}^{n} f_{ki}^{2}= \left\lbrace \begin{array}{rc} 1, & 1\leq i\leq l \\ -1, & l+1\leq i\leq n \end{array}\right.

odnosno

(7)
\sum\limits_{k=1}^{l}f_{ki}f_{kj}-\sum\limits_{k=1+1}^{n}f_{ki}f_{kj}=0; \ \ \ i\neq j.

Jer je matrica FJ-ortogonalna, takva je i matrica F^{T}, pa relacije (6) i (7) vrijede ako na svim mjestima zamijenimo donje indekse (f_{ki}\mapsto f_{ik}, f_{kj}\mapsto f_{jk}). Tako dobijemo analogne relacije

(8)
\sum_{k=1}^{l} f_{ik}^{2}-\sum_{k=l+1}^{n} f_{ik}^{2}= \left\lbrace \begin{array}{rc} 1, & 1\leq i\leq l \\ -1, & l+1\leq i\leq n \end{array}\right.

odnosno

(9)
\sum\limits_{k=1}^{l}f_{ik}f_{jk}-\sum\limits_{k=1+1}^{n}f_{ik}f_{jk}=0; \ \ \ i\neq j.

U našoj analizi trebat ćemo pojmove singularnih vrijednosti i vektora matrice. Sljedeći teorem dokazuje postojanje singularne dekompozicije matrice. Nama će trebati samo verzija za realne matrice.

Teorem 4. [Singularna dekompozicija] Ako je Cm\times n realna matrica, tada postoje ortogonalne matrice U i V reda m i n, respektivno, takve da je
(10)
U^{T} C V = \Sigma ,\qquad \Sigma =\text{diag}(\sigma_{1},\sigma_{2},\ldots ,\sigma_{\min\lbrace m,n\rbrace }),
pri čemu vrijedi \sigma_{1}\geq \sigma_{2}\geq\ \cdots\ \geq \sigma_{\min\lbrace m,n\rbrace }\geq 0. Brojevi \sigma_{1},\sigma_{2},\ldots ,\sigma_{\min\lbrace m,n\rbrace } su singularne vrijednosti matrice C. Stupci matrice U su lijevi, a stupci matrice V desni singularni vektori matrice C.

U slučaju kvadratne matrice reda n, \sigma_{\min\lbrace m,n\rbrace }=\sigma_{n}. Singularna dekompozicija se koristi u dokazu postojanja CS dekompozicije J-ortogonalne matrice, a mi ćemo ju koristiti samo za slučajeve m=n=2 i m=n=3 (vidjeti npr. [6, 3]).

Da bismo otkrili još neka zanimljiva svojstva J-ortogonalne matrice F, podijelimo ju na 4 bloka, prema matričnoj blok-particiji koju nosi J,

(11)
F=\left[\begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array}\right] \begin{array}{l} l\\ n-l \end{array} \ ,

pri čemu su F_{11} i F_{22} kvadratni blokovi. Tada se jednadžba J=F^{T}JF može nakon množenja na desnoj strani, zapisati u obliku

\begin{eqnarray*} \left[ \begin{array}{cc} I_{l} & 0 \\ 0 & -I_{n-l} \end{array}\right] &=& \left[\begin{array}{cc} F_{11}^{T} & F_{21}^{T} \\ F_{12}^{T} & F_{22}^{T} \end{array}\right] \left[ \begin{array}{cc} I_{l} & 0 \\ 0 & -I_{n-l} \end{array}\right] \left[\begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array}\right] \\ &=& \left[\begin{array}{cc} F_{11}^{T} F_{11}-F_{21}^{T} F_{21} & F_{11}^{T}F_{12}-F_{21}^{T}F_{22} \\ F_{12}^{T} F_{11}-F_{22}^{T} F_{21}& F_{12}^{T} F_{12}-F_{22}^{T} F_{22} \end{array}\right]. \end{eqnarray*}

Izjednačavajući blokove na lijevoj i desnoj strani, dobivamo

(12)
\begin{eqnarray} F_{11}^{T} F_{11}=F_{21}^{T} F_{21} + I_{l},\quad &&\quad F_{12}^{T} F_{12}=F_{22}^{T} F_{22}-I_{n-l}, \\[3pt] F_{11}^{T} F_{12}=F_{21}^{T} F_{22}, \quad\ &&\quad\ \ F_{12}^{T} F_{11}=F_{22}^{T} F_{21}. \end{eqnarray}

Svaka vlastita vrijednost simetrične matrice H\pm \alpha I je oblika \lambda \pm \alpha gdje je \lambda vlastita vrijednost matrice H. Stoga nam relacija (5) pokazuje da vrijedi

\begin{eqnarray*} \lambda_{i} (F_{11}^{T} F_{11}) - \lambda_{i} (F_{21}^{T} F_{21}) &=&1, \quad 1\leq i\leq l,\\ \lambda_{j} (F_{22}^{T} F_{22}) - \lambda_{j} (F_{12}^{T} F_{12}) &=&1, \quad 1\leq j\leq n-l. \end{eqnarray*}

Ako je Xr\times t realna matrica, korištenjem njene singularne dekompozicije odmah slijedi da su vlastite vrijednosti simetrične matrice X^{T}X  (XX^{T}) kvadrati singularnih vrijednosti od X, uz dodatno t-r (r-t) nula vlastitih vrijednosti u slučaju t\gt r (r\gt t)). Ako općenito \sigma_{i}(X) označava i-tu singularnu vrijednost od X, tada se zadnje dvije relacije mogu zapisati u obliku

(13)
\sigma_{i}^{2} (F_{11}) - \sigma_{i}^{2} (F_{21}) =1,\ 1\leq i\leq l,\ \ \sigma_{j}^{2} (F_{22}) - \sigma_{j}^{2}(F_{12}) =1,\ 1\leq j\leq n\text{–}l,

pri čemu se mora voditi računa od dimenzijama matrica F_{21} i F_{12}. Ako je manja dimenzija od F_{21} (F_{12}) manja od l (n-l), tada F_{21} (F_{12}) ima manje od l (n-l) singularnih vrijednosti, pa se zadnja relacija za odgovarajuće vrijednosti indeksa i (j) svodi na oblik \sigma_{i} (F_{11})=1  (\sigma_{j} (F_{22})=1).

Dakle se odgovarajuće singularne vrijednosti blokova F_{11} i F_{21} (F_{22} i F_{12}) ponašaju kao hiperbolni kosinus i sinus istog argumenta. Stoga se može očekivati da postoji neka dekompozicija J-ortogonalne matrice F, slična singularnoj dekompoziciji, kod koje će ortogonalne matrice koje množe F slijeva i zdesna također biti i J-ortogonalne. To nas vodi na tzv. hiperbolnu kosinus-sinus dekompoziciju J-ortogonalne matrice, koju u općenitom obliku dajemo bez dokaza. Dokaz je dugačak i zahtjevan (vidjeti \cite[Theorem 2.1]{Tru-00}).

Teorem 5. [Hiperbolna CS dekompozicija] Neka je FJ-ortogonalna matrica reda n kao u relaciji (3).

Ako je 2l\leq n, tada postoje ortogonalne blok-dijagonalne matrice U=\text{diag}(U_{11},U_{22}) i V=\text{diag}(V_{11},V_{22}) reda n pri čemu su U_{11} i V_{11} reda l tako da vrijedi
(14)
\left[\begin{array}{cc} U_{11}^{\tau} & 0 \\ 0 & U_{22}^{\tau} \end{array} \right] \left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array} \right] \left[ \begin{array}{cc} V_{11} & 0 \\ 0 & V_{22} \end{array} \right] = \left[ \begin{array}{c|cc} \Gamma & \Sigma & 0 \\\hline \Sigma & \Gamma & 0 \\ 0 & 0 & I \end{array} \right].
Pri tome su \Gamma i \Sigma dijagonalne matrice reda l s nenegativnim elementima, takve da je
(15)
\Gamma =\text{diag}(\gamma_{1},\gamma_{2},\ldots ,\gamma_{l}),\quad \Sigma =\text{diag}(\sigma_{1},\sigma_{2},\ldots ,\sigma_{l}),\quad \Gamma^{2}-\Sigma^{2}=I_{l}.
Ako je 2l \gt n, tada postoje ortogonalne blok-dijagonalne matrice U=\text{diag}(U_{11},U_{22}) i V=\text{diag}(V_{11},V_{22}) reda n pri čemu su U_{11} i V_{11} reda l tako da vrijedi
(16)
\left[ \begin{array}{cc} U_{11}^{\tau} & 0 \\ 0 & U_{22}^{\tau} \end{array} \right] \left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array} \right] \left[ \begin{array}{cc} V_{11} & 0 \\ 0 & V_{22} \end{array} \right] = \left[ \begin{array}{cc|c} \Gamma & 0 & \Sigma \\ 0 & I & 0 \\\hline \Sigma & 0 & \Gamma \end{array} \right].
Pritom su \Gamma i \Sigma dijagonalne matrice reda n-l s nenegativnim elementima, takve da je
(17)
\Gamma =\text{diag}(\gamma_{1},\gamma_{2},\ldots ,\gamma_{n-l}),\ \Sigma =\text{diag}(\sigma_{1},\sigma_{2},\ldots ,\sigma_{n-l}), \ \ \Gamma^{2}\!- \Sigma^{2}=I_{n-l}.


U teoremu su singularne vrijednosti blokova F_{11} i F_{22} označene sa \gamma_{i}, dok su singularne vrijednosti blokova F_{21} i F_{12} označene sa \sigma_{i}, 1\leq i\leq \min\lbrace l,n-l\rbrace. Ako je 2l=n, tada se na desnim stranama u relacijama (14) i (16) ispušta jedinična matrica I. Zbog svojstva \Gamma^{2} - \Sigma^{2} = I, dijagonalni elementi od \Gamma i \Sigma zadovoljavaju uvjet

(18)
\gamma_{i}^{2}-\sigma_{i}^{2}=1,\qquad 1\leq i\leq \min\lbrace l,n-l\rbrace .

Ako je 2l\leq n, tada je dijagonalna matrica \Gamma općenito oblika \text{diag}(\Gamma_{1},I_{l-k}), pri čemu dijagonalni elementi od \Gamma_{1} zadovoljavaju uvjet \gamma_{i}\gt 1, 1\leq i\leq k. Tada je dijagonalna matrica \Sigma oblika \text{diag}(\Sigma_{1},0_{l-k}), pri čemu dijagonalni elementi od \Sigma_{1} zadovoljavaju uvjet \sigma_{i}\gt 0, 1\leq i\leq k. U slučaju 2l\gt n može se pretpostaviti isto, samo l treba zamijeniti sa n-l. Zbog relacije (18) dijagonalni elementi \gamma_{i} se poistovjećuju sa kosinus hiperbolnim, a \sigma_{i} sa sinus hiperbolnim nekih kuteva. Stoga ćemo dekompoziciju iz Teorema 5 nazivati hiperbolnom CS dekompozicijom (kraće: HCSD) ili CS dekompozicijom J-ortogonalne matrice (kraće: CSD J-ortogonalne matrice).

Cilj ovog članka je na što elementarniji način izvesti CS dekompoziciju J ortogonalne matrice F reda 2, 3 i 4. U slučaju n=3 i n=4 postoje različite mogućnosti za J, ovisno o tome koliki je l u odnosu na n. Stoga će za svaki izbor od n i l postojati posebni dokaz.

Također ćemo i za n=3,4 dati primjene koje otvaraju nove netrivijalne probleme. Od kompliciranijih alata, koristit ćemo tek singularnu dekompoziciju za matrice reda 2 i 3.



2CSD J-ortogonalne matrice reda 2

U ovom slučaju jedini mogući oblik za J je \text{diag}(1,-1), pa je l=1. Stoga su i matrice U_{11}, U_{22}, V_{11}, V_{22} brojevi iz skupa \lbrace 1,-1\rbrace. Dakle, hiperbolna CSD za matricu F ima oblik

(1)
\!\! \left[\begin{array}{cc}f_{11}&f_{12}\\ f_{21}&f_{22}\end{array}\right] = \left[\begin{array}{cc}u_{11}&0\\ 0&u_{22}\end{array}\right]\! \left[\begin{array}{cc}\gamma_{1}&\sigma_{1}\\ \sigma_{1}&\gamma_{1}\end{array}\right]\! \left[\begin{array}{cc}v_{11}&\\ 0&v_{22}\end{array}\right],\ \begin{array}{l} \gamma_{1}^{2}-\sigma_{1}^{2}=1,\\[3pt] \gamma_{1}\geq 1,\ \sigma_{1}\geq 0, \end{array}

pri čemu su u_{11},u_{22},v_{11},v_{22}\in\lbrace 1,-1\rbrace. Kako odrediti elemente matrica na desnoj strani ako je dana matrica F svojim elementima?

Ako je |f_{11}|=1, tada iz relacija (6) i (8) za i=1 odmah slijedi f_{21}=0 i f_{12}=0. Stoga je |f_{22}|=1, pa mora biti \sigma_{1}=0, \gamma_{1}=1. Možemo odabrati u_{11}, u_{22} iz skupa \lbrace 1,-1\rbrace tako da vrijedi f_{11}=u_{11}\gamma_{1}, f_{22}=u_{22}\gamma_{1}, te onda staviti v_{11}=1, v_{22}=1.

Ako je |f_{11}|\gt 1, tada iz relacija (6) i (8) za i=1 odmah slijedi |f_{21}|\gt 0, |f_{12}|\gt 0 i |f_{21}|=|f_{12}|. Stoga je i |f_{22}|=|f_{11}|. Relacija (7) pokazuje da mora vrijediti f_{11}f_{12}=f_{21}f_{22}. Definirajmo \gamma_{1}=|f_{11}|, \sigma_{1}=|f_{21}|.

Možemo odabrati u_{11} i u_{22} tako da bude f_{11}=u_{11}\gamma_{1} i f_{21}=u_{22}\sigma_{1}. Zatim odaberimo v_{11}=1, a v_{22} odaberimo tako da bude f_{22}=(u_{22}\gamma_{1})v_{22}. Tada mora vrijediti relacija (??), čime je postignut traženi oblik iz teorema.



3CSD J-ortogonalne matrice reda 3

U ovom slučaju imamo dva podslučajeva: l=1 i l=2.

3.1Slučaj  n=3,  l=1

U ovom slučaju matrice F i J možemo zapisati na sljedeći način

F=\left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array}\right] = \left[ \begin{array}{l|rr} a & b & c \\\hline d & e & f \\ g & h & p \end{array}\right],\qquad J = \left[ \begin{array}{ccc} 1 & & \\ & -1 & \\ & & -1 \end{array}\right]

Načinimo singularnu dekompoziciju matrice F_{22}. Ona daje ortogonalne matrice reda 2, U_{22} i V_{22} takve da je

(1)
F_{22} = U_{22}\Gamma_{2}V_{22}^{T},\quad \Gamma_{2}= \left[ \begin{array}{cc}\gamma_{1} & \\ & \gamma_{2} \end{array}\right],\ \ \gamma_{1}\geq \gamma_{2}\geq 1.

Ovdje smo iskoristili relaciju (13) koja govori da su singularne vrijednosti matrice F_{22} veće ili jednake od 1.

Napomena 6. Nama će zapravo trebati malo modificirana singularna dekompozicija, najme ona koja će dati \gamma_{2}\geq \gamma_{1}\geq 1. To se postiže tako da se između U_{22} i \Gamma_{2}, te između \Gamma_{2} i V_{22}^{T} umetne produkt I_{12}I_{12} koji je jednak jediničnoj matrici I_{2}. Pritom se I_{12} dobije iz I_{2} zamjenom stupaca (ili redaka). Drugim riječima, sve što treba u (1) napraviti je: zamijeniti \gamma_{1} i \gamma_{2}, zamijeniti stupce od U_{22} i zamijeniti stupce od V_{22}.

Sada možemo pisati

(2)
\begin{eqnarray} F &=& \left[ \begin{array}{cc}F_{11} & F_{12} \\ F_{21} & U_{22}\Gamma_{2}V_{22}^{T} \end{array} \right] = \left[ \begin{array}{cc}1 & \\ & U_{22} \end{array}\right] \left[ \begin{array}{cc}F_{11} & F_{12}V_{22} \\ U_{22}^{T}F_{21} &\Gamma_{2}\end{array}\right] \left[ \begin{array}{cc}1 & \\ & V_{22}^{T} \end{array}\right]\\ &=& \left[ \begin{array}{cc}1 & \\ & U_{22} \end{array}\right] \left[ \begin{array}{l|rr} a & \tilde{b} & \tilde{c}\\\hline\\[-2ex] \tilde{d} & \gamma_{1} & 0 \\ \tilde{g} & 0 & \gamma_{2} \end{array}\right] \left[ \begin{array}{cc}1 & \\ & V_{22}^{T} \end{array}\right] \end{eqnarray}

U relaciji (2) sve matrice su J-ortogonalne, pa je takva i “srednja” matrica na desnoj strani koju označimo sa \tilde{F},

\tilde{F}=\left[ \begin{array}{l|rr} a & \tilde{b} & \tilde{c} \\\hline\\[-2ex] \tilde{d} & \gamma_{1} & 0 \\ \tilde{g} & 0 & \gamma_{2} \end{array}\right].

Iz relacija (7) i (9) za matricu \tilde{F} i za i=2, j=3, proizlazi \tilde{b}\tilde{c}=0 i \tilde{d}\tilde{g}=0. Sada uvjet \gamma_{1}\geq\gamma_{2}\geq 1 i relacije (6) i (8) pokazuju da ne može biti \gamma_{2}\gt 1. Jer \gamma_{2}\gt 1 povlači \gamma_{1}\gt 1, |\tilde{b}|\gt 0, |\tilde{c}|\gt 0 kao i |\tilde{d}|\gt 0, |\tilde{g}|\gt 0, pa ne bi moglo biti ni \tilde{b}\tilde{c}=0 niti \tilde{d}\tilde{g}=0. Dakle je \gamma_{2}=1, pa relacije (6) i (8) povlače |\tilde{c}|=0 i |\tilde{g}|=0. Dobili smo da je

(3)
\tilde{F}=\left[ \begin{array}{l|rr} a & \tilde{b} & 0 \\\hline\\[-2ex] \tilde{d} & \gamma_{1} & 0 \\ 0 & 0 & \gamma_{2} \end{array}\right].

Sada relacije (6) i (8) uz i=2 daju |\tilde{b}|=\sqrt{\gamma_{1}^{2}-1} i |\tilde{d}|=\sqrt{\gamma_{1}^{2}-1}. Ako iskoristimo iste relacije uz i=1, dobivamo |a|=\gamma_{1}. Mi trebamo dobiti a=\gamma_{1} i \tilde{b}=\tilde{d}\geq 0. To ćemo postići izborom ortogonalnih matrica U_{11} i V_{11} koje su reda 1, pa su to brojevi iz skupa \lbrace 1,-1\rbrace. Kako želimo da je a\gt 0, odaberimo U_{11}= \text{sgn}(a), V_{11}= 1. Time dobivamo

F = \left[ \begin{array}{cc}\text{sgn} (a) & \\ & U_{22} \end{array}\right] \left[ \begin{array}{l|rr} \gamma_{1} & \tilde{b}' & 0\\\hline\\[-2ex] \tilde{d}' & \gamma_{1} & 0 \\ 0 & 0 & 1 \end{array}\right] \left[ \begin{array}{cc}1 & \\ & V_{22}^{T} \end{array}\right]

Iz relacije (6) (ili (8)) slijedi \gamma_{1}\tilde{b}' =\gamma_{1}\tilde{d}' pa nakon kraćenja slijedi \tilde{b}' =\tilde{d}'. Ako je \tilde{b}'\geq 0 tada je HCSD je dovršena. Ako je \tilde{b}'\lt 0, sve što treba napraviti je pomnožiti prvi stupac od U_{22} i V_{22} sa -1. Da bi se u to uvjerili, uočimo da je matrica D=\text{diag}(1,-1,1)J-ortogonalna i da vrijedi D\cdot D=I_{3}. Stoga je

\begin{eqnarray*} F &=& \left[ \begin{array}{cc}\text{sgn} (a) & \\ & U_{22} \end{array}\right]D\cdot D \left[ \begin{array}{l|rr} \gamma_{1} & \tilde{b}' & 0\\\hline\\[-2ex] \tilde{d}' & \gamma_{1} & 0 \\ 0 & 0 & 1 \end{array}\right]D\cdot D \left[ \begin{array}{cc}1 & \\ & V_{22}^{T} \end{array}\right] \\ &=& \left[ \begin{array}{cc}\text{sgn} (a) & \\ & U_{22} \left[\begin{array}{rr}-1&0\\ 0&1\end{array}\right] \end{array}\right] \left[ \begin{array}{l|rr} \gamma_{1} & -\tilde{b}' & 0\\\hline\\[-2ex] -\tilde{d}' & \gamma_{1} & 0 \\ 0 & 0 & 1 \end{array}\right] \left[ \begin{array}{cc}1 & \\ & \left[\begin{array}{rr}-1&0\\ 0&1\end{array}\right] V_{22}^{T} \end{array}\right]. \end{eqnarray*}

Uočimo da je i \text{diag}(-1,1)\cdot V_{22}^{T}= [V_{22}\cdot \text{diag}(-1,1)]^{T}, pa i kod matrice V_{22} samo treba prvi stupac pomnožiti sa -1.

3.2Slučaj  n=3,  l=2

Sada je J=\text{diag}(1,1,-1). Dokaz teorema u ovom slučaju može se napraviti posve analogno kao i u prethodnom slučaju. Stoga ćemo ga napraviti na malo drugačiji način.

Iz teorema 5 slijedi, stoga što je 2l\gt n, da postoje ortogonalne matrice U=\text{diag}(U_{11},U_{22}) i V=\text{diag}(V_{11},V_{22}) tako da vrijedi relacija (16). Pri tome su u našem slučaju n=3, l=2, U_{11} i V_{11} ortogonalne matrice reda 2 i vidi se da je U_{11}^{T}F_{11}V_{11}=\text{diag}(\Gamma ,I) singularna dekompozicija bloka F_{11} matrice F. Zato izvod kreće od singularne dekompozicije matrice F_{11}.

Neka je matrica F oblika

F=\left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array} \right] =\left[ \begin{array}{ll|r} a & b & c \\ d & e & f \\\hline g & h & p \end{array} \right].

Načinimo singularnu dekompoziciju matrice F_{11}, F_{11}=U_{11}\Gamma_{1} V_{11}^{T} i formirajmo ortogonalne matrice U=\text{diag}(U_{11}, u), V=\text{diag}(V_{11}, v) gdje će dijagonalni elementi u,v\in\lbrace 1,-1\rbrace biti određeni kasnije. Izračunajmo \tilde{F}=U^{T}FV.

\tilde{F}=\left[ \begin{array}{cc} U_{11}^{\tau} & 0 \\ 0 & u_{22} \end{array} \right] \left[ \begin{array}{ll|r} a & b & c \\ d & e & f \\\hline g & h & p \end{array} \right] \left[ \begin{array}{cc} V_{11} & 0 \\ 0 & v_{22} \end{array} \right] = \left[ \begin{array}{ll|r} \gamma_{1} & 0 & \tilde{c} \\ 0 & \gamma_{2} & \tilde{f} \\\hline \tilde{g} & \tilde{h} & \tilde{p} \end{array} \right]

Pritom je zbog relacije (13), \gamma_{1}\geq \gamma_{2}\geq 1. Uočimo da su sve matrice U, F i VJ-ortogonalne, pa je takva i \tilde{F}. Stoga relacije (7) i (9) primijenjene na \tilde{F} za i=1, j=2 daju \tilde{c}\tilde{f}=0 i \tilde{g}\tilde{h}=0. Slično kao i prije zaključujemo da pretpostavka \gamma_{2}\gt 1 povlači \gamma_{1}\gt 1, a onda relacije (6) i (8) za i=1 i i=2 pokazuju da mora biti |\tilde{c}|\gt 0, |\tilde{f}|\gt 0, |\tilde{g}|\gt 0, |\tilde{h}|\gt 0, pa ne može biti ni \tilde{c}\tilde{f}=0 niti \tilde{g}\tilde{h}=0. Kako je \gamma_{2}\geq 1 zaključujemo da je \gamma_{2}= 1. Stoga \tilde{F} ima oblik

\tilde{F}=\left[ \begin{array}{ll|r} \gamma_{1} & 0 & \tilde{c} \\ 0 & 1 & 0 \\\hline \tilde{g} & 0 & \tilde{p} \end{array} \right]

Iskoristimo opet relacije (6) i (8) za i=1 da bi zaključili kako mora biti |\tilde{c}|=\sqrt{\gamma_{1}^{2}-1} i |\tilde{g}|=\sqrt{\gamma_{1}^{2}-1}. Kada to uvažimo i opet primijenimo relacije (6) i (8) za i=3, dobijemo |\tilde{p}|=\gamma_{1}. Neka je dijagonalni element u matrice U odabran tako da bude \tilde{p}=\gamma_{1}. Dakle odabrali smo u=\text{sgn}(\tilde{p}). Da bismo vidjeli kako su elementi \tilde{c} i \tilde{g} jednaki, primijenimo na \tilde{F} relaciju (7) ili (9) za i=1, j=3. Primjena relacije (7) daje \gamma_{1}\tilde{c}=\tilde{g}\gamma_{1}, odakle slijedi \tilde{c}=\tilde{g}. Preostaje pokazati da možemo odabrati dijagonalni element v matrice V tako da bude \tilde{c}=\tilde{g}\gt 0. Za to je dovoljno definirati v=\text{sgn}(\tilde{c}).

Kako je F=U\tilde{F}V^{T}, a \tilde{F} je traženog oblika kao na desnoj strani u relaciji (16), dokaz je dovršen.

4CSD J-ortogonalne matrice reda n=4

Kada je n=4 imamo tri podslučajeva: l=1, l=2 i l=3.

4.1Slučaj n=4,  l=1

U ovom slučaju imamo J=\text{diag}(1,-1,-1,-1), pa pretpostavimo sljedeću notaciju

F=\left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array} \right] = \left[ \begin{array}{l|rrr} a & b & c & d \\\hline e & h & o & p \\ f & q & r & s \\ g & t & w & z \end{array} \right], \qquad J= \left[ \begin{array}{l|rrr} 1 & & & \\\hline & -1 & & \\ & & -1 & \\ & & & -1 \end{array} \right].

Načinimo singularnu dekompoziciju matrice F_{22}, F_{22}=U_{22}\Gamma_{2} V_{22}^{T}, gdje je \Gamma_{2} =\text{diag}(\gamma_{1},\gamma_{2},\gamma_{3}), \gamma_{1}\geq\gamma_{2}\geq\gamma_{3}, a U_{22} i V_{22} su ortogonalne matrice reda 3. Neka su U=\text{diag}(u,U_{22}), V=\text{diag}(v,V_{22}), gdje ćemo brojeve u,v\in\lbrace 1,-1\rbrace kasnije odrediti. Za početak razmatranja stavimo u=1, v=1. Tada vrijedi

\tilde{F}=\left[ \begin{array}{cc} u & 0 \\ 0 & U_{22}^{\tau} \end{array} \right] \left[ \begin{array}{l|rrr} a & b & c & d \\\hline e & h & o & p \\ f & q & r & s \\ g & t & w & z \end{array} \right] \left[ \begin{array}{cc} v & 0 \\ 0 & V_{22} \end{array} \right] = \left[ \begin{array}{l|rrr} a & \tilde{b} & \tilde{c} & \tilde{d} \\\hline \tilde{e} & \gamma_{1} & 0 & 0 \\ \tilde{f} & 0 & \gamma_{2} & 0 \\ \tilde{g} & 0 & 0 & \gamma_{3} \end{array} \right]

Ovdje se element a nije promijenio jer je u=1=v. Jer su sve matrice u produktu, U, F i VJ-ortogonalne, takva je i \tilde{F}. Stoga primjena relacije (13) daje \gamma_{3}\geq 1. Također, primjena relacija (7) i (9) za svaki izbor i,j, pri čemu je 2\leq i\lt j\leq 4, daje

(1)
\begin{eqnarray} \tilde{b}\,\tilde{c}=0, &\quad& \tilde{b}\,\tilde{d}=0,\qquad \tilde{c}\,\tilde{d}=0, \\ \tilde{e}\,\tilde{f}=0, &\quad& \tilde{e}\,\tilde{g}=0,\qquad \tilde{f}\,\tilde{g}=0, \end{eqnarray}

a primjena relacija (6) i (8) za i=2,3,4 daje

(2)
\begin{eqnarray} \gamma_{1}^{2}=1+\tilde{b}^{2}, &\quad& \gamma_{2}^{2}=1+\tilde{c}^{2}, \qquad \gamma_{3}^{2}=1+\tilde{d}^{2}, \\ \gamma_{1}^{2}=1+\tilde{e}^{2}, &\quad& \gamma_{2}^{2}=1+\tilde{f}^{2}, \qquad \gamma_{3}^{2}=1+\tilde{g}^{2}. \end{eqnarray}

Tvrdimo da mora vrijediti \gamma_{2}=\gamma_{3}=1. Da bi to dokazali, pokažimo da suprotna pretpostavka, da je \gamma_{2}\gt \gamma_{3} ili \gamma_{3}\gt 1, vodi u kontradikciju.

Doista, kada bi bilo \gamma_{3}\gt 1, tada bi zapravo vrijedilo \gamma_{1}\geq\gamma_{2}\geq\gamma_{3}\gt 1, pa bi relacije (2) i (2) implicirale

|\tilde{b}|\geq |\tilde{c}|\geq |\tilde{d}|\gt 0\quad\text{i}\quad |\tilde{e}|\geq |\tilde{f}|\geq |\tilde{g}|\gt 0,

pa ne bi mogle vrijediti ni relacija (1) niti relacija (1).
Kada bi vrijedilo \gamma_{2}\gt \gamma_{3}, tada bi bilo \gamma_{1}\geq \gamma_{2}\gt 1, pa bi relacije (2) i (2) implicirale

|\tilde{b}|\geq |\tilde{c}|\gt 0\quad\text{i}\quad |\tilde{e}|\geq |\tilde{f}|\gt 0.

To bi povlačilo \tilde{b}\,\tilde{c}\ne 0 i \tilde{e}\,\tilde{f}\ne 0, što proturječi relacijama (1) i (1), respektivno.

Time je pokazano da mora biti \gamma_{2}=\gamma_{3}=1. Zbog relacija (2) i (2) to implicira da je \tilde{c}=0, \tilde{d}=0, \tilde{f}=0, \tilde{g}=0, pa matrica \tilde{F} ima oblik

\tilde{F}=\left[ \begin{array}{l|rrr} a & \tilde{b} & 0 & 0 \\\hline \tilde{e} & \gamma_{1} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right].

Opet koristeći relacije (2) i (2) lako zaključimo da je

|\tilde{b}| = \sqrt{\gamma_{1}^{2}-1},\quad |\tilde{e}| = \sqrt{\gamma_{1}^{2}-1}, \quad |a|=\gamma_{1}.

Sada ćemo odrediti prave vrijednosti za u i v. Odaberimo prvi dijagonalni element od U kao predznak od a, dakle u=\text{sgn}(a). To povlači da su se u matrici \tilde{F} elementi a i \tilde{b} zamijenili sa \gamma_{1} i \tilde{b}'= \text{sgn}(a)\tilde{b}, respektivno. Koristeći relaciju (7) ili (9) za i=1, j=2, dobijemo \gamma_{1}\,\tilde{b}' = \tilde{e}\gamma_{1}, što daje \tilde{b}' = \tilde{e}. Ovdje je v=1. Do istog zaključka i oblika matrice \tilde{F} došli bi izborom u=1, v=\text{sgn}(a).

Preostaje osigurati pozitivnost elementa \tilde{b}'. To možemo tako da istovremeno pomnožimo \tilde{F} slijeva i zdesna sa dijagonalnom matricom \Phi=\text{diag}(1,\text{sgn}(\tilde{b}'),1,1) koja je J-ortogonalna. Tada će \Phi \tilde{F}\Phi biti traženog oblika i sve što još treba je pomnožiti matrice U_{22} i V_{22} zdesna s \text{diag}(\text{sgn}(\tilde{b}'),1,1). To zapravo znači da je U=\text{diag}(\text{sgn}(a), U_{22}\Phi ) i V=\text{diag}(1, V_{22}\Phi).

4.2Slučaj n=4,  l=3

U ovom slučaju pretpostavljamo notaciju

F=\left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array} \right] = \left[ \begin{array}{lll|r} h & o & p & a \\ q & r & s & b \\ t & w & z & c \\\hline e & f & g & d \end{array} \right], \qquad J= \left[ \begin{array}{ccc|r} 1 & & & \\ & 1 & & \\ & & 1 & \\\hline & & & -1 \end{array} \right].

Načinimo singularnu dekompoziciju dijagonalnog bloka F_{11}, F_{11}=U_{11}\Gamma_{1}V_{11}^{T}, \Gamma_{1}=\text{diag}(\gamma_{1},\gamma_{2},\gamma_{3}), \gamma_{1}\geq\gamma_{2}\geq\gamma_{3}. Pritom su U_{11} i V_{11} ortogonalne matrice reda 3. Neka su U=\text{diag}(U_{11},u), V=\text{diag}(V_{11},v) ortogonalne matrice reda 4, gdje su elementi u,v\in\lbrace 1,-1\rbrace još neodređeni, a za početak razmatranja neka imaju vrijednost 1. Matrice U i V su ortogonalne i J-ortogonalne. Zaključujemo da je i matrica \tilde{F}=U^{T}FVJ-ortogonalna. Vrijedi

\tilde{F}= \left[\begin{array}{cc}U_{11}^{T} & 0 \\ 0 & u \end{array}\right] \left[\begin{array}{cc}F_{11} & F_{12} \\ F_{21} & F_{22}\end{array}\right] \left[\begin{array}{cc}V_{11} & 0 \\ 0 & v \end{array}\right] = \left[ \begin{array}{lll|r} \gamma_{1} & 0 & 0 & \tilde{a} \\ 0 & \gamma_{2} & 0 & \tilde{b} \\ 0 & 0 & \gamma_{3} & \tilde{c} \\\hline \tilde{e} & \tilde{f} & \tilde{g} & d \end{array}\right]

Ovdje se d nije promijenio jer je u=1=v. Jer je \tilde{F}J-ortogonalna, primijenimo na nju relaciju (13). Odmah dobijemo \gamma_{1}\geq\gamma_{2}\geq\gamma_{3}\geq 1.

Na slični način kao u prethodnom slučaju, lako se zaključi da mora vrijediti \gamma_{2}=\gamma_{3}=1, pa je \tilde{b}=\tilde{c}=0 i \tilde{f}=\tilde{g}=0. Stoga možemo pisati

(3)
\tilde{F}= \left[ \begin{array}{lll|r} \gamma_{1} & 0 & 0 & \tilde{a} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\\hline \tilde{e} & 0 & 0 & d \end{array}\right]

Koristeći relacije (6) i (8) lako zaključimo da je

|\tilde{a}|=\sqrt{\gamma_{1}^{2}-1},\quad |\tilde{e}|=\sqrt{\gamma_{1}^{2}-1},\quad |d|=\gamma_{1}.

Sada odaberimo u=\text{sgn}(d). To će utjecati na zadnji redak od \tilde{F}, tako da ćemo umjesto \tilde{e} pisati \tilde{e}'=\text{sgn}(d)\tilde{e}, a umjesto d ćemo pisati \gamma_{1}. Sada primjena relacije (7) ili (9) na \tilde{F} za i=1, j=4 daje \gamma_{1}\,\tilde{e}' = \tilde{a}\gamma_{1}. Nakon kraćenja sa \gamma_{1} slijedi \tilde{e}' = \tilde{a}. Do istog zaključka nas dovodi i izbor v=\text{sgn}(d) pri čemu ostaje u=1.

Preostaje osigurati nenegativnost od \tilde{a} odnosno \tilde{e}'. To ćemo postići tako da istovremeno pomnožimo \tilde{F} slijeva i zdesna sa dijagonalnom matricom \tilde{\Phi}=\text{diag}(\text{sgn}(\tilde{a}),1,1,1) koja je J-ortogonalna. Tada će \tilde{\Phi} \tilde{F}\tilde{\Phi} biti traženog oblika i sve što još treba je pomnožiti matrice U_{11} i V_{11} zdesna s \text{diag}(\text{sgn}(\tilde{a}),1,1). To zapravo znači da je U=\text{diag}(U_{11}\tilde{\Phi} , \text{sgn}(d)) i V=\text{diag}(V_{22}\tilde{\Phi},1). Time je postignut oblik kao u tvrdnji (16) teorema.

4.3Slučaj n=4,  l=2

Ovo je najzanimljiviji slučaj i on zahtijeva dvije singularne dekompozicije, jednu za blok F_{11}, drugu za blok F_{22}. Neka su F_{11}=U_{11} \Gamma_{1} V_{11}^{T} i F_{22}=U_{22} \Gamma_{2} V_{22}^{T} te dvije singularne dekompozicije i neka je U=\text{diag}(U_{11} , U_{22}), V=\text{diag}(V_{11} , V_{22}). Singularna dekompozicija daje dijagonalne elemente od \Gamma_{1} i \Gamma_{2} nenegativne i u nerastućem poretku. Neka je

(4)
\tilde{F}=\left[ \begin{array}{cc} U_{11}^{\tau} & 0 \\ 0 & U_{22}^{\tau} \end{array}\right] \left[ \begin{array}{cc} F_{11} & F_{12} \\ F_{21} & F_{22} \end{array} \right] \left[ \begin{array}{cc} V_{11} & 0 \\ 0 & V_{22} \end{array} \right] = \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & c & d \\ 0 & \gamma_{2} & g & h \\\hline p & q & \gamma_{3} & 0 \\ r & s & 0 & \gamma_{4} \end{array}\right].

Ovdje smo zbog jednostavnijeg pisanja izostavili znak  \tilde{}  na elementima (1,2) i (2,1) blokova matrice \tilde{F}. Uočimo da su matrice U (pa zato i U^{T}), V i FJ-ortogonalne, pa je takva i \tilde{F}. Koristeći relaciju (13) zaključujemo da su singularne vrijednosti dijagonalnih blokova matrice \tilde{F} veće ili jednake 1. Stoga vrijedi

(5)
\gamma_{1}\geq\gamma_{2}\geq 1,\qquad \gamma_{3}\geq\gamma_{4}\geq 1,

pa su oba dijagonalna bloka nesingularna.
Relacije (6), (7) i (8), (9) za matricu \tilde{F} povlače:

(6)
\begin{eqnarray} \gamma_{1}^{2} &=& 1+c^{2}+d^{2}\ \qquad \\[3pt] \gamma_{2}^{2} &=& 1+g^{2}+h^{2}\ \qquad \\[3pt] \gamma_{3}^{2} &=& 1+c^{2}+g^{2}\ \qquad \\[3pt] \gamma_{4}^{2} &=& 1+d^{2}+h^{2}\ \qquad \end{eqnarray}

(7)
\left[\begin{array}{cc}g & d \\ d & g \end{array}\right] \left[\begin{array}{c} c \\ h \end{array}\right] = \left[\begin{array}{c} 0 \\ 0 \end{array}\right]

 

(8)
\begin{eqnarray} \gamma_{1}^{2} &=& 1+p^{2}+r^{2}\qquad \\[3pt] \gamma_{2}^{2} &=& 1+q^{2}+s^{2}\quad \\[3pt] \gamma_{3}^{2} &=& 1+p^{2}+q^{2}\qquad \\[3pt] \gamma_{4}^{2} &=& 1+r^{2}+s^{2}\qquad \end{eqnarray}

(9)
\left[\begin{array}{cc}q & r \\ r & q \end{array}\right] \left[\begin{array}{c} p \\ s \end{array}\right] = \left[\begin{array}{c} 0 \\ 0 \end{array}\right]

Pogledajmo homogeni sustav linearnih jednadžbi (7).

Ako je determinanta sustava različita od nule, tj. ako je |g|\ne |d|, tada je rješenje sustava trivijalno, dakle c=h=0. No, c=h=0 u jednadžbama (6)–(6) daje

\gamma_{1} = \sqrt{1+d^{2}} = \gamma_{4}, \quad \gamma_{2} = \sqrt{1+g^{2}} = \gamma_{3}.

Sada relacija (5) daje \gamma_{2} =\gamma_{3}\geq \gamma_{4} =\gamma_{1}, pa mora biti \gamma_{1} =\gamma_{2} =\gamma_{3} =\gamma_{4}. Iz jednadžbi (6)–(6) odmah slijedi |d|=\sqrt{\gamma_{1}^{2}-1}=\sqrt{\gamma_{2}^{2}-1}=|g|. Dobili smo proturječje s polaznom pretpostavkom |g|\ne |d|, pa zaključujemo da je matrica sustava singularna, tj. vrijedi |g| = |d|.

Jer je |g| = |d|, relacije (6) i (6) povlače \gamma_{1} =\gamma_{3}, a relacije (6) i (6) povlače \gamma_{2} =\gamma_{4}.

Na posve isti način, iz jednadžbi (8)–(9) slijedi |q| = |r|.

Dakle, pokazali smo da mora vrijediti

(10)
\gamma_{1}=\gamma_{3} \geq \gamma_{2} =\gamma_{4}\geq 1\quad\text{i}\quad |g|=|d|,\ \ |q|=|r| .

Kako je |g| = |d|, imamo dvije mogućnosti: g = d i g=-d. Promotrimo ih zasebno.

4.3.1Slučaj   g=d

Sada relacija (7) povlači ili d=0 ili d\ne 0, h=-c.

Promotrimo prvo slučaj d=0. Tada je i g=0. Stoga, ako primijenimo relaciju (7) uz i=2, j=3 na matricu \tilde{F}, dobijemo

0=0\cdot c+\gamma_{2}\cdot g-q\cdot \gamma_{3}-s\cdot 0=0+\gamma_{2}\cdot 0-q\cdot \gamma_{1}-0=-q\cdot \gamma_{1}.

Dakle je q=0. Relacija (10) pokazuje da je |q| = |r|, pa mora biti i r=0.

Primijenimo li relaciju (7) uz i=1, j=3 na matricu \tilde{F}, dobijemo

0=\gamma_{1}\cdot c+0-p\cdot \gamma_{3}-0=\gamma_{1} (c-p),

pa mora biti c=p.

Primjenom relacije (7) uz i=2, j=4 na matricu \tilde{F}, dobijemo

0=0+\gamma_{2}\cdot h-0-s\cdot \gamma_{4}=\gamma_{2} (h-s),

pa mora biti h=s.

Time je pokazano da je matrica \tilde{F} oblika

(11)
\tilde{F} = \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & c & 0 \\ 0 & \gamma_{2} & 0 & h \\\hline c & 0 & \gamma_{1} & 0 \\ 0 & h & 0 & \gamma_{2} \end{array}\right],\quad c=\pm\sqrt{\gamma_{1}^{2}-1},\ h=\pm\sqrt{\gamma_{2}^{2}-1}.

Da bismo osigurali nenegativnost od c i h, još treba načiniti transformaciju sličnosti na matrici \tilde{F} s dijagonalnom matricom D=\text{diag}(\text{sgn}(c),\text{sgn}(h),1,1) koja je i ortogonalna i J-ortogonalna.

Promotrimo i drugu mogućnost: d\ne 0 i h=-c. Kako je i g=d, relacije (6) i (6) pokazuju da je \gamma_{1}=\gamma_{2}, relacije (6) i (6) pokazuju da je \gamma_{3}=\gamma_{4}, a relacije (6) i (6) daju \gamma_{2}=\gamma_{3}. Dakle je \gamma_{1}=\gamma_{2}=\gamma_{3}=\gamma_{4}.

Ako primijenimo relaciju (7) na matricu \tilde{F}, prvo za i=2, j=3, a zatim za i=1, j=4, dobijemo \gamma_{1} (g-q)=0 i \gamma_{1} (d-r)=0, dakle q=g i r=d. Isto tako, primjena relacije (7) na matricu \tilde{F}, prvo za i=1, j=3, a zatim za i=2, j=4, daje \gamma_{1} (c-p)=0 i \gamma_{1} (h-s)=0, dakle p=c i h=s. Stoga \tilde{F} ima oblik

\tilde{F} = \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & c & d \\ 0 & \gamma_{1} & d & -c \\\hline c & d & \gamma_{1} & 0 \\ d & -c & 0 & \gamma_{1} \end{array}\right]

Ako je \gamma_{1}=1, tada je c=d=0, pa smo dobili proturječje s d\ne 0. Dakle je \gamma_{1}\gt 1. Jer je c^{2}+d^{2}\gt 0, dobro je definirana ravninska rotacija R_{12}(\phi ) čiji kut \phi je određen formulama

\mathsf{c}=\cos\phi = \frac{c}{\sqrt{c^{2}+d^{2}}},\quad \mathsf{s}=\sin\phi = \frac{d}{\sqrt{c^{2}+d^{2}}}

Ona je ortogonalna i J-ortogonalna matrica. Sada je

\begin{eqnarray*} R_{12}^{T} (\phi )\tilde{F}R_{12} (\phi ) &=& \left[ \begin{array}{rr|rr} \mathsf{c} & \mathsf{s} & 0 & 0 \\ -\mathsf{s} & \mathsf{c} & 0 & 0 \\\hline 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & c & d \\ 0 & \gamma_{1} & d & -c \\\hline c & d & \gamma_{1} & 0 \\ d & -c & 0 & \gamma_{1} \end{array}\right] \left[ \begin{array}{rr|rr} \mathsf{c} & -\mathsf{s} & 0 & 0 \\ \mathsf{s} & \mathsf{c} & 0 & 0 \\\hline 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \\ &=& \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & \sigma_{1} & 0 \\ 0 & \gamma_{1} & 0 & -\sigma_{1} \\\hline \sigma_{1} & 0 & \gamma_{1} & 0 \\ 0 & -\sigma_{1} & 0 & \gamma_{1} \end{array}\right],\quad \sigma_{1}= \sqrt{c^{2}+d^{2}} = \sqrt{\gamma_{1}^{2}-1}. \end{eqnarray*}

Da bismo promijenili predznak od elementa -\sigma_{1}, dovoljno je načiniti transformaciju sličnosti na tako transformiranoj matrici \tilde{F} s dijagonalnom matricom D=\text{diag}(1,-1,1,1) koja je i ortogonalna i J-ortogonalna.

Time je dobivena tražena dekompozicija (14) matrice F. U njoj je \Gamma =\gamma_{1} I_{2}, \Sigma = \text{diag}(\sigma_{1} ,\sigma_{1}), U_{22} i V_{22} su matrice iz singularne dekompozicije (iz relacije (11)), dok se U_{11} i V_{11} iz (11) trebaju ažurirati (pomnožiti zdesna) s produktom vodećih podmatrica reda od 2 od R_{12}(\phi ) i od D, dakle s matricom \displaystyle \left[ \begin{array}{rr}\mathsf{c} & \mathsf{s} \\ \mathsf{s} & -\mathsf{c} \end{array}\right].

4.3.2Slučaj   g=-d

Razmatranje je vrlo slično prethodnom. Relacija (7) povlači ili d=0 ili d\ne 0, h=c.

Ako je d=0 onda je i g=0. Stoga, ako primijenimo relaciju (7) uz i=2, j=3 na matricu \tilde{F}, dobijemo -q\cdot \gamma_{3}=-q\cdot \gamma_{1}=0, pa je q=0. Prema relaciji (10) vrijedi |q| = |r|, pa mora biti i r=0.

Primjenom relacije (7) uz i=1, j=3 (uz i=2, j=4) na matricu \tilde{F}, dobijemo \gamma_{1} (c-p)=0  (\gamma_{2} (h-s)=0), pa mora biti c=p (h=s). Time je pokazano da je matrica \tilde{F} istog oblika kao u relaciji (11), pa se dokaz završi na isti način kao u točki 4.3.1.

Promotrimo i drugu mogućnost: h=c. Kako je i g=-d, relacije (6) i (6) pokazuju da je \gamma_{1}=\gamma_{2}, pa je zbog relacije (10) \gamma_{1}=\gamma_{2}=\gamma_{3}=\gamma_{4}.

Primijenimo li relaciju (7) na matricu \tilde{F}, prvo za i=2, j=3, a zatim za i=1, j=4, dobijemo \gamma_{1} (g-q)=0 i \gamma_{1} (d-r)=0, dakle je q=g i r=d. Isto tako, primjena relacije (7) na matricu \tilde{F}, prvo za i=1, j=3, a zatim za i=2, j=4, daje \gamma_{1} (c-p)=0 i \gamma_{1} (h-s)=0, dakle p=c i s=h. Stoga \tilde{F} ima oblik

\tilde{F} = \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & c & d \\ 0 & \gamma_{1} & -d & c \\\hline c & -d & \gamma_{1} & 0 \\ d & c & 0 & \gamma_{1} \end{array}\right]

Ako je \gamma_{1}=1, tada je c=d=0, pa je \tilde{F} = I_{4} i dokaz je gotov.

Ako je \gamma_{1}\gt 1, tada je c^{2}+d^{2}\gt 0, pa je dobro definirana ravninska rotacija R_{12}(\psi ) čiji kut \phi je određen formulama

\mathsf{c}=\cos\psi = \frac{c}{\sqrt{c^{2}+d^{2}}},\quad \mathsf{s}=\sin\psi = - \frac{d}{\sqrt{c^{2}+d^{2}}}

Ona je ortogonalna i J-ortogonalna matrica. Sada je

\begin{eqnarray*} R_{12}^{T} (\psi )\tilde{F}R_{12} (\psi )\! &=& \!\left[ \begin{array}{rr|rr} \mathsf{c} & \mathsf{s} & 0 & 0 \\ -\mathsf{s} & \mathsf{c} & 0 & 0 \\\hline 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & c & d \\ 0 & \gamma_{1} & -d & c \\\hline c & -d & \gamma_{1} & 0 \\ d & c & 0 & \gamma_{1} \end{array}\right] \left[ \begin{array}{rr|rr} \mathsf{c} & -\mathsf{s} & 0 & 0 \\ \mathsf{s} & \mathsf{c} & 0 & 0 \\\hline 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \\ &=& \left[ \begin{array}{ll|rr} \gamma_{1} & 0 & \sigma_{1} & 0 \\ 0 & \gamma_{1} & 0 & \sigma_{1} \\\hline \sigma_{1} & 0 & \gamma_{1} & 0 \\ 0 & \sigma_{1} & 0 & \gamma_{1} \end{array}\right],\quad \sigma_{1}= \sqrt{c^{2}+d^{2}} = \sqrt{\gamma_{1}^{2}-1}. \end{eqnarray*}

Time je dobivena tražena dekompozicija (14) matrice F. U njoj je \Gamma =\gamma_{1} I_{2}, \Sigma = \sigma_{1}I_{2}, U_{22} i V_{22} su iz singularne dekompozicije, tj. iz relacije (11), dok se U_{11} i V_{11} iz (11) trebaju ažurirati (pomnožiti zdesna) s vodećom podmatricom reda 2 od R_{12}(\psi ).

Primjer 7. Evo primjera CS dekompozicije J ortogonalne matrice W. Ako je
W\!=\!\frac{1}{8}\left[\begin{array}{cc|cc} \sqrt{30} - 2\sqrt{6} & 6\sqrt{2} + \sqrt{10} & -8 & 2\sqrt{2}\\ 2\sqrt{6}+ \sqrt{30} & \sqrt{10} - 6 \sqrt{2} & 8 & 2\sqrt{2}\\\hline -4\sqrt{2} & 4\sqrt{6} & - 8\sqrt{3} & 0\\ 2\sqrt{3} & 2 & 0 & 4\sqrt{5} \end{array}\right],\ J\!=\!\left[\begin{array}{rr|rr} 1&&&\\ &1&&\\\hline &&-1&\\ &&&-1 \end{array}\right],
tada je {
W= \left[\begin{array}{rr|rr} \frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}&&\\ -\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}&&\\\hline && \frac{\sqrt{3}}{2}&\frac{1}{2}\\ && -\frac{1}{2}&\frac{\sqrt{3}}{2} \end{array}\right] \left[\begin{array}{rr|rr} \sqrt{3}&&\sqrt{2}&\\ &\frac{\sqrt{5}}{2}&&\frac{1}{2}\\\hline \sqrt{2}&& \sqrt{3}&\\ &\frac{1}{2}&&\frac{\sqrt{5}}{2} \end{array}\right] \left[\begin{array}{rr|rr} -\frac{1}{2}&\frac{\sqrt{3}}{2}&&\\ \frac{\sqrt{3}}{2}&\frac{1}{2}&&\\\hline && 1&\\ && &-1 \end{array}\right]
. }

Napomena 8. U slučaju kada je podmatrica F_{11} (F_{22}) reda dva, tada su ortogonalne matrice U_{11} i V_{11} (U_{22} i V_{22}) ravninske rotacije ili reflektori. Ako je determinanta od F_{11} (F_{22}) pozitivna, tada korištenjem Binet-Cauchyjevog teorema lako zaključimo da obje matrice U_{11} i V_{11} (U_{22} i V_{22}) moraju biti ili rotacije ili reflektori. Korištenjem matrica \text{diag}(1,-1) ili \text{diag}(-1,1) možemo ih sve načiniti rotacijama ili reflektorima, ne mijenjajući ni \Gamma niti \Sigma. Ako je determinanta od F_{11} (F_{22}) negativna, tada tek možemo birati koju od matrica U_{11} ili V_{11} (U_{22} ili V_{22}) načiniti rotacijom. Druga će biti reflektor.

5Primjena na blok J-Jacobijeve metode

Ako se na računalu žele izračunati vlastite vrijednosti i vektori nesingularne indefinitne simetrične matrice H reda n, s visokom relativnom točnosti, matrica H se dekomponira pomoću posebne matrične faktorizacije [1] na produkt H=GJG^{T} gdje je J=\text{diag}(I_{l},-I_{n-l}), a G je nesingularna matrica reda n. Problem se zapisuje kao

Hx=\lambda x, \quad x\ne 0\qquad\text{odnosno}\qquad GJG^{T}x=\lambda x, \quad x\ne 0.

Pomnožimo zadnju jednadžbu slijeva s G^{T} i definirajmo vektor z=JG^{T}x. Tada je G^{T}G(JG^{T}x)=\lambda G^{T}x=\lambda J(JG^{T}x), pa smo dobili generalizirani problem vlastitih vrijednosti (GPVV)

Az=\lambda Jz, \quad z\ne 0,\quad\text{pri čemu je}\quad A=G^{T}G,\quad (JG^{T})x=z,

tj. kad izračunamo z, vlastiti vektor x se dobije rješavajući sustav linearnih jednadžbi s matricom sustava JG^{T}. Pritom je G matrica sa puno nula pa se rješenje sustava brzo i vrlo točno izračuna.

Jer je matrica A pozitivno definitna za par simetričnih matrica (A,J) postoji nesingularna matrica Z, takva da vrijedi Z^{T}AZ=D_{A} i Z^{T}JZ=D_{J}, pri čemu su D_{A} i D_{J} dijagonalne. Kako kongruencija čuva inerciju simetrične matrice, nesingularna dijagonalna matrica D_{J}=\text{diag}(d_{1},\ldots ,d_{n}) ima točno n-l negativnih dijagonalnih elemenata. Stoga postoji matrica permutacije P reda n takva da matrica P^{T}D_{J}P ima prvih l dijagonalnih elemenata pozitivne. Tada za nesingularnu matricu F=Z|D_{J}|^{-\frac{1}{2}}P vrijedi

\begin{eqnarray*} F^{T}JF &=& P^{T}\,|D_{J}|^{-\frac{1}{2}}\,Z^{T}JZ\,|D_{J}|^{-\frac{1}{2}}\,P = P^{T}\,|D_{J}|^{-\frac{1}{2}} D_{J}|D_{J}|^{-\frac{1}{2}}\,P =J,\\ F^{T}AF &=& P^{T}\,|D_{J}|^{-\frac{1}{2}}\,Z^{T}AZ\,|D_{J}|^{-\frac{1}{2}}\,P = P^{T}\,|D_{J}|^{-\frac{1}{2}} D_{A}|D_{J}|^{-\frac{1}{2}}\,P =\Lambda_{A} . \end{eqnarray*}

Pritom je \displaystyle |D_{J}|^{-\frac{1}{2}}=\text{diag}\left(1/\sqrt{|d_{1}|},\ldots ,1/\sqrt{|d_{n}|}\right), pa je \Lambda_{A} dijagonalna. Iz prve relacije vidimo da je FJ-ortogonalna matrica. Za nalaženje matrice F i dijagonalne matrice \Lambda_{A} postoji vrlo točna tzv. J-Jacobijeva metoda [5].

Ta metoda bazirana je na činjenici da za par matrica (\hat{A},\hat{J}),

\hat{A}=\left[\begin{array}{cc}a_{11}&a_{12}\\ a_{12}&a_{22}\end{array}\right],\qquad \hat{J}=\left[\begin{array}{cc}1&\\ &-1\end{array}\right],

pri čemu je \hat{A} pozitivno definitna, postoji \hat{J}-ortogonalna matrica \hat{F} takva da vrijedi \hat{F}^{T}\hat{A}\hat{F}=\text{diag}(a_{11}',a_{22}'). Pritom je (vidjeti [5])

\hat{F}=\left[\begin{array}{cc} \text{cosh} y& \text{sinh} y\\ \text{sinh} y& \text{cosh} y\end{array}\right],\quad \text{tanh} 2y= -\frac{2a_{12}}{a_{11}+a_{22}},\quad \begin{array}{l} a_{11}'=a_{11}+ \text{tanh} y \,a_{12},\\ a_{22}'=a_{22}+\text{tanh} y\, a_{12}. \end{array}

U općem slučaju kad su matrice A i J reda n, Veselićev J-Jacobijev algoritam [5] primjenjuje ove formule tako da izabire glavne podmatrice reda dva, \hat{A} od A i \hat{J} od J, u nekom redoslijedu, i primijenjuje ravninske hiperbolne rotacije. Ako je \hat{J} jednak I_{2} ili -I_{2}, koristi se jedan korak standardne Jacobijeve metode koja koristi ravninske rotacije.

Kada se F i \Lambda_{A} izračunaju, tražena dijagonalna matrica vlastitih vrijednosti od H je J\Lambda_{A}, dok je pripadna matrica ortonormiranih vektora Q=G^{-T}JF\Lambda_{A}^{\frac{1}{2}}. Doista,

\begin{eqnarray*} Q^{T}HQ &=& \Lambda_{A}^{\frac{1}{2}}F^{T}JG^{-1}\,GJG^{T}\,G^{-T}JF\Lambda_{A}^{\frac{1}{2}} = \Lambda_{A}^{\frac{1}{2}}F^{T}JF\Lambda_{A}^{\frac{1}{2}} =J\Lambda_{A} ,\\ Q^{T}Q &=& \Lambda_{A}^{\frac{1}{2}}(F^{T}J)(G^{-1}\,G^{-T})(JF)\Lambda_{A}^{\frac{1}{2}} = \Lambda_{A}^{\frac{1}{2}}JF^{-1}A^{-1}F^{-T}J\Lambda_{A}^{\frac{1}{2}}\\ &=& \Lambda_{A}^{\frac{1}{2}}J(F^{T}AF)^{-1}J\Lambda_{A}^{\frac{1}{2}} = \Lambda_{A}^{\frac{1}{2}}J\Lambda_{A}^{-1}J\Lambda_{A}^{\frac{1}{2}} =I_{n}. \end{eqnarray*}

Dakle, ortogonalna matrica Q dobijena je kao produkt u kojem se uz J nalaze tri neortogonalne matrice! Uočimo da je H=Q\Lambda Q^{T}, \Lambda=J\Lambda_{A} spektralna dekompozicija od H.

Danas je po brzini i visokoj relativnoj točnosti jedna od najefikasnijih metoda za istovremenu dijagonalizaciju matrica A i J tzv. jednostrana blok J-Jacobijeva metoda [2], koja je modifikacija Veselićeve J-Jacobijeve metode [5]. Ta blok metoda na svakom koraku treba rješenje vlastitog problema \hat{A}\hat{z}= \hat{\lambda}\hat{J}\hat{z} sa matricama \hat{A} i \hat{J} koje su manje dimenzije. Kod standardne (po elementima) J-Jacobijeve metode je \hat{n}=2, a kod blok metode je veći. Najčešće je ta dimenzija \hat{n}\in\lbrace 32,64,128\rbrace i \hat{n} ovisi o veličini cache memorije računala. Ovi manji problemi uspješno se rješavaju standardnom J-Jacobijevom metodom. Da bi se i ta obična metoda ubrzala, može se zamijeniti sa specijalnom blok J-Jacobijevom metodom koja na svakom koraku rješava GPVV sa matricama \tilde{A} i \tilde{J} koje su reda 4 ili 3 (3 samo ako je n neparan i \hat{A} ima elemente iz zadnjeg stupca matrice A). U tom slučaju se takova J-Jacobijeva metoda može uspješno koristiti i kad je red matrice A nekoliko tisuća.

Ako su \tilde{A} i \tilde{J} dimenzije 4 ili 3, postavlja se pitanje kako najbrže izračunati matricu \tilde{F} koja zadovoljava uvjet \tilde{F}^{T}\tilde{J}\tilde{F}=\tilde{J} i uvjet da je \tilde{F}^{T}\tilde{A}\tilde{F} dijagonalna matrica. Drugim riječima, otvara se problem kako izračunati što točnije i brže (sa što manje računskih operacija) traženu \tilde{J}-ortogonalnu matricu \tilde{F}. Jer je \tilde{A} pozitivno definitna, zna se da tražena \tilde{F} postoji.

Tu će nam pomoći rezultati iz prethodne točke o CS dekompoziciji J-ortogonalne matrice reda 3 i 4. Prvo ćemo se osvrnuti na slučaj kada su \tilde{A} i \tilde{J} reda 3, a zatim na slučaj kada su reda 4. Zbog lakšeg pisanja, maknut ćemo znak tilde sa matrica.

5.1Slučaj  n=3

Kada je n=3, najzanimljiviji je slučaj l=2. Iz teorema 5 za slučaj n=3, l=2, pogledajmo što nam kaže relacija (16). Vidimo da su matrice U_{11} i V_{11} reda 2 dok su U_{22} i V_{22} ortogonalne matrice reda 1, dakle brojevi 1 ili -1.

Napomena 9. Lako je pokazati da ortogonalne matrice reda 2 moraju biti rotacije ili reflektori, tj. oblika
R(\phi )=\left[\begin{array}{rr} c&-s \\ s&c\end{array}\right]\ \ \text{ili}\ \ \mathsf{R}(\phi )=\left[\begin{array}{rr} c&s \\ s&-c\end{array}\right],\quad c=\cos\phi ,\ \ s=\sin\phi, \ \phi\in [-\pi ,\pi ].
Uočimo da je \mathsf{R}(\phi )=R(\phi )D_{2}, gdje je D_{2}=\text{diag}(1,-1). Ako stavimo \Phi (\phi)=\text{sgn}(c)D_{2} onda vrijedi \mathsf{R}(\phi )=R(\psi )\Phi (\phi), \psi\in [-\frac{\pi}{2},\frac{\pi}{2}].

Matricu F možemo pisati u obliku

\begin{eqnarray*} F &=& \left[\begin{array}{rr|r} u_{11}&u_{12} & \\ u_{21}&u_{22}& \\\hline && u_{0} \end{array}\right] \left[\begin{array}{rr|r} \gamma_{1} & 0& \sigma_{1} \\ 0&1&0\\\hline \sigma_{1} & 0& \gamma_{1} \end{array}\right] \left[\begin{array}{rr|r} v_{11}&v_{21}&\\ v_{12}&v_{22}&\\\hline && v_{0}\end{array}\right], \ u_{0},v_{0}\in\lbrace -1,1\rbrace \\ &=& U_{12}W_{13}V_{12}^{T}. \end{eqnarray*}

Kada se na matricu A uzastopce primijene transformacije kongruencije, prvo s U_{12}, zatim sa W_{13} i konačno sa V_{12}^{T} moramo dobiti dijagonalnu matricu. Možemo pisati

\Lambda = F^{T}AF= V_{12}\left(W_{13}^{T}\left(U_{12}^{T} \left[\begin{array}{rr|r} a_{11}&a_{12}&a_{13}\\ a_{12}&a_{22}&a_{23}\\\hline a_{13}&a_{23}&a_{33}\end{array}\right] U_{12}\right)W_{13}\right)V_{12}^{T}

gdje je \Lambda dijagonalna. Matrice U_{12} i V_{12} su ravninske ortogonalne matrice, a W_{13} je ravninska J-ortogonalna matrica (tzv. hiperbolna rotacija).

Gledajući zadnju relaciju, možemo sljedeće zaključiti. Ravninska ortogonalana matrica V_{12}  (V_{12}^{T}) ne mijenja sumu kvadrata elemenata na pozicijama (1,3) i (2,3)  (odnosno (3,1) i (3,2)), a kako se ona primijenjuje zadnja, moraju elementi na pozicijama (1,3) i (2,3)  ((3,1) i (3,2)) već biti nula. Stoga je uloga od V_{12}^{T}, tansformacijom kongruencije (koja je i sličnost jer je V_{12} ortogonalna) poništiti elemente na pozicijama (1,2) i (2,1). To znači da transformacija sa matricom U_{12} treba pripremiti matricu A kako da bi transformacija s W_{13} poništila oba elementa na pozicijama (1,3) i (2,3). Dakle će se matrica V_{12} lako odrediti, npr. kao Jacobijeva rotacija.

Stoga je uloga J-ortogonalne matrice W_{13} transformacijom kongruencije poništiti elemente matrice U_{12}^{T}AU_{12} na pozicijama (1,3), (2,3) i (3,1), (3,2). Još kažemo da W_{13} mora biti istovremeno i Jacobijeva i Givensova hiperbolna rotacija. Da bi to mogla biti, uloga matrice U_{12} mora biti prirediti matricu A tako da to bude moguće. Stoga očekujemo najveći problem u određivanju elemenata matrice matrice U_{12}. Vjerojatno će trebati riješiti polinomijalnu (kubnu) jednadžbu za npr. tangens kuta koji određuje U_{12}.

Primjer 10. Neka je L zadana donje-trokutasta matrica, a J=\text{diag}(1,1,-1). Tada je H=LJL^{T} indefinitna nesingularna simetrična matrica. Relacija H=LJL^{T} za konkretnu matricu L ima sljedeći oblik:
H=\left[\begin{array}{rr|r} 4&-2&-1\\ -2&2&1\\\hline -1&1&-\frac{1}{2} \end{array}\right]= \left[\begin{array}{rr|r} 2&0&0\\ -1&1&0\\\hline -\frac{1}{2}&\frac{1}{2}&1 \end{array}\right] \left[\begin{array}{rr|r} 1&0&0\\ 0&1&0\\\hline 0&0&-1 \end{array}\right] \left[\begin{array}{rr|r} 2&-1&-\frac{1}{2}\\ 0&1&\frac{1}{2}\\\hline 0&0&1 \end{array}\right].

Problem se zapisuje kao Hx=\lambda x,   x\ne 0 i kako smo objasnili, svede se na oblik Az=\lambda Jz,  z\ne 0, pri čemu je  A=L^{T}L,  (JL^{T})x=z. Tražimo F koja zadovoljava F^{T}AF=\Lambda_{A} i F^{T}JF=J. Koristit ćemo MATLAB i njegov Symbolic toolbox da bismo račun načinili u aritmetici promjenjive preciznosti sa 80 dekadskih znamenaka. Ispis matrica međurezultata je načinjen tako da su se one prvo pretvorile (aproksimirale) u matrice tzv. dvostruke (double) preciznosti.

Prvo ispisujemo matrice A i F:
\begin{eqnarray*} A &=& \left[\begin{array}{rr|r} 5.25 & -1.25\ &\ -0.5 \\ -1.25 & 1.25\ &\ 0.5 \\\hline -0.5 & -0.5 \ &\ 1 \end{array}\right]\\ F &\approx& \left[\begin{array}{rr|r} 2.561736523957978e-01 & 9.674219085764793e-01\ &\ 3.911635687996478e-02\\ 9.871794546361790e-01 & -2.702217520080404e-01\ &\ -2.180437362413296e-01\\\hline -2.003701969794577e-01 & 9.447192414708516e-02\ &\ 1.024242725280311e+00 \end{array}\right] \end{eqnarray*}

Znamo da možemo načiniti hiperbolnu CS dekompoziciju matrice F,
F=UWV^{T} = U_{12}W_{13}V_{12}^{T}.
Izvod hiperbolne CSD u slučaju kada je n=3, l=2 ukazuje kako treba napisati algoritam koji se koristi u MATLABu. Matrice U_{12}, W_{13} i V_{12} su izračunate u visokoj preciznosti i onda su pretvorene u matrice dvostruke preciznosti. To znači da su im elementi točni u prvih 16 značajnih znamenaka.

Sada možemo primijeniti na A uzastopne transformacije kongruencije sa U_{12}, W_{13} i V_{12}^{T} i vidjeti na koji način i u kojem redoslijedu se poništavaju izvandijagonalni elementi od A. Mi ćemo prikazati najzanimljivije fenomene. Neka je
A^{(1)} = U_{12}^{T}AU_{12},\quad A^{(2)} = W_{13}^{T} A^{(1)}W_{13},\quad A^{(3)} =V_{12} A^{(2)}V_{12}^{T} .
Pođimo redom. Matrica U_{12} treba pripremiti matricu A kako bi hiperbolna rotacija W_{13} “blok dijagonalizirala” matricu A^{(1)}. Zadnja kongruencija sa V_{12}^{T} služi za dijagonalizaciju prvog dijagonalnog bloka, tj. za poništavanje elemenata na pozicijama (1,2) i (2,1) od A^{(3)}. Evo kako izgledaju izračunate matrice A^{(1)}, A^{(2)} i A^{(3)}:

\text{}A^{(1)}\text{} = \left[\begin{array}{rr|r} 1.809227260806340e\text{}+\text{}00 \ &\ -1.867263750517425e\text{}+\text{}00 \ \ &\ -5.804322905490655e\text{–}01\\[2pt] -1.867263750517425e\text{}+\text{}00 \ &\ 4.690772739193664e\text{}+\text{}00 \ \ &\ 4.038543748530719e\text{–}01\\[1pt]\hline\\[-6pt] -5.804322905490655e\text{–}01 \ &\ 4.038543748530719e\text{–}01 \ \ &\ 1.000000000000000e\text{}+\text{}00 \end{array}\right]
\text{}A^{(2)}\text{} = \left[\begin{array}{rr|r} 1.683690565854021e\text{}+\text{}00 \ &\ -1.823067622966421e\text{}+\text{}00 \ \ &\ 9.992007221626409e\text{–}16\\[2pt] -1.823067622966421e\text{}+\text{}00 \ &\ 4.690772739193664e\text{}+\text{}00 \ \ &\ -2.942091015256665e\text{–}15\\[1pt]\hline\\[-6pt] 9.714451465470120e\text{–}16 \ &\ -2.997602166487923e\text{–}15 \ \ &\ 8.744633050476804e\text{–}01 \end{array}\right]
\text{ }A^{(3)}\text{} = \left[\begin{array}{rr|r} 8.241380536131467e\text{–}01 \ & \ -1.831867990631508e\text{–}15 \ \ &\ \ \ 3.509088574926918e\text{–}16\\[2pt] -1.332267629550188e\text{–}15 \ & \ 5.550325251434538e\text{}+\text{}00 \ \ &\ \ \ 3.087258427627578e\text{–}15\\[1pt]\hline\\[-6pt] 3.996873412970663e\text{–}16 \ & \ 3.125631848201211e\text{–}15 \ \ &\ \ \ 8.744633050476804e\text{–}01 \end{array}\right]

Vidimo da kongruencija sa matricom W_{13} “poništava” elemente na pozicijama (1,3), (2,3), (3,1) i (3,2), dok transformacija s V_{12}^{T} poništava elemente na pozicijama (1,2) i (2,1), kako smo i predvidjeli.

Vlastite vrijednosti matrice H dobiju se kao produkt dijagonalnih elemenata matrica F^{T}AF i J: \lambda_{1}\approx 0.8241381, \lambda_{2}\approx 5.550325 i \lambda_{3}\approx -0.8744633. Pripadni vlastiti vektori su stupci od Q=L^{-T}JF\Lambda_{A}^{\frac{1}{2}}, a računaju se povratnim postupkom (stupac po stupac) iz linearne jednadžbe L^{T}X=JF\Lambda_{A}^{\frac{1}{2}}.

5.2Slučaj  n=4

Najzanimljiviji je slučaj kada je l=2. Relacija (16) iz teorema 5, za slučaj n=4, l=2, pokazuje da se J-ortogonalna matrica reda 4 može prikazati kao produkt od 4 ortogonalne i dvije hiperbolne ravninske matrice. Matricu F možemo pisati u obliku

\begin{eqnarray*} F &=& \left[\begin{array}{cc|cc} u_{11}&u_{12} & & \\ u_{21}&u_{22}& &\\\hline && u_{33}&u_{34}\\ && u_{43}&u_{44} \end{array}\right] \left[\begin{array}{cc|cc} \gamma_{1} & 0& \sigma_{1} &0\\ 0&\gamma_{2}&0&\sigma_{2}\\\hline \sigma_{1} & 0& \gamma_{1}&0\\ 0&\sigma_{2}& 0&\gamma_{2} \end{array}\right] \left[\begin{array}{cc|cc} v_{11}&v_{21} & & \\ v_{12}&v_{22}& &\\\hline && v_{33}&v_{43}\\ && v_{34}&v_{44} \end{array}\right]\\ &=& U_{12}U_{34}\, W_{13}W_{24}\, V_{12}^{T} V_{34}^{T}. \end{eqnarray*}

Za razliku od istoimenih matrica iz točke 5.1, sada su U_{12}, W_{13} i V_{12} ravninske matrice reda 4. Takve su i U_{34}, W_{24} i V_{34}. Pritom ortogonalne matrice U_{12} i U_{34} (V_{12} i V_{34}) međusobno komutiraju, baš kao i J-ortogonalne matrice W_{13} i W_{24}.

Kada se na matricu A uzastopce primijene transformacije kongruencije, prvo sa U_{12} i U_{34} zatim sa W_{13} i W_{24}, te konačno sa V_{12}^{T} i V_{34}^{T}, moramo dobiti dijagonalnu matricu F^{T}AF=\Lambda_{A}. To možemo zapisati ovako:
 

\Lambda_{A} = V_{34}V_{12}\left(\!W_{24}^{T} W_{13}^{T}\left(\! U_{34}^{T} U_{12}^{T} \left[\begin{array}{cc|cc} a_{11}&a_{12}&a_{13}&a_{14}\\ a_{12}&a_{22}&a_{23}&a_{24}\\\hline a_{13}&a_{23}&a_{33}&a_{34}\\ a_{14}&a_{24}&a_{34}&a_{44} \end{array}\right] U_{12}U_{34}\!\right)W_{13}W_{24}\!\right)V_{12}^{T} V_{34}^{T}.

Slično kao u slučaju n=3 možemo zaključiti sljedeće. Uloga transformacija sa matricama V_{12}^{T} i V_{34}^{T} je poništiti elemente na pozicijama (1,2), (2,1) i (3,4), (4,3), respektivno. Transformacije sa matricama W_{13} i W_{24} trebaju poništiti sve elemente na pozicijama (1,3), (1,4), (2,3), (2,4) i (3,1), (4,1), (3,2), (4,2), a da bi to mogle, moraju transformacije sa U_{12} i U_{34} prirediti matricu A za to.

Primjer 11. Neka je L zadana donje-trokutasta matrica, a J=\text{diag}(I_{2},-I_{2}). Tada je H=LJL^{T} indefinitna nesingularna simetrična matrica. Relacija H=LJL^{T} za konkretnu matricu L ima sljedeći oblik:
H=\left[\begin{array}{rrrr} 4&-2&-1&\frac{2}{5}\\ -2&2&\frac{1}{2}&-\frac{3}{5}\\ -1&\frac{1}{2}&0&-\frac{3}{20}\\ \frac{2}{5}&-\frac{3}{5}&-\frac{3}{20}&\frac{3}{20} \end{array}\right]= \left[\begin{array}{rrrr} 2&0&0&0\\ -1&1&0&0\\ -\frac{1}{2}&0&\frac{1}{2}&0\\ \frac{1}{5}&-\frac{2}{5}&\frac{1}{10}&\frac{1}{5} \end{array}\right] \left[\begin{array}{rrrr} 1&0&0&0\\ 0&\phantom{\text{}-\text{}}1&0&0\\ 0&0&-1&0\\ 0&0&0&-1 \end{array}\right] \left[\begin{array}{rrrr} 2&-1&-\frac{1}{2}&\frac{1}{5}\\ 0&1&0&-\frac{2}{5}\\ 0&0&\frac{1}{2}&\frac{1}{10}\\ 0&0&0&\frac{1}{5} \end{array}\right].

Problem se zapisuje kao Hx=\lambda x,   x\ne0 i kako smo objasnili, svede se na oblik
Az=\lambda Jz, \quad z\ne 0,\quad\text{pri čemu je}\quad A=L^{T}L,\quad (JL^{T})x=z.
Tražimo F koja zadovoljava F^{T}AF=\Lambda_{A},  F^{T}JF=J. Koristimo MATLAB na sličan način kako je to objašnjeno u prethodnom primjeru. Prvo smo izračunali matrice A i F.

A=\left[\begin{array}{rr|rr} 5.29e+00 & -1.08e+00\ &\ -2.3e-01 & 4.00e-02\\ -1.08e+00 & 1.16e+00\ &\ -4.0e-02 & -8.00e-02\\\hline -2.30e-01 & -4.00e-02\ &\ 2.6e-01 & 2.00e-02\\ 4.00e-02 & -8.00e-02\ &\ 2.0e-02 & 4.00e-02 \end{array}\right],

F\approx\left[\begin{array}{cc|cc} 0.2427978387670312 & 0.9716871112257911\ &\ 0.05583771862956592 & 0.002963411970954754\\ 0.9762085972426619 & -0.2393626027437477\ &\ 0.07587208631158646 & 0.06723918085070529\\\hline 0.08181757279331632 & 0.03687414741170095\ &\ 1.001339200694919 & -0.07330500062608739\\ 0.07238715785715838 & -0.01051641418185013\ &\ 0.07870342721056436 & 0.9995780440441821 \end{array}\right]
Znamo da možemo načiniti hiperbolnu CS dekompoziciju matrice F,
F=UWV^{T} = U_{12}U_{34}W_{13}W_{24}V_{12}^{T} V_{34}^{T}.
U odjeljku 4.3 opisan je postupak za određivanje svih tih 6 matrica. Taj postupak je jednostavno pretvoriti u program. Kao i prije, koristimo MATLAB i Symbolic Toolbox sa aritmetikom varijabilne preciznosti sa 80 dekadskih znamenaka. Kao izlazni podaci, te matrice su pretvorene u matrice dvostruke preciznosti.

Sada možemo primijeniti na A uzastopne transformacije kongruencije sa U_{12}, U_{34}, W_{13}, W_{24}, V_{12}^{T} i V_{34}^{T} i vidjeti kako i kojim redom se poništavaju izvandijagonalni elementi od A. Mi ćemo prikazati najzanimljivije fenomene. Neka je
\begin{eqnarray*} A^{(2)} &=& U^{T}AU=U_{34}^{T}U_{12}^{T}AU_{12}U_{34},\\ A^{(3)} &=& W_{13}^{T} A^{(2)}W_{13},\ \ A^{(4)}= W_{24}^{T} A^{(3)}W_{24},\\ A^{(6)} &=& V A^{(4)}V^{T}= V_{34}V_{12} A^{(4)}V_{12}^{T} V_{34}^{T}. \end{eqnarray*}
Pođimo redom. Matrice U_{12} i U_{34} (odnosno matrica U) trebaju pripremiti matricu A kako bi hiperbolne rotacije W_{13} i W_{24} “blok dijagonalizirale” matricu A^{(2)}. Zadnje dvije kongruencije sa V_{12}^{T} i V_{34}^{T} služe za dijagonalizaciju dobivenih dijagonalnih blokova. Evo kako izgledaju matrice A^{(2)}, A^{(3)}, A^{(4)}, i A^{(6)}:

\left[\begin{array}{rr|rr} 1.088223465155945 00 \ & \ 9.299521708882834\text{–}01 \ &\ \ \text{–}1.403526696245988\text{–}01\ & \ \text{–}4.039179998224724\text{–}02\\ 9.299521708882834\text{–}01 \ & \ 5.361776534844054 00 \ &\ \ \text{–}1.060107554620273\text{–}01\ & \ \text{–}1.730067927851752\text{–}01\\\hline \text{–}1.403526696245988\text{–}01 \ & \ \text{–}1.060107554620273\text{–}01\ &\ \ 1.955255429095872\text{–}01 \ & \ 1.021147635887550\text{–}01\\ \text{–}4.039179998224726\text{–}02 \ & \ \text{–}1.730067927851752\text{–}01\ &\ \ 1.021147635887550\text{–}01 \ & \ 1.044744570904127\text{–}01 \end{array}\right]
\left[\begin{array}{rr|rr} 1.072690726500961 00 \ & \ 9.238952584600005\text{–}01 \ & \ \ \text{–}1.831867990631508\text{–}15 \ & \ \text{–}2.927062675041160\text{–}02\\ 9.238952584600005\text{–}01 \ & \ 5.361776534844054 00 \ & \ \ \text{–}3.112673877916583\text{–}03 \ & \ \text{–}1.730067927851752\text{–}01\\\hline \text{–}1.835337437583462\text{–}15 \ & \ \text{–}3.112673877916597\text{–}03 \ & \ \ 1.799928042546040\text{–}01 \ & \ 9.824814007065660\text{–}02\\ \text{–}2.927062675041162\text{–}02 \ & \ \text{–}1.730067927851752\text{–}01 \ & \ \ 9.824814007065662\text{–}02 \ & \ 1.044744570904127\text{–}01 \end{array}\right]
\left[\begin{array}{rr|rr} 1.072690726500961 00 \ & \ 9.234314695820740\text{–}01 \ & \ \text{–}1.831867990631508\text{–}15 \ & \ \text{–}1.953298633949885\text{–}15\\ 9.234314695820740\text{–}01 \ & \ 5.356295375361384 00 \ & \ \text{–}1.004708469198867\text{–}14 \ & \ \text{–}1.637578961322106\text{–}15\\\hline \text{–}1.835337437583462\text{–}15 \ & \ \text{–}1.006139616066548\text{–}14 \ & \ 1.799928042546040\text{–}01 \ & \ 9.819882020000592\text{–}02\\ \text{–}1.967176421757699\text{–}15 \ & \ \text{–}1.710871028182126e\text{–}15 \ & \ 9.819882020000594\text{–}02 \ & \ 9.899329760774431\text{–}02 \end{array}\right]
\left[\begin{array}{rr|rr} 8.821031015553899\text{–}01 \ & \ \text{–}9.159339953157542\text{–}16 \ & \ \ \text{–}6.831387316538583\text{–}16 \ & \ 1.446383537458862\text{–}15\\ \text{–}8.881784197001252\text{–}16 \ & \ 5.546883000306955 00 \ & \ \ \text{–}9.596581516298218\text{–}15 \ & \ \text{–}4.017911259345387\text{–}15\\\hline \text{–}6.828780846655310\text{–}16 \ & \ \text{–}9.650296458455715\text{–}15 \ & \ \ 2.457156394325458\text{–}01 \ & \ 2.775557561562891\text{–}17\\ 1.445086068561601\text{–}15 \ & \ \text{–}3.964114150840219\text{–}15 \ & \ \ 3.469446951953614\text{–}18 \ & \ 3.327046242980235\text{–}02 \end{array}\right]\!\!.

Ovdje smo ispustili oznaku eksponenta “e”, ali smo zadržali predznak eksponenta i onda kada je pozitivan. Vidimo da kongruencija sa matricom W_{13} “poništava” tek (1,3)–element, dok sljedeća sa W_{24} poništava čak tri elementa u gornjem trokutu matrice, na pozicijama (1,4), (2,3) i (2,4). Zadnje transformacije s V_{12}^{T} i V_{34}^{T} poništavaju elemente na pozicijama (1,2), (2,1) i (3,4), (4,3), respektivno, kako smo i predvidjeli.

Vlastite vrijednosti matrice H dobiju se kao produkt dijagonalnih elemenata matrica F^{T}AF i J: \lambda_{1}\approx 5.546883, \lambda_{2}\approx 0.8821031, \lambda_{3}\approx -0.2457156 i \lambda_{4}\approx -0.03327046. Pripadni vlastiti vektori su stupci od Q=L^{-T}JF\Lambda_{A}^{\frac{1}{2}}, a računaju se povratnim postupkom iz linearne jednadžbe L^{T}X=JF\Lambda_{A}^{\frac{1}{2}}.


Zahvala. Ovaj rad djelomično je financiran sredstvima projekta IP-2014-09-3670 Hrvatske zaklade za znanost. Jadna od tema tog projekta je dijagonalizaciju matrica malog reda uz tek nekoliko ravninskih transformacija. U ovom kao i u prethodnom radu [3] pokazano je da je to moguće, pa još preostaje pronaći i algoritme. {80}

Bibliografija
[1] Bunch J. R., Parlett B. N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numerical Analysis 8 (1971) 639–655.
[2] Hari, V., Singer, S., Singer, S.: Full Block J-Jacobi Method for Hermitian Matrices. Linear Algebra Appl. 444 (2014) 1–27.
[3] Hari, V., Zadelj-Martić,  V., Kosinus-sinus dekompozicija ortogonalnih \linebreak matrica malog reda. Math.e, Vol.10, veljača 2007.
(http://e.math.hr/csdekompozicija/index.html).
[4] N. Truhar, Relative perturbation theory for matrix spectral decompositions, Doktorska disertacija, Sveučilište u Zagrebu, Zagreb (2000).
[5] Veselić, K.: A {J}acobi Eigenreduction Algorithm for Definite Matrix Pairs. Numer. Math. 64, (1) (1993) 241–269.
[6] Zadelj-Martić, V., Singularna dekompozicija matrice reda 2. Matematičko fizički list. 57 (2006/2007), 243-249.