Sylvesterovo kritérium

Sylvesterovo kritérium pozitivní definitnosti, pojmenované po Jamesi Sylvesterovi, uvádí nutnou a postačující podmínku pro rozhodnutí, zda komplexní hermitovská matice je pozitivně definitní.

Kritérium je možné zobecnit pro určení definitnosti matic, tj. pro rozpoznání pozitivně semidefinitních, negativně definitních, negativně semidefinitních i indefinitních matic.

Znění kritéria

Hermitovská matice je pozitivně definitní, právě když má všechny vedoucí hlavní subdeterminanty kladné.

Konkrétně, pro matici

{\boldsymbol {A}}={\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}&\ldots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\ldots &a_{nn}\end{pmatrix}}

mají být kladné determinanty:

|a_{11}|,\quad {\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}},\quad \ldots ,\quad {\begin{vmatrix}a_{11}&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}&\ldots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\ldots &a_{nn}\end{vmatrix}}=\det {\boldsymbol {A}}

.

Kritérium platí v nezměněné formě pro reálné symetrické matice, protože tyto matice jsou speciálním případem hermitovských matic.

Použitím vhodné permutace na řádky i sloupce matice ${\boldsymbol {A}}$ lze ukázat, ${\boldsymbol {A}}$ je pozitivně definitní, právě když subdeterminanty v libovolné posloupnosti $n$ do sebe vnořených hlavních podmatic matice ${\boldsymbol {A}}$ jsou všechny kladné.

Ukázky

Reálná symetrická matice

{\boldsymbol {A}}={\begin{pmatrix}2&1&0\\1&3&2\\0&2&4\\\end{pmatrix}}

je pozitivně definitní, protože

|a_{11}|=|2|=2>0,\quad {\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}}={\begin{vmatrix}2&1\\1&3\end{vmatrix}}=5>0\quad

a

\quad \det {\boldsymbol {A}}={\begin{vmatrix}2&1&0\\1&3&2\\0&2&4\\\end{vmatrix}}=12>0

.

Namísto všech vedoucích hlavních podmatic by bylo možné použít i jinou posloupnost tří do sebe vnořených hlavních podmatic, např.

|a_{33}|=|4|=4>0,\quad {\begin{vmatrix}a_{11}&a_{13}\\a_{31}&a_{33}\end{vmatrix}}={\begin{vmatrix}2&0\\0&4\end{vmatrix}}=8>0\quad

a

\quad \det {\boldsymbol {A}}={\begin{vmatrix}2&1&0\\1&3&2\\0&2&4\\\end{vmatrix}}=12>0

.

Naopak matice

{\boldsymbol {B}}={\begin{pmatrix}2&1&0\\1&-3&2\\0&2&-4\\\end{pmatrix}}

není pozitivně definitní, protože alespoň jeden z determinantů vedoucích hlavních podmatic není kladný:

|b_{11}|=|2|=2>0,\quad {\begin{vmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{vmatrix}}={\begin{vmatrix}2&1\\1&-3\end{vmatrix}}=-7<0\quad

a

\quad \det {\boldsymbol {B}}={\begin{vmatrix}2&1&0\\1&-3&2\\0&2&-4\\\end{vmatrix}}=20>0

Matice ${\boldsymbol {B}}$ zároveň ilustruje nutnost vzít do sebe vnořené hlavní podmatice. Kdyby namísto uvedené matice řádu 2 byla použita jiná hlavní podmatice, jejíž determinant je:

{\begin{vmatrix}b_{22}&b_{23}\\b_{32}&b_{33}\end{vmatrix}}={\begin{vmatrix}-3&2\\2&-4\end{vmatrix}}=16>0

,

byly by všechny determinanty tří hlavních podmatic různých řádů kladné, ale přesto matice ${\boldsymbol {B}}$ není pozitivně definitní.

Zobecnění

Pozitivně semidefinitní matice

Pozitivně semidefinitní matice lze charakterizovat analogicky:

Hermitovská matice je pozitivně semidefinitní, právě když má všechny hlavní subdeterminanty nezáporné.

Oproti pozitivně definitním maticím nestačí uvážit pouze $n$ hlavních vedoucích subdeterminantů, ale je třeba otestovat všech $2^{n}-1$ vedoucích subdeterminantů.

Ukázky

Reálná symetrická matice

{\boldsymbol {A}}={\begin{pmatrix}1&0&0\\0&4&2\\0&2&1\\\end{pmatrix}}

je pozitivně semidefinitní, protože

|a_{11}|=|a_{33}|=|1|=1\geq 0,\quad

|a_{22}|=|4|=4\geq 0,\quad

{\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}}={\begin{vmatrix}1&0\\0&4\end{vmatrix}}=4\geq 0,\quad \quad

{\begin{vmatrix}a_{11}&a_{13}\\a_{31}&a_{33}\end{vmatrix}}={\begin{vmatrix}1&0\\0&1\end{vmatrix}}=1\geq 0,\quad

