n+1 [sin n+1πij ] is unitary!

(1)

August 21, 2009: I succeed in proving a thing I have believed: q

2 n+1 [sin _n+1 ^πij ] is unitary!

Consider the Fourier matrix of order 2(n + 1):

F 2(n+1) = 1

p2(n + 1) [ω ^ij _2(n+1) ] ²⁽ⁿ⁺¹⁾ _i,j=0 ⁻¹ , ω 2(n+1) = e ⁻ⁱ

²⁽ⁿ⁺¹⁾^2π

= e ⁻ⁱ

ⁿ⁺¹^π

. Note that, if o n = p2/(n + 1), then

F 2(n+1) = ¹ ₂ (C − iS),

c ij = o n cos _n+1 ^ijπ , s ij = o n sin _n+1 ^ijπ , i, j = 0, . . . , 2(n + 1) − 1.

Since S and C are real symmetric matrices, we have I = F _2(n+1) ^∗ F 2(n+1) = 1

2 (C + iS) 1

2 (C − iS) = 1

4 [(C ² + S ² ) + i(SC − CS)], Q = F _2(n+1) ² = 1

2 (C − iS) 1

2 (C − iS) == 1

4 [(C ² − S ² ) − i(CS + SC)], being

Q =





 1

J 1 J







, J n × n counter-identity.

As a consequence C ² + S ² = 4I C ² − S ² = 4Q

CS = SC = 0 ⇒ S ² = 2(I − Q) = 2





 0

I −J

0 −J I





 .

Now let S 11 , S 12 , S 22 be the n × n matrices defined by the equality

S =





 0

S 11 S 12

0 S ₁₂ ^T S 22





 ,

that is,

(S 11 ) rs = o n sin _n+1 ^rsπ , (S 12 ) rs = o n sin ^r(n+1+s)π _n+1 , (S 22 ) rs = o n sin (n+1+r)(n+1+s)π

n+1 , 1 ≤ r, s ≤ n.

Observe that S 11 and S 22 are real symmetric and related by the identity S 22 = JS 11 J; moreover S 12 is persymmetric, i.e. S 12 J = JS ₁₂ ^T . (Recall that S 11 is the (sine) transform diagonalizing the algebra τ of all polynomials in

X =





 1

1 1

1 . ..

. .. 1

1 





(2)

).

Since

S ² =





 0

S ₁₁ ² + S 12 S ₁₂ ^T S 11 S 12 + S 12 S 22

0 S ₁₂ ^T S 11 + S 22 S ₁₂ ^T S ₁₂ ^T S 12 + S ₂₂ ²





 ,

we obtain four identities which in fact reduce to the following only two:

S ₁₁ ² + S 12 S ₁₂ ^T = 2I, S 11 S 12 J + S 12 JS 11 = −2I. (1) The sum of them yields 0 = S 11 (S 11 +S 12 J)+S 12 J(S 11 +S 12 J) = (S 11 +S 12 J) ² , but this can happen only if

S 11 + S 12 J = 0, S 12 = −S ¹¹ J (2) (a real symmetric matrix with all the eigenvalues equal to 0 must be null).

Now we are near the thesis. In fact, by (2) the first identity in (1) becomes 2I = S ₁₁ ² + ( −S ¹¹ J)( −S ¹¹ J) ^T = 2S ₁₁ ² , and so S ₁₁ ² = I.

Remark. From the equality F 2(n+1) = ¹ ₂ (C − iS) it follows that S = i(F 2(n+1) − F 2(n+1) ^∗ ) = i(I − Q)F ²⁽ⁿ⁺¹⁾ . So, the sine transform of z n × 1, S 11 z, can be computed via a discrete Fourier transform of order 2(n + 1):

i(I − Q)F ²⁽ⁿ⁺¹⁾





 0 z 0 0







=





 0

S 11 −S ¹¹ J 0

−JS ¹¹ JS 11 J











 0 z 0 0







=





 0 S 11 z

0 −JS ¹¹ z





 .

Investigate the four submatrices of C, perhaps they also can be expressed in terms of only one and this one is a transform diagonalizing some algebra of matrices . . .

The matrix

A =

3 2 1 2

does not satisfy the equation A ^∗ A = AA ^∗ , thus there is no unitary matrix diagonalizing A. However, T ⁻¹ AT is diagonal for a suitable T :

D ⁻¹ AD =

3 √

√ 2

2 2

