La matrice di Fourier, le matrici circolanti, e le trasformate discrete veloci Si consideri la seguente matrice n × n

(1)

Rome-Moscow school of Matrix Methods and Applied Linear Algebra

Rome, Sept 19 - Oct 3, 2010, Moscow, Oct 10 - Oct 24, 2010 Carmine Di Fiore In questi appunti si introducono e si studiano le matrici circolanti, τ e Toeplitz, le algebre di Hessenberg e le decomposizioni di dislocamento, gli spazi di classe V e le migliori approssimazioni nel senso dei minimi quadrati in tali spazi.

Come conseguenza dei risultati presentati, la scelta delle matrici coinvolte nelle decomposizioni di dislocamento, la scelta dei precondizionatori nella risoluzione di sistemi lineari e la scelta delle approssimazioni dell’Hessiano nei metodi di minimizzazione quasi-Newton, diventa possibile in classi pi` u ampie di algebre di matrici di bassa complessit` a.

La matrice di Fourier, le matrici circolanti, e le trasformate discrete veloci Si consideri la seguente matrice n × n

P 1 =





 0 1

0 1 . ..

1 1 0





 .

Sia ω ∈ C. Si noti che

P 1





 1 1 1







=





 1 1 1







= 1





 1 1 1





 , P 1





 1 ω ω ⁿ⁻¹







=





 ω ω ² ω ⁿ⁻¹

1 





= ω





 1 ω ω ⁿ⁻¹





 ,

dove l’ultima uguaglianza vale se ω ⁿ = 1. Pi` u in generale, se ω ⁿ = 1, valgono le seguenti identit` a vettoriali

P 1





 1 ω ^j ω ^(n−1)j







=





 ω ^j ω ^(n−1)j

1 





= ω ^j





 1 ω ^j ω ^(n−1)j





 , j = 0, 1, . . . , n − 1, o, equivalentemente, la seguente identit` a matriciale

P 1 W = W D 1ω

ⁿ⁻¹

,

D 1ω

ⁿ⁻¹

=





 1

ω

ω ⁿ⁻¹





 , W =







1 1 1 1

1 ω ω ^j ω ⁿ⁻¹

1 ω ⁿ⁻¹ ω ^(n−1)j ω ^{(n−1)(n−1)}





 .

Proposizione. Se ω ⁿ = 1 e se ω ^j 6= 1 per 0 < j < n, allora W ^∗ W = nI.

dimostrazione: poich´e |ω| = 1, ω = ω ⁻¹ , abbiamo [W ^∗ W ] ij = [W W ] ij = P n

k=1 [W ] ik [W ] kj = P n

k=1 ω ^{(i−1)(k−1)} ω ^{(k−1)(j−1)}

= P n

k=1 ω ^{(k−1)(j−i)} = P n

k=1 (ω ^j−i ) ^k−1 .

(2)

Quindi [W ^∗ W ] ij = n se i = j, e [W ^∗ W ] ij = ^1−(ω _1−ω

^j−ij−i

⁾

ⁿ

= 0 se i 6= j (si noti che l’ipotesi ω ^j 6= 1 per 0 < j < n `e essenziale per rendere 1 − ω ^j−i 6= 0).

Per il risultato della Proposizione, possiamo dire che la seguente matrice (simmetrica) di Fourier

F = 1

√ n W

