程序代写代做代考 AI C • Extension and Applications

• Extension and Applications
Lecture V
• The higher dimensional case of general real symmetric matrices
Fall 2020 Prof.Jiang@ECE NYU 210

to the diagonal form:
Fall 2020
k
Prof.Jiang@ECE NYU 211
The General Case
We already proved the result with N  2.
By induction, let us assume that for each integer 1 k  N, we can find an orthogonal matrix O
k which reduces a real symmetric matrix A  a 
1  0 OTAO  
kkk  0
k ij
kk

Fall 2020
Prof.Jiang@ECE NYU
212
The General Case: Goal
We want to find an orthogonal matrix ON 1
of order N 1, which reduces a real symmetric
matrix A  a  to the diagonal form:
N1 ij
(N1)(N1)
1  0 
OT A O     N1 N1 N1  
0  N 1 

Systematic Procedure
LetusnametherowsofA a 
as:
N1 ij a1 
(N1)(N1)
a2  A
N1  
 aN1  
and take an eigenvalue 1 and its associated 1
normalized eigenvector x .
Fall 2020 Prof.Jiang@ECE NYU
213

Systematic Procedure (cont’d)
By means of the Gram-Schmidt orthogonalization process,
wecanformanorthogonalmatrixO whosefirstcolumn 1
isthegivenx1 y1:
O y1, y2, , yN1
1
Then, as shown in Case N  2, it holds:
Fall 2020
Prof.Jiang@ECE NYU 214
 b  b  1 12 1,N1
OTA O0 A ,ANN 1N11N N
0 

Exercise
Can you prove the above identity?
Fall 2020 Prof.Jiang@ECE NYU 215

Fall 2020
Prof.Jiang@ECE NYU
216
Answer
Carrying out the multiplication, we have
 a1,x1  a1,xN1 
 AO
N1 1
 N1 1 N1 N1 
 a,xa,x
 x a1,x2  a1,xN1   111 

  x aN1,x2  aN1,xN1 
 1 1,N1


Answer (cont’d)
Since O is an orthogonal matrix, it follows that
1
 b  b  1 12 1,N1
OTA O0 A ,ANN 1N11N N
0 
Fall 2020 Prof.Jiang@ECE NYU 217

Comment 1
Furthermore, since OT A O must be symmetric, 1 N1 1
wehaveb 0, j2,…,N1, andA issymmetric. 1jN
Thus,
OTA O A ,AAT.
1 00 0
1N11 N N N 0

Fall 2020 Prof.Jiang@ECE NYU 218

Comment 2
Fall 2020
Prof.Jiang@ECE NYU 219
Given the identity
1 00
0
OTA O A ,AAT
1N11 N N N 0

we conclude that the eigenvalues of A must N
be2, 3, , N1, theremainingeigenvalues
ofA . N1

Systematic Procedure (cont’d)
By induction, there is an orthogonal matrix ON which reduces A to diagonal form. Form the
N
(N 1)-dimensional matrix
1 0 0 0 
SO N1  N 
0  
Clearly, SN 1 must also be orthogonal, i.e., SNT 1SN 1  I. Fall 2020 Prof.Jiang@ECE NYU 220

Fall 2020
Prof.Jiang@ECE NYU
221
Systematic Procedure (cont’d)
It can be directly checked that
1  0
ST OTA OS     N1 1 N1 1 N1  
or, equivalently,
1  0 OT A O    
N 1
N 1
N 1  0
with O
N1
 O S
1 N1
.

0

N 1 
 N 1 

Formal Statement of the Main Result
Let Ann be a real symmetric matrix. Then, it may be transformed into a diagonal form
by using an orthogonal matrix O so that
where
 i i1
Fall 2020
Prof.Jiang@ECE NYU 222
1  0 OTAO  
n
n
are the eigenvalues of A.
 0

Test for Positive Definiteness
A necessary and sufficient condition for a real symmetric matrix A to be positive definite
is that all eigenvalues of A are positive.
Fall 2020 Prof.Jiang@ECE NYU 223