, D =

√ 2 0

0 1

,

α −β

β α

3 √

√ 2

2 2

α β

−β α

=

1 0 0 4

, α = 1

√ 3 , β = r 2 3 , T = 1

√ 3

√ 2 0

0 1

1 √

2 − √

2 1

= 1

√ 3

√

2 2

− √ 2 1

.

The condition number of T (in the 2-norm), µ 2 (T ) = kT k ² kT ⁻¹ k ² , is greater than 1:

T ^∗ T = 1 3

4 √

√ 2

2 5

⇒ kT k ² = pρ(T ^∗ T ) = √

2,

(3)

T ⁻¹ =

√ 3 3 √

2 √ 1 −2 2 √

2 , (T ⁻¹ ) ^∗ (T ⁻¹ ) =

₁

2 0

0 1

⇒ kT ⁻¹ k ² = 1.

So, µ 2 (T ) = √

2. Since kT k ∞ = ^√ ^√ ²⁺² ₃ , kT ⁻¹ k ∞ = ^√ ^√ ³ ₂ , we have µ _∞ (T ) = 1+ √ 2.

Can a non-unitary matrix T have condition number equal to 1 ?

If yes, then, by the Bauer-Fike theorem, the eigenvalue problem would be optimally conditioned for a class of matrices A larger than normal (the A diag- onalized by T , µ 2 (T ) = 1).

A n × n matrix A is said reducible if there exists I ⊂ N = {1, 2, . . . , n}, I 6= ∅, N, such that a ^ik = 0 for all i ∈ I, k ∈ N \I. Equivalently, A is reducible if there exists a permutation matrix P such that

P ^T AP =

n −i ∗ 0 i

, k k × k matrices, i 6= 0, n (i = |I|, n − i = |N \I|).

Set

C i = {z ∈ C : |z − a ⁱⁱ | <

n

X

j=1,j 6=i

|a ^ij |}.

It is well known that the subset ∪ ⁿ i=1 C i of C includes all the eigenvalues of A (Gershgorin first theorem).

If A is not reducible then we can say something more:

If A is a irreducible n ×n matrix and C i are the inner parts of the Gershgorin disks, then the set ( ∪ ⁿ i=1 C i ) ∪ (∩ ⁿ i=1 ∂C i ) includes all the eigenvalues of A.

Proof. If λ is an eigenvalue of A, then P

j a ij x j = λx i , P

j,j6=i a ij x j = (λ − a ⁱⁱ )x i ,

|λ − a ii ||x i | ≤ X

j,j6=i

|a ij ||x j |, ∀ i.

Set I = {j : |x j | = kxk ∞ }. Assume I 6= N and let i ∈ I, k ∈ N \I such that a ik 6= 0. Then

|λ − a ii ||x i | ≤ P

j,j6=i |a ij ||x j |

= P

j∈I,j6=i |a ij ||x j | + |a ik ||x k | + P

j∈N \I,j6=k |a ij ||x j |

< P

j∈I,j6=i |a ^ij ||x ⁱ | + |a ^ik ||x ⁱ | + P

j∈N \I,j6=k |a ^ij ||x ⁱ |

= P

j,j 6=i |a ^ij ||x ⁱ |,

|λ − a ii | < P

j,j6=i |a ij |, i.e. λ ∈ C i .

Assume now I = N , that is all entries of the eigenvector x have the same absolute value. In this case:

|λ − a ii ||x i | ≤ X

j,j6=i

|a ij ||x j | = X

j,j6=i

|a ij ||x i |, ∀ i,

|λ − a ⁱⁱ | ≤ P

j,j6=i |a ^ij |, ∀ i, therefore either λ ∈ C ^s for some s or λ ∈ ∂C ⁱ ∀ i.

Use the result obtained to prove that any irreducible weakly diagonal dominant n × n matrix A is non singular

ρ(A) ≤ kAk ∞ .

(4)

By the Gershgorin first theorem, for any eigenvalue λ of A there exists i such that |λ| = |λ − a ⁱⁱ + a ii | ≤ |λ − a ⁱⁱ | + |a ⁱⁱ | ≤ P

j |a ^ij | ≤ kAk ∞

If A is irreducible and P

j |a sj | < kAk ∞ for some s, then ρ(A) < kAk ∞ . Given an eigenvalue λ of A, the Gershgorin first theorem for irreducible matrices implies either ∃ i | |λ| = |λ − a ii + a ii | ≤ |λ − a ii | + |a ii | < P