`e unitaria, i.e. F ^∗ F = I.

Esercizio. Provare che F ² = JP 1 dove J `e la matrice di permutazione Je k = e _n+1−k , k = 1, . . . , n (J `e di solito chiamata anti-identica).

L’identit` a matriciale soddisfatta da P 1 e da W pu` o essere ovviamente riscritta in termini di F , P 1 F = F D _1ω

n−1

, quindi otteniamo l’uguaglianza

P 1 = F D 1ω

ⁿ⁻¹

F ^∗

da cui segue che la matrice di Fourier diagonalizza la matrice P 1 , o, pi` u precisamente, che le colonne della matrice di Fourier formano un sistema di n autovettori unitariamente ortonormali per la matrice P 1 con corrispondenti autovalori 1, ω, . . . , ω ⁿ⁻¹ .

Ma se F diagonalizza P 1 , allora diagonalizza tutti i polinomi in P 1 : P ₁ ^k−1 = F D ^k−1 _1ω

n−1

F ^∗ ,

P n

k=1 a k P ₁ ^k−1 = F P n

k=1 a k D _1ω ^k−1

n−1

F ^∗

= F





 P n

k=1 a k

P n

k=1 a k ω ^k−1

P n

k=1 a k ω ^{(n−1)(k−1)}





 F ^∗

= F d(W a)F ^∗ = √

nF d(F a)F ^∗

dove con d(z) indichiamo la matrice diagonale i cui elementi diagonali sono z 1 , z 2 , . . . , z n .

Scriviamo le matrici P ₁ ^k−1 , k = 1, . . . , n, e la matrice P n

k=1 a k P ₁ ^k−1 nel caso n = 4:

P ₁ ⁰ = I, P ₁ ¹ =







0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0





 , P ₁ ² =







0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0





 , P ₁ ³ =







0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0





 ,

P ₁ ⁴ = P ₁ ³ P 1 = P ₁ ^T P 1 = I = P ₁ ⁰ ,

4 X

k=1

a k P ₁ ^k−1 =







a 1 a 2 a 3 a 4

a 4 a 1 a 2 a 3

a 3 a 4 a 1 a 2

a 2 a 3 a 4 a 1







= √

4F d(F a)F ^∗ , F = 1

√ 4







1 1 1 1

1 ω ω ² ω ³ 1 ω ² ω ⁴ ω ⁶ 1 ω ³ ω ⁶ ω ⁹





 ,

ω ⁴ = 1, ω ^j 6= 1, 0 < j < 4 (ω = e ^±i2π/4 ).

(3)

Si noti che, per n generico, abbiamo le identit` a e ^T ₁ P ₁ ^k−1 = e ^T _k , k = 1, . . . , n, e P ₁ ⁿ = I (provarle!). Ne segue che lo spazio C = {p(P 1 )} di tutti ipolinomi in P 1

`e generato dalle matrici J k = P ₁ ^k−1 ; il particolare polinomio P n

k=1 a k J k verr` a indicato con il simbolo C(a). Si osserva che C(a) `e la matrice di C la cui prima riga `e a ^T :

C(a) =

n

X

k=1

a k J k =







a 1 a 2 a _n−1 a n

a n a 1 a _n−1

a 3 a 2

a 2 a 3 a n a 1







= F d(F ^T a )d(F ^T e ₁ ) ⁻¹ F ⁻¹ .

C `e noto come lo spazio delle matrici circolanti.

Esercizio. (i) Si ripeta tutto, partendo dalla matrice n × n

P ₋₁ =







0 1

0 1 . ..

1 −1 0







e arrivando alla matrice (−1)-circolante la cui prima riga `e a ^T , a ∈ C ⁿ :

C ₋₁ (a) =







a 1 a 2 a _n−1 a n

−a n a 1 a _n−1

−a 3 a 2

−a 2 −a 3 −a n a 1





 .

(ii) Sia T una matrice di Toeplitz n × n, i.e. T = (t i−j ) ⁿ _i,j=1 , per certi t k ∈ C.

Mostrare che T pu` o essere riscritta come la somma di una circolante e di una (−1)-circolante, cio`e, T = C(a) + C −1 (b), a, b ∈ C ⁿ .

Perch´e le matrici circolanti possono essere interessanti nelle applicazioni dell’algebra lineare? La principale ragione `e nel fatto che il prodotto matrice- vettore C(a)z pu` o essere calcolato con al pi` u O(n log ₂ n) operazioni aritmetiche (mentre, di solito, un prodotto matrice-vettore richiede n ² moltiplicazioni).

Proposizione FFT. Dato z ∈ C ⁿ , la complessit` a del prodotto matrice-vettore F z

è al pi` u O(n log ₂ n). Tale operazione è chiamata trasformata discreta di Fourier (DFT) di z. Come conseguenza, il prodotto matrice-vettore C(a)z è calcolabile effettuando due DFT (dopo la pre-elaborazione della DFT F a).

dimostrazione: poiché ω ^{(i−1)(k−1)} è l’(i, k) elemento di W e z k è il k-esimo elemento di z ∈ C ⁿ , abbiamo

(W z) i = P n

k=1 ω ^{(i−1)(k−1)} z k = P n/2

j=1 ω (i−1)(2j−2) z _2j−1 + P n/2

j=1 ω (i−1)(2j−1) z 2j

= P n/2

j=1 (ω ² ) ^{(i−1)(j−1)} z _2j−1 + P n/2

j=1 ω (i−1)(2(j−1)+1) z 2j

= P n/2

j=1 (ω ² ) ^{(i−1)(j−1)} z _2j−1 + ω ⁱ⁻¹ P n/2

j=1 (ω ² ) ^{(i−1)(j−1)} z 2j .

Si noti che ω `e di fatto una funzione di n, cio`e la giusta notazione per ω dovrebbe

essere ω n . Allora ω ² = ω ² _n `e tale che (ω ² _n ) ^n/2 = 1 e (ω ² _n ) ⁱ 6= 1 0 < i < n/2; in

(4)

altre parole ω _n ² = ω n/2 . Quindi, abbiamo le identit` a

(W n z) i =

n/2

X

j=1

ω _n/2 ^{(i−1)(j−1)} z _2j−1 + ω _n ⁱ⁻¹

n/2

X

j=1

ω _n/2 ^{(i−1)(j−1)} z 2j , i = 1, 2, . . . , n. (?)

Ne segue che, per i = 1, . . . , ⁿ ₂ ,

(W n z) i = (W n/2





 z 1

z 3

z _n−1







) i + ω _n ⁱ⁻¹ (W n/2





 z 2

z 4

z n





 ) i .

Inoltre, ponendo i = ⁿ ₂ + k, k = 1, . . . , ⁿ ₂ , in (?), otteniamo (W n z )

ⁿ₂

+k = P n/2

j=1 ω _n/2

ⁿ²

^(j−1) ω _n/2 ^{(k−1)(j−1)} z _2j−1 + ω n

ⁿ²

ω ^k−1 _n P n/2

j=1 ω _n/2

ⁿ²

^(j−1) ω ^{(k−1)(j−1)} _n/2 z 2j

= P n/2

j=1 ω ^{(k−1)(j−1)} _n/2 z _2j−1 − ω n ^k−1

P n/2

j=1 ω _n/2 ^{(k−1)(j−1)} z 2j

= (W n/2





 z 1

z 3

z _n−1







) k − ω n ^k−1 (W n/2





 z 2

z 4

z n







) k , k = 1, . . . , ⁿ ₂ .

(ω n

ⁿ²

= −1; si pensi ω = e ^±i2π/n ). Le precedenti uguaglianze scalari possono essere riscritte in forma compatta:

W n z =

"

I D

1ω

n 2 −1

I −D _1ω

nⁿ2 −1 n

#

W n/2 0 0 W n/2

Qz,

D 1ω

n 2 −1 n

=





 1

ω n

ⁿ²

⁻¹





 , Q =





 1 0 0 1

1 0 0 1

0 0 0 1

0 1





 .

(??)

Se c n denota la complessit` a del prodotto matrice-vettore F n z, allora, per la formula precedente,

c n ≤ 2c n/2 + rn, r costante.

Ma questo implica c n = O(n log ₂ n). La dimostrazione dell’ultima affermazione

`e lasciata al lettore.

Ovviamente, ogni volta che una matrice n × n U, ben definita per tutti gli n, soddisfa per n pari una identit` a del tipo

U n = h

sparse matrix i

U n/2 0 0 U n/2

h

permutation matrix i

,

si pu` o dire che il prodotto matrice-vettore U n z pu` o essere calcolato con al pi` u

O(n log ₂ n) operazioni aritmetiche. L’identit` a di cui sopra `e verificata per al-

meno 10 matrici U , la trasformata di Fourier e la sua versione (−1), e le otto

(5)

trasformate di tipo Hartley. Si noti, comunque, che ci sono anche altre 16 trasformate discrete di complessit` a O(n log ₂ n), di tipo seno e di tipo coseno.

Vedi [],[].

Esercizio G. Si provi che la matrice n × n G = G ⁿ definita da G ij = 1

√ n (cos (2i + 1)(2j + 1)π

2n + sin (2i + 1)(2j + 1)π

2n ), i, j = 0, . . . , n − 1,

`e simmetrica, persimmetrica, reale, unitaria, e soddisfa l’identit` a:

G n = 1

√ 2

R + R ₋

−R − J R + J

G n/2 0 0 G n/2

Q, R _± = D c ± D s J, (J ⁿ ₂ × ⁿ 2 anti-identica) per opportune matrici diagonali ⁿ ₂ × ⁿ 2 D c e D s . Si provi, inoltre, che ciascuna riga di G n ha almeno un elemento nullo quando n = 2 + 4s (ci` o è come dire, vedremo, che lo spazio {Gd(z)G : z ∈ C ⁿ } non è uno spazio-h per tali valori di n); e che, invece, per tutti gli altri n, [G n ] 1k 6= 0 ∀ k (i.e., per tutti gli altri n, lo spazio {Gd(z)G : z ∈ C ⁿ } è uno spazio-1).

Esercizio. Si provi che lo spazio C ₋₁ ^S + JC ₋₁ ^SK , C ₋₁ ^S (−1)-circolanti simmetriche n × n, C ₋₁ ^SK (−1)-circolanti antisimmetriche n × n, `e una algebra commutativa di matrici (una matrice A `e antisimmetrica se if A ^T = −A).

La matrice seno e l’algebra (commutativa) delle matrici tau Si consideri la matrice n × n

P 0 + P ₀ ^T =





 0 1 1 0 1 0 1 0

1 1 0





 ,

e si ponga J 1 = I, e J 2 = P 0 + P ₀ ^T . Si noti che e ^T ₁ J 1 = e ^T ₁ , e ^T ₁ J 2 = e ^T ₂ . Inoltre, poich´e

(P 0 + P ₀ ^T ) ² =







1 0 1 0 2 0 1 1 0 2

1 1 2 0 0 1







=







0 0 1 0 1 0 1 1 0 1

1 1 1 0 1 0 0





 + I,

abbiamo e ^T ₁ ((P 0 + P ₀ ^T ) ² − I) = [0 0 1 0 · · · 0] = e ^T 3 . Si ponga J 3 = (P 0 + P ₀ ^T ) ² − I = J 2 (P 0 + P ₀ ^T ) − J ¹ ; allora e ^T ₁ J 3 = e ^T ₃ .

