Algebra lineare (2): matrici, determinanti, autovalori e SVD

Nella prima parte di questa serie abbiamo costruito gli spazi vettoriali e le applicazioni lineari, e abbiamo visto che una matrice non è altro che un'applicazione lineare scritta rispetto a due basi fissate. Qui prendiamo quell'oggetto e lo studiamo per conto suo: come si moltiplica, come si inverte, come si decompone.

Il filo conduttore dell'articolo è che quasi ogni formula matriciale si può leggere in più modi, e che scegliere la lettura giusta rende un risultato ovvio invece che oscuro. Il prodotto fra matrici, per dire, ammette quattro interpretazioni diverse che danno lo stesso numero ma raccontano cose diverse. Il punto d'arrivo sono la diagonalizzazione e la decomposizione ai valori singolari, cioè gli strumenti con cui si guarda dentro una matrice per capire cosa fa davvero.

1. Il prodotto righe per colonne

Partiamo dalla definizione classica, quella che si impara per prima e che si implementa con tre cicli annidati.

DefinizioneProdotto righe per colonne. Siano \(A = (a_{ik}) \in \mathbb{R}^{m \times n}\) e \(B = (b_{kj}) \in \mathbb{R}^{n \times p}\). Si dice prodotto di \(A \times B\) righe per colonne la matrice \(C \in \mathbb{R}^{m \times p}\) dove ogni elemento \(c_{ij}\) è la somma dei prodotti degli elementi della \(i\)-esima riga di \(A\) per quelli della \(j\)-esima colonna di \(B\): $$c_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj} \qquad i = 1 \dots m, \quad j = 1 \dots p$$

Il vincolo sulle dimensioni — le colonne di \(A\) devono essere tante quante le righe di \(B\) — non è una convenzione arbitraria, ma il riflesso del fatto che il codominio della prima applicazione deve coincidere con il dominio della seconda perché la composizione abbia senso.

ProposizioneProprietà del prodotto. Siano \(A, B, C\) matrici per cui abbiano senso le seguenti operazioni. Allora:

1. \(A \cdot (B + C) = A \cdot B + A \cdot C\)   (distributività destra)
2. \((A + B) \cdot C = A \cdot C + B \cdot C\)   (distributività sinistra)
3. \((A \cdot B) \cdot C = A \cdot (B \cdot C)\)   (associatività)
4. \(\forall k \in \mathbb{R} : (kA) \cdot B = A \cdot (kB) = k (A \cdot B)\)

Manca vistosamente la commutatività: in generale \(A \cdot B \neq B \cdot A\), e spesso uno dei due prodotti non è nemmeno definito. La ragione l'abbiamo vista nella prima parte — il prodotto rappresenta la composizione di funzioni, e comporre in ordine diverso dà risultati diversi. Fanno eccezione i vettori, per i quali \(x^T y = y^T x\).

Proposizione \((\mathbb{R}^{n \times n}, +, \times)\) è un anello unitario non commutativo. Infatti \((\mathbb{R}^{n \times n}, +)\) è un gruppo abeliano, il prodotto è associativo e distributivo rispetto alla somma, e l'elemento neutro della moltiplicazione è la matrice identità \(I_n\).

2. Prodotti fra vettori

Prima di scomporre il prodotto fra matrici conviene fissare i due casi estremi, quelli in cui gli operandi sono vettori. Sono duali l'uno dell'altro e producono oggetti di natura opposta: uno scalare il primo, una matrice il secondo.

Prodotto scalare (o interno)

Dati due vettori \(x, y \in \mathbb{R}^n\), il valore \(x^T y\), chiamato anche prodotto interno o prodotto scalare standard, è definito come:

$$x^T y = \begin{bmatrix} x_1 & x_2 & \dots & x_n \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} = \sum_{i=1}^n x_i y_i \ \in \mathbb{R}$$

Il prodotto scalare fra vettori è commutativo. Lo avevamo già incontrato nella definizione di spazio vettoriale euclideo: è una forma bilineare su \(\mathbb{R}^n\), e da esso discendono norma, distanza e angolo.

Prodotto esterno

Dati \(x \in \mathbb{R}^m\) e \(y \in \mathbb{R}^n\), la matrice \(x y^T \in \mathbb{R}^{m \times n}\), chiamata prodotto esterno, è definita come:

$$x y^T = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_m \end{bmatrix} \begin{bmatrix} y_1 & y_2 & \dots & y_n \end{bmatrix} = \begin{bmatrix} x_1 y_1 & x_1 y_2 & \dots & x_1 y_n \\ x_2 y_1 & x_2 y_2 & \dots & x_2 y_n \\ \vdots & \vdots & \ddots & \vdots \\ x_m y_1 & x_m y_2 & \dots & x_m y_n \end{bmatrix}$$

È lo stesso ordine di operandi, invertito, e produce una matrice \(m \times n\) invece di un numero. Si osservi che ogni colonna del risultato è un multiplo di \(x\): una matrice ottenuta come prodotto esterno ha sempre rango 1. Torneremo su questo fatto parlando di SVD, dove una matrice qualsiasi verrà scritta come somma di prodotti esterni.

3. Prodotto matrice-vettore: due letture

Data \(A \in \mathbb{R}^{m \times n}\) e \(x \in \mathbb{R}^n\), il prodotto è un vettore \(y = Ax \in \mathbb{R}^m\). Ci sono due modi di guardarlo, entrambi corretti, che portano a intuizioni diverse.

Prima lettura: per righe. Scrivendo \(A\) come pila di righe,

$$y = Ax = \begin{bmatrix} - & a_1^T & - \\ - & a_2^T & - \\ & \vdots & \\ - & a_m^T & - \end{bmatrix} x = \begin{bmatrix} a_1^T x \\ a_2^T x \\ \vdots \\ a_m^T x \end{bmatrix}$$

ossia l'\(i\)-esima componente di \(y\) è il prodotto scalare della \(i\)-esima riga di \(A\) con \(x\): \(y_i = a_i^T x\). Ogni riga di \(A\) è una "sonda" che misura \(x\) lungo una certa direzione.

Seconda lettura: per colonne. Scrivendo \(A\) come affiancamento di colonne \(a^1, \dots, a^n\),

$$y = Ax = \begin{bmatrix} | & | & & | \\ a^1 & a^2 & \dots & a^n \\ | & | & & | \end{bmatrix} x = a^1 x_1 + a^2 x_2 + \dots + a^n x_n$$

In altre parole il risultato \(y\) è la combinazione lineare delle colonne di \(A\), dove i coefficienti sono le componenti di \(x\). Questa seconda lettura è quella concettualmente più importante: dice che l'insieme dei possibili risultati \(Ax\), al variare di \(x\), è esattamente lo span delle colonne di \(A\). Ci ritorneremo definendo il range.

Sistemi lineari in forma matriciale

Con la notazione del prodotto possiamo rappresentare un sistema lineare in \(m\) equazioni e \(n\) incognite come

$$Ax = b$$

dove \(A \in \mathbb{R}^{m \times n}\), \(b \in \mathbb{R}^m\) è il vettore dei termini noti e \(x \in \mathbb{R}^n\) il vettore delle incognite. Denotando con \(A_{i,:}\) le righe di \(A\), la scrittura compatta equivale a

$$A_{1,:}\,x = b_1, \qquad A_{2,:}\,x = b_2, \qquad \dots \qquad A_{m,:}\,x = b_m$$

o, esplicitando i coefficienti:

$$\begin{align} A_{1,1}x_1 + A_{1,2}x_2 + \dots + A_{1,n}x_n &= b_1 \\ A_{2,1}x_1 + A_{2,2}x_2 + \dots + A_{2,n}x_n &= b_2 \\ &\ \ \vdots \\ A_{m,1}x_1 + A_{m,2}x_2 + \dots + A_{m,n}x_n &= b_m \end{align}$$

Le due letture del prodotto matrice-vettore danno due modi diversi di interpretare il sistema. Per righe: cerchiamo un punto che soddisfi simultaneamente \(m\) vincoli. Per colonne: ci chiediamo se \(b\) sia esprimibile come combinazione lineare delle colonne di \(A\) — e la risposta è sì esattamente quando \(b\) appartiene al loro span.

4. Prodotto matrice-matrice: quattro letture

Lo stesso gioco si può fare con il prodotto fra due matrici, e stavolta le letture sono quattro. Siano \(A \in \mathbb{R}^{m \times n}\), \(B \in \mathbb{R}^{n \times p}\) e \(C = AB \in \mathbb{R}^{m \times p}\).

4.1 Righe per colonne

