Predavanje RAG10.3: Gramova matrika

I.2. Gramova matrika

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.

Opomba. 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 1.12 (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. 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 1.13. 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 1.14. 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 1.15. (Hilbert, 1888) \sum_{m,n}= P_{m,n} natanko tedaj, ko je n=1 ali m=1 ali (n=2  in m=2 ).

Za lažji zapis bomo uporabljali multiindeksne oznake. Torej za \bar\alpha\in{\mathbb N}_0^n , \bar\alpha=(\alpha_1,\ldots,\alpha_n) , pišemo \bar X^{\bar\alpha}:=X_1^{\alpha_1}\cdots X_n^{\alpha_n}  . Hkrati |\bar\alpha|=\sum_{i=1}^n \alpha_i  . Tako lahko vsak polinom f\in{\mathbb R}[\bar X]  zapišemo kot

\displaystyle f=\sum_{\bar\alpha}f_{\bar\alpha}\bar X^{\bar\alpha},

kjer f_{\bar\alpha}\in{\mathbb R} .

Definicija Naj bo f\in{\mathbb R}[\bar X] .

  1. Množica vseh eksponentov \bar\alpha , katerih pripadajoči koeficient f_{\bar\alpha} polinoma f je neničeln, imenujemo nosilec polinoma f in ga označimo {\rm supp}(f) . Torej: \displaystyle {\rm supp}(f)=\{\bar\alpha\in{\mathbb N}_0^n\mid f_{\bar\alpha}\neq 0\}.
  2. Konveksna ogrinjača {\rm supp}(f) je Newtonov politop {\rm New}(f) prirejen f : \displaystyle {\rm New}(f)={\rm co}({\rm supp}(f)).

Zgled. Za p=2-X_1^2X_2^2+X_1^4X_2^2+X_1^2X_2^4\in{\mathbb R}[X_1,X_2]  velja {\rm supp}(f)=\{ (0,0), (2,2), (4,2), (2,4)  \} , {\rm New}(f) pa je trikotnik v ravnini {\mathbb R}^2 napet na točke (0,0) , (2,4) in (4,2)  .


Izrek 1.16. (Reznick) Naj bo f\in{\mathbb R}[\bar X]_{\leq 2d} . Potem velja

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

kjer je V vektor monomov, ki pripadajo točkam iz \frac 12 {\rm New}(f) .

Ekvivalentno: če je f=\sum_i g_i^2 , potem za vsak i velja {\rm New}(g_i)\subseteq  \frac 12 {\rm New}(f) .


Zgled. Naj bo p=1+X_1^2X_2^2+X_2^2X_3^2+X_3^2X_1^2-4X_1X_2X_3\in{\mathbb R}[X_1,X_2,X_3] .

  1. Velja p|_{{\mathbb R}^3}\geq 0 , saj iz sredine med aritmetično in geometrijsko sredino sledi \displaystyle   \frac{1+x_1^2x_2^2+x_2^2x_3^2+x_3^2x_1^2}4\geq \sqrt[4]{1\cdot  x_1^2x_2^2\cdot x_2^2x_3^2\cdot x_3^2x_1^2}=|x_1|\, |x_2|\, |x_3|.

    za vsa realna števila x_1,x_2,x_3 .

  2. p\not\in\sum{\mathbb R}[X_1,X_2,X_3]^2  . Poiščimo {\rm  supp}(p)=\{(0,0,0),(2,2,0),(0,2,2),(2,0,2),(1,1,1)\} in {\rm New}(p)={\rm co}(\{(0,0,0),(1,1,0),(0,1,1),(1,0,1),(\frac  12,\frac 12, \frac 12)\})= {\rm co}(\{(0,0,0),(1,1,0),(0,1,1),(1,0,1)\})  . Celoštevilske točke te konveksne množice so ravno \{(0,0,0),(1,1,0),(0,1,1),(1,0,1)\} . Vektor V iz Reznickovega izreka je torej V=\begin{bmatrix} 1\\ X_1X_2 \\ X_1X_3 \\ X_2X_3\end{bmatrix}  . Sedaj pa ne obstaja matrika G , za katero bi veljalo p=V^tGV , saj npr. monoma X_1X_2X_3 ni mogoče dobiti kot produkt dveh monomov iz V . V posebnem tudi pozitivno semidefinitna matrika G s to lastnostjo ne obstaja. Iz Reznickovega izreka sklepamo p\not\in\sum{\mathbb  R}[X_1,X_2,X_3]^2 .
This entry was posted in Pedagoško delo, Realna algebraična geometrija (FMF), Slovenščina. Bookmark the permalink.

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