Pi` u in generale, si ponga J i+1 = J i (P 0 + P ₀ ^T ) − J i−1 , i = 2, 3, . . . , n − 1. La matrice J i+1 `e un polinomio in P 0 +P ₀ ^T di grado i con la propriet` a e ^T ₁ J i+1 = e ^T _i+1 . dimostrazione: supponiamo di sapere che e ^T ₁ J j = e ^T _j , j = 1, . . . , i (ed effettiva- mente lo sappiamo per i = 1, 2); allora

e ^T ₁ J i+1 = e ^T ₁ (J i (P 0 +P ₀ ^T )−J i−1 ) = (e ^T _i (P 0 +P ₀ ^T ))−e ^T _i−1 = (e ^T _i−1 +e ^T _i+1 )−e ^T _i−1 = e ^T _i+1 .

(6)

Poiché J 1 , J 2 , . . . , J n sono linearmente indipendenti, possiamo dire che esse generano l’insieme {p(P 0 + P ₀ ^T )} di tutti i polinomi nella matrice P 0 + P ₀ ^T (si usi il teorema di Cailey-Hamilton). Chiamiamo τ tale insieme. Si noti che le matrici di τ sono definite una volta che la loro prima riga è nota; con il simbolo τ (a) denotiamo la matrice di τ la cui prima riga è a ^T , i.e. la matrice P

k a k J k . Troviamo una rappresentazione utile di τ e, in particolare, di τ (a). Innanz- itutto si osservi che valgono le seguenti uguaglianze vettoriali:





 1 1 0 1

1 1 1













sin _n+1 ^jπ sin _n+1 ^2jπ sin _n+1 ^njπ







= 2 cos jπ n + 1







sin _n+1 ^jπ sin _n+1 ^2jπ sin _n+1 ^njπ







, j = 1, . . . , n.

Tali n uguaglianze possono essere riscritte come una unica uguaglianza matriciale (P 0 + P ₀ ^T )S = SD dove S `e la matrice

S ij =

r 2

n + 1 sin ijπ

n + 1 , i, j = 1, . . . , n,

e D `e la matrice diagonale con elementi diagonali D jj = 2 cos _n+1 ^jπ . Si noti che la matrice S, chiamata matrice seno, `e reale, simmetrica e unitaria (dimostrarlo!).

Osservazione. Sia F 2(n+1) la matrice di Fourier di ordine 2(n + 1). Allora la matrice seno S soddisfa la seguente relazione:

i I − F 2(n+1) ² F _2(n+1) =







0 0 ^T 0 0 ^T

0 S 0 −SJ

0 0 ^T 0 0 ^T

0 −JS 0 JSJ