È la definizione: ogni elemento di \(C\) è il prodotto scalare di una riga di \(A\) per una colonna di \(B\).

$$C = AB = \begin{bmatrix} - & a_1^T & - \\ - & a_2^T & - \\ & \vdots & \\ - & a_m^T & - \end{bmatrix} \begin{bmatrix} | & | & & | \\ b^1 & b^2 & \dots & b^p \\ | & | & & | \end{bmatrix} = \begin{bmatrix} a_1^T b^1 & a_1^T b^2 & \dots & a_1^T b^p \\ a_2^T b^1 & a_2^T b^2 & \dots & a_2^T b^p \\ \vdots & \vdots & \ddots & \vdots \\ a_m^T b^1 & a_m^T b^2 & \dots & a_m^T b^p \end{bmatrix}$$

4.2 Colonne per righe

All'opposto, consideriamo \(A\) per colonne \(a^i\) e \(B\) per righe \(b_i\). Si ottiene un'interpretazione più sorprendente, come somma di prodotti esterni:

$$C = AB = \begin{bmatrix} | & | & & | \\ a^1 & a^2 & \dots & a^n \\ | & | & & | \end{bmatrix} \begin{bmatrix} - & b_1^T & - \\ - & b_2^T & - \\ & \vdots & \\ - & b_n^T & - \end{bmatrix} = \sum_{i=1}^n a^i b_i^T$$

In sostanza \(AB\) è la somma, per ogni \(i\), dei prodotti esterni della \(i\)-esima colonna di \(A\) per la \(i\)-esima riga di \(B\). Poiché ciascun addendo ha rango 1, questa lettura mostra che un prodotto di matrici è una somma di \(n\) matrici di rango 1 — ed è il germe dell'idea di approssimazione a basso rango: se molti addendi contribuiscono poco, si possono buttare via.

4.3 Matrice per set di colonne

Rappresentando \(B\) per colonne, \(C\) è l'affiancamento dei prodotti di \(A\) per ciascuna colonna di \(B\):

$$C = AB = A \begin{bmatrix} | & | & & | \\ b^1 & b^2 & \dots & b^p \\ | & | & & | \end{bmatrix} = \begin{bmatrix} | & | & & | \\ Ab^1 & Ab^2 & \dots & Ab^p \\ | & | & & | \end{bmatrix}$$

L'\(i\)-esima colonna di \(C\) è il prodotto di \(A\) per l'\(i\)-esima colonna di \(B\).

4.4 Set di righe per matrice

Simmetricamente, rappresentando \(A\) per righe:

$$C = AB = \begin{bmatrix} - & a_1^T & - \\ - & a_2^T & - \\ & \vdots & \\ - & a_m^T & - \end{bmatrix} B = \begin{bmatrix} - & a_1^T B & - \\ - & a_2^T B & - \\ & \vdots & \\ - & a_m^T B & - \end{bmatrix}$$

L'\(i\)-esima riga di \(C\) è il prodotto della \(i\)-esima riga di \(A\) per \(B\). Vale la pena tenere a mente tutte e quattro: nelle dimostrazioni, scegliere la lettura giusta spesso riduce a due righe un conto che altrimenti richiede indici ovunque. Ne vedremo un esempio parlando di diagonalizzazione.

DefinizioneMatrice identità. $$I_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}$$ \(I_{ij}\) si identifica anche con \(\delta_{ij}\), simbolo di Kronecker.

5. Trasposta, simmetria, traccia

DefinizioneMatrice trasposta. Si definisce trasposta della matrice \(A \in \mathbb{R}^{m \times n}\) la matrice \(A^T \in \mathbb{R}^{n \times m}\) che si ottiene scambiando le righe con le colonne: \(A^T_{ij} = A_{ji}\).

ProposizioneProprietà della trasposizione.

• \((A^T)^T = A\)
• \((A + B)^T = A^T + B^T\)
• \((A \cdot B)^T = B^T \cdot A^T\)
• se esiste \(A^{-1}\), allora \((A^{-1})^T = (A^T)^{-1}\)

La terza proprietà, con l'inversione dell'ordine, è quella che si dimentica più spesso ed è responsabile di metà degli errori nei conti con i gradienti. Torneremo a usarla continuamente nella terza parte.

DefinizioneMatrice simmetrica e antisimmetrica. \(A\) è simmetrica se \(A = A^T\); è antisimmetrica se \(A = -A^T\).

È facile dimostrare che per ogni \(A \in \mathbb{R}^{n \times n}\) la matrice \(A + A^T\) è simmetrica e \(A - A^T\) è antisimmetrica. Da qui segue una decomposizione che useremo subito:

$$A = \frac{1}{2}(A + A^T) + \frac{1}{2}(A - A^T)$$

ossia ogni matrice quadrata è somma di una parte simmetrica e di una antisimmetrica, in modo unico. L'insieme delle matrici simmetriche di ordine \(n\) si denota con \(\mathbf{S}^n\), e scrivere \(A \in \mathbf{S}^n\) significa che \(A\) è simmetrica \(n \times n\). Che le simmetriche siano importanti lo abbiamo anticipato nella prima parte: sono la controparte in coordinate delle forme bilineari simmetriche, cioè di una struttura che non dipende dalla base.

DefinizioneMatrice diagonale. Una matrice quadrata di ordine \(n\) si dice diagonale se in essa sono nulli tutti gli elementi non appartenenti alla diagonale principale.

DefinizioneTraccia. Si definisce traccia di una matrice quadrata \(A\), e si denota con \(\mathrm{tr}\, A\), la somma degli elementi sulla diagonale principale: $$\mathrm{tr}\, A = \sum_{i=1}^{n} a_{ii}$$

ProposizioneProprietà della traccia.

• \(\forall A \in \mathbb{R}^{n \times n} : \mathrm{tr}\, A = \mathrm{tr}\, A^T\)
• \(\forall A, B \in \mathbb{R}^{n \times n} : \mathrm{tr}(A + B) = \mathrm{tr}\, A + \mathrm{tr}\, B\)
• \(\forall A \in \mathbb{R}^{n \times n},\ \forall k \in \mathbb{R} : \mathrm{tr}(kA) = k\, \mathrm{tr}\, A\)
• ove \(AB\) sia quadrata: \(\mathrm{tr}\, AB = \mathrm{tr}\, BA\)
• ove \(ABC\) sia quadrata: \(\mathrm{tr}\, ABC = \mathrm{tr}\, CAB = \mathrm{tr}\, BCA\)

La proprietà ciclica è meno innocua di quanto sembri: permette di far ruotare i fattori dentro una traccia, ed è il trucco standard per riscrivere espressioni scalari in forma trattabile. Si noti che è una permutazione ciclica, non arbitraria: in generale \(\mathrm{tr}\, ABC \neq \mathrm{tr}\, ACB\).

6. Rango

DefinizioneRango delle righe e delle colonne. Il rango delle righe di una matrice \(A \in \mathbb{R}^{m \times n}\) è la dimensione del più grande sottoinsieme di vettori linearmente indipendenti composto da righe di \(A\); il rango delle colonne si definisce analogamente sulle colonne.

TeoremaRango di una matrice. Per una qualsiasi matrice \(A \in \mathbb{R}^{m \times n}\) il rango delle righe è uguale al rango delle colonne, per cui lo si denota semplicemente rango della matrice, \(\mathrm{rank}(A)\).

Che i due numeri coincidano non è affatto ovvio: righe e colonne vivono in spazi di dimensione diversa (\(\mathbb{R}^n\) le une, \(\mathbb{R}^m\) le altre) e non c'è ragione a priori perché le loro ridondanze si corrispondano. Il rango è dunque una quantità intrinseca della matrice, e misura quante direzioni sopravvivono alla trasformazione: è, nel linguaggio della prima parte, la dimensione dell'immagine.

ProposizioneProprietà del rango. $$\forall A \in \mathbb{R}^{m \times n} : \mathrm{rank}(A) = \mathrm{rank}(A^T)$$ $$\forall A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times p} : \mathrm{rank}(A \cdot B) \leq \min\big(\mathrm{rank}(A),\, \mathrm{rank}(B)\big)$$ $$\forall A, B \in \mathbb{R}^{m \times n} : \mathrm{rank}(A + B) \leq \mathrm{rank}(A) + \mathrm{rank}(B)$$

La seconda proprietà dice che moltiplicare non può aumentare il rango: l'informazione, una volta persa, non si recupera. È la ragione per cui in una rete neurale una sequenza di soli strati lineari, per quanto lunga, non può fare più di quanto faccia una sola matrice — servono le non linearità.

7. Inversa