Indeed,
Recall that a real matrix A is positive definite if xT Ax0, xn,x0.
Then,
xTAxxTOOTx, wherediag
 yT y,  n  y 2
i where y  OT x  y 
ii i1
So, the equivalence property follows readily.
Fall 2020 Prof.Jiang@ECE NYU 224
i
n1

Repeated Eigenvalues
As shown previously, if a matrix A has distinct eigenvalues, then its associated eigenvectors are linearly independent.
Questions :
WhatifAhasarepeatedeigenvalue1 of
(algebraic) multiplicity k?
 Are there always k linearly independent eigenvectors?
Fall 2020 Prof.Jiang@ECE NYU 225

Comment
As shown in Lecture IV, the answer is generally negative for a real matrix which is not
be symmetric.
However, for a real symmetric matrix, we can always find k linearly independent eigenvectors for any repeated eigenvalue of multiplicity k.
Fall 2020 Prof.Jiang@ECE NYU 226

Indeed,
 an orthogonal matrix O such that 1  0
AOO   
0 n
where1 k, i 1,ik1,…,n. Now, the first k columns of O are of course
linearly independent, and are eigenvectors
associated with 1.
Fall 2020 Prof.Jiang@ECE NYU 227

In addition,
Any other eigenvector y associated with  1
is linear combination of these k vectors. n
Infact,ycxi, withxi theithcolumnofO.
i i 1
c  0,i  k 1, , n because these eigenvectors i
x areorthogonalwithx , y, 1 jk. ij
(see Lecture IV)
Fall 2020 Prof.Jiang@ECE NYU 228

Special Case of Cayley-Hamilton Theorem
As a direct application of the diagonal canonical form, we have
Any real symmetric matrix satisfies its own
characteristic equation: A A0,
where A  detI  A n  AA:Ann iAni,withA0I.
i1
Fall 2020 Prof.Jiang@ECE NYU 229
n
 i1
 ni , i

Application:
Solving Differential Equations
Fall 2020
Prof.Jiang@ECE NYU 230
Solving for the solutions of
x  Ax
boils down to an easier problem for

yAy c

whereA isacanonicalformofAunder c
a nonsingular transformation P1 : x  y  P1x
sothatA P1AP andxPy. c


3 1 0 
Exercise 1
Solve the following initial-value problem:
13 1 xt xt, x0 .
i.e,
xt?, t0.
Fall 2020 Prof.Jiang@ECE NYU 231

Exercise 2: Extension to Difference Equations
Find an explicit expression for xn , n  0,1,…, given that
x  1, x  2 and 01
xn axn1xn2, n2,3,…
Fall 2020 Prof.Jiang@ECE NYU 232

Hint
Fall 2020
Prof.Jiang@ECE NYU 233
Rewrite the second-order difference equation as:
xn10 1xn2, n2,3,… x  1 ax 
n n1
Equivalently,
n An1,n1,2,…
with
 :xn1.
n x n

Another Extension
Question : When does there exist an orthogonal matrix O which simultaneously reduces two real symmetric matrices A, B to diagonal form?
Fall 2020 Prof.Jiang@ECE NYU 234

Motivational Problem
Solve the 2nd-order differential equation:

Ax(t)Bx(t)0, xn
where A, B  nn are symmetric matrices. Note that such equations often occur in
mass-spring problems.
Fall 2020 Prof.Jiang@ECE NYU 235

OT AO  diag   i
Basic Result
A necessary and sufficient condition for the existence of an orthogonal matrix O such that
 O T B O  d i a g   i 
is that A and B commute, i.e. AB  BA.
Note: See Section 1.3 of the 2013 textbook of Horn and Johnson for extensions to more than 2 matrices.
Fall 2020 Prof.Jiang@ECE NYU 236

Proof of the Necessity
Clearly,
A  OT diag  O and B  OT diag  O
ii commute, because O is orthogonal.
Fall 2020 Prof.Jiang@ECE NYU 237