(si noti che F _2(n+1) ² `e una matrice di permutazione). Come conseguenza, una trasformata seno pu` o essere calcolata effettuando una trasformata discreta di Fourier.

Quindi, le colonne della matrice seno S formano un sistema di autovettori unitariamente ortonormali per la matrice P 0 + P ₀ ^T . In altre parole, la matrice unitaria S diagonalizza P 0 + P ₀ ^T e, ovviamente, diagonalizza ogni polinomio in P 0 + P ₀ ^T , i.e. ogni matrice τ :

P 0 + P ₀ ^T = SDS, (P 0 + P ₀ ^T ) ^k = SD ^k S, τ = {p(P 0 + P ₀ ^T )} = { P n

k=1 a k (P 0 + P ₀ ^T ) ^k−1 : a k ∈ C} = {Sd(z)S : z ∈ C ⁿ }.

In particolare, `e evidente che la matrice di τ con prima riga a ^T `e τ (a) =

n

X

k=1

a k J k = Sd(S ^T a)d(S ^T e ₁ ) ⁻¹ S ⁻¹ .

Quest’ultima formula implica che prodotti matrice-vettore coinvolgenti matrici τ hanno complessit` a al pi` u O(n log ₂ n).

Proposizione PC. Data X ∈ C ^n×n generica, abbiamo {p(X)} ⊂ {A ∈ C ^n×n : AX = XA},

dim({p(X)}) ≤ n ≤ dim{A ∈ C ^n×n : AX = XA}

(7)

e se vale una identit` a allora vale anche l’altra identit` a. Quindi, X `e non derogatoria se e solo se dim({p(X)}) = n = dim{A ∈ C ^n×n : AX = XA}.

La Proposizione di cui sopra suggerisce la seguente ulteriore rappresentazione delo spazio τ :

τ = {A ∈ C ^n×n : A(P 0 + P ₀ ^T ) = (P 0 + P ₀ ^T )A}.

Il fatto che ogni matrice di τ deve commutare con P 0 + P ₀ ^T `e equivalente a richiedere che valgono le seguenti n ² condizioni di somma in croce:

a _i,j−1 + a i,j+1 = a _i−1,j + a i+1,j , i, j = 1, . . . , n

dove abbiamo posto a 0,j = a n+1,j = a i,0 = a i,n+1 = 0, i, j = 1, . . . , n. Possiamo usare tali condizioni per scrivere la generica matrice di τ la cui prima riga `e [a 1 a 2 · · · a n ]. Per esempio, per n = 4, possiamo dire che

τ (a) =







a 1 a 2 a 3 a 4

a 2 a 1 + a 3 a 2 + a 4 a 3

a 3 a 2 + a 4 a 1 + a 3 a 2

a 4 a 3 a 2 a 1







, J 1 = I, J 2 =







0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0





 ,

J 3 =







0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0





 , J 4 =







0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0







, J 2 −J ⁴ =







0 1 0 −1

1 0 0 0

0 0 0 1

−1 0 1 0





 ,

e cos`ı via.

Esercizio. Provare che per n pari la matrice J 2 `e invertibile, e, se possibile, calcolare l’inversa.

soluzione: Sappiamo che se J 2 `e invertibile, allora J ₂ ⁻¹ ∈ τ (dal fatto che J ² commuta con P 0 + P ₀ ^T segue che anche J ₂ ⁻¹ commuta con P 0 + P ₀ ^T !). Quindi J ₂ ⁻¹ = τ (z) per qualche z ∈ C ⁿ . Si noti che l’identit` a matriciale τ (z)J 2 = I

`e equivalente all’identit` a vettoriale z ^T J 2 = e ^T ₁ . Cos`ı, per esempio, per n = 4 abbiamo la condizione

[z 1 z 2 z 3 z 4 ]







0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0







= [1 0 0 0],

che implica z 1 = 0, z 2 = 1, z 3 = 0, z 4 = −1, e, quindi,

J ₂ ⁻¹ =







0 1 0 −1

1 0 0 0

0 0 0 1

−1 0 1 0







= J 3 − J ⁴ .

La dimostrazione per n = 6, 8, . . . `e lasciata al lettore.

Esercizio Ttau. Sia T una matrice di Toeplitz simmetrica n × n, i.e. T = (t _|i−j| ) ⁿ _i,j=1 , per certi t k ∈ C. Mostrare che T = A + B dove A `e una matrice τ di ordine n e

B =





0 0 0

0 R 0

0 0 0



 , R ∈ τ, R ∈ C (n−2)×(n−2) .

(8)

Esercizio. Scrivere matrici τ di rango uno (si provi inizialmente per n = 2, n = 3, n = 4, n = 5, n = 6, . . .)

Algebre di Hessenberg

Sia X la seguente matrice di Hessenberg inferiore 3 × 3

X =





a 11 b 1 0 a 21 a 22 b 2

a 31 a 32 a 33



 .

Mostriamo adesso che lo spazio di tutti i polinomi in X `e generato da tre matrici J 1 , J 2 , J 3 tali che e ^T ₁ J k = e ^T _k , k = 1, 2, 3, a condizione che X ii+1 6= 0, i = 1, 2.

Come J 1 prendiamo la matrice identica, J 1 = X ⁰ = I. Definiamo J 2 :

X − a 11 I =





0 b 1 0

a 21 a 22 − a 11 b 2

a 31 a 32 a 33 − a 11



 , b 1 6= 0 ⇒

J 2 = 1

b 1 (X − a ¹¹ I) =





0 1 0

a 21 /b 1 (a 22 − a ¹¹ )/b 1 b 2 /b 1

a 31 /b 1 a 32 /b 1 (a 33 − a ¹¹ )/b 1



 .

Si noti che e ^T ₁ J 2 = e ^T ₂ . Poi, definiamo J 3 :

J ₂ ² =





a 22 /b 1 (a 22 − a ¹¹ )/b 1 b 2 /b 1 

 , b 2 6= 0 ⇒

J 3 = b 1

b 2

(J ₂ ² − a 22

b 1 I − a 22 − a ¹¹ b 1

J 2 ).

Si noti che e ^T ₁ J 3 = e ^T ₃ . Infine, il teorema di Cailey-Hamilton implica la tesi, {p(X)} = Span {J 1 , J 2 , J 3 }.

La seguente Proposizione generalizza a un generico n le osservazioni di cui sopra. Per una dimostrazione dettagliata si veda [].

Proposizione. Sia X una matrice di Hessenberg inferiore n × n. Allora lo spazio H X di tutti i polinomi in X

H X = {

n

X

k=1

α k X ^k−1 : α k ∈ C}

è generato da n matrici J 1 , . . . , J n tali che e ^T ₁ J k = e ^T _k , k = 1, . . . , n, a condizione che X ii+1 6= 0, i = 1, . . . , n−1; in tal caso, H ^X è chiamato algebra di Hessenberg, e per ogni a ∈ C ⁿ c’è una unica matrice in H X con prima riga a ^T , denotata H X (a), i.e. H X (a) = P

k a k J k .

Ovviamente, per la Proposizione PC, ogni algebra di Hessenberg H X am- mette anche la seguente rappresentazione

H X = {A ∈ C ^n×n : AX = XA}.

(9)

Finora abbiamo visto due esempi di algebre di Hessenberg, le ξ-circolanti ξ 6= 0 (X = P ξ ) e le matrici tau (X = P 0 + P ₀ ^T ). Entrambe possono essere simultaneamente diagonalizzate da una opportuna matrice. Un esempio di algebra di Hessenberg le cui matrici non possono essere simultaneamente diagonalizzate `e H P

0

, lo spazio di tutte le matrici triangolari superiori di Toeplitz.

La matrice H P

0

(a) `e riportata qui sotto

H P

0

(a) =







a 1 a 2 a n

a 1 a 2

. .. ...

. .. a 2

a 1





 .

La stessa matrice P 0 , i.e. la matrice generante lo spazio, non `e diagonalizzabile.

(Vedremo, tuttavia, che H P

0

pu` o essere immersa nello spazio delle matrici circolanti 2n × 2n, che sono diagonalizzabili).

Si noti che quando X = P 0 o, pi` u in generale, quando X = P ξ , le matrici J k

sono semplicemente le potenze di X, i.e. J k = X ^k−1 . Per esempio, per n = 3

J 1 = I, J 2 = X =





0 1 0 0 0 1 ξ 0 0



 , J 3 = X ² =





0 0 1 ξ 0 0 0 ξ 0



 .

Le algebre di Hessenberg costituiscono una sottoclasse di algebre di matrici commutative della classe degli spazi-1 definiti qui sotto

Definizione. L ⊂ C ^n×n si dice spazio-1 se L = Span {J 1 , . . . , n} con J k tali che e ^T ₁ J k = e ^T _k , k = 1, . . . , n.

Ecco un esempio di spazio-1 L che non `e un’algebra di Hessenberg:

L = {

A JB

JB A

: A, B n 2 × n

2 circolanti}.

Si pu` o facilmente provare che L è un’algebra non commutativa. Un esempio di spazio-1 che non è un’algebra di matrici è l’insieme di tutte le matrici di Toeplitz simmetriche n × n (vedi la prossima sezione).

Sistemi lineari di Toeplitz e decomposizioni di dislocamento

Una matrice n × n di Toeplitz `e una matrice della forma T = (t i−j ) ⁿ _i,j=1 . Nelle applicazioni spesso occorre risolvere sistemi lineari di Toeplitz T x = b.

Ecco qui di seguito una matrice 3 × 3 di Toeplitz:

T =





t 0 t ₋₁ t ₋₂ t 1 t 0 t ₋₁ t 2 t 1 t 0



 .

Un esempio di matrice di Toeplitz T `e la matrice dei coefficienti del sistema

lineare derivante dalla risoluzione, col metodo delle differenze finite o degli el-

ementi finiti, il problema differenziale con valori al bordo −u ^” = f , u(a) = α,

u(b) = β. In tal caso T `e simmetrica e la sua prima riga `e [2 − 1 0 · · · 0]. Un

(10)

altro esempio, importante nella probabilit` a applicata, `e T = (t ^|i−j| ) ⁿ _i,j=1 con |t|

(t ∈ C) minore di 1.

Esercizio. Lo spazio vettoriale di tutte le matrici di Toeplitz simmetriche n × n

`e uno spazio-1, essendo (t _|i−j| ) ⁿ _i,j=1 uguale alla somma P n

k=1 t _k−1 J k dove le J k

sono le matrici simmetriche di Toeplitz con prima riga e ^T _k . Si dimostri che tale spazio-1 non `e un’algebra di matrici.

Nell’ambito della teoria di dislocamento `e possibile ottenere alcune decomposizioni di T ⁻¹ coinvolgenti matrici di algebre di Hessenberg (o di pi` u generali spazi-h commutativi) del tipo

T ⁻¹ =

α

X

k=1

M k N k , 2 ≤ α ≤ 4.

Di solito, le matrici M k e N k , che appaiono in tali formule, possono essere moltiplicate per un vettore con al pi` u O(n log 2 n) operazioni aritmetiche; come conseguenza si ottengono veloci risolutori diretti di sistemi lineari di Toeplitz.

Qui sotto c’`e un esempio di tali formule:

T ⁻¹ = L 1 U 1 + L 2 U 2 . (GS) Le L j e U j sono opportune matrici triangolari di Toeplitz, inferiori e superiori, cio`e elementi o trasposte di elementi dell’algebra di Hessenberg H P

0

.

Osservazione. Per la formula di Gohberg-Semencul (GS), se le matrici L j e U j

sono note (un modo per ottenerle `e indicato in []), allora il prodotto matrice- vettore T ⁻¹ b pu` o essere calcolato con al pi` u O(n log ₂ n) operazioni aritmetiche.

Quindi, non contando la pre-elaborazione su T , la complessit` a del problema della risoluzione di un qualsiasi sistema di Toeplitz T x = b `e al pi` u O(n log ₂ n).

dimostrazione: è sufficiente provare che una qualsiasi matrice di Toeplitz (in particolare una triangolare) pu` o essere moltiplicata per un vettore effettuando un numero finito di trasformate discrete di Fourier. Quest’ultimo risultato è immediato se osserviamo che una qualsiasi matrice n × n di Toeplitz può essere immersa in una matrice circolante (2n + k) × (2n + k), k ≥ 0; per esempio, se n = 3 abbiamo

T =





t 0 t ₋₁ t ₋₂ t 1 t 0 t ₋₁ t 2 t 1 t 0



 , C =







t 0 t ₋₁ t ₋₂ t 2 t 1

t 1 t 0 t ₋₁ t ₋₂ t 2

t 2 t 1 t 0 t ₋₁ t ₋₂ t 2 t 1 t 0 t ₋₁ t ₋₂ t ₋₂ t 2 t 1 t 0 t ₋₁ t ₋₁ t ₋₂ t 2 t 1 t 0







(k = 0). ` E evidente che il vettore T · z `e la prima parte del vettore C

z 0

.

La rappresentazione (GS) di cui sopra per l’inversa di una matrice di Toeplitz,

