Theorem 6.24:

Page 1

Review

⌅⌅ Theorem 6.24: V is an inner product space:T : V ! V is linear.

Then T is an orthogonal projection , T² = T = T^⇤. Proof:

” ( ”: Assume T² = T = T ^⇤ ) T is a projection.

Let x 2 R(T ) and y 2 N(T ). ) T (x) = x, T (y) = 0.

) hx, yi = hT (x), yi = hx, T^⇤(y)i = hx, T (y)i = hx, 0i = 0 ) x 2 N(T )^? ) R(T ) ✓ N(T )^? (1)

Let x 2 N(T )^?

) x = x1 + x₂, x₁ 2 R(T ), x2 2 N(T ) [projection]

) 0 = hx, x2i = hx1, x₂i + hx2, x₂i = ||x2||² [* x1 2 N(T )^? (1)]

) x2 = 0 ) x = x1 2 R(T ) ) N(T )^? ✓ R(T ) ) N(T )^? = R(T ) [(1)]

Page 2

⌅⌅ Theorem 6.25 (The spectral theorem): V is an inner product space over F ; dim(V ) < 1; T : V ! V is a linear operator with

distinct eigenvalues: spectrum ₁ · · · k

corresponding eigenspaces W₁ · · · W_k orthogonal projection on W_i T₁ · · · Tk

and T is normal if F = C and self-adjoint if F = R. Then the following statements are true.

1. V = W₁ · · · W_k. 2. W_i^? = ^k_j=1,j6=iW_j. 3. T_iT_j = T₀, i 6= j.

4. T₁ + · · · + T_k = I.

5. T = ₁T₁ + · · · + kT_k: spectral decomposition

Page 3

⌅⌅ Corollary 6.25.2: V is an inner product space over C; dim(V ) <

1; T : V ! V is unitary , T is normal and | | = 1 for every eigenvalue of T .

Proof.

”)” If T is unitary, then T is normal and every eigenvalue of T has absolute value 1 (* ||T(x)|| = ||x||).

⌅⌅ Corollary 6.25.3: V is an inner product space over C; dim(V ) <

1; T : V ! V is normal. Then T is self-adjoint , every eigen- value of T is real.

Proof.

”)” T^⇤ = T ) T^⇤(v_i) = _iv_i = T (v_i) = _iv_i ) i is real.

Page 4

⌅⌅ Reflection is an example that is both self adjoint and unitary.

T =

 cos2✓ sin2✓

sin2✓ cos2✓

⌅ [End of Review ]

II.

Page 5

Singular value decomposition and pseudoinverse

⌅⌅ generalization:

normal/self-adjoint operator ) linear transformation T : V ! V ) T : V ! W

[T ] 2 Mⁿ_⇥n ) [T ] 2 M^m_⇥n eigenvalue ) singular value

[T ] = A = QDQ^⇤ ) [T ] = A = U⌃V ^⇤

⌅⌅ For convenience, we assume F = R or C and by unitary we mean either unitary (C) or orthogonal (R).

⌅⌅ adjoint of a linear transformation T : V ! W : T ^⇤ : W ! V such that hT (x), yi_W = hx, T^⇤(y)i_V

Page 6

⌅⌅ Theorem 6.26 (singular value theorem): V and W are inner product spaces; dim(V ), dim )W ) < 1; T : V ! W is linear; rank(T ) = r.

then 9 scalars 1 · · · ^r > 0, and

1. 9 orthonormal bases {v1, · · · , vⁿ} for V such that T^⇤T (v_i) =

( 2

i v_i, 1  i  r 0, i > r .

2. 9 orthonormal bases {u1, · · · , u^m} for W such that T (v_i) =

(

iu_i, 1  i  r 0, i > r . proof: T^⇤T is self-adjoint.

) 9 orthonormal basis = {v1, · · · , vⁿ} for V consisting of eigen- vectors of T^⇤T with corresponding eigenvalues _i. [Thm 6.17]

) hT (vi), T (v_i)i_W = hT^⇤T (v_i), v_ii_V = h iv_i, v_ii_V = _ihvi, v_ii_V

) i 0

