J-simetrični Jacobijev algoritam

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.

 

Boroj 30

Poštovani čitatelji,

izašao je 30 broj časopisa e.math. U ovom broju donosimo članke O zlatnom trokutu, Uparena optimizacijska metoda i CS-dekompozicija J-ortogonalnih matrica malog reda.

U članku O zlatnom trokutu autori Mirela Katic Žlepalo i Bojan Kovačić s Tehničkog veleučilišta Zagreb uvode pojam zlatnog trokuta, te prikazuju geometrijske konstrukcije vezane uz zlatni trokut koje se mogu izvesti ravnalom i šestarom. Članak je od posebnog interesa za metodičare matematike. U članku Uparena optimizacijska metoda, autori Luka Borozan, Slobodan Jelić, Domagoj Matijević, Domagoj Ševerdija sa Sveučilišta J.J. Strossmayera u Osijeku, Odjela za matematiku daju prikaz metoda gradijentnog i zrcalonog spusta u konveksnoj optimizaciji. Temeljem izloženh osnovnih svojstava metoda autori diskutiraju njihoev prednosti i mane i predlažu uparenu - hibridnu - metodu koja kombinacijom pristupa daje robustniji algoritam. Konačno, u članku CS-dekompozicija J-ortogonalnih matrica malog reda autora Vjeran Harija i Vide Zadelj-Martić prezentira se konstruktivna metoda (kombinacijom elementarnih hiperbolnih rotacija i refleksija) konstrukcije dijagonalizacijske matrice (matrice vlastitih vektora) dane indefinitne hermitske matrice. Također, autori daju prikaz algeberskih tehnika kojima se može analizirati odnos dva potprostora u prostorima s indefinitnom metrikom. Ovi rezultati vrijede općenito, no zbog smanjivanja tehničke zahtijevnosti prezentacije, koje ne bi bitno doprinjele razumijevanju tremeljnih koncepeata, autori daju prikaz ključnih tehnika sa svim detaljima na malim primjerim. Također, kratki diskutiraju veze ovakvog pristupa rješavanju indefinitnog simetričnog problema vlastitih vrijednosti u modernom softveru. Ovaj broj tako daje prikaz tehnika vezanih uz osnovne geometrijska preslikavanja (rotacije i zrcaljenja) iz tri različita kuta. MEtodičkog, optimizacijskom i kuta matrične analize.  

Na kraju, koristim ovu priliku zaželjeti svim čitateljima časopisa sve najbolje u nadolazećoj godini.

Luka Grubišić