che pu` o essere molto utile per risolvere efficientemente sistemi lineari di Toeplitz

[], segue dalla decomposizione di dislocamento stabilita nel seguente teorema

Teorema DD. Sia X una matrice di Hessenberg n × n. Si supponga che X ^ij =

X i+1,j+1 , i, j = 1, . . . , n − 1 (X ha struttura di Toeplitz), e che b = X ⁱⁱ⁺¹ 6= 0,

(11)

e si consideri l’algebra (commutativa) di Hessenberg H X generata da X (si noti che H X `e uno spazio-1).

Si supponga che A ∈ C ^n×n `e tale che AX − XA = P α

m=1 x _m y ^T _m . Allora bA = −

α

X

m=1

H P

0

(˜ x _m ) ^T H X (y m ) + bH X (A ^T e ₁ ) (DD)

dove, per z ∈ C ⁿ , H P

0

(z) è la matrice triangolare superiore di Toeplitz con prima riga z ^T , H X (z) è la matrice di H X con prima riga z ^T , e ˜ z è il vettore [0 z 1 · · · z n−1 ] ^T .

Nota: Oltre DD valgono diverse altre decomposizioni di dislocamento, di carat- tere generale come DD, cioè rappresentanti generiche matrici A, oppure special- izzate per matrici A centrosimmetriche (vedi []). Tali decomposizioni permet- tono di ottenere formule per l’inversa di matrici Toeplitz, Toeplitz pi` u Hankel, e tipo Toeplitz pi` u Hankel, utili per risolvere sistemi lineari di tipo Toeplitz pi` u Hankel. Si ricorda che una matrice di Hankel non è altro che una matrice della forma JT dove T è Toeplitz (la ben nota matrice di Hilbert è un esempio di matrice di Hankel).

Per dimostrare il Teorema DD, `e fondamentale il seguente Lemma.

Lemma []. Sia L uno spazio-1 commutativo di matrici n×n, cio`e L = { P

k α k J k : α k ∈ C}, con J k ∈ C ^n×n tali che e ^T ₁ J k = e ^T _k , J k J s = J s J k . Sia X un elemento di L, e si supponga che A ∈ C ^n×n sia tale che AX − XA = xy ^T . Allora x ^T L(y) ^T = 0 ^T .

dimostrazione: si noti che l’uguaglianza J k J s = J s J k implica e ^T ₁ J k J s = e ^T ₁ J s J k , e ^T _k J s = e ^T _s J k ∀ s, k, quindi

x ^T L(y) ^T e _r = x ^T ( P

k y k J k ) ^T e _r = x ^T P

k y k J _k ^T e _r

= x ^T P

k y k J _r ^T e _k = x ^T J _r ^T P

k y k e _k

= x ^T J _r ^T y = P

i,j x i y j [J _r ^T ] ij

= P

i,j x i y j [J r ] ji = P

i,j [AX − XA] ij [J r ] ji

= P

i [(AX − XA)J r ] ii = P

i [(AJ r )X − X(AJ r )] ii

= tr ((AJ r )X) − tr (X(AJ r )) = 0

(si ricorda che le due matrici M N e N M , M, N ∈ C ^n×n , hanno lo stesso polinomio caratteristico, anche se pu` o accadere (nel caso det(M ) = det(N ) = 0) che M N e N M non siano simili tra loro).

Riportiamo adesso una bozza della dimostrazione del Teorema DD (per una dimostrazione pi` u dettagliata vedi []). Per ottenere l’identit` a (DD), che `e del tipo

bA = E + bH X (A ^T e ₁ ),

`e sufficiente mostrare l’uguaglianza

EX − XE = (bA)X − X(bA), (∗ ∗ ∗)

e osservare che la prima riga di E `e nulla. Infatti, l’uguaglianza di cui sopra implica (bA−E)X −X(bA−E) = 0, e quindi ci permette di concludere che bA−

E ∈ H X . Il Lemma, applicato per L = H X , `e fondamentale nella dimostrazione

di (***).

(12)

Una algebra di matrici che non `e uno spazio-1: la classe degli spazi in V Ricordiamo che una matrice A si dice simmetrica se A ^T = A (a ji = a ij ), antisimmetrica se A ^T = −A (a ^ji = −a ^ij ) e persimmetrica se A ^T = JAJ (a ji = a n+1−i,n+1−j ).

Si consideri una matrice 6 × 6 (−1)-circolante simmetrica A ∈ C ₋₁ ^S ,

A =







a 0 a 1 a 2 0 −a 2 −a 1

a 1 a 0 a 1 a 2 0 −a ² a 2 a 1 a 0 a 1 a 2 0

0 a 2 a 1 a 0 a 1 a 2

−a ² 0 a 2 a 1 a 0 a 1

−a ¹ −a ² 0 a 2 a 1 a 0





 ,

una matrice 6 × 6 (−1)-circolante antisimmetrica B ∈ C ₋₁ ^SK , e la matrice JB,

B =







0 b 1 b 2 b 3 b 2 b 1

−b ¹ 0 b 1 b 2 b 3 b 2

−b ² −b ¹ 0 b 1 b 2 b 3

−b 3 −b 2 −b 1 0 b 1 b 2

−b 2 −b 3 −b 2 −b 1 0 b 1

−b 1 −b 2 −b 3 −b 2 −b 1 0





 , JB =







−b ¹ −b ² −b ³ −b ² −b ¹ 0

−b ² −b ³ −b ² −b ¹ 0 b 1

−b ³ −b ² −b ¹ 0 b 1 b 2

−b 2 −b 1 0 b 1 b 2 b 3

−b 1 0 b 1 b 2 b 3 b 2

0 b 1 b 2 b 3 b 2 b 1





 .

Lo spazio vettoriale γ di tutte le matrici del tipo A + JB ha dimensione uguale a 6 (si usi la formula dim(A + JB) = dim(A) + dim(JB) − dim(A ∩ JB)).

Mostriamo adesso che non esiste una base {J ^k } di γ tale che e ^T 1 J k = e ^T _k , k = 1, 2, 3, 4, 5, 6, cio`e mostriamo che γ non `e uno spazio-1. Si noti che

e ^T ₁ (A + JB) = [(a 0 − b 1 )(a 1 − b 2 )(a 2 − b 3 )(−b 2 )(−a 2 − b 1 )(−a 1 )], quindi, l’uguaglianza e ^T ₁ (A + JB) = e ^T ₂ `e soddisfatta se e solo se

a 0 − b ¹ = 0, a 1 − b ² = 1, a 2 − b ³ = 0, −b ² = 0, −a ² − b ¹ = 0, −a ¹ = 0.

Poich´e devono essere verificate entrambe le condizioni b 2 = 0 e b 2 = −1, non pu` o esistere una matrice J 2 ∈ γ tale che e ^T 1 J 2 = e ^T ₂ .

Tuttavia, esiste una base {J ^k } di γ che soddisfa le identit`a (e ¹ +e 6 ) ^T J k = e ^T _k , k = 1, 2, 3, 4, 5, 6. Per esempio, una matrice J 2 ∈ γ con la propriet`a (e ¹ + e ₆ ) ^T J 2 = e ^T ₂ si ottiene come segue. Si noti che

e ^T ₆ (A + JB) = [(−a ¹ )(−a ² + b 1 )(b 2 )(a 2 + b 3 )(a 1 + b 2 )(a 0 + b 1 )], quindi, per la somma della prima e della sesta riga di A + JB, otteniamo la formula

(e 1 + e 6 ) ^T (A + JB)

= [(a 0 − b 1 − a 1 )(a 1 − b 2 − a 2 + b 1 )(a 2 − b 3 + b 2 )(−b 2 + a 2 + b 3 )(−a 2 − b 1 + a 1 + b 2 )(−a 1 + a 0 + b 1 )].

