Corso di Algebra Avanzata Teoria dei Codici e Crittografia: 2 Algebra Lineare Avanzata

Algebra Lineare Avanzata

Autovalori e autovettori — diagonalizzazione — matrici simmetriche, SVD, applicazioni a sistemi dinamici e crittografia.

Obiettivi

Fornire strumenti teorici e computazionali per: calcolare autovalori/autovettori; decidere diagonalizzabilità; usare decomp. spettrali in applicazioni (es. stabilità di sistemi lineari, compressione, crittografia). Capire i risultati chiave: teorema spettrale, forma di Jordan, SVD e loro significato pratico.

1. Autovalori e autovettori — definizione e significato

Per una matrice quadrata \(A\in\mathbb{K}^{n\times n}\) (con \(\mathbb{K}=\mathbb{R}\) o \(\mathbb{C}\)), un numero \(\lambda\in\mathbb{K}\) è un autovalore se esiste un vettore non nullo \(v\neq 0\) tale che

\(\displaystyle A v = \lambda v.\)

Il vettore \(v\) è un autovettore associato a \(\lambda\). Dal punto di vista geometrico \(A\) agisce moltiplicando la direzione \(v\) solo per lo scalare \(\lambda\), senza ruotarla (a meno di fattori complessi).

Gli autovalori si trovano risolvendo il polinomio caratteristico

\(\displaystyle \chi_A(\lambda)=\det(A-\lambda I)=0.\)

Proprietà utili

• Somma degli autovalori (con molteplicità algebrica) = \(\mathrm{tr}(A)\).
• Prodotto degli autovalori = \(\det(A)\).
• Per matrici reali, autovalori complessi compaiono a coniugati complessi.

2. Diagonalizzazione: quando è possibile e come procedere

Una matrice \(A\) è diagonalizzabile se esiste una matrice invertibile \(P\) tale che

\(\displaystyle P^{-1} A P = D\), con \(D\) diagonale (gli autovalori di \(A\) sulle diagonali).

Condizione necessaria e sufficiente: la somma delle dimensioni dei sottospazi propri (dimensioni geometriche, cioè il numero di autovettori linearmente indipendenti) deve essere \(n\). In pratica: per ogni autovalore \(\lambda\) la molteplicità geometrica (dim kernel\((A-\lambda I)\)) deve uguagliare la molteplicità algebrica.

Algoritmo per diagonalizzare (se possibile)

1. Calcola il polinomio caratteristico e trova gli autovalori \(\lambda_i\) con le loro molteplicità algebriche \(m_i\).
2. Per ciascun \(\lambda_i\) risolvi \((A-\lambda_i I)v=0\) e trova una base del corrispondente spazio proprio (dimensione \(g_i\)).
3. Se per ogni \(i\) vale \(g_i=m_i\), allora raccogli gli autovettori in colonne in \(P\) e ottieni \(P^{-1}AP=D\).

3. Esempio numerico 1 — Matrice \(2\times 2\)

Consideriamo

\(\displaystyle A=\begin{pmatrix}4 & 1\\[4pt] 2 & 3\end{pmatrix}.\)

Passo 1 (polinomio caratteristico):

\(\chi_A(\lambda)=\det\!\begin{pmatrix}4-\lambda & 1\\ 2 & 3-\lambda\end{pmatrix}=(4-\lambda)(3-\lambda)-2\).

Calcolo esplicito (digit-by-digit):

\((4-\lambda)(3-\lambda)=12-4\lambda-3\lambda+\lambda^2=\lambda^2-7\lambda+12\).

Sottraendo 2 otteniamo \(\lambda^2-7\lambda+10\).

Le radici: \(\lambda^2-7\lambda+10=0 \Rightarrow \lambda=\dfrac{7\pm\sqrt{49-40}}{2}=\dfrac{7\pm3}{2}\). Quindi \(\lambda_1=5\), \(\lambda_2=2\).

Passo 2 (autovettori):

Per \(\lambda=5\): risolvi \((A-5I)v=0\Rightarrow \begin{pmatrix}-1 & 1\\ 2 & -2\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=0\). Equazione: \(-x+y=0\Rightarrow y=x\). Possiamo scegliere \(v_1=(1,1)^T\).

