• 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
kk
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:
N1 ij
(N1)(N1)
1 0
OT A O N1 N1 N1
0 N 1
Systematic Procedure
LetusnametherowsofA a
as:
N1 ij a1
(N1)(N1)
a2 A
N1
aN1
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, , yN1
1
Then, as shown in Case N 2, it holds:
Fall 2020
Prof.Jiang@ECE NYU 214
b b 1 12 1,N1
OTA O0 A ,ANN 1N11N 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,xN1
AO
N1 1
N1 1 N1 N1
a,xa,x
x a1,x2 a1,xN1 111
x aN1,x2 aN1,xN1
1 1,N1
Answer (cont’d)
Since O is an orthogonal matrix, it follows that
1
b b 1 12 1,N1
OTA O0 A ,ANN 1N11N N
0
Fall 2020 Prof.Jiang@ECE NYU 217
Comment 1
Furthermore, since OT A O must be symmetric, 1 N1 1
wehaveb 0, j2,…,N1, andA issymmetric. 1jN
Thus,
OTA O A ,AAT.
1 00 0
1N11 N N N 0
Fall 2020 Prof.Jiang@ECE NYU 218
Comment 2
Fall 2020
Prof.Jiang@ECE NYU 219
Given the identity
1 00
0
OTA O A ,AAT
1N11 N N N 0
we conclude that the eigenvalues of A must N
be2, 3, , N1, theremainingeigenvalues
ofA . N1
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
SO N1 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 OS N1 1 N1 1 N1
or, equivalently,
1 0 OT A O
N 1
N 1
N 1 0
with O
N1
O S
1 N1
.
0
N 1
N 1
Formal Statement of the Main Result
Let Ann be a real symmetric matrix. Then, it may be transformed into a diagonal form
by using an orthogonal matrix O so that
where
i i1
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 Ax0, xn,x0.
Then,
xTAxxTOOTx, wherediag
yT y, n y 2
i where y OT x y
ii i1
So, the equivalence property follows readily.
Fall 2020 Prof.Jiang@ECE NYU 224
i
n1
Repeated Eigenvalues
As shown previously, if a matrix A has distinct eigenvalues, then its associated eigenvectors are linearly independent.
Questions :
WhatifAhasarepeatedeigenvalue1 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
AOO
0 n
where1 k, i 1,ik1,…,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,ycxi, withxi theithcolumnofO.
i i 1
c 0,i k 1, , n because these eigenvectors i
x areorthogonalwithx , y, 1 jk. 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 A0,
where A detI A n AA:Ann iAni,withA0I.
i1
Fall 2020 Prof.Jiang@ECE NYU 229
n
i1
ni , 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
yAy c
whereA isacanonicalformofAunder c
a nonsingular transformation P1 : x y P1x
sothatA P1AP andxPy. c
3 1 0
Exercise 1
Solve the following initial-value problem:
13 1 xt xt, x0 .
i.e,
xt?, t0.
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 axn1xn2, n2,3,…
Fall 2020 Prof.Jiang@ECE NYU 232
Hint
Fall 2020
Prof.Jiang@ECE NYU 233
Rewrite the second-order difference equation as:
xn10 1xn2, n2,3,… x 1 ax
n n1
Equivalently,
n An1,n1,2,…
with
:xn1.
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, xn
where A, B nn 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,
Axx ABxBAxBx.
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, 1in.
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 .
j1
c xj, i1,2,,k. ij
Now, consider the linear combination Fall 2020 Prof.Jiang@ECE NYU
i1
ai x .
240
ij
ji k i
Fall 2020
i1 i1
Prof.Jiang@ECE NYU 241
Sufficiency: Sketch of Proof
Case 2 (cont’d) : We have kkkkk
i1 i1 j1
B(axi) a c xj
c a xj.
i
Thus, if we choose ai so that
i
ij
ij i
j1 i1
k cara,j1,2,,k,rICa0
iji 1j 1 i1
then we have
B k axi r k axi
i1
i
Sufficiency: Sketch of Proof
kk Case 2(cont’d): Baxi r axi
1
with eigenvector k ai xi .
i1 i1
i1
implies r is an eigenvalue of B, associated
i1
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
z1zk T x1xk 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 M2 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. IfAisnormalandBA, 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
nn
A matrix A is conjugate normal if AA =A A.
Show that a block-upper-triangular matrix 11 12
AA 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