Network Bar

martedì 13 maggio 2014

Il giardino degli spettraedri

Uno spettraedro (spectrahedron) è un insieme convesso che viene variamente utilizzato in matematica. Introdotto all'interno della programmazione semidefinita(1), il nome unisce spectra, che evoca gli autovalori di una matrice, con hedron, per suggerire come gli spettraedri siano una generalizzazione dei più classici poliedri.
Lo spettraedro qui sopra, che è una variazione di quello realizzato da Nie, Parrillo e Sturmfels(2), è stato realizzato da Cynthia Vinzant che per il numero di maggio delle Notices of American Mathematical Society ha scritto un breve articolo su queste curiosità geometriche(3). Iniziamo con il definirli, ma per farlo introduco, come Vinzant, un po' di algebra lineare. Innanzitutto una matrice è una tabella di numeri. Questa tabella agisce su un insieme di numeri, posti in colonna e chiamati vettore colonna. Il risultato è anch'esso un vettore colonna. Quando quest'ultimo è linearmente legato al vettore colonna di partenza, allora lo scalare che fa passare dall'uno all'altro è chiamato autovalore, mentre il vettore, autostato della matrice. Ora, data una matrice reale simmetrica, i suoi autovalori sono definiti reali, e se gli autovalori sono tutti non negativi allora la matrice è semidefinita positiva. L'insieme delle matrici semidefinite positive è rappresentato da un cono convesso all'interno di uno spazio vettoriale costituito dalle matrici simmetriche reali(4).
A questo punto possiamo definire lo spettraedro come l'intersezione di uno spazio lineare affine con il cono convesso delle matrici di cui sopra. Per spazio affine si intende un insieme di punti che è messo in connessione con un dato spazio vettoriale. Lo spazio affine delle matrici reali simmetriche sarà definito dalla seguente parametrizzazione: \[A (x) = A_0 + x_1 A_1 + \cdots + x_n A_n\] dove $x = (x_1, \cdots, x_n)$ è un vettore reale, mentre $A_0, \cdots, A_n$ sono matrici reali simmetriche. Gli spettraedri saranno quindi tutti gli $x$ tali che la matrice $A (x)$ è definita semipositiva(3).
Degli esempi proposti dall'autrice nel suo articolo, quello che mi piace di più è legato a un particolare polinomio di quarto grado, $p(t) = t^4 + t^2 + 1$, che può essere rappresentato nel modo seguente: \[p (t) = (1 \; t \; t^2) \begin{pmatrix} 1 & 0 & a \\ 0 & 1-2a & 0 \\ a & 0 & 1 \end{pmatrix} \begin{pmatrix} 1\\ t\\ t^2 \end{pmatrix}\] dove gli spettraedri sono tutte le matrici per $a \in [-1, 1/2]$.
P.S.: chissà... magari da domani si inizierà a utilizzare il termine spettraedro, che avrò avuto l'onore di avere introdotto!
(1) Ramana M. & Goldman A.J. (1995). Some geometric results in semidefinite programming, Journal of Global Optimization, 7 (1) 33-50. DOI:
(2) Nie J., Parrilo P.A. & Sturmfels B. (2008). Semidefinite Representation of the k-Ellipse, Algorithms in Algebraic Geometry, 146 117-132. DOI: (arXiv)
Nella figura la parte a forma di scodella nella parte superiore del grafico è la somma delle distanze della funzione \[(x, y) \rightarrow \sum_{i=1}^k \sqrt{(x - u_i)^2 + (y - v_i)^2}\] mentre ognuna delle altre tre forme è associata con una differente combinazione di segni nel prodotto \[\prod \left ( d - \sum_{i=1}^k (-1)^{\sigma_i} \sqrt{(x - u_i)^2 + (y - v_i)^2} \right )\] La superficie ha un totale di $2^k = 8$ rami, ma sono presenti solo i quattro nel semispazio $d \geq 0$, poiché è simmetrica rispetto al piano $d = 0$. (3) Vinzant C. (2014). WHAT IS... a Spectrahedron?, Notices of the American Mathematical Society, 61 (5) 492-494. DOI:
(4) Immagino già che qualcuno si trovi in difficoltà con l'idea di riuscire a costruire uno spazio vettoriale, ovvero qualcosa di simile allo spazio in cui ci muoviamo, utilizzando delle matrici, ma ciò è possibile quando si trattano le matrici come se fossero dei vettori e non come delle tabelle. Tecnicamente complicato, certo, ma tremendamente efficace.

Nessun commento:

Posta un commento