Matrici circolanti e supercircolanti - algoritmi divide and conquer

Matrici con molta ripetizione possono essere trattate con algoritmi sublineari nel numero di elementi. Qui si studiano due famiglie: le supercircolanti (SC), costruite a quadranti in modo ricorsivo, e le circolanti (CR), ottenute ruotando la prima riga. Sul modello di costo (operazioni tra scalari a costo $1$, assegnamenti e copie a costo $0$) vedi 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 →. Gli elementi sono numeri reali o complessi e $n = 2^k$ (per le SC).

Matrici supercircolanti

Definizione. Una matrice $A$ di ordine $n = 2^k$ è supercircolante (SC) se: $n = 1$ (ogni scalare è SC di ordine $1$); oppure $n > 1$ e

$$A = \begin{pmatrix} A_1 & A_2 \\ A_2 & A_1 \end{pmatrix}$$

con $A_1, A_2$ matrici SC di ordine $\frac n2$ (quadranti alternati).

Esempio. Con quattro scalari $a, b, c, d$: $\begin{pmatrix} a & b \\ b & a \end{pmatrix}$ e $\begin{pmatrix} c & d \\ d & c \end{pmatrix}$ sono SC di ordine $2$; componendole come $A_1, A_2$ si ottiene la SC di ordine $4$

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

Proprietà

1. Ogni riga è una permutazione della prima, e la matrice è simmetrica. Per induzione: per $n = 1$ è ovvio; per $n > 1$ la riga $i$ della metà alta è la riga $i$ di $(A_1 \; A_2)$ e quella della metà bassa è la riga $i$ di $(A_2 \; A_1)$, cioè le stesse due metà scambiate, e per ipotesi le righe di $A_1, A_2$ sono permutazioni delle loro prime righe. Per la simmetria: $A^T = \begin{pmatrix} A_1^T & A_2^T \\ A_2^T & A_1^T \end{pmatrix} = A$ perché $A_1, A_2$ sono simmetriche per ipotesi. Di conseguenza il numero massimo di elementi distinti è $n$, non $n^2$, e una SC è determinata dalla prima riga $r(A)$, scelta in modo arbitrario.
2. Elemento $(h, k)$. Con indici da $0$ a $n-1$: $A_{hk} = r(A)_{h \oplus k}$, dove $\oplus$ è lo XOR bit a bit (esercizio: Esercizio - elemento (h,k) di una matrice supercircolante (esercizi su supercircolanti e circolanti, es. SC 5)).
3. Chiusura. Somma, differenza, prodotto per scalare e prodotto di due SC sono SC.
4. Commutatività: $AB = BA$ per ogni coppia di SC.

Dimostrazione di 3 e 4 (induzione su $k$, insieme per somma e prodotto). Base $n = 1$: somma e prodotto di scalari sono scalari, e il prodotto di scalari commuta. Passo: siano

$$A = \begin{pmatrix} A_1 & A_2 \\ A_2 & A_1 \end{pmatrix}, \qquad B = \begin{pmatrix} B_1 & B_2 \\ B_2 & B_1 \end{pmatrix}.$$

Per la somma, sfruttando la proprietà frattale (si somma quadrante per quadrante),

$$A + B = \begin{pmatrix} A_1 + B_1 & A_2 + B_2 \\ A_2 + B_2 & A_1 + B_1 \end{pmatrix},$$

con $A_1 + B_1$ e $A_2 + B_2$ SC di ordine $\frac n2$ per ipotesi induttiva: due quadranti alternati SC, quindi $A + B$ è SC. Per il prodotto, per la proprietà frattale del prodotto a blocchi,

$$AB = \begin{pmatrix} A_1B_1 + A_2B_2 & A_1B_2 + A_2B_1 \\ A_2B_1 + A_1B_2 & A_2B_2 + A_1B_1 \end{pmatrix} = \begin{pmatrix} C_1 & C_2 \\ C_2 & C_1 \end{pmatrix}, \quad C_1 = A_1B_1 + A_2B_2, \; C_2 = A_1B_2 + A_2B_1.$$

Ogni quadrante è somma di prodotti di SC di ordine $\frac n2$, quindi SC per ipotesi (prodotto e somma): $AB$ ha quadranti alternati SC. Infine $BA$ ha $C_1' = B_1A_1 + B_2A_2$ e $C_2' = B_1A_2 + B_2A_1$, e per commutatività a ordine $\frac n2$ si ha $C_1' = C_1$, $C_2' = C_2$: $BA = AB$. $\blacksquare$

