程序代写代做代考 algorithm AI Lecture VI

Lecture VI
Extensions to Complex Matrices, in particular Hermitian Matrices.
Key Notions:
* Unitary matrices
* Unitary equivalence
* Schur’s unitary triangularization * QR factorization
* Congruence and simultaneous diagonalization
Fall 2020 Prof.Jiang@ECE NYU 249

Fall 2020
Prof.Jiang@ECE NYU 250
Orthogonality Between Complex Vectors
Given any pair of (complex) vectors x, y  n , the inner product is defined as
x, y  y*x
 x y  x y  x y .
1122nn They are said to be orthogonal, if
x,y 0.

Fall 2020
Prof.Jiang@ECE NYU 251

x,x 0,xn;
Facts about the Inner Product
It can be easily checked that the inner product enjoys the following properties:
 
x, yz  x, y  x, z , x,y,zn. x, y  x, y , , scalar.
0, ifandonlyifx0. 

Orthogonal & Orthonomral Sets of Vectors
 A set of vectors xi n is said to be orthogonal, if xi,xj 0,1i,jk,ij.
 A set of vectors xi n is said to be orthonormal if,additionally, xi : xi,xi 1,1ik.
Fall 2020 Prof.Jiang@ECE NYU 252

Remark
k Any orthogonal set of nonzero vectors yi 
i1 can be made an orthonormal set, by defining
Fall 2020
Prof.Jiang@ECE NYU 253
xi : 1 yi, 1ik. yi , yi

Fundamental Results
1) Any orthogonal set of nonzero vectors is linearly independent.
2) Any orthonormal set of vectors is linearly independent.
Fall 2020 Prof.Jiang@ECE NYU 254

Unitary Matrix
A matrix U nn is said to be unitary **T
ifU U I. (RecallthatU U )
Of course, a real orthogonal matrix O  nn is unitary, but the converse is not true.
Can you find some examples?
Fall 2020 Prof.Jiang@ECE NYU 255

Complex Orthogonal Matrix
A matrix Ann is said to be complex orthogonal, if: AT A  I.
Remark:
A complex orthogonal matrix is unitary if and only if it is real.
Fall 2020 Prof.Jiang@ECE NYU 256

Equivalent Characterizations
The following are equivalent:  U is unitary;
 U is nonsingular and U* U1;  UU* I;
 U* isunitary;
 The columns of U form an orthonormal set;  The rows of U form an orthonormal set;
 Foranyxn,yUxsatisfiesy*yx*x.
Fall 2020 Prof.Jiang@ECE NYU 257

Exercise
Are the following statements true or false?
1) For any given real parameters i , 1  i  n, Udiag e k isalwaysunitary.
 j 
2) Any diagonal unitary matrix can always be put into the above form.
3) Any diagonalizable unitary matrix can be transformed
to the above form.
Fall 2020 Prof.Jiang@ECE NYU 258

Question
How to apply a unitary matrix, instead of a real orthogonal matrix, to transform a Hermitian matrix into a canonical diagonal form?
Fall 2020 Prof.Jiang@ECE NYU 259

Review: Canonical Form of a Real Symmetrical Matrix
Let Ann be a real symmetric matrix. Then, it can be transformed into the diagonal form by using an orthogonal matrix O so that
where
 i i1
Fall 2020
Prof.Jiang@ECE NYU 260
1  0 OTAO  
n
n
are the eigenvalues of A.
 0

Extension
It is possible to generalize this important result to (possibly complex) Hermitian matrices H , i.e.,
H* H.
In this case, we use unitary matrices U , instead of
orthogonal matrices, i.e., *
U U  I.
Fall 2020 Prof.Jiang@ECE NYU 261

Examples
 The matrix  1 2i is Hermitian. 2i 3

 The matrix  1 2i is not Hermitian,
2i 3 
but is a complex symmetrical matrix.
Fall 2020 Prof.Jiang@ECE NYU 262

Eigenvalues of Hermitian Matrices
The eigenvalues of a Hermitian matrix are real, and eigenvectors associated with distinct eigenvalues are orthogonal.
Fall 2020 Prof.Jiang@ECE NYU 263

Canonical Transformation
If H is a Hermitian matrix, there exists a unitary matrix U such that
1  0 U*HU  .
 0