Sufficiency: Sketch of Proof
Case 1: Either A or B has distinct eigenvalues. Assume that A has distinct eigenvalues. Then,
Axx ABxBAxBx.
So, Bx, if nonzero, is an eigenvector too, for the same eigenvalue . In other words,
Bx is a multiple of x. As a result, Bxi xi,foreachpair,xi.
ii
This equality of course also holds if Bx=0.
Fall 2020 Prof.Jiang@ECE NYU 238

Sufficiency: Sketch of Proof
Case 1 (cont’d)
Now, we observe that A, B have the same
eigenvectorsxi, 1in.
Thus, we can define the orthogonal transformation matrix O as follows:
O  x1, x2 ,, xn 
Fall 2020 Prof.Jiang@ECE NYU 239

Sufficiency: Sketch of Proof
Case 2 :  repeats k times associated with (linearly 1
independent/orthonormal) eigenvectors x1,, xk . Then, using previous computation, we have
k
Bxi 
Inaddition, xj,Bxi c  Bxj,xi c .
j1
c xj, i1,2,,k. ij
Now, consider the linear combination Fall 2020 Prof.Jiang@ECE NYU
i1
ai x .
240
ij
ji k i

Fall 2020
 i1   i1 
Prof.Jiang@ECE NYU 241
Sufficiency: Sketch of Proof
Case 2 (cont’d) : We have kkkkk

i1 i1  j1 
B(axi) a  c xj 
c a xj.
i
Thus, if we choose ai so that
i
ij
ij i

 
j1  i1
k cara,j1,2,,k,rICa0
iji 1j 1 i1
then we have
    B k axi r k axi
i1 
i


Sufficiency: Sketch of Proof
kk Case 2(cont’d): Baxi r axi 
1
with eigenvector k ai xi .

 i1   i1 
i1
implies r is an eigenvalue of B, associated
i1
On the other hand, r is an eigenvalue of C  c 
1 ij associated with eigenvector a  col ai .
Fall 2020 Prof.Jiang@ECE NYU 242
i

Sufficiency: Sketch of Proof
Case 2 (end) :
If T is a k-dim. orthogonal transformation reducing
k
C into a diagonal form, then
z1zk  T x1xk  is an orthonormal set k
with each zi being common eigenvector for both A and B. left as an exercise
Fall 2020 Prof.Jiang@ECE NYU 243

Fall 2020
Prof.Jiang@ECE NYU 244
Exercise 3
Show how to transform the following matrix into a canonical diagonal form, by means of an orthogonal matrix:
1 2 0 M2 1 0

0 0 1 

if AA  A A.
Normal Matrices:
A generalization of real symmetric matrices
Definition: A square matrix A is said to be normal, **
 If A is normal and  is a scalar, then A also is normal. IfAisnormalandBA, thenBalsoisnormal.
 Every unitary matrix is normal.
 Every real symmetric or skew-symmetric matrix is normal.  Every Hermitian or skew-Hermitian matrix is normal.
Fall 2020 Prof.Jiang@ECE NYU 245

and has eigenvalues a  ib.
Fall 2020 Prof.Jiang@ECE NYU
246
Exercise 4
Let a, b be constants. Show that  a b  is normal
b a 

Exercise 5
nn 
A matrix A is conjugate normal if AA =A A.
Show that a block-upper-triangular matrix  11 12 
AA A  isconjugatenormal 0A
 22
if and only if its diagonal blocks A , A are conjugate
normal, and A  0. In particular, an upper triangular 12
matrix is conjugate normal iff it is diagonal.
See the text (2nd ed.) by Horn-Johnson, p. 268.
Fall 2020 Prof.Jiang@ECE NYU 247
11 22

Fall 2020
Prof.Jiang@ECE NYU 248
Homework #5
1. Using the Gram-Schmidt process find a set of mutually orthonormal vectors u1, u2, u3,
based on: 100
 
010 x1 ,x2 ,x3 .
0  0  1  
1 1 1 