Page 7

rank(T^⇤T ) = rank([T^⇤T ] ) = rank([T^⇤] [T ] ) for some .

=rank(([T ] )^⇤[T ] ) [exercise 6.3.15]

=rank([T ] ) [Lemma 6.12.2]

=rank(T )

) 1 · · · ^r > 0; _i = 0, i > r after reordering . We have proven ”1” if we set _i = p

i. Let u_i = ¹

iT (v_i), i = 1, · · · , r.

) hui, u_ji_W = h ¹_iT (v_i), ¹

jT (v_j)i

W

= ¹

i jhT^⇤T (v_i), v_ji_V

= ¹

i jh iv_i, v_ji_V

i2

i jhvi, v_ji_V = _ij

) {u1, · · · , u^r} is orthonormal.

)It extends to an orthonormal basis {u1, · · · , u^m} for W .

Page 8

) T (vi) = (

iu_i, 1  i  r 0, i > r[ _i = 0]

⌅⌅ singular value of T : ₁, · · · , _k, where k =min(m, n), in the theorem.

⌅⌅ The singular values are unique to T , but the bases are not.

⌅⌅ The singular values of T and T^⇤ are identical.

⌅⌅ The theorem is symmetric, ie, the roles of T and T ^⇤ can be inter- changed

Page 9

⌅⌅ example: consider T : P₂(R ! P1(R) such that T (f) = f⁰ and hf, gi = R ₁

1 f (x)g(x)dx.

to find the bases in the theorem, we need to work with the matrix representations relative to ”orthonormal bases”.

Let = {

q1 2,

q3 2x,

q5

8(3x² 1)}, = {

q1 2,

q3

2x}, arbitrary choice.

) A = [T ] =

✓ 0 p

3 0 0 0 p

15

◆

) A^⇤A = 0

@

0 0

p3 0 0 p

15 1 A✓

0 p

3 0 0 0 p

15

◆

= 0

@ 0 0 0 0 3 0 0 0 15

1 A

) 1 = 15, ₂ = 3, ₃ = 0: eigenvalues in decreasing order.

) z1 = (0, 0, 1)^t, z₂ = (0, 1, 0)^t, z₃ = (1, 0, 0)^t :corresponding eigenvectors of A^⇤A in R³

) {v1, v₂, v₃}: the orthonormal basis for V in the theorem.

-

.

一一

u

랴홄

=

制耳

湜言 ^뗴

-

Page 10

) 1 = p

15, ₂ = p

3: singular values.

) u1 = ¹

1T (v₁) =

q3

2x, u₂ = ¹

2T (v₂) =

q1 2

) {u1, u₂}: the orthonormal basis for W in the theorem.

⌅⌅ example: T : R² ! R² is linear and invertible;

T has singular values _{1 2} > 0;

{v1, v₂} and {u1, u₂} are orthonormal bases for R² such that T (v₁) =

1u₁ and T (v₂) = ₂u₂.

Then the unit circle is mapped to an ellipse as follows.

Page 11

⌅⌅ singular value of a matrix A: singular value of L_A

⌅⌅ Theorem 6.27 (singular value decomposition theorem):

A 2 M^m_⇥n; rank(A) = r; A has singular values ₁ · · · ^r;

⌃ 2 M^m_⇥m is such that ⌃_ij = (

i, i = j < r

0, else . Then 9U 2 Mm⇥m and V 2 Mn⇥n, both unitary, such that A = U ⌃V ^⇤ (singular value decomposition of A).

proof: Let T = L_A : Fⁿ ! F^m, and apply theorem 6.26 to get orthonormal bases = {v1, · · · , cⁿ} and = {u1, · · · , u^m}

such that T (v_i) = (

iu_i, 1  i  r 0, i > r .

Let U = (u₁, · · · , u^m) and V = (v₁, · · · , vⁿ).

) AV = (Av1, · · · , Avn) = ( ₁u₁, · · · , ru_r, 0, · · · , , 0) = U⌃

) A = U⌃V ^⇤