j |a ij | ≤ kAk ∞ or |λ| = |λ − a ii + a ii | ≤ |λ − a ii | + |a ii | = P

j |a ij |, ∀ i, also for i = s, for which we know that P

j |a ^sj | < kAk ∞

(Jacobi method is able to solve linear systems Ax = b with A weakly diagonal dominant because in this case the Jacobi iteration matrix J satisfies the conditions ∃ s | P

j |[J] ^sj | < kJk ∞ and kJk ∞ = 1, thus, by the result of the Exercise, ρ(J) < 1).

Proof of the existence of the SVD of A ∈ C ^n×n

A n × n ⇒ ∃ U, σ, V , U, V unitary, σ = diag (σ i ) with σ 1 ≥ σ ² . . . ≥ σ n such that A = U σV ^∗ .

Proof. Let v 1 , kv ¹ k ² = 1, be such that kAk ² = kAv ¹ k ² and set u 1 = Av 1 / kAv ¹ k ² ( ku ¹ k ² = 1 and Av 1 = kAk ² u 1 ). Let ˜ u _i , ˜ v _i ∈ C ⁿ be such that U = [u 1 |˜u ² | · · · |˜u n ] and V = [v 1 |˜v ² | · · · |˜v n ] are unitary. Then

U ^∗ AV =





 u ^∗ ₁

˜ u ^∗ ₂

· · ·

˜ u ^∗ _n







A[v 1 |˜v ² | · · · |˜v ⁿ ] =





 u ^∗ ₁

˜ u ^∗ ₂

· · ·

˜ u ^∗ _n







[ kAk ² u ₁ |A˜v ² | · · · |A˜v ⁿ ] =

kAk ² w ^∗ 0 A ˆ

,

kAk ² = kU ^∗ AV k ² = sup v 6=0 k



 kAk ² w ^∗ 0 A ˆ



vk

2

kvk

2

≥

k



 kAk ² w ^∗ 0 A ˆ







 kAk ² w



 k

2

k



 kAk ² w



k

2

≥ √ ^kAk

²²

⁺ ^kwk

²²

kAk

²2

+ kwk

²2

= pkAk ² 2 + kwk ² 2

⇒ w = 0 ⇒

kAk ² = kU ^∗ AV k ² = sup v 6=0 k



 kAk ² 0 ^∗ 0 A ˆ



vk

2

kvk

2

≥ sup ˆ v 6=0 k



 kAk ² 0 ^∗ 0 A ˆ









0 ˆ v



k

2

k





0 ˆ v



 k

2

= k ˆ A k ²

⇒ U ^∗ AV =

kAk ² 0 ^∗ 0 A ˆ

with ˆ A such that k ˆ A k ² ≤ kAk ² .

The thesis follows if we assume it true for matrices of order n − 1.

On SVD: best rank-r approximation of A.

A n × n, A = UσV ^∗ = P n

1 σ i u _i v ^∗ _i , A r = P r

1 σ i u _i v _i ^∗ ⇒

min {kA − Bk ² : rank(B) ≤ r} = kA − A ^r k ² = σ r+1

(5)

Proof. Let B be a n × n matrix with complex entries whose rank is no more than r and set L = {v : Bv = 0}. Observe that

kA − Bk ² = sup

v

k(A − B)vk ² kvk ² ≥ sup

v ∈L

kAvk ² kvk ² .

Set M = Span {v ¹ , v 2 , . . . , v r+1 }. Since dim M + dim L ≥ n + 1, there exists z 6= 0, z ∈ M ∩ L,

kA − Bk ² ≥ kAzk ²

kzk ² ≥ σ ^r+1 (first: z ∈ L; second: z ∈ M ⇒ z = P r+1

1 α i v _i ⇒ Az = P r+1

1 α i σ i u _i ).

Moreover,

kA − A ^r k ² = kU diag (0, . . . , 0, σ ^r+1 , . . . , σ n )V ^∗ k ² = k diag (. . .)k ² = σ r+1

and rank(A r ) ≤ r.

Remark. We also have:

min {kA − Bk F : rank(B) ≤ r} = kA − A r k F = v u u t

n

X

r+1

σ ² _j

In functional analysis for compact operators . . . (linear banded operators on Hilbert spaces) use * as a definition of singular values, approximate an object with something of finite dimension