In altre parole le SC $n \times n$ formano un sottoanello commutativo delle matrici simmetriche.

Somma, differenza, prodotto per scalare

Se si rappresenta una SC con la sua prima riga, la somma è la somma delle prime righe: $n$ somme. Con la sola struttura ricorsiva:

S_SUM(A, B)               { A, B SC dello stesso ordine n = 2^k }
  n <- rows(A)
  if n = 1 then return [a11 + b11]
  * A = [A1 A2; A2 A1], B = [B1 B2; B2 B1] *
  C1 <- S_SUM(A1, B1)
  C2 <- S_SUM(A2, B2)
  return [C1 C2; C2 C1]

La correttezza dipende dal fatto che $C_1, C_2$ sono somme di SC e quindi si ottengono richiamando lo stesso algoritmo specializzato. La ricorrenza è $T_S(1) = 1$, $T_S(n) = 2\,T_S(\frac n2)$; con la formula generale (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 →) $s = 2$, $w = 0$: restano solo le foglie, $T_S(n) = 2^{\log_2 n} \cdot 1 = n$. È sorprendentemente poco: è la lunghezza di una riga. S_SUB e S_SCALPROD (prodotto per scalare) si scrivono allo stesso modo e costano $n$.

La matrice in uscita si ottiene copiando $C_1$ e $C_2$ due volte: le copie sono quadratiche in $n$ ma nel modello di costo valgono $0$. Se gli assegnamenti costassero $1$, si avrebbe $T(n) = T(\frac n2) + \Theta(n^2)$, caso 3 del 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 →, cioè $\Theta(n^2)$: nessun risparmio asintotico rispetto alle matrici generali.

Prodotto: dalle 4 chiamate alle 2

Dalla struttura, con $C = AB$ SC di quadranti $C_1, C_2$:

$$C_1 = A_1B_1 + A_2B_2, \qquad C_2 = A_1B_2 + A_2B_1.$$

Calcolare i soli quadranti distinti richiede 4 chiamate ricorsive e $2$ somme di SC di ordine $\frac n2$: $T(n) = 4T(\frac n2) + n$ (lavoro $2 \cdot \frac n2 = n$). La soglia è $n^2$, siamo nel caso 1 e $T = \Theta(n^2)$ (esatto: $2n^2 - n$). Domina il lavoro alle foglie: come per Strassen, si riducono le chiamate aumentando il lavoro di divide e conquer. Si calcolano

$$U = (A_1 + A_2)(B_1 + B_2) = A_1B_1 + A_1B_2 + A_2B_1 + A_2B_2,$$ $$V = (A_1 - A_2)(B_1 - B_2) = A_1B_1 - A_1B_2 - A_2B_1 + A_2B_2.$$

Si somma e si sottrae (i termini misti $A_1B_2 + A_2B_1$ cambiano segno, gli altri no):

$$U + V = 2(A_1B_1 + A_2B_2) = 2C_1, \qquad U - V = 2(A_1B_2 + A_2B_1) = 2C_2.$$

Dunque $C_1 = \frac 12 (U + V)$ e $C_2 = \frac 12 (U - V)$. Le due matrici $A_1 \pm A_2$ e $B_1 \pm B_2$ sono SC (chiusura), quindi $U$ e $V$ sono prodotti di SC e si ottengono ricorsivamente.

S_MUL(A, B)
  n <- rows(A)
  if n = 1 then return [a11 * b11]
  * A = [A1 A2; A2 A1], B = [B1 B2; B2 B1] *
  Ap <- S_SUM(A1, A2);  Bp <- S_SUM(B1, B2)           { DIVIDE: 4 operazioni su SC di ordine n/2 }
  Am <- S_SUB(A1, A2);  Bm <- S_SUB(B1, B2)
  U <- S_MUL(Ap, Bp)                                  { RECURSE: 2 chiamate }
  V <- S_MUL(Am, Bm)
  C1 <- S_SCALPROD(1/2, S_SUM(U, V))                  { CONQUER: 4 operazioni }
  C2 <- S_SCALPROD(1/2, S_SUB(U, V))
  return [C1 C2; C2 C1]

