Predavanje RAG.2: Metoda Gramove matrike

1.3. Metoda Gramove matrike

Fiksirajmo nekaj oznak, ki jih bomo v prihodnje uporabljali: {\mathbb R}^{m\times n}=M_{m\times n}({\mathbb R}) je množica vseh m\times n realnih matrik. Kadar je m=n , pišemo krajše M_n({\mathbb R})={\mathbb R}^{n\times n} . Množica vseh simetričnih matrik je S{\mathbb R}^{n\times n}= \{A\in{\mathbb R}^{n\times n}\mid A^t=A\} .

Pomembno vlogo v nadaljevanju bodo igrale pozitivno (semi)definitne matrike. Pri tem je A\in S{\mathbb R}^{n\times n} pozitivno semidefinitna (A\succeq 0 ), če je x^tAx=\langle Ax,x\rangle \geq 0 za vse x\in{\mathbb R}^n . Če je A še obrnljiva, potem ji rečemo pozitivno definitna (A\succ 0 ).

Strnimo nekaj osnovnih lastnosti pozitivno semidefinitnih matrik v naslednjo trditev.

Trditev 1 Naj bo A\in S{\mathbb R}^{n\times n} .

  1. A je pozitivno semidefinitna natanko tedaj, ko ima same nenegativne lastne vrednosti.
  2. A je pozitivno definitna natanko tedaj, ko ima same pozitivne lastne vrednosti.
  3. A je pozitivno semidefinitna natanko tedaj, ko jo lahko zapišemo kot A=B^tB za neko B\in{\mathbb R}^{n\times n} .
  4. A je pozitivno definitna natanko tedaj, ko jo lahko zapišemo kot A=B^tB za neko obrnljivo B\in{\mathbb R}^{n\times n} .
  5. A je pozitivno semidefinitna natanko tedaj, ko obstaja unitarna matrika P in diagonalna matrika D z nenegativnimi elementi na diagonali, da velja A=P^t DP .
  6. A je pozitivno definitna natanko tedaj, ko obstaja unitarna matrika P in diagonalna matrika D s pozitivnimi elementi na diagonali, da velja A=P^t DP .
  7. A je pozitivno semidefinitna natanko tedaj, ko so vsi glavni minorji nenegativni.
  8. A je pozitivno definitna natanko tedaj, ko so vsi vodilni minorji pozitivni.

Naj bo sedaj p=\det (A-\lambda I_n)= (-1)^n \lambda^n + a_{n-1} \lambda^{n-1} +\cdots + a_{n-m}\lambda^{n-m}\in{\mathbb R}[\lambda] karakteristični polinom matrike A . Potem je

  • A pozitivno semidefinitna tedaj in le tedaj, ko je a_k a_{k+1}< 0 za vse k=n-m,\ldots,n-1 .
  • A pozitivno definitna tedaj in le tedaj, ko je a_k a_{k+1}< 0 za vse k=0,\ldots,n-1 .

Za pozitivne polinome je pojem pozitivno semidefinitnih matrik pomemben predvsem zaradi

Izrek 2 (Metoda Gramove matrike) Naj bo f\in{\mathbb R}[\bar X]_{\leq 2d} . Potem je

\displaystyle f\in\sum {\mathbb R}[\bar X]^2 \quad \Leftrightarrow \quad \exists G\succeq 0:\; f=V_d^tGV.

Pri tem je število kvadratov potrebnih za zapis takšnega f kot vsote kvadratov, enako (najmanjšemu) rangu Gramove matrike G .

V izreku vpeljana oznaka V_d pomeni vektor vseh monomov v \bar X stopnje \leq d . Na primer: za d=n=2 je V_d=\begin{bmatrix}1 & X_1 & X_2 & X_1^2 & X_1X_2 & X_2^2\end{bmatrix}^t .

Zgled 3 f=1-2X_1+X_2-X_1X_2+3X_1^2X_2+X_1^4-X_1^2X_2^2\not\in\sum {\mathbb R}[X_1,X_2]^2 .

Trditev 4 Za vsak f\in{\mathbb R}[\bar X]_{\leq 2d} obstaja simetrična matrika G , za katero je f=V_d^tGV . Taki matriki pravimo Gramova matrika za polinom f . Pozor: matrika G ni nujno enolična.

Trditev 5 Za f\in{\mathbb R}[\bar X]_{\leq 2} iz f|_{{\mathbb R}^n}\geq 0 sledi f\in\sum{\mathbb R}[\bar X]^2 .

V splošnem pozitivni polinomi niso nujno vsote kvadratov polinomov. Za natančen opis stanja potrebujemo še dve novi oznaki. S P_{m,n} označimo množico vseh nenegativnih polinomov v n spremenljivkah stopnje \leq 2m . Podobno je \sum_{m,n} množica vseh polinomov stopnje \leq 2m v n spremenljivkah, ki so vsote kvadratov polinomov. Očitno za vse m,n velja \sum_{m,n}\subseteq P_{m,n} .

Izrek 6 (Hilbert, 1888) \sum_{m,n}= P_{m,n} natanko tedaj, ko je n=1 ali m=1 ali (n=2 in m=2 ).

This entry was posted in Pedagoško delo, Realna algebraična geometrija (FMF), Slovenščina. Bookmark the permalink.

One Response to Predavanje RAG.2: Metoda Gramove matrike

  1. Pingback: Predavanje RAG.4 → (poglavje 1) « igor’s math Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s