Ne segue che la condizione (e 1 + e 6 ) ^T (A + JB) = e ^T ₂ `e soddisfatta se e solo se il seguente sistema di equazioni lineari ha soluzione

a 0 − b 1 − a 1 = 0, a 1 − b 2 − a 2 + b 1 = 1, a 2 − b 3 + b 2 = 0, −b 2 + a 2 + b 3 = 0,

−a 2 − b 1 + a 1 + b 2 = 0, −a 1 + a 0 + b 1 = 0,

(13)

e tale sistema ha l’unica soluzione a 0 = a 1 = ¹ ₂ , a 2 = 0, b 2 = b 3 = − ¹ ₂ , b 1 = 0.

La matrice J 2 ∈ γ tale che (e 1 + e 6 ) ^T J 2 = e ^T ₂ `e riportata qui di seguito:

J 2 =







1 2 1 ¹ ₂ ¹ ₂ 0 − ¹ 2

1 1 1 0 0 0

1 2 1 ¹ ₂ ¹ ₂ 0 − ¹ 2 1

2 0 ¹ ₂ ¹ ₂ 0 − ¹ 2

0 0 0 0 0 0

− ¹ 2 0 − ¹ 2 − ¹ 2 0 ¹ ₂





 .

Analogamente si ottengono le altre matrici J k , per cui (e 1 + e 6 ) ^T J k = e ^T _k :

J 1 =







1 ¹ ₂ ¹ ₂ ¹ ₂ ¹ ₂ 0

1 2 1 ¹ ₂ ¹ ₂ 0 − ¹ 2 1

2 1

2 1 0 − ¹ 2 − ¹ 2 1

2 1

2 0 0 − ¹ 2 − ¹ 2 1

2 0 − ¹ 2 − ¹ 2 0 − ¹ 2

0 − 2 ¹ − ¹ 2 − ¹ 2 − ¹ 2 0





 , J 3 =







1 2

1 2 1 0 − ¹ 2 − ¹ 2 1

2 1 ¹ ₂ ¹ ₂ 0 − ¹ 2

1 ¹ ₂ ¹ ₂ ¹ ₂ ¹ ₂ 0 0 ¹ ₂ ¹ ₂ ¹ ₂ ¹ ₂ 0

− ¹ 2 0 ¹ ₂ ¹ ₂ 0 ¹ ₂

− ¹ 2 − ¹ 2 0 0 ¹ ₂ ¹ ₂





 ,

(a 1 = a 2 = 0, a 0 = ¹ ₂ , b 2 = b 3 = − ¹ ₂ , b 1 = − ¹ ₂ ), (a 0 = a 1 = a 2 = ¹ ₂ , b 1 = b 2 = 0, b 3 = − ¹ 2 ),

J 4 =







1 2

1 2 0 0 − ¹ 2 − ¹ 2 1

2 0 ¹ ₂ ¹ ₂ 0 − ¹ 2

0 ¹ ₂ ¹ ₂ ¹ ₂ ¹ ₂ 0 0 ¹ ₂ ¹ ₂ ¹ ₂ ¹ ₂ 1

− ¹ 2 0 ¹ ₂ ¹ ₂ 1 ¹ ₂

− ¹ 2 − ¹ 2 0 1 ¹ ₂ ¹ ₂





 , J 5 =







1 2 0 − ¹ 2 − ¹ 2 0 − ¹ 2

0 0 0 0 0 0

− ¹ 2 0 ¹ ₂ ¹ ₂ 0 ¹ ₂

− ¹ 2 0 ¹ ₂ ¹ ₂ 1 ¹ ₂

0 0 0 1 1 1

− ¹ 2 0 ¹ ₂ ¹ ₂ 1 ¹ ₂





 ,

(a 0 = a 1 = a 2 = ¹ ₂ , b 1 = b 2 = 0, b 3 = ¹ ₂ ), (a 0 = a 1 = ¹ ₂ , a 2 = 0, b 2 = b 3 = ¹ ₂ , b 1 = 0),

J 6 =







0 − ¹ 2 − ¹ 2 − ¹ 2 − ¹ 2 0

− 2 ¹ 0 − ¹ 2 − ¹ 2 0 ¹ ₂

− 2 ¹ − ¹ 2 0 0 ¹ ₂ ¹ ₂

− 2 ¹ − ¹ 2 0 1 ¹ ₂ ¹ ₂

− 2 ¹ 0 ¹ ₂ ¹ ₂ 1 ¹ ₂ 0 ¹ ₂ ¹ ₂ ¹ ₂ ¹ ₂ 1





 .

(a 1 = a 2 = 0, a 0 = ¹ ₂ , b 1 = b 2 = b 3 = ¹ ₂ ).

Ovviamente si ha γ = Span {J 1 , J 2 , J 3 , J 4 , J 5 , J 6 } (le J k sono linearmente indipendenti!). La matrice P

k a k J k viene indicata con il simbolo γ(a). Si noti che (e 1 + e 6 ) ^T γ(a) = a ^T , per questo γ(a) `e chiamata la matrice di γ la cui (e 1 + e 6 )-riga `e a ^T .

Pi` u in generale, si pu` o facilmente dimostrare che l’insieme γ = C ₋₁ ^S + JC ₋₁ ^SK ,

C ₋₁ ^S n × n (−1)-circolanti simmetriche, C ₋₁ ^SK n × n (−1)-circolanti antisim-

metriche, `e uno spazio vettoriale di dimensione n, ed `e una algebra di ma-

trici commutativa. Inoltre, `e uno spazio-1 se e solo se n `e uno degli interi

{3, 4, 5, 7, 8, 9, 11, 12, 13, 15, . . .}; per i rimanenti valori di n, cio`e per n = 2 + 4s,

s ∈ N, nessuna riga di una matrice A + JB di γ determina A + JB, in altre

parole, non c’`e nessun indice h per cui esiste una base {J k } di γ con la propriet`a

e ^T _h J k = e ^T _k . Invece, per ogni n la somma della prima e della n-esima riga di

(14)

A + JB determina A + JB, cio`e esiste una base {J k } di γ con la propriet`a (e 1 + e n ) ^T J k = e ^T _k .

Le matrici di γ possono essere simultaneamente diagonalizzate da una trasformata discreta veloce. Pi` u precisamente, per ogni valore di n vale la seguente identit` a:

γ = {Gd(z)G ⁻¹ : z ∈ C ⁿ }, G ij = ^√ ¹ _n

cos (2i−1)(2j−1)π

2n + sin (2i−1)(2j−1)π 2n

, i, j = 1, . . . , n

(vedi []). Si noti che la matrice G `e reale, simmetrica, persimmetrica e unitaria.

Il fatto che il prodotto matrice-vettore Gz possa essere calcolato con al pi` u O(n log ₂ n) operazioni aritmetiche segue dalla rappresentazione di G n , G n := G, stabilita nell’Esercizio G.

Si noti che per n = 6 la matrice G ha dieci zeri tra i suoi elementi, e che tali zeri sono posizionati come in figura:

G =







0 0 0 0

0 0

0 0 0

0 



 .

Quindi ciascuno dei vettori G ^T e _k , k = 1, . . . , 6, ha almeno un elemento nullo, cioè la matrice d(G ^T e _k ) ⁻¹ non è mai ben definita. Quest’ultima affermazione è vera ogni volta che n è del tipo n = 2 + 4s, s ∈ N. In altre parole, γ può essere rappresentata come

γ = {Gd(G ^T z)d(G ^T e _k ) ⁻¹ G ⁻¹ : z ∈ C ⁿ }.

se e solo se n 6= 2 + 4s, s ∈ N (per tali n si pu`o scegliere k = 1). Tuttavia, come si pu` o indovinare dalla discussione di cui sopra (dettagliata, per n = 6), si pu` o facilmente mostrare che [G ^T (e 1 + e n )] k 6= 0 ∀ k e ∀ n. Quindi, abbiamo la seguente rappresentazione per γ