Il lavoro dei nodi interni è di $8$ operazioni su SC di ordine $\frac n2$ (quattro somme/sottrazioni nel divide, due nel conquer, due prodotti per scalare), ciascuna di costo $\frac n2$: $8 \cdot \frac n2 = 4n$. La ricorrenza è

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

La soglia è $n^{\log_2 2} = n = \Theta(w(n))$: caso 2, $T_M = \Theta(n \log n)$. Il conto esatto con la formula generale ($s = 2$, $w = 4n$, $\log_2 n = k$ livelli interni, $2^k = n$ foglie): al livello $\ell$ ci sono $2^\ell$ nodi di lavoro $4 \cdot \frac{n}{2^\ell}$, cioè $4n$ per livello:

$$T_M(n) = \sum_{\ell=0}^{k-1} 2^\ell \cdot 4\,\frac{n}{2^\ell} + 2^k = 4nk + n = 4n \log_2 n + n.$$

Esempio ($n = 4$). $A$ con prima riga $(1, 2, 3, 4)$, $B$ con prima riga $(1, 0, 2, 1)$: quindi $A_1 \leftrightarrow (1, 2)$, $A_2 \leftrightarrow (3, 4)$, $B_1 \leftrightarrow (1, 0)$, $B_2 \leftrightarrow (2, 1)$. Divide: $A_1 + A_2 \leftrightarrow (4, 6)$, $B_1 + B_2 \leftrightarrow (3, 1)$, $A_1 - A_2 \leftrightarrow (-2, -2)$, $B_1 - B_2 \leftrightarrow (-1, -1)$. Per $U = S\_MUL((4,6),(3,1))$ con $n = 2$: la somma delle metà dà $(10)$ e $(4)$, la differenza $(-2)$ e $(2)$, i prodotti $40$ e $-4$, quindi $U = \bigl(\frac{40 - 4}{2}, \frac{40 + 4}{2}\bigr) = (18, 22)$. Per $V = S\_MUL((-2,-2),(-1,-1))$: somma $(-4)$ e $(-2)$, differenza $0$ e $0$, prodotti $8$ e $0$, quindi $V = (4, 4)$. Conquer: $C_1 = \frac 12 (U + V) = (11, 13)$ e $C_2 = \frac 12 (U - V) = (7, 9)$. La prima riga del prodotto è $(11, 13, 7, 9)$. Controllo dalla definizione: $C_1 = A_1B_1 + A_2B_2$ ha prima riga $(1, 2) + (10, 11) = (11, 13)$, e $C_2 = A_1B_2 + A_2B_1$ ha $(4, 5) + (3, 4) = (7, 9)$.

Diagonalizzazione e trasformata di Hadamard

Due matrici simmetriche in generale non si diagonalizzano nella stessa base, ma le SC commutano, e matrici diagonalizzabili che commutano hanno una base comune di autovettori (infatti se $Av = \alpha v$ e $AB = BA$ allora $A(Bv) = B(Av) = \alpha\,Bv$: $B$ manda autovettori di $A$ in autovettori con lo stesso autovalore). Qui la base comune si esibisce direttamente (per il richiamo teorico vedi DiagonalizzazioneUna matrice è diagonalizzabile se è simile a una diagonale, cioè se esiste una base di autovettori: allora A = S D S⁻¹ con gli autovettori nelle colonne di S e gli autovalori in D. Criterio: tutti gli autovalori nel campo e molteplicità geometrica uguale a quella algebrica. Le matrici simmetriche reali hanno autovalori reali.Diagonalizzazione → e Autovalori e autovettoriUn autovettore è un vettore non nullo che una funzione lineare manda in un suo multiplo; si trovano gli autovalori come radici del polinomio caratteristico det(A − λI) e gli autovettori come nucleo di A − λI. Matrici simili hanno gli stessi autovalori.Autovalori e autovettori →).

La base $\mathcal B(n)$

Si definisce per induzione: $\mathcal B(1) = \{[1]\}$ e, per $n \ge 2$,

$$\mathcal B(n) = \left\{ \begin{pmatrix} w \\ w \end{pmatrix} : w \in \mathcal B(\tfrac n2) \right\} \cup \left\{ \begin{pmatrix} w \\ -w \end{pmatrix} : w \in \mathcal B(\tfrac n2) \right\}.$$