On SVD: kernel and image of A.

A n × n, A = UσV ^∗ , σ 1 ≥ . . . ≥ σ k > 0 = σ k+1 = . . . = σ n ⇒ (1) {x ∈ C ⁿ : Ax = 0 } = Span {v ^k+1 , . . . , v n }

(2) {Ax : x ∈ C ⁿ } = Span {u ¹ , . . . , u k } (3) rank(A) = k = # {σ ⁱ : σ i > 0 }

Proof. (1): Ax = 0 iff σV ^∗ x = 0 iff S k V _k ^∗ x = 0,

S k =





 σ 1

. ..

σ k





 , V k =



 v ^∗ ₁

· · · v ^∗ _k



 ,

iff V _k ^∗ x = 0 iff x is orthogonal to v 1 , . . . , v k iff x is a linear combination of v _k+1 , . . . , v n .

(2):

Ax = [U k ]

S k 0

0 0

V _k ^∗

= U k (S k V _k ^∗ x), U k = [u 1 · · · u ^k ]

⇒ Ax ∈ Span {u ¹ , . . . , u k } ⇒ {Ax : x ∈ C ⁿ } ⊂ Span {u ¹ , . . . , u k }. Now let us show that for any z ∈ C ^k there exists x ∈ C ⁿ , U k z = Ax:

∃ x | Ax = U ^k z iff

∃ x | U k S k V _k ^∗ x = U k z iff

∃ x | S k V _k ^∗ x = z iff

∃ x | V k ^∗ x = S _k ⁻¹ z.

(6)

Since rank(V _k ^∗ ) = k, the latter system admits solution.

On SVD: exercises

A = 1 81





−65 76 104

76 −206 8

104 8 109



 = U DU ^∗ ,

U = 1 9





−4 4 7

8 1 4

1 8 −4



 , D =





−3 2

−1



 . Write the SVD of A.

λ i eigenvalues of A ⇒ σ ⁿ ≤ |λ ⁱ | ≤ σ ¹ .

(Ax = λx, A = U σV ^∗ ⇒ y ^∗ σ ² y = x ^∗ A ^∗ Ax = |λ| ² kxk ² 2 . . .).

On SVD: how to compute the rank of a matrix, Gram-Schmidt vs SVD Let a 1 , a 2 , . . . , a m , . . . be a sequence of non null n × 1 vectors and set A ^m = [a 1 a ₂ · · · a ^m ], m = 1, 2, . . .. There follows an algorithm which computes matrices Q m = [q 1 q ₂ · · · q ^m ], n × m, and R ^m , upper triangular m × m, such that

(1) A m = Q m R m , m = 1, 2, . . .

(2) {q ¹ } ∪ {q ^k : 2 ≤ k ≤ m, a ^k ∈ Span {a / ¹ , . . . , a _k−1 }} is an orthonormal basis of the space Span {a ¹ , . . . , a m }

(3) if a k , 2 ≤ k ≤ m is linearly dependent from a ¹ , . . . , a _k−1 , then the k-row of R m is null and q k can be chosen arbitrarily (for instance, q k = 0 or such that Q ^∗ _m Q m = I)

(4) The rank of A m is the number of non null rows of R m

Set ˆ q ₁ = a 1 and q 1 = ˆ q ₁ / kˆq ¹ k ² . Then a 1 = kˆq ¹ k ² q ₁ , i.e.

h a 1

i = h q 1

i [ kˆq ¹ k ² ].

Set ˆ q ₂ = a 2 − r ¹² q ₁ , r 12 such that q ^∗ ₁ q ˆ ₂ = 0 (r 12 = q ^∗ ₁ a ₂ ) and, if ˆ q ₂ 6= 0, q 2 = ˆ q 2 / kˆq ² k ² . Then a 2 = r 12 q 1 + kˆq ² k ² q 2 , i.e.



 a 1 a 2



 =



 q 1 q 2





kˆq ¹ k ² r 12

0 kˆq ² k ²

.

Else, if ˆ q ₂ = 0, or, equivalently, a 2 = r 12 q ₁ ∈ Span {a ¹ }, we can write



 a ₁ a ₂



 =



 q ₁ q ₂





kˆq ¹ k ² r 12

0 0

, q 2 := ˆ q ₂ = 0 or arbitrary.

Assume that the first case occurs. Set ˆ q ₃ = a 3 −r ¹³ q ₁ −r ²³ q ₂ , r 13 , r 23 such that