2

계

T계가

=

a.ua 0001명 _i )

Page 12

⌅⌅ example: A =

✓ 3 1 1 1 3 1

◆

, A^⇤A = 0

@ 10 0 2 0 10 4 2 4 2

1

A , AA^⇤ =

✓ 11 1 1 11

◆

eigenvalues of A^⇤A : ₁ = 12, ₂ = 10, ₃ = 0 eigenvectors of A^⇤A, normalized:

v₁ = ^p1

6(1, 2, 1)^t, v₂ = ^p1

5(2, 1, 0)^t, v₃ = ^p1

30(1, 2, 5)^t

1 = p

12, ₂ = p 10 u₁ = ¹

1L_A(v₁) = p¹

2(1, 1)^t, u₂ = ¹

2L_A(v₂) = p¹

2(1, 1)^t Note also that eigenvalues of AA^⇤ : ₁ = 12, ₂ = 10

eigenvectors of AA^⇤, normalized:

u₁ = ^p1

2(1, 1)^t, u₂ = ^p1

2(1, 1)^t v₁ = ¹

1L_A⇤(u₁), v₂ = ¹

2L_A⇤(u₂), v₃ cannot be computed.

Page 13

V = 0 BB

@

p1 6

p2 5

p1 2 30

p6

p1 5

p2 1 30

p6 0 ^p5

30

1 CC

A , ⌃ =

✓ p12 0 0

0 p

10 0

◆

, U = 0

@

p1 2

p1 1 2

p2

p1 2

1 A

A = U ⌃V ^⇤ = 0

@

p1 2

p1 1 2

p2

p1 2

1 A

✓ p12 0 0

0 p

10 0

◆ 0 BB

@

p1 6

p2 6

p1 2 6

p5

p1

5 0

p1 30

p2 30

p5 30

1 CC A

⌅ V and W are inner product spaces; dim(V ), dim(W ) < 1;

T : V ! W is linear; rank(T ) = r; then define ”partly invertible”

L : N (T )^? ! R(T ) is such that 8x 2 N(T )^?, L(x) = T (x).

陶龜

Page 14

⌅ pseudoinverse T^† of T :

T ^† : W ! V such that T^†(y) =

(L ¹(y), y 2 R(T ) 0, y 2 R(T )^?

⌅ T ^† is linear.

⌅ T ^† exists when T ¹ does not.

⌅ T is invertible ) T^† = T ¹.

⌅ T = T₀(V ! W ) ) T ^† = T₀(W ) W ).

⌅ T T^†T = T

⌅ T ^†T T^† = T^†

⌅ T T^† and T^†T are self-adjoint.

Page 15

⌅ In theorem 6.26,

{v1, · · · , c^r} is a basis for N(T )^? {vr+1, · · · , vⁿ} is a basis for N(T ), {u1, · · · , u^r} is a basis for R(T ), and {ur+1, · · · , u^m} is a basis for R(T )^?. Let L be the restriction of T to N(T )^?. ) L ¹(u_i) = ¹

iv_i, 1  i  r ) T^†(u_i) =

( ₁

iv_i, 1  i  r 0, r < i  m ) T T ^†(u_i) =