γ = {Gd(G ^T z)d(G ^T (e 1 + e n )) ⁻¹ G ⁻¹ : z ∈ C ⁿ }

valida per tutti gli n (anche per n = 2 + 4s, s ∈ N, caso in cui le d(G ^T e k ) non sono invertibili). Quest’ultima formula conferma il fatto che la generica matrice di γ è univocamente determinata dalla somma delle sua prima riga e della sua n-esima riga; in particolare, poiché la somma della prima e della n-esima riga della matrice Gd(G ^T a)d(G ^T (e 1 + e n )) ⁻¹ G ⁻¹ è uguale ad a ^T , possiamo dire che tale matrice è esattamente la matrice γ(a) (gi` a definita sopra per n = 6), i.e. la matrice di γ la cui (e 1 + e n )-riga è a ^T .

E ora naturale introdurre una classe di spazi che includono (oltre gli spazi-1, ` come le algebre di Hessenberg) anche spazi tipo l’algebra γ.

Definizione. Un sottoinsieme L di C ^n×n si dice spazio di V, se L = Span {J 1 , . . . , J n } con v ^T J k = e ^T _k per qualche vettore v ∈ C ⁿ . Dato z ∈ C ⁿ , la matrice P

k z k J k ∈ L viene indicata con il simbolo L(z). Poich´e v ^T L(z) = z ^T , L(z) `e

chiamata la matrice di L la cui v-riga `e z ^T .

(15)

Esempio. L = sd M = {Md(z)M ⁻¹ : z ∈ C ⁿ } `e in V poich´e

L = Span {J 1 , . . . , J n }, J k = M d(M ^T e _k )d(M ^T v) ⁻¹ M ⁻¹ , per ogni vettore v tale che [M ^T v] i 6= 0 ∀ i, e

v ^T J k = v ^T M d(M ^T e _k )d(M ^T v) ⁻¹ M ⁻¹ = e ^T _k M d(M ^T v)d(M ^T v) ⁻¹ M ⁻¹ = e ^T _k . Si noti che L(z) = Md(M ^T z)d(M ^T v) ⁻¹ M ⁻¹ .

Una matrice X ∈ C ^n×n si dice non derogatoria se la condizione p(X) = 0, p polinomio, implica ∂p ≥ n. Si noti che per il teorema di Cailey-Hamilton il polinomio caratteristico di X è nullo in X. Quindi, X è non derogatoria se e solo se l’insieme {p(X)} di tutti i polinomi in X ha dimensione n. In [] si stabilisce il seguente risultato, da cui segue che V è un’ampia classe di spazi di matrici.

Teorema ND. Sia X una matrice n × n con elementi in C. Allora X `e non derogatoria se e solo se {p(X)} := {p(X) : p polinomi} appartiene a V.

La Proposizione qui di seguito elenca diverse propriet` a degli spazi di V. Esse saranno utilizzate (nella prossima sezione) per dimostrare importanti propriet` a della migliore approssimazione nel senso dei minimi quadrati in L di una matrice A, valide per tutti gli spazi L di una particolare sottoclasse di V.

Proposizione V (propriet` a degli spazi di V). Sia L uno spazio in V, i.e. L = Span {J 1 , . . . , J n } con v ^T J k = e ^T _k per qualche v ∈ C ⁿ .

(1) Se X ∈ L e v ^T X = 0 ^T , allora X = 0, quindi v ^T X = v ^T Y , X, Y ∈ L, implica X = Y

dimostrazione: 0 ^T = v ^T X = v ^T P

k α k J k = P

k α k e ^T _k = [α 1 · · · α n ] ⇒ α k = 0

∀ k.

(2) Se J i X ∈ L, X ∈ C ^n×n , allora J i X = P

k [X] ik J k

dimostrazione: esistono α k tali che J i X = P

k α k J k ; moltiplicando quest’ultima identit` a per v ^T abbiamo le uguaglianze

e ^T _i X = v ^T J i X = X

k

α k e ^T _k = [α 1 · · · α ⁿ ]

che implicano α k = [X] ik .

(3) Siano P k ∈ C ^n×n le matrici definite dalle identit` a e ^T _s P k = e ^T _k J s (si noti che e ^T _k = v ^T J k = P

i v i e ^T _i J k = P

i v i e ^T _k P i = e ^T _k P

i v i P i , quindi P v k P k = I).

Allora le seguenti affermazioni sono equivalenti:

(i) L `e chiuso rispetto alla moltiplicazione tra matrici (ii) J i J j = P

k [J j ] ik J k ∀ i, j (iii) P r J j = J j P r ∀ r, j (iv) P k P r = P

i [P r ] ki P i

dimostrazione: L’implicazione (i) ⇒ (ii) segue da (2) per X = J ^j . L’implicazione nell’altro senso `e ovvia. Il fatto che le condizioni (ii) e (iii) sono equivalenti segue prendendo l’elemento (r, s) dell’uguaglianza in (ii):

e ^T _i P r J j e _s = e ^T _r J i J j e _s = X

k

[J j ] ik [J k ] rs = X

k

[J j ] ik [P r ] ks = [J j P r ] is .

(16)

Il fatto che le condizioni (iii) e (iv) sono equivalenti segue dalle identit` a:

[P k P r ] ms = [J m P r ] ks = [P r J m ] ks = [J k J m ] rs = X

i

[J k ] ri [J m ] is = X

i

[P r ] ki [P i ] ms .

(3.5) Se I ∈ L, allora P

i v i J i = I e v ^T P k = e ^T _k , i.e. anche lo spazio Span {P 1 , . . . , P n } `e in V (con lo stesso v)

dimostrazione: sia I che P

i v i J i hanno v ^T come v-riga, ed entrambi, per ipotesi, sono matrici di L, quindi esse devono essere uguali; inoltre, abbiamo

v ^T P k = X

i

v i e ^T _i P k = X

i

v i e ^T _k J i = e ^T _k X

i

v i J i = e ^T _k .

(4) Se L `e chiuso rispetto alla moltiplicazione tra matrici, allora L(L(z) ^T z ⁰ ) = L(z ⁰ )L(z), ∀ z, z ⁰ ∈ C ⁿ

dimostrazione: poiché L è chiuso, la matrice L(z ⁰ )L(z) è in L; inoltre, la sua v-riga è z ^0T L(z); la tesi segue dal fatto che anche L(L(z) ^T z ⁰ ) è la matrice di L la cui v-riga è z ^0T L(z).

(5) Si supponga I ∈ L e L chiuso rispetto alla moltiplicazione tra matrici.

Allora X ∈ L `e non singolare se e solo se ∃ z ∈ C ⁿ tale che z ^T X = v ^T ; in questo caso X ⁻¹ = L(z)

dimostrazione: evidenziando la k-esima riga della matrice L(z)X, e applicando le propriet` a (3) e (3.5), otteniamo le identit` a

e ^T _k L(z)X = e ^T k

X

s

z s J s X = X

s

z s e ^T _s P k X = z ^T P k X = z ^T XP k = v ^T P k = e ^T _k ,

o, equivalentemente, l’identit` a L(z)X = I, la quale implica che X `e non singolare e X ⁻¹ = L(z).

La migliore approssimazione nel senso dei minimi quadrati di A in L ⊂ C ^n×n Dato un sottospazio L ⊂ C ^n×n e una matrice n × n A, è ben definita L Â , la proiezione su L di A. Nel seguente teorema stabiliamo alcune ipotesi su L (in particolare consideriamo sottospazi di C ^n×n n-dimensionali) che assicurano che L Â è hermitiana ogni volta che lo è A, e che gli autovalori di L Â sono limitati da quelli di A. Vedremo che in tali ipotesi L deve essere necessariamente in V.

Teorema L ^A . Ipotesi:

L ⊂ C ^n×n , I ∈ L, L = Span {J ¹ , . . . , J n } con J ^k tali che

J _i ^H J j =

n

X

k=1

[J k ] ij J k , i, j = 1, . . . , n. (∗)

A ∈ C ^n×n .

L A ∈ L, kA − L A k F ≤ kA − Xk F , ∀ X ∈ L (tale matrice L A è ben definita perché C ^n×n è uno spazio di Hilbert rispetto alla norma k · k F indotta dal prodotto scalare (A, B) F = P

ij a ij b ij e L `e un sottospazio di C ^n×n ).