DefinizioneMatrice invertibile. \(A \in \mathbb{R}^{n \times n}\) si dice invertibile, o regolare, o non singolare, se esiste \(B \in \mathbb{R}^{n \times n}\) tale che \(A \cdot B = B \cdot A = I_n\). Se \(A\) non è invertibile si dice singolare.

ProposizioneUnicità dell'inversa. Se \(A\) è invertibile, la matrice tale che \(A \cdot A^{-1} = I = A^{-1} \cdot A\) esiste ed è unica, e si denota con \(A^{-1}\).

Denotiamo con \(GL(n, \mathbf{K})\) l'insieme delle matrici quadrate invertibili di ordine \(n\) sul campo \(\mathbf{K}\).

ProposizioneProprietà della matrice inversa. Se \(A, B \in \mathbb{R}^{n \times n}\) sono invertibili, si dimostra che $$(A^{-1})^{-1} = A \qquad (A \cdot B)^{-1} = B^{-1} \cdot A^{-1} \qquad (A^{-1})^T = (A^T)^{-1}$$

Per l'ultima identità si abbrevia spesso \((A^{-1})^T\) con \(A^{-T}\). Si noti ancora una volta l'inversione dell'ordine nel prodotto, per la stessa ragione della trasposta: per disfare due operazioni applicate in sequenza bisogna disfarle a partire dall'ultima.

Proposizione \((GL(n,\mathbf{K}), \times)\) è un gruppo.

Dimostrazione

\(GL(n,\mathbf{K})\) non è vuoto, poiché \(I_n \in GL(n,\mathbf{K})\). È chiuso rispetto al prodotto: se \(A, B \in GL(n,\mathbf{K})\), allora \(AB\) è invertibile con \((AB)^{-1} = B^{-1}A^{-1}\). L'associatività è ereditata dal prodotto fra matrici, l'elemento neutro è \(I_n\) e l'inverso di ogni elemento esiste per definizione. \(\blacksquare\)

Con l'inversa possiamo finalmente risolvere \(Ax = b\), almeno formalmente:

$$Ax = b \quad \Rightarrow \quad A^{-1}Ax = A^{-1}b \quad \Rightarrow \quad I x = A^{-1}b \quad \Rightarrow \quad x = A^{-1}b$$

Il passaggio è corretto ma, va detto, non è così che si risolve un sistema in pratica: calcolare esplicitamente \(A^{-1}\) è costoso e numericamente instabile. Si preferisce una fattorizzazione (LU, QR, Cholesky) seguita da sostituzione. La formula resta però indispensabile come strumento teorico.

8. Matrici ortogonali

DefinizioneVettori ortogonali e normalizzati. Due vettori \(x, y \in \mathbb{R}^n\) si dicono ortogonali se \(x^T y = 0\). Un vettore \(x \in \mathbb{R}^n\) è normalizzato se \(\lVert x \rVert_2 = 1\). Vettori a due a due ortogonali e normalizzati si dicono ortonormali.

Ai fini dell'ortogonalità in \(\mathbb{R}^n\) si assume come forma bilineare il prodotto scalare standard. Con un prodotto scalare diverso cambia anche chi è ortogonale a chi.

DefinizioneMatrice ortogonale. Una matrice \(U \in \mathbb{R}^{n \times n}\) si dice ortogonale se le sue colonne sono ortonormali, cioè se formano una base ortonormale di \(\mathbb{R}^n\).

Dalla definizione discende immediatamente la proprietà che rende queste matrici così comode:

$$U^T U = I = U U^T$$

Il conto è quello del punto 4.1: l'elemento \((i,j)\) di \(U^T U\) è il prodotto scalare della colonna \(i\) con la colonna \(j\), che vale 1 se \(i = j\) (normalizzazione) e 0 altrimenti (ortogonalità). In altre parole l'inversa di una matrice ortogonale è la sua trasposta: \(U^{-1} = U^T\). Invertire, che in generale è l'operazione più costosa, diventa gratuito.

ProposizioneCaratterizzazione delle matrici ortogonali. Una matrice \(A \in M_n(\mathbf{K})\) è ortogonale se e solo se:

1. la somma dei quadrati degli elementi di ogni riga (colonna) di \(A\) è uguale a 1;
2. la somma dei prodotti degli elementi di ogni riga (colonna) per quelli di un'altra riga (colonna) è zero.

Un'altra proprietà fondamentale è che moltiplicare per una matrice ortogonale non altera la norma euclidea: per ogni \(U \in \mathbb{R}^{n \times n}\) ortogonale e ogni \(x \in \mathbb{R}^n\),

$$\lVert Ux \rVert_2 = \lVert x \rVert_2$$

Geometricamente, le trasformazioni ortogonali sono rotazioni e riflessioni: cambiano l'orientamento delle cose ma non le deformano. Numericamente, questo significa che non amplificano gli errori — motivo per cui gli algoritmi seri, dove possono, lavorano con matrici ortogonali.

9. Proiezione, range, nullspace

DefinizioneProiezione di un vettore su un sottospazio. La proiezione di \(y \in \mathbb{R}^m\) sullo span di \(\{x_1, \dots, x_n\}\), con \(x_i \in \mathbb{R}^m\), è il vettore \(v\) più vicino possibile a \(y\), misurandone la distanza con la norma euclidea: $$\mathrm{Proj}\big(y; \{x_1, \dots, x_n\}\big) = \arg\min_{v \in \mathrm{span}(\{x_1, \dots, x_n\})} \lVert y - v \rVert_2$$

DefinizioneRange, o spazio delle colonne. Il range di una matrice \(A \in \mathbb{R}^{m \times n}\), denotato \(\mathbf{R}(A)\), è lo span delle colonne di \(A\): $$\mathbf{R}(A) = \{\, v \in \mathbb{R}^m : v = Ax,\ x \in \mathbb{R}^n \,\}$$

Le due definizioni della sezione 3 tornano qui: poiché \(Ax\) è la combinazione lineare delle colonne di \(A\) con coefficienti \(x\), l'insieme di tutti i possibili \(Ax\) è precisamente lo span delle colonne. Il range di \(A\) è dunque l'immagine dell'applicazione lineare \(f : \mathbb{R}^n \rightarrow \mathbb{R}^m\) associata ad \(A\), e la sua dimensione è il rango.

ProposizioneFormula dei minimi quadrati per la proiezione. Se \(A\) ha pieno rango \(n \lt m\), la proiezione di \(y \in \mathbb{R}^m\) sul range di \(A\) è data da: $$\mathrm{Proj}(y; A) = \arg\min_{v \in \mathbf{R}(A)} \lVert v - y \rVert_2 = A (A^T A)^{-1} A^T y$$

Quando \(A\) si riduce a una sola colonna \(a\), la formula si semplifica nella proiezione su una retta:

$$\mathrm{Proj}(y; a) = \frac{a a^T}{a^T a}\, y$$

dove si riconosce al numeratore un prodotto esterno (una matrice di rango 1) e al denominatore un prodotto scalare. Nella terza parte ricaveremo la formula generale per via differenziale, derivando le equazioni normali dei minimi quadrati.

DefinizioneNullspace, o kernel. Si definisce nullspace di una matrice \(A \in \mathbb{R}^{m \times n}\), e si denota con \(\mathbf{N}(A)\), l'insieme dei vettori che moltiplicati per \(A\) danno come risultato il vettore nullo: $$\mathbf{N}(A) = \{\, x \in \mathbb{R}^n : Ax = 0 \,\}$$

DefinizioneComplemento ortogonale. Sia \(\mathbf{E}\) uno spazio vettoriale euclideo e \(\mathbf{V}\) un suo sottospazio. Si chiama complemento ortogonale di \(\mathbf{V}\), e si denota con \(\mathbf{V}^{\perp}\), il sottoinsieme $$\mathbf{V}^{\perp} = \{\, y \in \mathbf{E} : \forall x \in \mathbf{V},\ \varphi(x,y) = 0 \,\}$$

Mettendo insieme i pezzi si ottiene una delle relazioni più eleganti dell'algebra lineare: il nullspace di \(A\) e il range di \(A^T\) sono complementi ortogonali l'uno dell'altro, e insieme ricostruiscono tutto lo spazio di partenza:

$$\mathbf{R}(A^T) \oplus \mathbf{N}(A) = \mathbb{R}^n, \qquad \mathbf{R}(A^T) \perp \mathbf{N}(A)$$

Ogni vettore \(x \in \mathbb{R}^n\) si scompone dunque, in modo unico, in una parte che \(A\) annulla e una che \(A\) conserva. Le dimensioni si sommano a \(n\), e ritroviamo il teorema del rango visto nella prima parte.