Per \(\lambda=2\): \((A-2I)v=0\Rightarrow \begin{pmatrix}2 & 1\\ 2 & 1\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=0\). Equazione: \(2x+y=0\Rightarrow y=-2x\). Scegliamo \(v_2=(1,-2)^T\).

Poiché abbiamo due autovettori linearmente indipendenti, \(A\) è diagonalizzabile: con \(P=[v_1\; v_2]=\begin{pmatrix}1 & 1\\1 & -2\end{pmatrix}\), si verifica \(P^{-1}AP=\mathrm{diag}(5,2)\).

Nota applicativa: per il sistema lineare dinamico \(\dot x = A x\), la soluzione è \(x(t)=P e^{Dt} P^{-1} x(0)\). Qui \(e^{Dt}=\mathrm{diag}(e^{5t},e^{2t})\): entrambe le componenti crescono → sistema instabile.

4. Esempio numerico 2 — Matrice simmetrica \(3\times 3\)

Prendiamo la tridiagonale simmetrica

\(\displaystyle A=\begin{pmatrix}2 & 1 & 0\\[4pt] 1 & 2 & 1\\[4pt] 0 & 1 & 2\end{pmatrix}.\)

Caratteristica e autovalori (calcoli):

Determinante \(\det(A-\lambda I)\) si calcola con espansione: si ottiene \((2-\lambda)\big((2-\lambda)^2-1\big) - 1\cdot\big(1(2-\lambda)-0\big)\). Lo sviluppo dà (dopo semplificazioni) la fattorizzazione \(\chi_A(\lambda)=(2-\lambda)\big(\lambda^2-4\lambda+2\big)\).

Quindi autovalori: \(\lambda_1=2\), e le due soluzioni \(\lambda=\dfrac{4\pm\sqrt{16-8}}{2}=2\pm\sqrt{2}\). Numericamente: \(\lambda_2\approx 2+\sqrt{2}\approx 3.4142\), \(\lambda_3\approx 2-\sqrt{2}\approx 0.5858\).

Autovettori (scelta ragionevole):

• Per \(\lambda_1=2\): risolve \((A-2I)v=0\Rightarrow\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}v=0\). Da qui \(v_2=0\) e \(v_1=-v_3\). Scegliamo \(v^{(1)}=(1,0,-1)\).
• Per \(\lambda_2=2+\sqrt2\): si trova un autovettore proporzionale a \( (1,\sqrt2,1) \). (Verifica diretta: \(A(1,\sqrt2,1)^T=(2+\sqrt2)(1,\sqrt2,1)^T\).)
• Per \(\lambda_3=2-\sqrt2\): autovettore proporzionale a \( (1,-\sqrt2,1) \).

Rilevanza: per matrici simmetriche reali vale il teorema spettrale: sono diagonalizzabili con una matrice ortogonale \(Q\) (cioè \(Q^TQ=I\)): \(Q^T A Q = \mathrm{diag}(\lambda_i)\). Gli autovettori si possono scegliere ortogonali e normalizzati.

5. Jordan form e matrici non diagonalizzabili

Non tutte le matrici sono diagonalizzabili: quando la molteplicità geometrica di un autovalore è minore della sua molteplicità algebrica si ottiene una matrice di Jordan. Esempio classico:

\(J=\begin{pmatrix}2 & 1\\ 0 & 2\end{pmatrix}\) ha unico autovalore \(\lambda=2\) con molteplicità algebrica 2 ma solo un autovettore → non diagonalizzabile.

In questo caso \(A\) è simile a blocchi di Jordan e si può calcolare \(e^{At}\) tramite formule per blocchi di Jordan (che introducono polinomi in \(t\) moltiplicati a \(e^{\lambda t}\)).

6. SVD (decomposizione ai valori singolari)

Per ogni matrice reale \(A\in\mathbb{R}^{m\times n}\) esiste una decomposizione

\(\displaystyle A = U \Sigma V^T,\)