n
In particular, U becomes a real orthogonal matrix
when H is a real symmetric matrix.
Fall 2020 Prof.Jiang@ECE NYU 264

Fall 2020
i1
Prof.Jiang@ECE NYU 265
Idea of Proof
As in the case of real symmetric matrices, we use the Gram-Schmidt Orthogonalization Process, noting the following:
For complex vectors x, y  n , the inner product is defined
as follows: x,yyTxn xiyi.

Fall 2020
x, y in the orthogonalization process.)
Prof.Jiang@ECE NYU 266
(Hint: use x, y =
n
2
x y for complex vectors
Exercise
Compute the eigenvalues 1, 2 of H1 2i
2i 3 
and find a unitary matrix U that reduces H to the diagonal form 1
ii i1
0 . 0

Schur’s Unitary Triangularization
For any square, not necessarily Hermitian, n  n matrix A, there is a unitary matrix U for which
1 *  *
0  U*AU     *
00 n
with * being zero or nonzero scalars.
Fall 2020 Prof.Jiang@ECE NYU 267

Fall 2020
Prof.Jiang@ECE NYU 268


Algorithm
Step 1: Take a normalized eigenvector x1 of A associated with an eigenvalue  , and
1
find n 1 vectors y2 ,, yn so that
x1, y2 ,, yn are linearly independent.

Fall 2020
Prof.Jiang@ECE NYU 269
Algorithm
Step 2 : Apply the Gram-Schimidt orthonormalization procedure to x1, y2 ,, yn to produce an orthonormalsetx1, z2,,zn.
Define U  x1, z2 ,, zn  which, clearly, is 1
a unitary matrix.

Fall 2020
Prof.Jiang@ECE NYU 270
Algorithm
Step2(cont’d):UnderU x1,z2,,zn, 1
 *
U*AU 1 ,withA(n1)n1.
110A1 1
Of course, A has eigenvalues  ,, . 12n

Fall 2020
2
Prof.Jiang@ECE NYU 271
Algorithm
Step 3: For A (n1)n1, apply Steps 1-2 1
to arrive at an orthonormal set x2 , z3 , , zn 11
n1 andaunitarymatrix
U x2, z3, , zn(n1)n1
211 so that
U*AU 2 *,withA(n2)n2 2120A2

Fall 2020
Prof.Jiang@ECE NYU 272
Algorithm
Step 4 : It is easy to check that,
V 1 0  and UV nn
20U12 2
are both unitary. In addition,
1 * * *
UV*AUV  
12 12
OA  (n2)2 2 
0  * * 2
 

Fall 2020
0 n
Algorithm
Last Step : Continuing these steps to arrive at the last step, where we have produced
unitary matrices Ui (ni1)(ni1) , and V nn, i2,3,,n1
i
so that
 UUVV , and
12 n1
 * *
1 U*AU  .
Prof.Jiang@ECE NYU 273

Some Applications of Schur’s Theorem
• Useful for solving algebraic, differential or difference linear equations.
Do you know why?
Fall 2020 Prof.Jiang@ECE NYU 274

Applications of Schur’s Theorem
• Cayley-HamiltonTheorem
Let pA  be the characteristic polynomial of A, thatis,pAdetIAn 1n1n. Then,pAA:An 1An1nI0.
See the textbook of Horn & Johnson (2nd ed., 2013),
pp. 109~110.
Fall 2020 Prof.Jiang@ECE NYU 275

Comment
Cayley-Hamilton Theorem is extremely important in linear systems theory.
Fall 2020 Prof.Jiang@ECE NYU 276

Technical Remark
For any square n  n matrix A, for any integer i  n, there exist constants ci1,,cin such that
Ai ci1An1 cin1AcinI, in.
Fall 2020 Prof.Jiang@ECE NYU 277

Exercise
Consider the matrix A   3 2. 1 0

 Use Cayley-Hamilton Theorem to
express A2 , A3 , A4 as linear combinations
of A, I.
 Use Cayley-Hamilton Theorem to find
the inverse A1.
Fall 2020 Prof.Jiang@ECE NYU 278

QR Factorization
For any (possibly nonsquare) matrix A  nm ,
withnm,Qnm,Rmm suchthat
 The columns of Q form an orthonormal set,
and R is an upper triangular matrix;  AQR.
If, in addition, A is nonsingular, then the diagonal entries of R are positive. Moreover, in this case, Q and R are unique.
Fall 2020 Prof.Jiang@ECE NYU 279

Remark
The factors Q and R may be taken real, if A is a real matrix.
Proof: See the textbook, pp.89~90, for the constructive procedure closely tied to the Gram-Schmidt (G-S) algorithm.
Fall 2020 Prof.Jiang@ECE NYU 280

An Example
What is the QR factorization of A1 0
2 3 
Fall 2020 Prof.Jiang@ECE NYU 281

Solution
Forsimplicity,denoteA1 0:a1 a2. 2 3
Then,letq1 a1 / a1   and, 55
like in the G-S process, compute y2a2q1*a2q16 3T
Fall 2020 Prof.Jiang@ECE NYU 282
 1 2T
55 

Solution (cont’d)
2 1T Now,letq2y2/y2  .
55 SetQq1 q2which,byconstruction,
is orthonormal. Then, R  r , (with r =0k  j) ij kj
can be determined according to the general formula:
aj  Fall 2020
j k1
rqk,j1,2,…,m kj
m = 2, here R is upper-triangular. 283

Solution (end)
So,r  5, r 0, r  6 ,r  3 . 11 21 12 522 5
Thatis: R  0 3
56 5
 5
It is directly verified that A  QR.
Fall 2020 Prof.Jiang@ECE NYU 284

can be written as:
* nn
B: Positive semi-definite
B  LL , with L   if A is nonsingular.
Application to
Cholesky factorization
By means of QR factorization, any matrix B  nn
* nn takingtheformBA A, withA
,
lower triangular. Moreover, this factorization is unique,
Indeed, it suffices to write A  QR to obtain L  R. Fall 2020 Prof.Jiang@ECE NYU 285

QR Numerical Algorithm This is a powerful tool for computing the
eigenvalues of a matrix.
Fall 2020 Prof.Jiang@ECE NYU 286

Fall 2020
Prof.Jiang@ECE NYU 287
QR Numerical Algorithm
Step 1: For any given A  nn , factorize 0
AQR 000
Step 2: Define A  R Q , and factorize 100
AQR 111
Continuing this process, we have
k 1,
A QR kkk
A RQ k1 kk

Proposition
EachA isunitarilyequivalenttoA,andthus k0
they have the same eigenvalues.
IfA hasdistincteigenvalues,thenA converges
0k to an upper triangular matrix.
Fall 2020 Prof.Jiang@ECE NYU 288

A Numerical Exercise
Use MATLAB simulation to validate the QR algorithm for the matrix
A1 0. 2 3

Fall 2020 Prof.Jiang@ECE NYU 289

Congruence
Consider two matrices A, B  nn .
(1) B is said to be *congruent to A, if B  SAS*
for some nonsingular matrix S.
(2) B is said to be congruent, or T congruent to A,
if B  SAST for some nonsingular matrix S. Notice that both congruence are equivalence relations.
(Horn-Johnson, 2nd ed., 2013; p. 281)
Fall 2020 Prof.Jiang@ECE NYU 290

i(A)i A, i A, i0 A where
Inertia
Consider a Hermitian matrix Ann. Its inertia is defined as the ordered triple:
i  A  the number of positive eigenvalues of A; i  A  the number of negative eigenvalues of A; i0  A  the number of zero eigenvalues of A.
Fall 2020 Prof.Jiang@ECE NYU 291

Sylvester’s Law of Inertia
Hermitian matrices A, B  nn are *congruent
if and only if they have the same inertia,
i.e., the same number of positive eigenvalues and
the same number of negative eigenvalues.
For the proof, see (Horn-Johnson, 2nd Ed., 2013, p. 282)
Fall 2020 Prof.Jiang@ECE NYU 292

Simultaneous Diagonalization
Consider two Hermitian matrices A, B  nn .
There is a unitary matrix U nn and real diagonal
matrices , M such that A=UU* , B=UMU* iff AB is Hermitian, that is, AB  BA.
See (Horn-Johnson, 2nd Edition, 2013, page 286.)
Fall 2020 Prof.Jiang@ECE NYU 293

Homework VI
1. Transform the following Hermitian matrix 0 2 1
H2 5 6 
1 6 8 
into a diagonal form.
2. If a (real) Hermitian matrix H is positive definite,
provethat HP2,
for a positive definite matrix P.
Fall 2020 Prof.Jiang@ECE NYU 294