10. Determinanti

Il determinante associa a ogni matrice quadrata un unico scalare che ne riassume una proprietà cruciale: se sia invertibile o no. La definizione classica è ricorsiva, per sviluppo di Laplace.

DefinizioneDeterminante. Se \(A \in M_n(\mathbf{K})\), ad \(A\) si associa un elemento di \(\mathbf{K}\), denotato \(|A|\), così definito:

• se \(n = 1\), cioè \(A = (a_{11})\), si pone \(|A| = a_{11}\);
• se \(n \gt 1\), si suppone data la definizione per \(n-1\); si dice che \(a_{ij}\) è di posto pari se \(i+j\) è pari, di posto dispari se \(i+j\) è dispari;
• si definisce determinante di \(A\) la somma dei prodotti degli elementi di una riga (o colonna) arbitrariamente scelta per i rispettivi complementi algebrici.

Quindi, fissata una riga \(i\) oppure una colonna \(j\): $$|A| = \sum_{j=1}^n a_{ij} \Delta_{ij} \qquad\qquad |A| = \sum_{i=1}^n a_{ij} \Delta_{ij}$$

DefinizioneMinore complementare. Sia \(A = (a_{ij}) \in M_n(\mathbf{K})\). Si dice minore complementare dell'elemento \(a_{ij}\), e si denota con \(M_{ij}\), il determinante della matrice di ordine \(n-1\) che si ottiene da \(A\) sopprimendo la riga \(i\)-esima e la colonna \(j\)-esima.

DefinizioneComplemento algebrico (cofattore). Sia \(A \in M_n(\mathbf{K})\) con \(n \gt 1\). Si definisce complemento algebrico di \(a_{ij}\), denotato \(A_{ij}\) o \(\Delta_{ij}\), il minore complementare di \(a_{ij}\) se \(a_{ij}\) è di posto pari, il suo opposto se è di posto dispari. In formula: \(\Delta_{ij} = (-1)^{i+j} M_{ij}\).

Interpretazione geometrica. Il determinante di una matrice \(2 \times 2\) è l'area (con segno) del parallelogramma individuato dai due vettori riga o colonna. Per una \(3 \times 3\) è il volume del parallelepipedo individuato dai tre vettori, e la cosa si generalizza a ordine \(n\). Il determinante misura dunque di quanto la trasformazione dilata i volumi — e vale zero esattamente quando li schiaccia a volume nullo, cioè quando la trasformazione perde una dimensione.

DefinizioneAggiunta classica. Data \(A \in \mathbb{R}^{n \times n}\), la matrice aggiunta di \(A\) è definita come $$\mathrm{adj}(A) \in \mathbb{R}^{n \times n}, \qquad (\mathrm{adj}(A))_{ij} = \Delta_{ji} = (-1)^{i+j} \left| A_{\setminus j, \setminus i} \right|$$ dove \(A_{\setminus j, \setminus i}\) è la matrice ottenuta da \(A\) rimuovendo la riga \(j\)-esima e la colonna \(i\)-esima. Si noti l'inversione degli indici: l'aggiunta è la trasposta della matrice dei cofattori.

ProposizioneProprietà dei determinanti.

1. \(|A^T| = |A|\)
2. Il determinante di una matrice diagonale è il prodotto degli elementi sulla diagonale principale; in particolare \(|I_n| = 1\).
3. \(\forall A, B \in \mathbb{R}^{n \times n} : |AB| = |A||B| = |B||A|\)
4. \(\forall A \in \mathbb{R}^{n \times n}\) non singolare: \(|A^{-1}| = 1/|A|\)
5. \(|A| = 0\) se e solo se \(A\) è singolare, ossia non ha rango \(n\), e questo avviene se e solo se una qualsiasi riga (o colonna) è combinazione lineare delle altre.
6. Se si scambiano fra loro due righe o due colonne di \(A\), si ottiene una matrice \(A'\) con \(|A'| = -|A|\).
7. Se si moltiplica ogni elemento di una riga o colonna per uno scalare \(\lambda \in \mathbf{K}\), si ottiene \(A'\) con \(|A'| = \lambda |A|\).
8. Condizione necessaria e sufficiente affinché \(p\) vettori \(v_1, \dots, v_p\) di \(\mathbf{E}\), con \(\dim \mathbf{E} = n\), siano linearmente indipendenti è che il determinante relativo a una qualsiasi base \(\mathbf{B} = (e_i)\) non sia nullo.
9. Se tutti gli elementi di una riga (o colonna) sono somma di due addendi, allora \(|A| = |A'| + |A''|\), dove \(A'\) e \(A''\) si ottengono da \(A\) tenendo rispettivamente il primo o il secondo addendo e lasciando inalterate le altre righe o colonne.
10. Se a una riga o colonna si aggiunge una combinazione lineare delle altre righe o colonne, il determinante non cambia.

La proprietà 3, la moltiplicatività, è quella meno intuitiva e più potente: il determinante trasforma prodotti di matrici in prodotti di numeri. La 10 è invece il fondamento dell'eliminazione di Gauss — permette di semplificare una matrice senza alterarne il determinante.

TeoremaII teorema di Laplace. La somma dei prodotti degli elementi di una riga (colonna) per i complementi algebrici corrispondenti di un'altra riga (colonna) è zero: $$\forall i, h \in \{1 \dots n\},\ i \neq h \quad \Rightarrow \quad \sum_{j=1}^n a_{ij}\Delta_{hj} = 0 \ \wedge \ \sum_{j=1}^n a_{ji}\Delta_{jh} = 0$$

Sviluppando lungo la riga giusta si ottiene il determinante, sviluppando lungo quella sbagliata si ottiene zero. È esattamente la struttura di un'identità del tipo \(\delta_{ik}\), e infatti è quello che serve per dimostrare il teorema seguente.

TeoremaInvertibilità e determinante. Sia \(A \in M_n(\mathbf{K})\). Allora $$A \in GL(n,\mathbf{K}) \iff |A| \neq 0$$

Dimostrazione

(\(\Rightarrow\)) Se \(A \in GL(n,\mathbf{K})\), esiste \(A^{-1}\) con \(A \cdot A^{-1} = I_n\). Passando ai determinanti e usando la moltiplicatività, \(|A| \cdot |A^{-1}| = |I_n| = 1\), quindi \(|A| \neq 0\).

(\(\Leftarrow\)) Sia \(|A| \neq 0\) e consideriamo la matrice \(B\) definita da

$$b_{ij} = \frac{\Delta_{ji}}{|A|}$$

Mostriamo che \(AB = I_n = BA\). Posto \(C = AB\), con \(C = (c_{ik})_{i,k = 1 \dots n}\):

$$c_{ik} = \sum_{j=1}^n a_{ij} b_{jk} = \sum_{j=1}^n a_{ij} \frac{\Delta_{kj}}{|A|}$$

Se \(i = k\), la sommatoria \(\sum_{j=1}^n a_{ij}\Delta_{ij}\) è proprio lo sviluppo di Laplace lungo la riga \(i\), quindi vale \(|A|\) e \(c_{ii} = 1\). Se invece \(i \neq k\), la sommatoria \(\sum_{j=1}^n a_{ij}\Delta_{kj}\) mescola gli elementi di una riga con i cofattori di un'altra, e per il II teorema di Laplace vale 0, da cui \(c_{ik} = 0\).

Dunque \(c_{ik} = \delta_{ik}\), cioè \(AB = I_n\), e analogamente si verifica \(BA = I_n\). \(\blacksquare\)

In questa dimostrazione abbiamo implicitamente ricavato una formula esplicita per l'inversa a partire dall'aggiunta classica:

$$A^{-1} = \frac{1}{|A|}\, \mathrm{adj}(A)$$

Formula elegante ma di scarso uso pratico — richiede il calcolo di \(n^2\) determinanti di ordine \(n-1\) — che però ci tornerà utile nella terza parte, quando calcoleremo il gradiente del determinante. Si noti anche che il determinante di una matrice ortogonale vale \(\pm 1\), coerentemente col fatto che rotazioni e riflessioni non alterano i volumi.

Matrici simili

DefinizioneMatrici simili. Siano \(A, B \in M_n(\mathbf{K})\). Si dicono simili se esiste \(P \in GL(n,\mathbf{K})\) tale che \(B = P^{-1} A P\).

La similitudine è il modo formale di dire "stessa trasformazione, coordinate diverse": \(P\) è la matrice di cambiamento di base, e \(B\) descrive la stessa applicazione lineare vista da un altro sistema di riferimento.