(u_i, 1  i  r

0, r < i  m , T^†T (v_i) =

(v_i, 1  i  r 0, r < i  n

.

랑

- ^-

W

RT가

Page 16

⌅⌅ example: continuing the earlier example, T : P₂(R) ! P1(R) such that T (f) = f⁰ and hf, gi = R ₁

1 f (x)g(x)dx.

singular values : ₁ = p

15, ₂ = p 3 v₁ =

q5

8(3x² 1), v₂ =

q3

2x, v₃ =

q1

2; u₁ =

q3

2x, u₂ =

q1 2

T ^†(u₁) = p¹

15v₁ = p¹

24(3x² 1) T ^†(u₂) = ^p1

3v₂ = ^p1

2x ) T^†(a + bx) = T^†

✓

ap

2u₂ + b

q2 3u₁

◆

= ap 2 ⇣

p1

2x⌘

+ b

q2 3

⇣p1

24(3x² 1)⌘

= ₆^b + ax + ₂^bx²

Page 1

Review

Singular value decomposition and pseudoinverse

 generalization:

normal/self-adjoint operator ⇒ linear transformation T : V → V ⇒ T : V → W

[T ]_β ∈ M_n×n ⇒ [T ]^γ_β ∈ M_m×n eigenvalue ⇒ singular value

[T ]_β = A = QDQ^∗ ⇒ [T ]^γ_β = A = U ΣV ^∗

 For convenience, we assume F = R or C and by unitary we mean either unitary (C) or orthogonal (R).

 adjoint of a linear transformation T : V → W : T ^∗ : W → V such that hT (x), yi_W = hx, T^∗(y)i_V

Page 2

 Theorem 6.26 (singular value theorem): V and W are inner product spaces; dim(V ), dim )W ) < ∞; T : V → W is linear; rank(T ) = r.

then ∃ scalars σ₁ ≥ · · · ≥ σ_r > 0, and

1. ∃ orthonormal bases {v₁, · · · , v_n} for V such that T^∗T (v_i) =