q ^∗ ₁ q ˆ ₃ = q ^∗ ₂ q ˆ ₃ = 0 (r 13 = q ^∗ ₁ a ₃ , r 23 = q ^∗ ₂ a ₃ ) and assume ˆ q ₃ = 0, or, equivalently,

(7)

a ₃ = r 13 q ₁ + r 23 q ₂ ∈ Span {a ¹ , a 2 }. Then we can write:



 a ₁ a ₂ a ₃



 =



 q ₁ q ₂ q ₃









kˆq ¹ k ² r 12 r 13

0 kˆq ² k ² r 23

0 0 0



 , q 3 := ˆ q 3 = 0 or arbitrary.

Set ˆ q 4 = a 4 − r ¹⁴ q 1 − r ²⁴ q 2 , r 14 , r 24 such that q ^∗ ₁ q ˆ 4 = q ^∗ ₂ q ˆ 4 = 0 (r 14 = q ^∗ ₁ a 4 , r 24 = q ^∗ ₂ a 4 ) and assume ˆ q 4 = 0, or, equivalently, a 4 = r 14 q 1 + r 24 q 2 ∈

Span {a ¹ , a 2 }. Then we can write:



 a ₁ a ₂ a ₃ a ₄



 =



 q ₁ q ₂ q ₃ q ₄











kˆq ¹ k ² r 12 r 13 r 14

0 kˆq ² k ² r 23 r 24

0 0 0 0





 ,

q ₃ := ˆ q ₃ = 0, q 4 := ˆ q ₄ = 0 or arbitrary.

Set ˆ q ₅ = a 5 − r ¹⁵ q ₁ − r ²⁵ q ₂ , r 15 , r 25 such that q ^∗ ₁ q ˆ ₅ = q ^∗ ₂ ˆ q ₅ = 0 (r 15 = q ^∗ ₁ a ₅ , r 25 = q ^∗ ₂ a ₅ ) and assume ˆ q ₅ 6= 0. Set q ⁵ = ˆ q ₅ / kˆq ⁵ k ² . Then a 5 = r 15 q ₁ +r 25 q ₂ + kˆq ⁵ k ² q ₅ , i.e.



 a ₁ a ₂ a ₃ a ₄ a ₅



 =



 q ₁ q ₂ q ₃ q ₄ q ₅











kˆq ¹ k ² r 12 r 13 r 14 r 15

0 kˆq ² k ² r 23 r 24 r 25

0 0 0 0 0

0 0 0 0 kˆq ⁵ k ²





 ,

q ₃ , q 4 null or arbitrary.

. . .

Remark. Since the calculator uses finite arithmetic, the check if ˆ q _k , k ≥ 2, is zero or nonzero must be replaced with something of type: kˆq ^k k is less than ε or not? Moreover, take into account that even a very little perturbation in one entry of a triangular matrix can change the value of its rank (see the following example). These facts imply that the (Gram-Schmidt) algorithm illustrated above may generate a numeric rank of A m which is different from the rank of A m .

Example. Let R be the n × n upper triangular matrix

R =







1 −1 −1 · · · −1 0 1 −1 · · · −1 .. . . .. 1 ... ...

.. . . .. ... −1 0 · · · · 0 1





 .

The rank of R is n, but if the 0 in the (n, 1) entry is replaced with −2 ²⁻ⁿ (which for large n is a very little perturbation), then the rank of R becomes n − 1. The SVD of R predicts this observation. In fact, the singular value σ n −1 of R for n = 5, 10, 15 has more or less the same value, 1.5, whereas the smallest singular value, σ n , seems to tend to zero:

n = 5 : σ 5 ≈ 1

10 , n = 10 : σ 10 ≈ 1

100 , n = 15 : σ 15 ≈ 1

10000 .

(8)

So, by examining the singular values of R we see that even if det(R) = 1 (far from zero) for all n, greater is n, smaller is the distance of R from a singular matrix. (Note that R is not normal, in fact µ 2 (R) = σ 1 /σ n ≈ 30, 2000, 10 ⁵

> 1 = max |λ ⁱ |/ min |λ ⁱ |).

It is known that small perturbations on the entries of A imply at most small perturbations on U, σ, V , A = U σV ^∗ (SVD problem is well conditioned).

n+1 [sin n+1πij ] is unitary!

August 21, 2009: I succeed in proving a thing I have believed: q

2