Proposizione La relazione di similitudine è una relazione di equivalenza.

Dimostrazione

Riflessiva: \(I_n^{-1} A I_n = A\), quindi \(A \sim A\).

Simmetrica: se \(A \sim B\), esiste \(P\) con \(B = P^{-1} A P\), da cui \(P B P^{-1} = A\); posto \(Q = P^{-1}\), si ha \(A = Q^{-1} B Q\), cioè \(B \sim A\).

Transitiva: se \(A \sim B\) e \(B \sim C\), esistono \(P, Q\) con \(A = P^{-1} B P\) e \(B = Q^{-1} C Q\); sostituendo, \(A = P^{-1} Q^{-1} C Q P = (QP)^{-1} C (QP)\), cioè \(A \sim C\). \(\blacksquare\)

11. Forme quadratiche

Nella prima parte avevamo visto che una forma bilineare si scrive \(\varphi(x,y) = x^T A y\). Ponendo \(y = x\) si ottiene la forma quadratica, che è la generalizzazione a più dimensioni del polinomio di secondo grado \(ax^2\).

DefinizioneForma quadratica. Data \(A \in \mathbb{R}^{n \times n}\) e \(x \in \mathbb{R}^n\), il valore scalare \(x^T A x\) è chiamato forma quadratica: $$x^T A x = \sum_{i=1}^n x_i (Ax)_i = \sum_{i=1}^n x_i \left( \sum_{j=1}^n A_{ij}x_j \right) = \sum_{i=1}^n \sum_{j=1}^n A_{ij} x_i x_j$$ Si denota anche con \((Ax \mid x)\).

C'è una sottigliezza che vale la pena mettere in luce, perché spiega perché in questo contesto si assume quasi sempre \(A\) simmetrica: la parte antisimmetrica di \(A\) non contribuisce affatto al valore della forma.

ProposizioneForma quadratica di una matrice antisimmetrica. Siano \(x \in \mathbb{R}^n\) e \(A \in \mathbb{R}^{n \times n}\) antisimmetrica. Allora \(x^T A x = 0\).

Dimostrazione

Poiché \(x^T A x\) è uno scalare, coincide con la propria trasposta. Applicando \((ABC)^T = C^T B^T A^T\):

$$x^T A x = (x^T A x)^T = x^T A^T x$$

Ma \(A\) è antisimmetrica, cioè \(A^T = -A\), quindi \(x^T A^T x = -x^T A x\). Mettendo insieme le due relazioni si ottiene \(x^T A x = -x^T A x\), cioè \(2\, x^T A x = 0\) e quindi \(x^T A x = 0\). \(\blacksquare\)

Da qui segue il risultato annunciato. Decomponiamo \(A\) nella sua parte simmetrica e antisimmetrica:

$$A = \underbrace{\frac{1}{2}(A + A^T)}_{\text{simmetrica}} + \underbrace{\frac{1}{2}(A - A^T)}_{\text{antisimmetrica}}$$

Nella forma quadratica il secondo addendo dà contributo nullo per la proposizione appena dimostrata, e resta

$$x^T A x = x^T \left( \frac{1}{2}(A + A^T) \right) x$$

ossia solo la parte simmetrica di \(A\) contribuisce alla forma quadratica. Assumere \(A\) simmetrica non è dunque una restrizione: è semplicemente eliminare una parte che non ha alcun effetto sul risultato.

DefinizioneMatrici definite e semidefinite. Sia \(A \in \mathbb{R}^{n \times n}\).

• \(A\) si dice definita positiva se \(\forall x \in \mathbb{R}^n,\ x \neq 0 : x^T A x \gt 0\)
• \(A\) si dice semidefinita positiva se \(\forall x \in \mathbb{R}^n : x^T A x \geq 0\)
• \(A\) si dice definita negativa se \(\forall x \in \mathbb{R}^n,\ x \neq 0 : x^T A x \lt 0\)
• \(A\) si dice semidefinita negativa se \(\forall x \in \mathbb{R}^n : x^T A x \leq 0\)
• \(A\) si dice indefinita se non rientra in nessuno dei casi precedenti

La definitezza è la generalizzazione del segno di un numero, e regola tutto ciò che riguarda minimi e massimi: nella terza parte vedremo che una matrice hessiana definita positiva in un punto critico identifica un minimo, esattamente come \(f''(x) \gt 0\) nel caso a una variabile.

Proposizione Una matrice definita positiva (o negativa) ha sempre rango \(n\), ed è quindi invertibile.

Dimostrazione

Supponiamo per assurdo che \(A\) non abbia rango \(n\). Allora una colonna di \(A\) è combinazione lineare delle altre \(n-1\):

$$a_j = \sum_{i \neq j} x_i a_i \qquad \text{per qualche } x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_n \in \mathbb{R}$$

Ponendo \(x_j = -1\) otteniamo un vettore \(x\) non nullo tale che

$$Ax = \sum_{i=1}^n x_i a_i = 0$$

e quindi \(x^T A x = 0\) per un \(x \neq 0\). Ma allora \(A\) non può essere né definita positiva né definita negativa. Pertanto una matrice definita deve necessariamente avere rango \(n\), ed essere quindi invertibile. \(\blacksquare\)

ProposizioneMatrice di Gram. Sia \(A \in \mathbb{R}^{m \times n}\). La matrice \(G = A^T A\) è sempre semidefinita positiva. Inoltre, se \(m \geq n\) e \(A\) ha rango \(n\), allora \(A^T A\) è definita positiva.

Il perché si vede in una riga: \(x^T A^T A x = (Ax)^T(Ax) = \lVert Ax \rVert_2^2 \geq 0\). È il motivo per cui la matrice \((A^T A)^{-1}\) che compare nella formula dei minimi quadrati esiste ogni volta che \(A\) ha pieno rango.

12. Autovalori e autovettori

Arriviamo al cuore del capitolo. La domanda è: esistono direzioni che la trasformazione \(A\) non ruota, ma si limita a dilatare o contrarre?

DefinizioneAutovalori e autovettori. Sia \(A \in \mathbb{R}^{n \times n}\). Diciamo che \(\lambda \in \mathbb{C}\) è autovalore per \(A\) e \(x \in \mathbb{C}^n\) è autovettore di \(A\) se $$Ax = \lambda x, \qquad x \neq 0$$

Se \(x\) è autovettore e \(c \in \mathbb{C}\), allora \(A(cx) = cAx = c\lambda x = \lambda(cx)\), quindi anche \(cx\) è autovettore associato allo stesso autovalore. Un autovettore individua dunque una direzione, non un vettore specifico; per convenzione si sceglie quello di norma 1.

Una conseguenza immediata, che tornerà utilissima, riguarda le potenze: da \(Av = \lambda v\) segue \(A^2 v = A(\lambda v) = \lambda A v = \lambda^2 v\), e in generale

$$A^k v = \lambda^k v$$

Lungo un autovettore, applicare \(A\) mille volte costa quanto elevare un numero alla millesima potenza. È l'osservazione da cui nasce tutto il resto della sezione.

Polinomio caratteristico

Riscriviamo la definizione come sistema omogeneo:

$$(A - \lambda I_n)\,x = 0, \qquad x \neq 0$$

Il sistema ammette soluzioni non nulle se e solo se il nullspace di \(A - \lambda I_n\) non si riduce al solo vettore nullo, ossia se e solo se \(A - \lambda I_n\) è singolare, cioè se \(\det(A - \lambda I_n) = 0\). Altrimenti l'unica soluzione sarebbe \(x = 0\), che la definizione esclude.

DefinizionePolinomio caratteristico. Sviluppando il determinante di \(A - \lambda I\) si ottiene un polinomio in \(\lambda\) di grado \(n\), chiamato polinomio caratteristico di \(A\). L'equazione caratteristica di \(A\) consiste nel polinomio caratteristico uguagliato a zero.

La ricetta operativa segue: per calcolare gli autovalori si risolve l'equazione caratteristica; per ogni autovalore trovato si sostituisce in \((A - \lambda I_n)x = 0\) e si risolve il sistema lineare in \(x\) per ottenere i corrispondenti autovettori. Poiché il polinomio ha grado \(n\), sul campo complesso ci sono sempre \(n\) autovalori contati con molteplicità — ed è questa la ragione per cui la definizione è data su \(\mathbb{C}\) e non su \(\mathbb{R}\).

TeoremaMatrici simili hanno lo stesso polinomio caratteristico. Siano \(A, B \in M_n(\mathbf{K})\) simili. Allora \(\det(A - \lambda I_n) = \det(B - \lambda I_n)\).

Dimostrazione