{\begin{vmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{vmatrix}}={\begin{vmatrix}4&2\\2&1\end{vmatrix}}=0,\quad \quad

a

\quad \det {\boldsymbol {A}}={\begin{vmatrix}1&0&0\\0&4&2\\0&2&1\\\end{vmatrix}}=0

.

Reálná symetrická matice.

{\boldsymbol {B}}={\begin{pmatrix}0&0&-1\\0&-1&0\\-1&0&0\end{pmatrix}}

má hodnoty vedoucích hlavních subdeterminantů nezáporné:

|0|=0,\quad {\begin{vmatrix}0&0\\0&-1\end{vmatrix}}=0\quad

a

\quad \det {\boldsymbol {B}}={\begin{vmatrix}0&0&-1\\0&-1&0\\-1&0&0\end{vmatrix}}=1>0

Tento výpočet ovšem není dostatečný pro test pozitivní semidefinitnosti matice ${\boldsymbol {B}}$ . Pro vektor ${\boldsymbol {x}}=(0,2,0)^{\mathrm {T} }$ platí: ${\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {Bx}}=-4<0$ , čili matice ${\boldsymbol {B}}$ není pozitivně semidefinitní.

Negativně (semi)definitní matice

Hermitovská matice je negativně definitní právě když znaménko každého vedoucího hlavního subdeterminantu řádu $k$ je $(-1)^{k}$ .

U negativně semidefinitních matic je třeba otestovat všech $2^{n}-1$ vedoucích subdeterminantů, jejichž znaménko musí být buď $0$ nebo $(-1)^{k}$ , kde $k$ je řád subdeterminantu.

V ostatních případech je matice indefinitní.

Idea důkazu

Dopřednou implikaci lze dokázat například následujícím způsobem: Je-li hermitovská ${\boldsymbol {A}}$ řádu $n$ pozitivně definitní a ${\boldsymbol {B}}$ je její vedoucí hlavní podmatice řádu $k\leq n$ , potom je ${\boldsymbol {B}}$ také pozitivně definitní, protože libovolný nenulový vektor ${\boldsymbol {v}}\in \mathbb {C} ^{k}$ lze doplnit $n-k$ nulami na nenulový vektor ${\boldsymbol {u}}\in \mathbb {C} ^{n}$ , pro nějž pak platí:

{\boldsymbol {v}}^{\mathrm {H} }{\boldsymbol {Bv}}={\boldsymbol {u}}^{\mathrm {H} }{\boldsymbol {Au}}>0

Pozitivně definitní matice mají kladný determinant, kupříkladu protože mají všechna vlastní čísla kladná anebo protože mají své odmocniny (viz. též Choleského rozklad).

Pro obrácenou implikaci je možné využít algoritmus pro výpočet Choleského rozkladu ${\boldsymbol {A}}={\boldsymbol {LL}}^{\mathrm {H} }$ . Ten by selhal jen v případě, kdy by některý prvek $l_{kk}$ na diagonále byl dán odmocninou z nekladného čísla $s$ . V tuto chvíli vypočtený rozklad by měl splňovat ${\boldsymbol {A}}_{k}={\boldsymbol {L}}_{k}{\boldsymbol {L}}_{k}^{\mathrm {H} }$ i pro vedoucí hlavní podmatice matic ${\boldsymbol {A}}$ a ${\boldsymbol {L}}$ řádu $k$ . Pokud by $s\leq 0$ , nastal by v takovém případě spor s předpokladem, že matice ${\boldsymbol {A}}_{k}$ má kladný determinant, protože jej lze podle věty o determinantu součinu matic vyjádřit výrazem:

\det {\boldsymbol {A}}_{k}=s\cdot \prod \limits _{i=1}^{k-1}l_{ii}^{2}\leq 0

Kromě uvedeného argumentu lze podat i přímý, ale pracný důkaz matematickou indukcí, jenž je založen na výpočtu signatury kvadratické formy Gaussovou eliminací upravenou pro řádky i sloupce.

Numerické záležitosti

Při výpočtu všech determinantů zároveň Gaussovou eliminací, při níž je zakázáno měnit pořadí řádků, lze spočítat všechny determinanty v čase $O(n^{3})$ , což je asymptoticky stejně rychlé jako test pozitivní definitnosti pomocí Choleského rozkladu.

Pokud by byl každý determinant počítán zvlášť, časová složitost vychází $O(n^{4})$ pro test pozitivně definitních matic.

Složitost testu pozitivně semidefinitních matic prostřednictvím Sylvestreova kritéria je $O(2^{n}n^{3})$ , a proto je vhodnější použít jiné postupy.

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Sylvestrovo kritérium na slovenské Wikipedii a Sylvester's criterion na anglické Wikipedii.

Literatura

BEČVÁŘ, Jindřich. Lineární algebra. 1. vyd. Praha: Matfyzpress, 2019. 436 s. ISBN 978-80-7378-392-1.
HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5.
OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online.
JUKL, Marek. Bilineární a kvadratické formy. In: Olomouc: Univerzita Palackého, Přírodovědecká fakulta, 2000. Dostupné online. ISBN 80-244-0170-3. S. 53–57.

Související články