I vettori sono $n$, hanno componenti $\pm 1$ (norma $\sqrt n$) e la prima componente vale sempre $1$. Sono a due a due ortogonali, quindi una base di $\mathbb R^n$. Per induzione: $n = 1$ è banale. Per $n > 1$ due vettori distinti hanno una delle tre forme: $(w; w)$ e $(u; u)$ con $w \neq u$, prodotto scalare $2\,w \cdot u = 0$ per ipotesi; $(w; -w)$ e $(u; -u)$, prodotto $w \cdot u + w \cdot u = 0$; oppure $(w; w)$ e $(u; -u)$, prodotto $w \cdot u - w \cdot u = 0$ (anche per $w = u$).

Le matrici $H(n)$ che hanno per colonne i vettori di $\mathcal B(n)$ sono le matrici di Hadamard (di Sylvester): $H(1) = [1]$ e

$$H(n) = \begin{pmatrix} H(\frac n2) & H(\frac n2) \\ H(\frac n2) & -H(\frac n2) \end{pmatrix}, \qquad H(2) = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad H(4) = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}.$$

Sono simmetriche e $H(n)H(n) = nI$, per induzione: $H(n)H(n) = \begin{pmatrix} 2H(\frac n2)H(\frac n2) & 0 \\ 0 & 2H(\frac n2)H(\frac n2) \end{pmatrix} = \begin{pmatrix} 2\cdot\frac n2 I & 0 \\ 0 & 2\cdot\frac n2 I \end{pmatrix} = nI$. Quindi $H(n)^{-1} = \frac 1n H(n)$.

$\mathcal B(n)$ diagonalizza tutte le SC

Teorema. Per ogni SC $A$ di ordine $n$ e ogni $v \in \mathcal B(n)$ vale $Av = \alpha v$ con $\alpha = r(A) \cdot v$ (prodotto scalare della prima riga con $v$).

Dimostrazione per induzione su $k$. Per $n = 1$: $A = [a]$, $v = [1]$, $Av = a\,v$ e $r(A) \cdot v = a$. Per $n > 1$, $v = (w; \varepsilon w)$ con $w \in \mathcal B(\frac n2)$ e $\varepsilon = \pm 1$. Allora

$$Av = \begin{pmatrix} A_1 w + \varepsilon A_2 w \\ A_2 w + \varepsilon A_1 w \end{pmatrix} = \begin{pmatrix} (A_1 + \varepsilon A_2) w \\ \varepsilon (A_1 + \varepsilon A_2) w \end{pmatrix},$$

perché $A_2 w + \varepsilon A_1 w = \varepsilon (A_1 w + \varepsilon A_2 w)$ (si usa $\varepsilon^2 = 1$). Ora $A_1 + \varepsilon A_2$ è una SC di ordine $\frac n2$ (chiusura), e per ipotesi $(A_1 + \varepsilon A_2) w = \beta w$ con $\beta = r(A_1 + \varepsilon A_2) \cdot w = r(A_1) \cdot w + \varepsilon\,r(A_2) \cdot w$. Quindi $Av = \beta (w; \varepsilon w) = \beta v$, e $\beta = r(A) \cdot v$ perché $r(A) = (r(A_1), r(A_2))$ e $v = (w; \varepsilon w)$. $\blacksquare$

Poiché la prima componente di ogni $v$ è $1$, basta la prima riga per avere l'autovalore, senza moltiplicare l'intera matrice per $v$ (si passa da $O(n^2)$ a $O(n)$ per autovalore). Indicando con $\alpha_j$ l'autovalore di $v_j$ (colonna $j$ di $H(n)$):

$$(\alpha_1, \dots, \alpha_n)^T = H(n)\, r(A)^T.$$

Gli autovalori di una SC sono la trasformata di Hadamard della sua prima riga. Il teorema ha una conseguenza immediata: gli autovettori di $A$ con $\varepsilon = +1$ sono quelli di $A_1 + A_2$ e quelli con $\varepsilon = -1$ quelli di $A_1 - A_2$. Quindi $A$ è invertibile se e solo se lo sono $A_1 + A_2$ e $A_1 - A_2$, e $\det A = \det(A_1 + A_2) \det(A_1 - A_2)$. I valori calcolati alle foglie della ricorsione di S_MUL sono proprio gli autovalori.

Fast Hadamard Transform

La struttura di $H(n)$ dà la proprietà di sottostruttura: con $x = (u; v)$, $u, v \in \mathbb R^{n/2}$,

