Esercizio - matrici SIR, somma, prodotto e inversa (compito del 29 gennaio 2026, es. 1)

Compito d'esame di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 29 gennaio 2026, seconda parte, esercizio 1 (17 punti). Teoria usata: Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchimodello di costo sulle matrici n x n (operazioni tra scalari, taglia n oppure N = n^2); somma in n^2 operazioni (ottima); prodotto righe per colonne iterativo con costo esatto 2n^3 - n^2; proprietà frattale del prodotto a blocchi dimostrata sugli indici; algoritmo ricorsivo RMUL con T(n) = 8T(n/2) + n^2, Theta(n^3) e soluzione esatta 2n^3 - n^2 per induzione e per srotolamento: fa le stesse operazioni dell'iterativo.Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi →, Matrici circolanti e supercircolanti - algoritmi divide and conquerle matrici supercircolanti (quadranti alternati ricorsivi) hanno solo n valori distinti: somma in n operazioni, prodotto in 4n log2 n + n con il trucco (A1+A2)(B1+B2) e (A1-A2)(B1-B2) invece delle 4 chiamate (Theta(n^2)); gli autovalori sono la trasformata di Hadamard della prima riga (FHT, n log2 n) e il prodotto passa dalla base diagonalizzante; le matrici circolanti sono polinomi nella matrice di rotazione R, il loro prodotto è la convoluzione ciclica delle prime righe e si diagonalizzano con la matrice di Fourier: prodotto in O(n log n) con la FFT.Matrici circolanti e supercircolanti - algoritmi divide and conquer →, Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni →, Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze → e Matrice inversaL'inversa di una matrice quadrata A è la matrice A⁻¹ con A A⁻¹ = A⁻¹ A = I; esiste se e solo se rango(A) = n e si calcola con Gauss-Jordan riducendo (A | I) fino a (I | A⁻¹).Matrice inversa →.*

Testo

Sia $n \ge 1$ una potenza di due. Una matrice $T \in \mathbb R^{n \times n}$ si dice Supertriangolare Inferiore Ripetitiva di ordine $n$ ($n$-SIR, in breve) se $n = 1$, oppure, per $n > 1$,

$$T = \begin{pmatrix} T_1 & 0_{n/2} \\ T_2 & T_1 \end{pmatrix},$$

con $T_1, T_2$ matrici $\frac n2$-SIR.

• 1.(a) [5 punti] Si dimostri che, se $T$ e $V$ sono $n$-SIR, allora $T + V$, $T - V$ e $T \cdot V$ sono $n$-SIR.
• 1.(b) [6 punti] Si descrivano (senza necessariamente fornire lo pseudocodice) e si analizzino algoritmi divide-and-conquer SUM$(T, V)$, SUB$(T, V)$ e MULT$(T, V)$ per la somma, sottrazione e prodotto di due matrici $n$-SIR $T$ e $V$. Si esprima la complessità di tali algoritmi in funzione del numero di operazioni aritmetiche tra scalari reali eseguite.
• 1.(c) [6 punti] Si dia per dimostrato che una matrice $n$-SIR $T$ è invertibile se e solo se $n = 1$ e $t_{11} \ne 0$, oppure $n > 1$ e $T = \begin{pmatrix} T_1 & 0_{n/2} \\ T_2 & T_1 \end{pmatrix}$, con $T_1$ $\frac n2$-SIR invertibile, e che la sua inversa $T^{-1}$ è essa stessa una matrice $n$-SIR. Si determini la forma di $T^{-1}$ in funzione di $T$ e si scriva e si analizzi lo pseudocodice di un algoritmo divide-and-conquer che, data una matrice $n$-SIR invertibile, ne restituisca l'inversa.

Attenzione: per ottenere punteggio pieno, ciascuno dei tre algoritmi deve eseguire $o(n^2)$ operazioni tra scalari reali.

Come si legge la struttura

Una $n$-SIR è triangolare inferiore (zeri in alto a destra) con due sole matrici indipendenti di ordine $\frac n2$: $T_1$ compare sulla diagonale in blocchi, $T_2$ nel quadrante in basso a sinistra. Ricorsivamente restano $n$ valori indipendenti. Per $n = 4$, con $T_1 = \begin{pmatrix} a & 0 \\ b & a \end{pmatrix}$ e $T_2 = \begin{pmatrix} c & 0 \\ d & c \end{pmatrix}$:

$$T = \begin{pmatrix} a & 0 & 0 & 0 \\ b & a & 0 & 0 \\ c & 0 & a & 0 \\ d & c & b & a \end{pmatrix}.$$

Il quadrante in alto a sinistra è uguale a quello in basso a destra ($T_1$): per questo "ripetitiva". Come rappresentazione compatta si possono tenere i due quadranti $(T_1, T_2)$, ricorsivamente, cioè $n$ scalari.

Punto (a): chiusura per somma, differenza e prodotto

Induzione su $k \ge 0$ con $n = 2^k$. Base ($n = 1$): ogni matrice $1 \times 1$ è $1$-SIR, e somma, differenza e prodotto di scalari sono scalari. Passo: siano $T, V$ $n$-SIR, $n > 1$, e

$$T = \begin{pmatrix} T_1 & 0 \\ T_2 & T_1 \end{pmatrix}, \qquad V = \begin{pmatrix} V_1 & 0 \\ V_2 & V_1 \end{pmatrix}.$$

Con le operazioni per blocchi (proprietà frattale di somma e prodotto: Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchimodello di costo sulle matrici n x n (operazioni tra scalari, taglia n oppure N = n^2); somma in n^2 operazioni (ottima); prodotto righe per colonne iterativo con costo esatto 2n^3 - n^2; proprietà frattale del prodotto a blocchi dimostrata sugli indici; algoritmo ricorsivo RMUL con T(n) = 8T(n/2) + n^2, Theta(n^3) e soluzione esatta 2n^3 - n^2 per induzione e per srotolamento: fa le stesse operazioni dell'iterativo.Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi →):

$$T \pm V = \begin{pmatrix} T_1 \pm V_1 & 0 \\ T_2 \pm V_2 & T_1 \pm V_1 \end{pmatrix}, \qquad T \cdot V = \begin{pmatrix} T_1 V_1 + 0 \cdot V_2 & T_1 \cdot 0 + 0 \cdot V_1 \\ T_2 V_1 + T_1 V_2 & T_2 \cdot 0 + T_1 V_1 \end{pmatrix} = \begin{pmatrix} T_1 V_1 & 0 \\ T_2 V_1 + T_1 V_2 & T_1 V_1 \end{pmatrix}.$$

In tutti e tre i risultati il quadrante in alto a destra è $0$ e i due quadranti diagonali sono uguali ($T_1 \pm V_1$, oppure $T_1 V_1$). I quadranti rimasti sono somme, differenze o prodotti di matrici $\frac n2$-SIR: per ipotesi induttiva (che vale per somma, differenza e prodotto) sono $\frac n2$-SIR. Quindi $T + V$, $T - V$ e $TV$ hanno la forma $\begin{pmatrix} S_1 & 0 \\ S_2 & S_1 \end{pmatrix}$ con $S_1, S_2$ $\frac n2$-SIR: sono $n$-SIR. $\blacksquare$

Punto (b): SUM, SUB, MULT

Somma e differenza. Dal punto (a): $T \pm V$ ha come quadranti diversi da zero e dalla ripetizione solo $S_1 = T_1 \pm V_1$ e $S_2 = T_2 \pm V_2$, due chiamate ricorsive su matrici $\frac n2$-SIR; la seconda copia di $S_1$ e il blocco nullo non costano. Con $T_{sum}(1) = 1$:

$$T_{sum}(n) = 2\,T_{sum}\!\left(\tfrac n2\right) \;\Rightarrow\; T_{sum}(n) = 2^k = n,$$

e uguale per la differenza: $T_{sub}(n) = n$. (Formula generale: $s = 2$, $w = 0$, solo le $n$ foglie.) Sono $n$ operazioni, $o(n^2)$.

Prodotto. Dal punto (a): $TV = \begin{pmatrix} T_1V_1 & 0 \\ T_2V_1 + T_1V_2 & T_1V_1 \end{pmatrix}$. Il prodotto $T_1V_1$ compare due volte (lo si calcola una volta); servono quindi tre prodotti ricorsivi su matrici $\frac n2$-SIR: $P = T_1V_1$, $Q = T_2V_1$, $R = T_1V_2$, e una somma $Q + R$ (con SUM, di costo $\frac n2$):

MULT(T, V)
  n <- T.rows
  if n = 1 then return [t11 * v11]
  * T = [T1 0; T2 T1],  V = [V1 0; V2 V1] *
  P <- MULT(T1, V1)
  Q <- MULT(T2, V1)
  R <- MULT(T1, V2)
  S <- SUM(Q, R)                        { n/2 operazioni }
  return [P 0; S P]

La correttezza segue dal punto (a) (e le chiamate sono legittime perché $T_1, T_2, V_1, V_2$ sono $\frac n2$-SIR). La ricorrenza è

$$T_{mult}(n) = \begin{cases} 1 & n = 1, \\ 3\,T_{mult}\!\left(\frac n2\right) + \frac n2 & n > 1. \end{cases}$$

Master Theorem. $a = 3$, $b = 2$, soglia $n^{\log_2 3} \approx n^{1.585}$, $w(n) = \frac n2 = O(n^{\log_2 3 - \varepsilon})$ (per esempio $\varepsilon = 0.5$): caso 1, $T_{mult}(n) = \Theta(n^{\log_2 3}) = o(n^2)$.

Soluzione esatta. Formula generale con $s = 3$, $w(n) = \frac n2$, livello $\ell$: $3^\ell$ nodi su taglia $\frac{n}{2^\ell}$ con lavoro $\frac{n}{2^{\ell+1}}$; le foglie sono $3^k$:

$$T_{mult}(n) = \sum_{\ell=0}^{k-1} 3^\ell \cdot \frac{n}{2^{\ell+1}} + 3^k = \frac n2 \sum_{\ell=0}^{k-1} \left(\tfrac 32\right)^\ell + 3^k = \frac n2 \cdot 2 \left( \left(\tfrac 32\right)^k - 1 \right) + 3^k = n \left( \frac{3^k}{n} - 1 \right) + 3^k = 2 \cdot 3^k - n,$$

cioè $T_{mult}(n) = 2 \cdot 3^k - 2^k = 2n^{\log_2 3} - n$ (la somma geometrica è $\frac{(3/2)^k - 1}{3/2 - 1} = 2((3/2)^k - 1)$ e $(\frac 32)^k = \frac{3^k}{n}$). Controllo: $n = 1$ dà $1$; $n = 2$ dà $2 \cdot 3 - 2 = 4$ (tre prodotti più una somma di scalari: $T = \begin{pmatrix} a & 0 \\ b & a \end{pmatrix}$ per $V = \begin{pmatrix} c & 0 \\ d & c \end{pmatrix}$ dà $\begin{pmatrix} ac & 0 \\ bc + ad & ac \end{pmatrix}$, con $ac$, $bc$, $ad$ e una somma: $4$ operazioni).

Punto (c): inversa

Sia $T = \begin{pmatrix} T_1 & 0 \\ T_2 & T_1 \end{pmatrix}$ invertibile ($n > 1$); allora $T_1$ è invertibile e $T^{-1}$ è $n$-SIR, quindi della forma $T^{-1} = \begin{pmatrix} X & 0 \\ Y & X \end{pmatrix}$ con $X, Y$ $\frac n2$-SIR. Si impone $T \cdot T^{-1} = I_n$, usando la formula del prodotto del punto (a):

$$\begin{pmatrix} T_1 X & 0 \\ T_2 X + T_1 Y & T_1 X \end{pmatrix} = \begin{pmatrix} I_{n/2} & 0 \\ 0 & I_{n/2} \end{pmatrix}.$$

• Dal quadrante in alto a sinistra: $T_1 X = I_{n/2}$, quindi $X = T_1^{-1}$.
• Dal quadrante in basso a sinistra: $T_2 X + T_1 Y = 0$, cioè $T_1 Y = -T_2 X$ e, moltiplicando a sinistra per $T_1^{-1} = X$: $Y = -X\,T_2\,X = -T_1^{-1}\,T_2\,T_1^{-1}$.

$$T^{-1} = \begin{pmatrix} T_1^{-1} & 0 \\ -T_1^{-1}\,T_2\,T_1^{-1} & T_1^{-1} \end{pmatrix}.$$

Per $n = 1$: $T^{-1} = [1 / t_{11}]$ (con $t_{11} \ne 0$).

Esempio ($n = 2$). $T = \begin{pmatrix} 2 & 0 \\ 3 & 2 \end{pmatrix}$: $X = \frac 12$, $Y = -\frac 12 \cdot 3 \cdot \frac 12 = -\frac 34$, $T^{-1} = \begin{pmatrix} \frac 12 & 0 \\ -\frac 34 & \frac 12 \end{pmatrix}$. Controllo: $3 \cdot \frac 12 + 2 \cdot \left( -\frac 34 \right) = \frac 32 - \frac 32 = 0$. ✓

Algoritmo. Si calcola una volta $X = T_1^{-1}$ con una chiamata ricorsiva ($T_1$ è $\frac n2$-SIR invertibile), poi $Y$ con due prodotti di matrici SIR (usando MULT), con il segno meno gratuito (come nel compito del 18 giugno 2026, gli opposti non costano; altrimenti si aggiungerebbero $\frac n2$ operazioni, ininfluenti sull'ordine di grandezza):

INV(T)
  n <- T.rows
  if n = 1 then return [1 / t11]
  * T = [T1 0; T2 T1] *
  X <- INV(T1)
  Y <- - MULT(MULT(X, T2), X)             { due prodotti di SIR di ordine n/2 }
  return [X 0; Y X]

La correttezza segue dalla forma di $T^{-1}$ ricavata e dalla correttezza di MULT. Ricorrenza:

$$T_{inv}(n) = \begin{cases} 1 & n = 1, \\ T_{inv}\!\left(\frac n2\right) + 2\,T_{mult}\!\left(\frac n2\right) & n > 1. \end{cases}$$

Il lavoro dei nodi interni è $w(n) = 2\,T_{mult}(\frac n2) = 2\,\bigl( 2 \cdot 3^{k-1} - 2^{k-1} \bigr) = \frac 43 \cdot 3^k - 2^k$, cioè $\Theta(n^{\log_2 3})$. Master Theorem: $a = 1$, $b = 2$, soglia $n^{\log_2 1} = 1$; $w(n) = \Theta(n^{\log_2 3}) = \Omega(n^{\varepsilon})$ con $\varepsilon = 1$; condizione di regolarità: $1 \cdot w(\frac n2) \le c\,w(n)$ con $c < 1$ vale per un lavoro polinomiale ($w(\frac n2) \approx \frac 13 w(n)$). Siamo nel caso 3: $T_{inv}(n) = \Theta(n^{\log_2 3}) = o(n^2)$.

Soluzione esatta. Srotolando con $T_{inv}(1) = 1$: $T_{inv}(2^k) = 1 + \sum_{j=1}^{k} 2\,T_{mult}(2^{j-1}) = 1 + \sum_{j=1}^{k} \bigl( 4 \cdot 3^{j-1} - 2^{j} \bigr) = 1 + 2(3^k - 1) - (2^{k+1} - 2) = 2 \cdot 3^k - 2^{k+1} + 1$, cioè

$$T_{inv}(n) = 2n^{\log_2 3} - 2n + 1.$$

Controllo: $n = 2$ dà $2 \cdot 3 - 4 + 1 = 3$ (un reciproco e due prodotti, come nell'esempio). Il costo della soluzione del corso è dato solo come ordine di grandezza ($\Theta(n^{\log_2 3})$), coerente.

Verifica con un programma. Un'implementazione di MULT e INV sulle matrici SIR rappresentate dai quadranti, con conteggio delle operazioni, confrontata con il prodotto e l'inversa calcolati sulle matrici piene (in aritmetica razionale), per $n = 1, \dots, 128$, dà $T_{mult} = 2 \cdot 3^k - 2^k$ e $T_{inv} = 2 \cdot 3^k - 2^{k+1} + 1$ per ogni $k$.