dove \(U\in\mathbb{R}^{m\times m}\) e \(V\in\mathbb{R}^{n\times n}\) sono ortogonali e \(\Sigma\) è una matrice rettangolare diagonale con valori singolari \(\sigma_i\ge0\) ordinati decrescenti. SVD è fondamentale per:

• riduzione di rango (best low-rank approx: Eckart–Young),
• soluzione dei minimi quadrati e inversione numericamente stabile (pseudoinversa),
• analisi dei dati (PCA: autovettori di \(A^TA\) corrispondono a colonne di \(V\)).

7. Applicazioni: sistemi dinamici lineari e stabilità

Consideriamo il sistema autonomo lineare

\(\displaystyle \dot x(t) = A x(t),\qquad x(0)=x_0.\)

Soluzione formale: \( x(t)= e^{A t}x_0 \). Se \(A\) è diagonalizzabile \(A=PDP^{-1}\) allora \(e^{At}=P e^{Dt} P^{-1}\) e \(e^{Dt}\) è diagonale con \(e^{\lambda_i t}\) sulle diagonali.

Criterio di stabilità (lineare): lo stato \(x=0\) è asintoticamente stabile se tutti gli autovalori di \(A\) hanno parte reale < 0. Se esiste un autovalore con parte reale positiva, il sistema è instabile.

Esempio pratico (2×2): con la matrice \(A\) del paragrafo 3 gli autovalori erano \(5\) e \(2\) (reali e positivi) → soluzioni esplodono esponenzialmente → instabile.

8. Matrici simmetriche, prodotto scalare e positività

Se \(A=A^T\) allora tutti gli autovalori sono reali e si ha una base ortonormale di autovettori. Se inoltre \(x^T A x >0\) per ogni \(x\neq 0\), \(A\) è definita positiva e tutte le autovalori sono positive. Questo è cruciale in problemi di energia, stabilità e ottimizzazione convessa.

9. Applicazioni avanzate in informatica e crittografia

• Riduzione dimensionalità e PCA: autovettori di \(A^TA\) danno direzioni di massima varianza; proiezione sui primi k autovettori riduce rumore e dati.
• Codici e trasformazioni: nelle trasformazioni lineari su campi finiti (es. \( \mathbb{F}_{2^8} \) per AES) la teoria degli autovalori non vale identicamente come su \(\mathbb{R}\), ma le strutture di modulo e le proprietà di invertibilità delle matrici sono fondamentali.
• Analisi della stabilità numerica: SVD e condizionamento (numero di condizionamento \( \kappa(A)=\sigma_{\max}/\sigma_{\min} \)) valutano la sensibilità delle soluzioni lineari agli errori nei dati.

10. Esercizi svolti e raccomandazioni pratiche

Esercizio A — diagonalizzazione 3×3 (svolto): prova a diagonalizzare numericamente la matrice del paragrafo 4; normalizza gli autovettori e costruisci \(Q\) ortogonale.

Esercizio B — forma di Jordan (svolto): per \(J=\big(\begin{smallmatrix}2&1\\0&2\end{smallmatrix}\big)\) calcola \(e^{Jt} = e^{2t}\begin{pmatrix}1 & t \\ 0 & 1\end{pmatrix}\).

Esercizio C — SVD e approssimazione: calcola SVD di una matrice 3×2 numerica semplice (es. \(\begin{pmatrix}3&1\\2&2\\0&1\end{pmatrix}\)) e ricostruisci la migliore approssimazione di rango 1.

11. Conclusione e linee di approfondimento

L’algebra lineare avanzata presenta risultati teorici potenti (teorema spettrale, SVD, Jordan form) con impatti pratici in analisi dei dati, simulazioni dinamiche e crittografia. Per un uso efficace: padroneggia calcoli di autovalori/autovettori, pratica la costruzione di basi proprie, impara a usare la SVD per problemi numerici e valuta sempre il condizionamento delle matrici per garantire stabilità numerica.

Se vuoi, posso: (a) generare immagini PNG delle principali dimostrazioni/figure per inserirle su Blogger senza dipendere da MathJax, (b) fornire notebook Python (NumPy/SciPy) con i calcoli numerici svolti, oppure (c) spezzare questo materiale in blocchi pronti per più post.