$$H(n)\,x = \begin{pmatrix} H(\frac n2)(u + v) \\ H(\frac n2)(u - v) \end{pmatrix}.$$

Un'istanza di taglia $n$ si riduce a due di taglia $\frac n2$, con $\frac n2$ somme e $\frac n2$ differenze. L'algoritmo divide & conquer è la FHT:

FHT(x)                      { x di lunghezza n = 2^k }
  n <- length(x)
  if n = 1 then return x
  for i <- 1 to n/2 do
    s[i] <- x[i] + x[i + n/2]
    d[i] <- x[i] - x[i + n/2]
  return concatena(FHT(s), FHT(d))

$T(1) = 0$ (per $n = 1$, $H(1)x = x$ non fa operazioni) e $T(n) = 2T(\frac n2) + n$, cioè $T(n) = n \log_2 n$: ogni livello interno ha lavoro $2^\ell \cdot \frac{n}{2^\ell} = n$, e i livelli sono $\log_2 n$. (Le note del corso scrivono $T(1) = 1$ e poi riportano $n \log_2 n$: con $T(1) = 1$ la soluzione sarebbe $n \log_2 n + n$; il caso base non esegue operazioni, quindi $T(1) = 0$ è la scelta coerente con il risultato.) L'inversa $H(n)^{-1} = \frac 1n H(n)$ si calcola con una FHT e $n$ moltiplicazioni per $\frac 1n$: $n \log_2 n + n$ operazioni.

Esempio ($n = 4$). Per la SC con prima riga $x = (1, 2, 3, 4)$ gli autovalori sono $H(4)\,x$. Con $u = (1, 2)$ e $v = (3, 4)$: $u + v = (4, 6)$ e $u - v = (-2, -2)$; $H(2)(4, 6) = (4 + 6, 4 - 6) = (10, -2)$ e $H(2)(-2, -2) = (-4, 0)$. Gli autovalori sono $(10, -2, -4, 0)$: i primi due sono quelli di $A_1 + A_2 \leftrightarrow (4, 6)$, gli altri due quelli di $A_1 - A_2 \leftrightarrow (-2, -2)$. Si controlla con le righe di $H(4)$: $1 - 2 + 3 - 4 = -2$, $1 + 2 - 3 - 4 = -4$, $1 - 2 - 3 + 4 = 0$. Poiché un autovalore è $0$, questa SC non è invertibile ($\det A = 10 \cdot (-2) \cdot (-4) \cdot 0 = 0$).

Prodotto di SC passando dalla base diagonalizzante

Teorema. Se $A, B$ sono SC e $c(A), c(B), c(C)$ sono le prime righe viste come vettori colonna ($c(A) = r(A)^T$), il prodotto $C = AB$ soddisfa

$$c(C) = H(n)^{-1} \bigl[ (H(n)\,c(A)) \otimes (H(n)\,c(B)) \bigr],$$

dove $\otimes$ è il prodotto componente per componente.

Infatti gli autovalori di $AB$ sono i prodotti degli autovalori $\alpha_j\beta_j$ (stessa base), e si torna alla prima riga con l'inversa della trasformata. Costo: due FHT ($2n\log_2 n$), $n$ prodotti, una trasformata inversa ($n \log_2 n + n$): in tutto $3n \log_2 n + 2n = O(n \log n)$ operazioni (verificato con un programma). Il metodo diretto S_MUL ($4n \log_2 n + n$) non ha bisogno di autovalori; i due costi differiscono solo per la costante (per $n \ge 4$ la via di Hadamard è più economica).

Il passaggio per autovalori serve soprattutto a risolvere problemi analoghi, per esempio l'inversione: la proprietà di sottostruttura di $A_1, A_2$ non dice nulla sull'invertibilità di $A$, mentre con gli autovalori $A$ è invertibile se e solo se nessuno è nullo, e l'inversa si ottiene prendendo i reciproci e tornando alla prima riga. Si ricava anche $\det A = \prod_j \alpha_j$ con $n \log_2 n + n - 1$ operazioni.

Matrici circolanti

Definizione. Una matrice $n \times n$ è circolante (CR) se ogni riga è la rotazione di una posizione verso destra della precedente, cioè $A_{(h+\ell) \bmod n,\,(k+\ell) \bmod n} = A_{h,k}$ per ogni $h, k, \ell$.