Essendo \(A\) e \(B\) simili, esiste \(P \in GL(n,\mathbf{K})\) con \(B = P^{-1}AP\). Osserviamo che anche \(\lambda I_n\) si può riscrivere come \(P^{-1}(\lambda I_n)P\), poiché l'identità commuta con tutto. Quindi

$$B - \lambda I_n = P^{-1}AP - P^{-1}(\lambda I_n)P = P^{-1}(A - \lambda I_n)P$$

Passando ai determinanti e sfruttando la moltiplicatività:

$$\det(B - \lambda I_n) = \det(P^{-1}) \det(A - \lambda I_n) \det(P) = \det(P^{-1}P) \det(A - \lambda I_n) = \det(A - \lambda I_n)$$

I due polinomi coincidono, quindi hanno le stesse radici. \(\blacksquare\)

TeoremaCambiamento di base. Siano \(\mathbf{E}\) uno spazio vettoriale su \(\mathbf{K}\) e \((e_i)\), \((e_i')\) due sue basi. Se \(v \in \mathbf{E}\) e \(x = (x_i)\), \(x' = (x_i')\) sono i vettori delle componenti di \(v\) rispetto alle due basi, allora \(x = P x'\), dove \(P\) è una matrice invertibile di ordine \(n\).

Proposizione Siano \(\mathbf{E}\) uno spazio vettoriale, \(f \in \mathrm{End}(\mathbf{E})\) e \(\mathbf{B} = (e_i)\), \(\mathbf{B}' = (e_i')\) due basi di \(\mathbf{E}\). Dette \(M_B(f)\) e \(M_{B'}(f)\) le matrici associate a \(f\) rispetto alle due basi, si ha \(M' = P^{-1} M P\), dove \(P\) è la matrice di passaggio da \(\mathbf{B}\) a \(\mathbf{B}'\). Di conseguenza \(M\) e \(M'\) sono simili.

Unendo gli ultimi due risultati si ottiene una conclusione importante: a un endomorfismo si può associare lo stesso polinomio caratteristico indipendentemente dalla base scelta. Gli autovalori non sono una proprietà della matrice, ma della trasformazione che la matrice rappresenta. Ecco perché sono così informativi: sopravvivono al cambiamento di coordinate.

ProposizioneProprietà degli autovalori.

• \(\mathrm{tr}\, A = \sum_{i=1}^n \lambda_i\)
• \(|A| = \prod_{i=1}^n \lambda_i\)
• Se \(A\) è invertibile e \(\lambda\) è autovalore di \(A\) con autovettore \(x\), allora \(\frac{1}{\lambda}\) è autovalore di \(A^{-1}\) con lo stesso autovettore associato.
• Gli autovalori di una matrice diagonale sono semplicemente gli elementi della diagonale principale.
• Se \(A\) è diagonalizzabile, il rango di \(A\) è pari al numero dei suoi autovalori non nulli.

Le prime due sono notevoli perché legano due quantità immediate da calcolare (traccia e determinante) alle radici di un polinomio che invece è difficile risolvere. La seconda in particolare chiarisce il legame con l'invertibilità: \(|A| = 0\) se e solo se almeno un autovalore è nullo, cioè se e solo se esiste una direzione che \(A\) schiaccia sullo zero.

L'ultima proprietà richiede l'ipotesi di diagonalizzabilità. In generale è falsa: la matrice \(\begin{bmatrix} 0 & 1 \\ 0 & 0\end{bmatrix}\) ha entrambi gli autovalori nulli ma rango 1. Per le matrici simmetriche, che sono sempre diagonalizzabili, il problema non si pone.

Il teorema di min-max per le matrici simmetriche

Il risultato che segue caratterizza gli autovalori estremi di una matrice simmetrica come minimo e massimo della forma quadratica sulla sfera unitaria. È il ponte fra algebra lineare e ottimizzazione, e la dimostrazione — la più lunga di questa serie — merita di essere seguita per intero perché mostra il meccanismo all'opera.

TeoremaAutovalori di una matrice simmetrica. Sia \(A \in M_n(\mathbb{R})\) simmetrica. Denotati $$m = \min_{\lVert x \rVert = 1} x^T A x \qquad\qquad M = \max_{\lVert x \rVert = 1} x^T A x$$ si ha che:

1. \(\forall x \in \mathbb{R}^n : m \lVert x \rVert^2 \leq x^T A x \leq M \lVert x \rVert^2\)
2. \(m\) è il più piccolo autovalore di \(A\), \(M\) il più grande.

Dimostrazione

Esistenza di minimo e massimo. Denotiamo \(S = \{x \in \mathbb{R}^n : \lVert x \rVert = 1\}\). La funzione \(x^T A x = \sum_{i,j} a_{ij}x_i x_j\) è un polinomio in \(n\) variabili, quindi continua; \(S\) è chiuso e limitato in \(\mathbb{R}^n\), quindi compatto. Per il teorema di Weierstrass minimo e massimo esistono, e la tesi ha senso.

Punto 1. Sia \(x \in \mathbb{R}^n\). Se \(x = 0\) la catena di disuguaglianze è banale, perché tutti i membri sono nulli. Se \(x \neq 0\), il vettore \(x/\lVert x \rVert\) appartiene a \(S\), quindi per definizione di \(m\) e \(M\):

$$m \leq \left(\frac{x}{\lVert x \rVert}\right)^T A \left(\frac{x}{\lVert x \rVert}\right) = \frac{x^T A x}{\lVert x \rVert^2} \leq M$$

Moltiplicando per \(\lVert x \rVert^2 \gt 0\) si ottiene \(m \lVert x \rVert^2 \leq x^T A x \leq M \lVert x \rVert^2\), che è la tesi.

Punto 2, prima parte: ogni autovalore è compreso fra \(m\) e \(M\). Sia \(\lambda \in \mathbb{R}\) un autovalore di \(A\) (reale, perché \(A\) è simmetrica), con autovettore \(x \neq 0\), cioè \(Ax = \lambda x\). Allora

$$x^T A x = x^T \lambda x = \lambda \lVert x \rVert^2$$

e per il punto 1, dividendo per \(\lVert x \rVert^2\), si ha \(m \leq \lambda \leq M\).

Punto 2, seconda parte: \(m\) e \(M\) sono effettivamente autovalori. Consideriamo la funzione

$$F(x) = \frac{x^T A x}{\lVert x \rVert^2}, \qquad x \in \mathbb{R}^n \setminus \{0\}$$

che è un rapporto di polinomi con denominatore non nullo, quindi differenziabile. Per il punto 1 si ha \(F(x) \geq m\) ovunque, e per definizione di minimo esiste \(\dot v \in S\) con \(\lVert \dot v \rVert = 1\) tale che \(m = \dot v^T A \dot v = F(\dot v)\). Dunque \(\dot v\) è un punto di minimo assoluto — e quindi anche relativo — per \(F\), e in un punto di minimo relativo interno il gradiente si annulla:

$$\forall h = 1 \dots n : \quad \frac{\partial F}{\partial x_h}(\dot v) = 0$$

Calcoliamo la derivata parziale con la regola del quoziente:

$$\frac{\partial F}{\partial x_h}(x) = \frac{\lVert x \rVert^2 \frac{\partial}{\partial x_h}(x^T A x) - (x^T A x)\frac{\partial}{\partial x_h}\lVert x \rVert^2}{\lVert x \rVert^4}$$

Serve il numeratore. Isolando nella doppia sommatoria i termini che contengono \(x_h\):

$$\frac{\partial}{\partial x_h}(x^T A x) = \frac{\partial}{\partial x_h}\left[ \sum_{\substack{i,j \\ i,j \neq h}} a_{ij}x_i x_j + \sum_{j \neq h} a_{hj}x_h x_j + \sum_{i \neq h} a_{ih}x_i x_h + a_{hh}x_h^2 \right]$$

Il primo blocco non dipende da \(x_h\) e dà 0; restano

$$= \sum_{j \neq h} a_{hj}x_j + \sum_{i \neq h} a_{ih}x_i + 2 a_{hh}x_h \ \overset{(A \text{ simmetrica})}{=}\ 2 \sum_{i=1}^n a_{ih}x_i$$

Per l'altro pezzo, da \(\lVert x \rVert^2 = x_1^2 + \dots + x_n^2\) segue \(\frac{\partial}{\partial x_h}\lVert x \rVert^2 = 2x_h\). Sostituendo:

$$\frac{\partial F}{\partial x_h}(x) = \frac{2\lVert x \rVert^2 \sum_{i=1}^n a_{ih}x_i - 2(x^T A x)x_h}{\lVert x \rVert^4} = \frac{2}{\lVert x \rVert^2}\left[ \sum_{i=1}^n a_{ih}x_i - F(x)\, x_h \right]$$

Valutando in \(\dot v\), dove \(\lVert \dot v \rVert = 1\) e \(F(\dot v) = m\), e imponendo l'annullamento:

$$\frac{\partial F}{\partial x_h}(\dot v) = 2\left[ \sum_{i=1}^n a_{ih}\dot v_i - m\, \dot v_h \right] = 0 \quad \Rightarrow \quad \forall h : \sum_{i=1}^n a_{ih}\dot v_i = m\, \dot v_h$$

Le \(n\) uguaglianze scalari, messe insieme, sono esattamente l'equazione vettoriale

$$A \dot v = m \dot v$$

cioè \(m\) è autovalore di \(A\) con autovettore \(\dot v\). Lo stesso ragionamento applicato al punto di massimo mostra che anche \(M\) è autovalore. Poiché per la prima parte ogni autovalore sta fra \(m\) e \(M\), essi sono rispettivamente il minimo e il massimo. \(\blacksquare\)

Il risultato è notevole: cercare il massimo di una forma quadratica sulla sfera unitaria — un problema di ottimizzazione vincolata — equivale a trovare un autovalore, che è un problema algebrico. Nella terza parte ritroveremo lo stesso fatto per via lagrangiana, e lo vedremo comparire come principio dietro alla PCA.

DefinizioneSpettro e raggio spettrale. Si definisce spettro di una matrice, o di un endomorfismo, l'insieme dei suoi autovalori. Si chiama raggio spettrale il massimo della norma dei suoi autovalori.

DefinizioneAutospazio. Siano \(\mathbf{E}\) uno spazio vettoriale su \(\mathbf{K}\), \(f \in \mathrm{End}(\mathbf{E})\) e \(\lambda\) un autovalore di \(f\). L'insieme \(\mathbf{E}_\lambda\) costituito da tutti gli autovettori di \(f\) corrispondenti a \(\lambda\), più il vettore nullo, è un sottospazio vettoriale di \(\mathbf{E}\) e si chiama autospazio associato all'autovalore \(\lambda\).

ProposizioneCaratterizzazione delle matrici definite. Sia \(A \in \mathbb{R}^{n \times n}\) simmetrica, e siano \(m\) e \(M\) il più piccolo e il più grande dei suoi autovalori. Allora:

• \(A\) è definita positiva \(\iff m \gt 0\)
• \(A\) è definita negativa \(\iff M \lt 0\)

È il corollario immediato del teorema di min-max: se il minimo della forma quadratica sulla sfera è positivo, la forma è positiva ovunque tranne che nell'origine. Verificare la definitezza si riduce così a guardare il segno degli autovalori.

13. Diagonalizzazione

DefinizioneMatrice diagonalizzabile. Una matrice \(A \in M_n(\mathbf{K})\) si dice diagonalizzabile se esiste \(P \in GL(n,\mathbf{K})\) tale che \(P^{-1}AP\) sia una matrice diagonale, ossia se \(A\) è simile a una matrice diagonale.

TeoremaEndomorfismo diagonalizzabile. Sia \(f \in \mathrm{End}(\mathbf{E})\). Allora \(f\) è diagonalizzabile se e solo se esiste una base di \(\mathbf{E}\) formata da autovettori di \(f\).

Il teorema dice esattamente cosa significhi diagonalizzare: trovare un sistema di riferimento in cui la trasformazione si limita a scalare gli assi. Vediamo come si costruisce.

ProposizioneDecomposizione in autovettori. Sia \(A \in \mathbb{R}^{n \times n}\), siano \(v_1, \dots, v_n\) i suoi autovettori e \(\lambda_1, \dots, \lambda_n\) i corrispondenti autovalori. Allora \(A v_i = \lambda_i v_i\) per \(i = 1, \dots, n\). Raccogliendo gli autovettori come colonne di una matrice \(V\) e gli autovalori in una matrice diagonale \(\Lambda\), si ottiene $$A = V \Lambda V^{-1}$$

Il passaggio chiave usa la lettura 4.3 del prodotto. Posto \(V = [\,v_1 \ \dots \ v_n\,]\), moltiplicare \(A\) per \(V\) significa moltiplicare \(A\) per ciascuna colonna di \(V\):

$$AV = [\,Av_1 \ \dots \ Av_n\,] = [\,\lambda_1 v_1 \ \dots \ \lambda_n v_n\,] = V\Lambda \qquad\text{dove}\qquad \Lambda = \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix}$$

Moltiplicando a destra per \(V^{-1}\) si ottiene \(A = V\Lambda V^{-1}\). Si noti come la scelta della lettura giusta del prodotto abbia ridotto tutto a due passaggi: con gli indici sarebbe stato un conto ben più laborioso.

In generale gli autovalori possono essere complessi, ma le matrici simmetriche reali si comportano molto meglio, e si decompongono con una matrice ortogonale:

$$A = Q \Lambda Q^T$$

dove \(Q\) è ortogonale e composta dagli autovettori di \(A\). Poiché per una matrice ortogonale l'inversa è la trasposta, la decomposizione diventa gratuita da invertire.

ProposizioneAutovalori di matrici simmetriche. Sia \(A \in \mathbb{R}^{n \times n}\) simmetrica. Allora:

1. tutti gli autovalori sono reali; li denotiamo con \(\lambda_1, \dots, \lambda_n\);
2. esiste un insieme di autovettori \(u_1, \dots, u_n\) che costituiscono una base ortonormale di \(\mathbb{R}^n\), corrispondenti agli autovalori \(\lambda_i\);
3. detta \(U\) la matrice le cui colonne sono tali autovettori, si ha \(A = U \Lambda U^T\).

Dimostrazione del punto 3

Usando la lettura "matrice per set di colonne":

$$AU = A\,[\,u^1, \dots, u^n\,] = [\,Au^1, Au^2, \dots, Au^n\,] = [\,\lambda_1 u^1, \dots, \lambda_n u^n\,] = U\,\mathrm{diag}(\lambda_1, \dots, \lambda_n) = U\Lambda$$

Ricordando che per una matrice ortonormale vale \(U U^T = I\), si conclude:

$$A = A I_n = A U U^T = U \Lambda U^T \qquad \blacksquare$$

Questa rappresentazione di \(A\) come \(U \Lambda U^T\) è chiamata diagonalizzazione della matrice \(A\), e permette di trattare una matrice simmetrica come se fosse diagonale — cosa molto più semplice da capire e da calcolare.

Il cambio di base come cambio di prospettiva

Vale la pena vedere in dettaglio che cosa significhi operativamente. Una matrice ortonormale \(U\) definisce una base ortonormale di \(\mathbb{R}^n\): ogni \(x \in \mathbb{R}^n\) si scrive come combinazione lineare di \(u_1, \dots, u_n\) con opportuni coefficienti \(\hat x_1, \dots, \hat x_n\), cioè \(x = U \hat x\). Ma poiché \(U^T U = I\),

$$x = U \hat x \iff \hat x = U^T x$$

Il vettore \(\hat x = U^T x\) è dunque la rappresentazione di \(x\) rispetto alla base \(U\), e passare avanti e indietro fra le due rappresentazioni costa una moltiplicazione per \(U\) o per \(U^T\).

ProposizioneIl prodotto matrice-vettore nella base degli autovettori. Sia \(z = Ax\). Allora la rappresentazione di \(z\) nella base \(U\) è $$\hat z = U^T z = U^T A x = U^T U \Lambda U^T x = \Lambda \hat x = \begin{bmatrix} \lambda_1 \hat x_1 \\ \lambda_2 \hat x_2 \\ \vdots \\ \lambda_n \hat x_n \end{bmatrix}$$

Moltiplicare a sinistra per \(A\) nello spazio originale equivale dunque a moltiplicare per la matrice diagonale \(\Lambda\) rispetto alla nuova base: nella base giusta, l'azione di \(A\) si riduce a scalare ciascuna coordinata per il proprio autovalore. Il vantaggio esplode con le potenze. Calcoliamo \(q = AAAx\):

$$\hat q = U^T q = U^T A A A x = U^T U \Lambda \underbrace{U^T U}_{I} \Lambda \underbrace{U^T U}_{I} \Lambda U^T x = \Lambda^3 \hat x = \begin{bmatrix} \lambda_1^3 \hat x_1 \\ \lambda_2^3 \hat x_2 \\ \vdots \\ \lambda_n^3 \hat x_n \end{bmatrix}$$

I fattori \(U^T U\) si annullano a coppie e restano solo le potenze degli autovalori. Elevare una matrice alla \(k\)-esima potenza costa \(n\) elevamenti a potenza scalari invece di \(k\) moltiplicazioni matriciali. È la stessa idea che rende trattabili le catene di Markov e i sistemi dinamici lineari.

ProposizioneDiagonalizzazione di una forma quadratica. Come corollario diretto: $$x^T A x = x^T U \Lambda U^T x = \hat x^T \Lambda \hat x = \sum_{i=1}^n \lambda_i \hat x_i^{\,2}$$

Nella base degli autovettori la forma quadratica perde tutti i termini misti e diventa una somma pesata di quadrati: \(n\) addendi invece dei \(n^2\) richiesti dal calcolo diretto \(x^T A x = \sum_{i,j} a_{ij}x_i x_j\). Da questa scrittura la caratterizzazione della definitezza diventa evidente.

ProposizioneAutovalori e definitezza. Data \(A \in \mathbb{R}^{n \times n}\) simmetrica con autovalori \(\lambda_i\):

1. se \(\lambda_i \gt 0\) per ogni \(i\), allora \(A\) è definita positiva, poiché \(x^T A x = \sum_i \lambda_i \hat x_i^{\,2} \gt 0\) per ogni \(\hat x \neq 0\);
2. se \(\lambda_i \geq 0\) per ogni \(i\), allora \(A\) è semidefinita positiva;
3. analogamente se gli autovalori sono tutti negativi o tutti non positivi;
4. se \(A\) ha sia autovalori positivi sia negativi, è indefinita.

Dimostrazione del punto 4

Siano \(\lambda_i \gt 0\) e \(\lambda_j \lt 0\). Scegliamo \(\hat x\) con \(\hat x_i = 1\) e \(\hat x_k = 0\) per ogni \(k \neq i\): allora \(x^T A x = \sum_k \lambda_k \hat x_k^{\,2} = \lambda_i \gt 0\). Scegliendo invece \(\hat x_j = 1\) e le altre componenti nulle si ottiene \(x^T A x = \lambda_j \lt 0\). La forma assume dunque valori di entrambi i segni, cioè \(A\) è indefinita. \(\blacksquare\)

14. Decomposizione ai valori singolari (SVD)

La diagonalizzazione ha un limite: si applica solo a matrici quadrate, e per avere una base ortonormale di autovettori serve anche la simmetria. La SVD rimuove entrambe le restrizioni. Vale per qualsiasi matrice, anche rettangolare, e produce sempre due basi ortonormali.

L'idea è decomporre una matrice \(m \times n\) in tre componenti: una matrice unitaria a sinistra, una matrice diagonale al centro e una matrice unitaria a destra trasposta. Formalmente, data \(A \in \mathbb{R}^{m \times n}\), la sua SVD è

$$A = U D V^T$$

dove:

• \(U\) è una matrice unitaria \(m \times m\) le cui colonne sono gli autovettori sinistri di \(A\), cioè quelli che si ottengono dall'equazione \(v A = \lambda v\). Una matrice unitaria è tale che \(U U^* = I\), dove \(U^*\) è la trasposta coniugata di \(U\);
• \(D\) è una matrice diagonale \(m \times n\) contenente i valori singolari di \(A\);
• \(V\) è unitaria \(n \times n\) e contiene nelle colonne gli autovettori destri di \(A\), ottenuti da \(Av = \lambda v\).

La decomposizione ha una lettura geometrica pulita: ogni trasformazione lineare, per quanto complicata, è la composizione di una rotazione (\(V^T\)), una dilatazione lungo gli assi (\(D\)) e un'altra rotazione (\(U\)). Non c'è altro.

Come si calcola

1. Calcolare \(A^T A\) e \(A A^T\). Questi prodotti sono matrici quadrate e simmetriche, quindi molto più maneggevoli dell'originale per il calcolo di autovalori e autovettori.
2. Calcolare autovalori e autovettori di \(A^T A\) e \(A A^T\). Gli autovalori saranno i quadrati dei valori singolari di \(A\), e gli autovettori corrispondenti saranno i vettori singolari sinistri e destri.
3. Calcolare i valori singolari. Sono le radici quadrate degli autovalori di \(A^T A\) (equivalentemente di \(A A^T\)), ordinati in senso decrescente.
4. Costruire \(U\) e \(V\). Le colonne di \(U\) sono gli autovettori normalizzati di \(A A^T\); le colonne di \(V\) sono gli autovettori normalizzati di \(A^T A\).
5. Costruire \(D\). È una matrice \(m \times n\) diagonale, con i valori singolari lungo la diagonale principale in ordine decrescente e zeri altrove, per far tornare le dimensioni.

Riassumendo il legame con la diagonalizzazione: i vettori singolari sinistri di \(A\) sono gli autovettori di \(A A^T\), i vettori singolari destri sono gli autovettori di \(A^T A\), e i valori singolari di \(A\) sono le radici quadrate degli autovalori di \(A^T A\). Il fatto che tutto funzioni non è casuale — abbiamo visto nella sezione 11 che \(A^T A\) è sempre semidefinita positiva, quindi i suoi autovalori sono non negativi e la radice quadrata esiste sempre.

Combinando la SVD con la lettura 4.2 del prodotto si ottiene \(A = \sum_i \sigma_i\, u_i v_i^T\): una somma di matrici di rango 1, pesate dai valori singolari e ordinate per importanza decrescente. Troncando la somma ai primi \(k\) termini si ottiene la migliore approssimazione di rango \(k\) di \(A\) — il risultato su cui poggiano la compressione di immagini, la PCA e i sistemi di raccomandazione.

15. Pseudo-inversa di Moore-Penrose

L'inversa non è definita per matrici non quadrate, ma spesso è proprio quello che ci servirebbe: risolvere \(Ax = y\) con \(A\) rettangolare. Se disponessimo di un'inversa sinistra \(B\), cioè tale che \(BA = I\), potremmo scrivere \(x = By\). Il problema è che non sempre esiste: se \(A\) ha più righe che colonne (sistema sovradeterminato) potrebbe non esserci alcuna soluzione, se ne ha meno (sottodeterminato) le soluzioni potrebbero essere infinite.

La pseudo-inversa di Moore-Penrose dà una risposta sensata in entrambi i casi ed è definita così:

$$A^+ = \lim_{\alpha \to 0} (A^T A + \alpha I)^{-1} A^T$$

Il termine \(\alpha I\) è una regolarizzazione che rende la matrice invertibile anche quando \(A^T A\) è singolare, e il limite la fa sparire. Nella pratica però non si calcola così, ma tramite la SVD:

$$A^+ = V D^+ U^T$$

dove \(U\) e \(V\) provengono dalla SVD di \(A\) e \(D^+\) è la pseudo-inversa della matrice diagonale \(D\), ottenuta prendendo il reciproco degli elementi non nulli di \(D\) e trasponendo il risultato. Se \(D\) ha valori singolari \(\sigma_1, \sigma_2, \dots, \sigma_r\), allora \(D^+\) è la matrice diagonale con elementi \(\frac{1}{\sigma_1}, \frac{1}{\sigma_2}, \dots, \frac{1}{\sigma_r}\), zeri fuori dalla diagonale, trasposta.

Il comportamento nei due casi problematici è esattamente quello che si vorrebbe:

• quando \(A\) ha più colonne che righe e le soluzioni sono infinite, \(x = A^+ y\) restituisce quella di norma euclidea \(\lVert x \rVert_2\) minima;
• quando \(A\) ha più righe che colonne e potrebbe non esistere alcuna soluzione, \(x = A^+ y\) restituisce l'\(x\) per cui \(Ax\) è il più vicino possibile a \(y\), misurando con \(\lVert Ax - y \rVert_2\).

Il secondo caso è precisamente il problema dei minimi quadrati, e infatti quando \(A\) ha pieno rango si ha \(A^+ = (A^T A)^{-1}A^T\), che ritroveremo nella terza parte per via differenziale.

Dove si va da qui

Abbiamo visto le matrici da vicino: le quattro letture del prodotto, il rango come misura dell'informazione conservata, il determinante come volume, e infine autovalori e valori singolari come strumenti per guardare dentro una trasformazione e capire in quali direzioni agisce e con quale intensità.

Manca un pezzo: la derivazione. Nella terza e ultima parte introduciamo il gradiente rispetto a una matrice e l'hessiana, calcoliamo le derivate delle forme lineari e quadratiche, deriviamo le equazioni dei minimi quadrati, e chiudiamo il cerchio ritrovando gli autovalori come soluzioni di un problema di ottimizzazione vincolata.