(σ_i²v_i, 1 ≤ i ≤ r 0, i > r .

2. ∃ orthonormal bases {u₁, · · · , u_m} for W such that T (v_i) =

(σ_iu_i, 1 ≤ i ≤ r 0, i > r .

 Singular value of T : σ₁, · · · , σ_k, where k =min(m, n).

 The singular values are unique to T , but the bases are not.

 The singular values of T and T^∗ are identical.

 The roles of T and T^∗ can be interchanged

Page 3

 singular value of A: that of L_A, σ_i = pλ_i(A^∗A) = pλ_i(AA^∗).

 Theorem 6.27 (singular value decomposition theorem):

A ∈ M_m×n; rank(A) = r; A has singular values σ₁ ≥ · · · ≥ σ_r; Σ ∈ M_m×m is such that Σ_ij =

(σ_i, i = j < r

0, else . Then

∃U ∈ M_m×m and V ∈ M_n×n, both unitary, such that A = U ΣV ^∗ (singular value decomposition of A).

proof: Let T = L_A : Fⁿ → F^m, and apply theorem 6.26 to get orthonormal bases β = {v₁, · · · , c_n} and γ = {u₁, · · · , u_m}

such that T (v_i) =

(σ_iu_i, 1 ≤ i ≤ r 0, i > r .

Let U = (u₁, · · · , u_m) and V = (v₁, · · · , v_n).

⇒ AV = (Av₁, · · · , Av_n) = (σ₁u₁, · · · , σ_ru_r, 0, · · · , , 0) = U Σ

⇒ A = U ΣV ^∗

Page 4

 T : V → W is linear; rank(T ) = r; then define ”partly invertible”

L : N (T )^⊥ → R(T ) is such that ∀x ∈ N (T )^⊥, L(x) = T (x).

 pseudoinverse T^† of T :

T ^† : W → V such that T^†(y) =

(L⁻¹(y), y ∈ R(T ) 0, y ∈ R(T )^⊥

 T ^† is linear.

 T ^† exists when T⁻¹ does not.

 T is invertible ⇒ T ^† = T⁻¹.

 T = T₀(V → W ) ⇒ T ^† = T₀(W ⇒ W ).

 T T^†T = T , T^†T T^† = T ^†

 T T^† and T^†T are self-adjoint.

Page 5

 In theorem 6.26,

{v₁, · · · , c_r} is a basis for N (T )^⊥ {v_r+1, · · · , v_n} is a basis for N (T ), {u₁, · · · , u_r} is a basis for R(T ), and {u_r+1, · · · , u_m} is a basis for R(T )^⊥. Let L be the restriction of T to N (T )^⊥.

⇒ L⁻¹(u_i) = _σ¹

iv_i, 1 ≤ i ≤ r

⇒ T^†(u_i) =

( ₁

σ_iv_i, 1 ≤ i ≤ r 0, r < i ≤ m

⇒ T T ^†(u_i) =

(u_i, 1 ≤ i ≤ r

0, r < i ≤ m , T^†T (v_i) =

(v_i, 1 ≤ i ≤ r 0, r < i ≤ n

 [End of Review]

Page 6

 pseudoinverse A^† of a matrix A : L_A† = (L_A)^†

 Theorem 6.29: A ∈ M_m×n; rank(A) = r, A = U ΣV ^∗; σ₁ ≥ · · · ≥ σ_r > 0 are singular values of A;

Σ^† ∈ M_n×m is such that Σ^†_ij =

( ₁

σ_i, i = j ≤ r

0, else . Then

A^† = V Σ^†U^∗, and this is a singular value decomposition of A^†.

 A ∈ M_m×n ⇒ A^† ∈ M_n×m

 Σ^† is the pseudoinverse of Σ

 AA^†A = U ΣV ^∗V Σ^†U^∗U ΣV ^∗ = U ΣΣ^†ΣV ^∗ = A

 AA^† = U ΣΣ^†U^∗ and A^†A = V Σ^†ΣV ^∗ are self-adjoint.

Page 7

 example: Continuing the earlier example, A =

 3 1 1

−1 3 1



, A^∗A =





10 0 2 0 10 4 2 4 2



 , AA^∗ =  11 1 1 11



A = U ΣV ^∗ =





√1 2

√1 1 2

√2 −^√1

2





 √

12 0 0

0 √

10 0











√1 6

√2 6

√1 2 6

√5 −^√1

5 0

√1 30

√2

30 −^√5

30









A^† = V Σ^†U^∗ =









√1 6

√2 5

√1 2 30

√6 −^√1

5

√2 1 30

√6 0 −^√5

30

















√1

12 0 0 ^√1

10

0 0













√1 2

√1 1 2

√2 −^√1

2





A^† = ₆₀¹





17 −7 4 16 5 5



 , AA^† =  1 0 0 1



, A^†A = ₆₀¹





58 −4 10

−4 52 20 10 20 10





Page 8

 Lemma 6.30: V and W are inner product spaces;

dim(V ), dim(W ) < ∞; T : V → W is linear. Then 1. T^†T is the orthogonal projection of V on N (T )^⊥.

2. T T^† is the orthogonal projection of W on R(T ).

proof. Let

L : N (T )^⊥ → R(T ) be such that ∀x ∈ N (T )^⊥, L(x) = T (x).

”1”: T^†T (x) =

(L⁻¹L(x) = x, x ∈ N (T )^⊥ T ^†(0) = 0 x ∈ N (T ) .

”2” is similar.

Page 9

 Theorem 6.30: A ∈ M_m×n; b ∈ F^m; and z = A^†b. Then

1. If Ax = b has a solution, then z is the unique minimal solution (solution with minimum norm).

2. If Ax = b has no solution, then

∀y ∈ Fⁿ, ||Az − b|| ≤ ||Ay − b|| (best approximate solution) with equality if and only if Az = Ay.

Furthermore, Az = Ay ⇒ ||z|| ≤ ||y|| (minimum norm) with equality if and only if z = y (unique).

proof:

”1”: Assume Ax = b has solution y.

⇒ Az = AA^†b = L_AL^†_A(b) = b [∵ b ∈ R(LA); Lemma 6.30]

⇒ z is a solution to Ax = b.

⇒ ∀ solution y, L^†_AL_A(y) = L^†_A(b) = A^†b = z

⇒ z is the orthogonal projection of y on N (L_A)^⊥ [∵ Lemma 6.30].

Page 10

⇒ z is the unique minimal solution.

[N (L_A)^⊥ = R(L_A^∗) ⇒ z = A^∗u, AA^∗u = b, see Thm 6.13]

”2”: Assume Ax = b has no solution, ie, b /∈ R(L_A).

⇒ Az = AA^†b = L_AL^†_A(b) /∈ b

⇒ Az is the orthogonal projection of b on R(L_A). [∵ Lemma 6.30]

⇒ ∀y ∈ F ⁿ, ||Az − b|| ≤ ||Ay − b||

with equality if and only if Az = Ay. [orthogonal proj]

Now assume Az = Ay = c.

⇒ A^†c = A^†Az = A^†AA^†b = A^†b = z

⇒ z is the unique minimal solution to Ax = c. [1]

Page 11

Ch. 7 Jordan canonical form

 V is a vector space; dim(V ) < ∞; T : V → V is linear but ”not diagonalizable”; f_T(t) splits. Then ∃ a basis β for V , called Jordan canonical basis for T , such that

[T ]_β =









A₁ O · · · O O A₂ · · · O ... ... ...

O O · · · A_k









, A_i =

















λ_i 1 0 · · · 0 0 0 λ_i 1 · · · 0 0 0 0 λ_i · · · 0 0 ... ... ... ... ...

0 0 0 · · · λ_i 1 0 0 0 · · · 0 λ_i















 .

 [T ]_β is called a Jordan canonical form of T .

 A_i is called a Jordan canonical block.

 If T is diagonalizable, then all the Jordan canonical blocks become 1 × 1, making the Jordan canonical form diagonal.

Page 12

 example: T : C⁸ → C⁸; β = {v₁, · · · , v₈} is a Jordan canonical basis for T . Then

[T ]_β =

























2 1 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 3 1 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

























is a Jordan canonical form of T .

f_T(t) = (t − 2)⁴(t − 3)²t²

v₁, v₄, v₅ and v₇ are eigenvectors. v₂, v₃, v₆ and v₈ are generalized eigenvectors.

Page 13

 generalized eigenvector x of T corresponding to λ:

(T − λI)^p(x) = 0 for a positive integer p

 Theorem 7.4 (portion) : dim(V ) < ∞; T : V → V is linear; f_T(t) splits. Then there exists a basis for V consisting of generalized eigenvectors of T .

 Corollary 7.7.1: dim(V ) < ∞; T : V → V is linear; f_T(t) splits.

Then T has a Jordan canonical form.

 Corollary 7.7.2: A ∈ M_n×n; f_A(t) splits. Then A is similar to a Jordan canonical form.

Page 14

 example:

A =





3 1 −2

−1 0 5

−1 −1 4



 ⇒ f (t) = det(A − tI) = −(t − 3)(t − 2)² λ₁ = 3 : (A − 3I)v₁ = 0 ⇒ v₁ = (−1, 2, 1)^t

λ₂ = 2 : (A − 2I)v₂ = 0 ⇒ v₂ = (1, −3, −1)^t, only one

(A − 2I)²v₃ = 0 ⇒ v₃ = (−1, 2, 0)^t, generalized eigenvector

⇒ β = {v₁, v₂, v₃} ⇒ J = [L_A]_β =





3 0 0 0 2 1 0 0 2





Q = (v₁, v₂, v₃) =





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



 ⇒ A = QJQ⁻¹, J = Q⁻¹AQ

Page 15

Conclusion

 Linear systems, linear control systems, system applications (com- munication, energy, mechanical, electrical power, signal, ...)

 Optimization, machine Learning