Con indici da $0$: $A_{hk} = A_{0,(k-h) \bmod n} = r(A)_{(k-h) \bmod n}$. Per esempio, con $r(A) = (1, 2, 0, 3)$:

$$A = \begin{pmatrix} 1 & 2 & 0 & 3 \\ 3 & 1 & 2 & 0 \\ 0 & 3 & 1 & 2 \\ 2 & 0 & 3 & 1 \end{pmatrix}.$$

Le CR sono casi particolari di matrici di Toeplitz. A differenza delle SC valgono per ogni $n$ (non solo per le potenze di $2$), e modellano i sistemi lineari tempo-invarianti con ingressi periodici di periodo $n$.

La matrice di rotazione $R$

Sia $R$ la CR con prima riga $(0, 1, 0, \dots, 0)$, la matrice di rotazione circolare a sinistra: $R_{h,k} = 1$ se $k = (h + 1) \bmod n$, altrimenti $0$.

• Per un vettore colonna $x = (x_0, \dots, x_{n-1})$ si ha $Rx = (x_1, x_2, \dots, x_{n-1}, x_0)$. Quindi $R^n = I$.
• $A$ è CR se e solo se $RA = AR$. Si calcola $(RA)_{h,k} = A_{h+1,k}$ (la riga $h$ di $RA$ è la riga $h + 1$ di $A$) e $(AR)_{h,k} = \sum_j A_{h,j} R_{j,k} = A_{h,k-1}$ (l'unico $j$ con $R_{jk} = 1$ è $j = k - 1$), indici modulo $n$. L'uguaglianza $A_{h+1,k} = A_{h,k-1}$ per ogni $h, k$ è $A_{h+1,k+1} = A_{h,k}$, la definizione di CR.
• Ogni CR è un polinomio in $R$: $$A = \sum_{k=0}^{n-1} A_{0k} R^k.$$ Infatti $R^k$ ha $1$ in posizione $(h, (h+k) \bmod n)$, quindi la sua prima riga è $e_k$ e il termine $A_{0k}R^k$ contribuisce $A_{0k}$ a tutte le diagonali circolari corrispondenti. Nell'esempio sopra $A = I + 2R + 0R^2 + 3R^3$. Le CR sono tutte e sole le combinazioni lineari delle potenze di $R$.

Da qui seguono: chiusura per somma (somma di polinomi), per prodotto (prodotto di polinomi in $R$, ridotto con $R^n = I$), e commutatività (due polinomi nella stessa matrice commutano). Le CR formano un sottoanello commutativo.

Prodotto e convoluzione ciclica

Il prodotto di due polinomi in $R$ è un polinomio in $R$ con $R^n = I$, cioè calcolato modulo $z^n - 1$. Date le sequenze $a, b$ di lunghezza $n$, la convoluzione ciclica $c = a \circledast b$ è la sequenza con

$$p_c(z) = p_a(z)\,p_b(z) \bmod (z^n - 1), \qquad c_k = \sum_{i=0}^{n-1} a_i\, b_{(k-i) \bmod n}.$$

(Ridurre modulo $z^n - 1$ significa sostituire $z^{n+j}$ con $z^j$: il coefficiente di $z^k$ riceve tutti i termini $a_ib_j$ con $i + j \equiv k \pmod n$, cioè $j = (k - i) \bmod n$.) Scrivendo $A = \sum a_k R^k$ e $B = \sum b_k R^k$ e usando $R^n = I$:

$$AB = \sum_{i,j} a_i b_j R^{i+j} = \sum_{k=0}^{n-1} \Bigl( \sum_{i + j \equiv k} a_i b_j \Bigr) R^k, \qquad r(AB) = r(A) \circledast r(B).$$

Moltiplicare matrici circolanti equivale a convolvere ciclicamente le prime righe (vedi anche Polinomi - rappresentazione per coefficienti e per valori e convoluzioneun polinomio di grado limitato da n si rappresenta con n coefficienti o con n valori su n punti distinti (teorema di interpolazione, matrice di Vandermonde). Per coefficienti la somma costa n e il prodotto, la convoluzione lineare, n^2 prodotti e (n-1)^2 somme; per valori il prodotto costa 2n-1 prodotti ma serve una base estesa di almeno 2n-1 punti. Le conversioni generali costano troppo: valutazione n volte con Horner 2n(n-1), interpolazione con Gauss-Jordan n^3 o con Lagrange n^2. Serve una base speciale: la DFT.Polinomi - rappresentazione per coefficienti e per valori e convoluzione → e, per il lato segnali, ConvoluzioneLa convoluzione $xy(t)=\int x(u),y(t-u),du$ combina due segnali ribaltando e traslando il secondo, moltiplicando e integrando. È commutativa, associativa, lineare; l'area del risultato è il prodotto delle aree; l'estensione è la somma delle estensioni (estremo con estremo); l'impulso $\delta$ è l'elemento neutro; la convoluzione con il gradino integra. Per due segnali periodici di uguale periodo si usa la convoluzione ciclica (integrale su un periodo). È l'operazione del filtraggio: l'uscita di un filtro è la convoluzione dell'ingresso con la risposta impulsiva.Convoluzione → e Trasformata di Fourier discreta (DFT) e convoluzione circolareLa DFT di N campioni x[0..N-1] è X[k] = sum x[n] e^{-j2pi kn/N}, k = 0..N-1 (IDFT: x[n] = (1/N) sum X[k] e^{j2pi kn/N}); vede il segnale come periodico di periodo N e dà N campioni equispaziati della DTFT, cioè X(z) valutata sulle radici N-esime dell'unità. Se x ha durata M <= N non c'è aliasing temporale e lo zero-padding (N > M) infittisce solo i campioni della stessa DTFT. Proprietà: traslazione circolare, simmetria coniugata X[k] = X[N-k], prodotto = convoluzione circolare. La convoluzione circolare coincide con la lineare solo se N >= Dx + M - 1; altrimenti la coda si ripiega sull'inizio. La FFT calcola la DFT con (N/2) log2 N moltiplicazioni invece di N^2.Trasformata di Fourier discreta (DFT) e convoluzione circolare →).

Diagonalizzazione: emerge la DFT

Poiché le CR sono polinomi in $R$ e commutano, basta diagonalizzare $R$. Se $A = M \,\mathrm{diag}(\lambda_1, \dots, \lambda_n)\, M^{-1}$ allora $A^i = M \,\mathrm{diag}(\lambda_1^i, \dots, \lambda_n^i)\, M^{-1}$ (i fattori $M^{-1}M$ si semplificano) e per ogni polinomio $p$ vale $p(A) = M\,\mathrm{diag}(p(\lambda_1), \dots, p(\lambda_n))\,M^{-1}$.

Sia $\omega_n = e^{i2\pi/n}$. Per $j = 0, \dots, n-1$ il vettore $w_j = (\omega_n^{0j}, \omega_n^{1j}, \dots, \omega_n^{(n-1)j})$ è un autovettore di $R$: la componente $k$ di $Rw_j$ è la componente $k + 1$ di $w_j$, cioè $\omega_n^{(k+1)j} = \omega_n^{j}\,\omega_n^{kj}$ (per $k = n - 1$ si usa $\omega_n^{nj} = 1$). L'autovalore è $\omega_n^j$: gli autovalori di $R$ sono le $n$ radici $n$-esime dell'unità, tutte distinte. La matrice $M = [w_0, \dots, w_{n-1}]$ è la matrice di Fourier $F^{(n)}$, di Vandermonde sulle radici dell'unità (vedi DFT, matrice di Fourier e radici n-esime dell'unitàla DFT di ordine n valuta un polinomio di grado limitato da n sulle n radici n-esime dell'unità, y_i = p(ω^i) con ω = e^{2πi/n}; è il prodotto per la matrice di Fourier F_n, una Vandermonde invertibile. Le radici formano un gruppo moltiplicativo e valgono tre lemmi: cancellazione (ω_{dn}^{dk} = ω_n^k, ω_n^{n/2} = -1), dimezzamento (i quadrati delle n radici sono le n/2 radici n/2-esime, ciascuna due volte) e somma (la somma delle potenze di ω^k vale n se k è multiplo di n, 0 altrimenti). Teorema di convoluzione lineare: (c|0) = DFT^{-1}{2n}(DFT{2n}(a|0) ⊙ DFT_{2n}(b|0)).DFT, matrice di Fourier e radici n-esime dell'unità →). Quindi $F^{(n)}$ diagonalizza tutte le CR, e l'autovalore di $A$ relativo a $w_j$ è $p_A(\omega_n^j) = \sum_k A_{0k}\omega_n^{jk}$:

$$(\alpha_0, \dots, \alpha_{n-1})^T = F^{(n)}\, r(A)^T.$$

Gli autovalori di una CR sono la DFT della sua prima riga. Questo è l'equivalente matriciale del teorema di convoluzione ciclica.

Teorema (convoluzione ciclica, forma matriciale). Per due CR $A, B$ di ordine $n$:

$$r(C)^T = \bigl(F^{(n)}\bigr)^{-1} \bigl[ \bigl(F^{(n)} r(A)^T\bigr) \otimes \bigl(F^{(n)} r(B)^T\bigr) \bigr].$$

Con l'algoritmo FFT (Fast Fourier Transform - algoritmo ricorsivo e trasformata inversala FFT calcola DFT_n (n potenza di due) con divide et impera: si separano i coefficienti di indice pari e dispari, p(x) = p0(x^2) + x p1(x^2), e per il lemma di dimezzamento bastano due DFT di ordine n/2; y_i = y0_i + w^i y1_i e y_{i+n/2} = y0_i - w^i y1_i. La ricorrenza T(n) = 2T(n/2) + 2n con T(1) = 0 ha soluzione esatta 2 n log2 n. L'inversa ha matrice F^{-1}_{ij} = w^{-ij}/n: si ottiene con la FFT sulle potenze negative (poi si divide per n fuori dalla ricorsione) oppure con DFT_n(y) rovesciato. LIN_CONV moltiplica due polinomi con n coefficienti in 12 n log2(2n) + 4n operazioni.Fast Fourier Transform - algoritmo ricorsivo e trasformata inversa →) le due trasformate e l'antitrasformata costano $O(n \log n)$ e il prodotto puntuale $n$: due CR si moltiplicano in tempo $O(n \log n)$ (le note del corso scrivono "FHT" per le CR, ma qui serve la trasformata di Fourier, la FFT: la FHT diagonalizza solo le SC). La differenza con il caso SC è nell'algoritmo: la FHT è semplice, la FFT richiede più sofisticazione (valutazione e interpolazione di polinomi, radici dell'unità come punti di valutazione). Un esempio numerico completo è in Esercizio - prodotto di matrici circolanti e convoluzione ciclica con la DFT (esercizi su supercircolanti e circolanti, es. CR 10).

Esercizi collegati

• Esercizio - matrici RCA, somma e prodotto matrice-vettore (compito del 18 giugno 2026, es. 1): stessa tecnica delle SC su matrici con quadranti opposti.
• Esercizio - matrici SIR, somma, prodotto e inversa (compito del 29 gennaio 2026, es. 1): matrici con quadranti ripetuti, prodotto con tre chiamate e inversa.
• Esercizio - elemento (h,k) di una matrice supercircolante (esercizi su supercircolanti e circolanti, es. SC 5): lettura di un elemento in $O(\log n)$.
• Esercizio - algoritmo di Strassen sulle matrici supercircolanti (esercizi su supercircolanti e circolanti, es. SC 6): Strassen specializzato sulle SC.
• Esercizio - prodotto di matrici circolanti e convoluzione ciclica con la DFT (esercizi su supercircolanti e circolanti, es. CR 10): prodotto di circolanti e autovalori, con esempio numerico.

Domande d'esame

1. Qual è il numero massimo di elementi distinti di una matrice supercircolante di ordine $n$, e quante somme servono per sommare due SC? Risposta: $n$ elementi distinti (una riga determina la matrice); $n$ somme, da $T(n) = 2T(\frac n2)$, $T(1) = 1$.
2. Con quale ricorrenza si analizza il prodotto di SC con il trucco $U, V$, e qual è la sua complessità? Traccia: $2$ chiamate, $8$ operazioni su SC di ordine $\frac n2$ ($4n$ in totale), $T(n) = 2T(\frac n2) + 4n$, soglia $n$, caso 2: $\Theta(n \log n)$, esatta $4n \log_2 n + n$. Senza il trucco: $4T(\frac n2) + n$, $\Theta(n^2)$.
3. Perché le matrici circolanti si moltiplicano in $O(n \log n)$? Traccia: sono polinomi in $R$ con $R^n = I$, il prodotto è la convoluzione ciclica delle prime righe; la matrice di Fourier le diagonalizza (autovalori $=$ DFT della prima riga), quindi: DFT di entrambe, prodotto puntuale, DFT inversa, con la FFT.