Tesi: Se A = A ^H , allora L A = L ^H A e min λ(A) ≤ λ(L A ) ≤ max λ(A).

(17)

Nota: se A è reale simmetrica, allora L A è in generale hermitiana; essa è reale simmetrica nell’ulteriore ipotesi che L sia generata da matrici reali (dimostrarlo!).

Nota: vedremo che le ipotesi del Teorema L ^A sono soddisfatte in particolare da spazi del tipo {Md(z)M ⁻¹ : z ∈ C ⁿ } se la matrice M ^H M `e diagonale e i suoi elementi diagonali sono positivi; tuttavia, le stesse ipotesi possono essere soddisfatte anche da spazi non commutativi (ne vedremo un esempio, per altri si veda []), quindi anche per questi ultimi spazi possiamo dire che valgono le conclusioni del Teorema L A .

Applicazioni del Teorema L Â . Se le condizioni del Teorema L Â sono soddisfatte, allora L Â è definita positiva (i.e. L Â = L ^H A e z ∈ C ⁿ z 6= 0 ⇒ z ^H L Â z positivo) ogni volta che lo è A. Quindi, per risolvere il sistema lineare

Ax = b, A definita positiva si pu` o risolvere il sistema equivalente

L ⁻¹ A Ax = L ⁻¹ A b

la cui matrice dei coefficienti ha autovalori reali e positivi che spesso sono meglio distribuiti di quelli di A (ci` o risulta, per esempio, in una maggiore velocit` a di convergenza dei risolutori iterativi di sistemi lineari). Inoltre, se le condizioni del Teorema L A sono soddisfatte e L è generato da matrici reali, allora L A è definita positiva reale (i.e. L Â = L ^T A , L Â ∈ R ^n×n , e z ∈ C ⁿ z 6= 0 ⇒ z ^H L Â z positivo) ogni volta che lo è A. In altre parole, valgono le seguenti implicazioni

B k definita positiva reale ⇒ L ^B

k

definita positiva reale ⇒

ϕ(L ^B

k

, s k , y k ) definita positiva reale ⇒ L ϕ(L

Bk

,s

k

,y

k

) definita positiva reale

(a patto che s ^T _k y k sia positivo), e di conseguenza entrambe le seguenti S e NS LQN direzioni di ricerca

d k+1 = −ϕ(L ^B

k

, s k , y k ) ⁻¹ ∇f(x ^k+1 ) d k+1 = −L ⁻¹ _ϕ(L

_Bk

,s

k

,y

k

) ∇f(x ^k+1 ), sono direzioni di discesa in x k+1 , per la funzione f : R ⁿ → R, ben definite (si veda [] per le definizioni di B k , s k , y k , ϕ, S e NS LQN).

dimostrazione (del Teorema L A ): La matrice L A = P

s α s J s `e definita univocamente dalla seguente condizione

(X, A − L A ) F = 0, X ∈ L o, equivalentemente, dalle n condizioni (J k , A − P

s α s J s ) F = 0, k = 1, . . . , n, che possono essere riscritte come segue

n

X

s=1

(J k , J s ) F α s = (J k , A) F , k = 1, . . . , n.

In altre parole, vale la seguente formula L ^A = X

s

[B ⁻¹ c] s J s , B ks = (J k , J s ) F , c k = (J k , A) F , k, s = 1, . . . , n.

(18)

Osservazione. B `e definita positiva, i.e. B = B ^∗ e z ^H Bz > 0 ∀ z ∈ C ⁿ z 6= 0.

dimostrazione: B ks = (J k , J s ) F = (J s , J k ) F = B sk , cioè, B è una matrice hermitiana. Inoltre, poiché 0 < ( P

s z s J s , P

s z s J s ) F = P

k,s z k z s (J k , J s ) F = z ^H Bz ogni volta che z 6= 0, abbiamo la tesi.

Osservazione. Siano v k ∈ C tale che I = P

k v k J k (tali v k esistono perch´e I ∈ L).

Allora il vettore v i cui elementi sono i v k soddisfa le identit` a v ^T J k = e ^T _k , quindi L ∈ V e tutti i risultati stabiliti per gli spazi di V valgono per il nostro spazio L.

dimostrazione: Si moltiplichi (*) per v i e si sommi su i l’identit` a ottenuta.

Allora si ha

v i J _i ^H J j = X

k

v i [J k ] ij J k , J j = X

k

( X

i

v i [J k ] ij )J k = X

k

(v ^H J k e _j )J k

e questo implica v ^H J k e j = 0 se k 6= j e v ^H J k e j = 1 se k = j, i.e. v ^T J k = e ^T _k . Come immediata conseguenza delle due osservazioni di cui sopra, abbiamo che L A `e la matrice di L la cui v-riga `e (B ⁻¹ c) ^T ,

L ^A = X

s

[B ⁻¹ c ] s J s = L(B ⁻¹ c ),

e, inoltre,

L ^A = L(B ⁻¹ c ) = L((B ^H ) ⁻¹ c ) = L((B ⁻¹ ) ^T c ).

Osservazione. L `e chiuso per trasposizione coniugata.

dimostrazione: si moltiplichi (*) per v j e si sommi su j l’identit` a ottenuta:

J _i ^H v j J j = X

k

v j [J k ] ij J k , J _i ^H = X

k

( X

j

v j [J k ] ij )J k ⇒ J i ^H ∈ L.

Quest’ultima osservazione consente di ottenere parte della tesi del Teorema L A , perch´e essa implica che L ^H A ∈ L, e questo fatto, assieme alle uguaglianze

kA − L A k F = kA ^H − L ^H A k F = kA − L ^H A k F

(A è hermitiana!) e all’unicit` a della migliore approssimazione di A, conducono all’identit` a L Â = L ^H A . In altre parole, nelle nostre condizioni su L la proiezione su L di una matrice hermitiana è hermitiana.

Osservazione. L `e chiuso rispetto alla moltiplicazione tra matrici (L `e una algebra di matrici).

dimostrazione: l’insieme {J i ^H } forma una base alternativa per L (dimostrarlo!), quindi esistono z _i ^(s) ∈ C tali che J ^s = P

i z _i ^(s) J _i ^H . Si moltiplichi (*) per z _i ^(s) e si sommi su i l’identit` a ottenuta,

z _i ^(s) J _i ^H J j = X

k

z _i ^(s) [J k ] ij J k , J s J j = X

k

( X

i

z ^(s) _i [J k ] ij )J k ,

per osservare che J s J j ∈ L.

Osservazione. B = P

k tr (J k )J k , quindi B ∈ L, e, poiché B è non singolare (è

definita positiva!), per il risultato V (5) anche la matrice B ⁻¹ appartiene ad L.

La matrice di Fourier, le matrici circolanti, e le trasformate discrete veloci Si consideri la seguente matrice n × n

Rome-Moscow school of Matrix Methods and Applied Linear Algebra