Home / Math and Physics Files / Math / math misc

linearAlg

PDF · 15 pages · 137.9 KB

Excerpt of a chapter on linear algebra, apparently from lecture notes or a thesis on spectral graph theory, since it motivates the material by adjacency and incidence matrices. It covers characteristic polynomials, diagonal form, Hermitian and unitary matrices, Schur's lemma, the spectral theorem, the Jordan form and the minimum polynomial. The author appears to be someone other than Phil, and the text is noisy from font-encoding damage.

AI-written summary; may contain errors. This description is approximate.

Extracted text (machine-read; may contain errors)

Chapter 2 Linearalgebra 2.1 Eigenvalues and eigenvectors In this section, we shall concern with square matrices only, unless stated otherwise. As we have seen,theadjacencymatrixandincidencematrixofagrapharealgebraicstructureswhichcontain graphicalinformation. Thisisthemotivationforustodigdeeperintolinearalgebra. Eigenvalues andeigenvectors sayalotabout amatrix,hence wewouldhope thattheytellussomething aboutthe graph. 2.1.1 Preliminaries Theeigenvalues of a matrix /BTare the numbers /ALsuch that the equation /B4 /AL/C1 /A0 /BT /B5 /DC /BP /BChas a non-zero solution vector, in which case the solution vector /DCis the corresponding eigenvector . Since /DI/BCis always asolution, it would be unique if /CS/CT/D8/B4 /AL/C1 /A0 /BT /B5 /BI/BP/BC. Hence, the eigenvalues are solutions to the equation /CS/CT/D8/B4 /AL/C1 /A0 /BT /B5 /BP /BC, i.e. /D4/BT /B4 /AL /B5 /BP /BCwhere /D4/BT /B4 /AL /B5is thecharacteristic polynomial of /BT. Theorem 2.1. Let /AL/BD /BN/BM/BM/BM /BN/AL/D2be the eigenvalues of an /D2 /A2 /D2complex matrix /BT, then (i) /AL/BD /B7 /A1/A1/A1 /B7 /AL/D2 /BP /D8/D6 /BT( /BM/BP /C8/CX /CP/CX/CX). (ii) /AL/BD /BM/BM/BM /AL/D2 /BP /CS/CT/D8 /BT. Proof.Suppose/D4/BT /B4 /AL /B5/BP /CH/CX /B4 /AL /A0 /AL/CX /B5/BP /AL /D2/B7 /CR/D2 /A0 /BD /AL /D2 /A0 /BD/B7 /A1/A1/A1 /B7 /CR/BD /AL /B7 /CR/BC It is easy to see that /CR/D2 /A0 /BD /BP /A0 /B4 /C8/CX /CP/CX/CX /B5, proving (i). On the other hand, /CR/BC /BP/B4 /A0 /BD/B5 /D2/CS/CT/D8 /BT, proving (ii). 2.1.2 The diagonalform Proposition 2.2. Suppose the /D2 /A2 /D2matrix /BThas /D2linearly independent eigenvectors /DC/CX /BN /BD /AK/CX /AK /D2. Then if these vectors are columns of matrix /CB, it follows that /CB /A0 /BD/BT/CB /BP/A3where /A3is a diagonal matrix with /B4/A3/B5/CX/CX /BP /AL/CX. Proof.It’s easy to see that /BT/CB /BP /CB /A3. 9 Proposition 2.3. If /DC/BD /BN/BM/BM/BM /DC/CZare eigenvectors corresponding to distinct eigenvalues /AL/BD /BN/BM/BM/BM /AL/CZ, then /DC/BD /BN/BM/BM/BM /DC/CZare linearly independent. Proof.When /CZ /BP/BE, suppose /CR/BD /DC/BD /B7 /CR/BE /DC/BE /BP/BC. Multiplying by /BTgives /CR/BD /AL/BD /DC/BD /B7 /CR/BE /AL/BE /DC/BE /BP/BC. Subtracting /AL/BEtimes the previous equation we have/CR/BD /B4 /AL/BD /A0 /AL/BE /B5 /DC/BD /BP/BC Hence, /CR/BD /BP/BCsince /AL/BD /BI/BP /AL/BEand /DC/BD /BI/BP/BC. The general case can be done by induction. Proposition 2.4. If /AL/BD /BN/BM/BM/BM /AL/D2are eigenvalues of /BT, then /AL /CZ/BD /BN/BM/BM/BM /AL /CZ/D2are eigenvalues of /BT /CZ.I f /CB diagonalizes /BT,i.e. /CB /A0 /BD/BT/CB /BP/A3,then /CB /A0 /BD/BT /CZ/CB /BP/A3 /CZ Proof.Easy. 2.1.3 Symmetric and Hermitian matrices We’ll be working on /BV, so let’s ﬁx some terminologies. For /DC /BE /BV /D2, let /AM /DCdenotes its complex conjugate. The inner product of /DCand /DDis deﬁned to be/AM /DC /CC/DD /BP /AM /DC/BD /DD/BD /B7 /A1/A1/A1 /B7 /AM /DC/D2 /DD/D2 If /BTis any complex matrix, the Hermitian transpose /BT /A3of /BTis deﬁned to be /AM/BT /CC. Note that just as in the real matrix case, /B4 /BT/BU /B5 /A3/BP /BU /A3/BT /A3./BTissaidtobe Hermitian if /BT /BP /BT /A3.I f /BTcontains onlyrealentries, beingHermitianimplies being symmetric. Also notice that if /BTis Hermitian then the diagonal entries are reals. Lemma 2.5. Wehave 1. If /BTis Hermitian, then for all /DC /BE /BV /D2, /DC /A3/BT/DCis real. 2. Every eigenvalue of a Hermitian matrix if real.3. The eigenvectors of a Hermitian matrix, if come from distinct eigenvalues are orthogonal to one another. Proof.It is straightforward that 1./B4 /DC /A3/BT/DC /B5 /A3/BP /DC /A3/BT /A3/DC /A3/A3/BP /DC /A3/BT/DC. 2. /BT/DC /BP /AL/DCimplies /AL /BP /DC /A3/BT/DC /DC /A3/DC. 3. Suppose /BT/DC /BP /AL/BD /DC, /BT/DD /BP /AL/BE /DD, /AL/BD /BI/BP /AL/BEand /BT /BP /BT /A3./B4 /AL/BD /DC /B5 /A3/DD /BP/B4 /BT/DC /B5 /A3/DD /BP /DC /A3/BT/DD /BP /DC /A3/B4 /AL/BE /DD /B5 Hence, /B4 /AL/BD /A0 /AL/BE /B5 /DC /A3/DD /BP/BC. 10 2.1.4 Orthonormal and unitary matrices Arealmatrix /C9issaidtobe orthogonal if /C9 /CC/C9 /BP /C1. Acomplexmatrix /CDisunitaryif /CD /A3/CD /BP /C1. In other words, the columns of /CD(and /C9) are orthonormal. Clearly orthogonal is a special case of unitary. We state without proof a simple proposition. Proposition 2.6. Let /CDbe a unitary matrix, then (i) /B4 /CD/DC /B5 /A3/B4 /CD/DD /B5/BP /DC /A3/DD,and /CZ /CD/DC /CZ /BE/BP /CZ /DC /CZ /BE. (ii) Every eigenvalue /ALof /CDhas modulus /BD(i.e. /CY /AL /CY /BP/BD). (iii) Eigenvectors corresponding to distinct eigenvalues of /CDare orthonormal. (iv) If /CD /BCis another unitary matrix, then /CD/CD /BCis unitary. 2.1.5 The Spectral theorem and the Jordan form First, a few deﬁnitions. Two matrices /BTand /BUaresimilariff there is an invertible matrix /C5 such that /C5 /A0 /BD/BT/C5 /BP /BU. Proposition 2.7. If /BU /BP /C5 /A0 /BD/BT/C5, then /BTand /BUhave the same eigenvalues. An eigenvector /DC of /BTcorresponds to an eigenvector /C5 /A0 /BD/DCof /BU. Proof. /BT/DC /BP /AL/DCimplies /B4 /C5 /A0 /BD/BT /B5 /DC /BP /AL/C5 /A0 /BD/DC,o r /B4 /BU/C5 /A0 /BD/B5 /DC /BP /AL /B4 /C5 /A0 /BD/DC /B5. Another proof would go/CS/CT/D8/B4 /DC/C1 /A0 /BU /B5 /BP /CS/CT/D8/B4 /C5 /A0 /BD/B4 /DC/C1 /B5 /C5 /A0 /C5 /A0 /BD/BT/C5 /B5/BP /CS /CT /D8 /B4 /C5 /A0 /BD/B4 /DC/C1 /A0 /BT /B5 /C5 /B5/BP /CS /CT /D8 /B4 /DC/C1 /A0 /BT /B5 The vector space spanned by all eigenvectors corresponding to a particular eigenvalue /ALis called the eigenspace associated with /AL, or the /AL-eigenspace. We shall often use /CE/ALto denote this space if the underlying matrix is clear from context. Corollary 2.8. If /BTand /BUaresimilar, then thecorresponding eigenspaces of /BTand /BUhave the same dimension. Proof.Suppose /BU /BP /C5 /A0 /BD/BT/C5, then the mapping Ꜷ /BM /DC /AX /C5 /A0 /BD/DCis an invertible linear transformation from one eigenspace of /BTto the corresponding eigenspace of /BU. Lemma 2.9 (Schur’s lemma). For any /D2 /A2 /D2matrix /BT, there is a unitary matrix /CDsuch that/CD /A0 /BD/BT/CDis upper triangular. Proof.Note that the eigenvalues of /BTare then lying on the diagonal of /CD /A0 /BD/BT/CD. We show this by induction on /D2. The lemma holds when /D2 /BP /BD. When /D2 /BQ /BD, over /BV /BT musthaveatleastoneeigenvalue /AL/BD. Let /DC/BDbeacorresponding eigenvector. Use Gram-Schmidt processtogetasetoforthonormalvectors /CU /DC/BD /BN/DC/BE /BN/BM/BM/BM /BN/DC/D2 /CV. Let /CD/BDbethematrixwhosecolumns are this set of vectors in order. Clearly, 11 /BT/CD/BD /BP /CD/BD /BE/BI/BI/BI/BI/BG /AL/BD /A3 /A3 /BM/BM/BM /A3/BC /A3 /A3 /BM/BM/BM /A3/BC /A3 /A3 /BM/BM/BM /A3/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BC /A3 /A3 /BM/BM/BM /A3 /BF/BJ/BJ/BJ/BJ/BH,so /CD /A0 /BD/BD /BT/CD/BD /BP /BE/BI/BI/BI/BI/BG /AL/BD /A3 /A3 /BM/BM/BM /A3/BC /A3 /A3 /BM/BM/BM /A3/BC /A3 /A3 /BM/BM/BM /A3/BM/BM/BM/BM/BM/BM /BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BC /A3 /A3 /BM/BM/BM /A3 /BF/BJ/BJ/BJ/BJ/BH Now, let /BT /BC= /B4 /CD /A0 /BD/BD /BT/CD/BD /B5/BD/BD(crossing off row /BDand column /BDof /CD /A0 /BD/BD /BT/CD/BD). Then by induc- tion there exists an /B4 /D2 /A0 /BD/B5 /A2 /B4 /D2 /A0 /BD/B5unitary matrix /C5such that /C5 /A0 /BD/BT /BC/C5is upper triangular. Let /CD/BEbethe /D2 /A2 /D2matrixobtained byadding anewrowandnewcolumn to /C5withallnewen- tries equal /BCexcept /B4 /CD/BE /B5/BD/BD /BP/BD. Clearly /CD/BEisunitary and /CD /A0 /BD/BE /B4 /CD /A0 /BD/BD /BT/CD/BD /B5 /CD/BEisupper triangular. Letting /CD /BP /CD/BD /CD/BEcompletes the proof. The following theorem is one of the most important theorems in linear algebra, besides the Jordan form given next. Theorem 2.10 (Spectral theorem). Every real symmetric matrix can be diagonalized by an orthogonal matrix, and every Hermitian matrix can be diagonalized by a unitary matrix: (real case) /C9 /A0 /BD/BT/C9 /BP/A3(complex case) /CD /A0 /BD/BT/CD /BP/A3 Moreover, in both cases all eigenvalues are real. Proof.Therealcase follows fromthe complex case. Firstly, bySchur’s lemmathere isaunitary matrix /CDsuch that /CD /A0 /BD/BT/CDis upper triangular. Moreover,/B4 /CD /A0 /BD/BT/CD /B5 /A3/BP /CD /A3/BT /A3/B4 /CD /A0 /BD/B5 /A3/BP /CD /A0 /BD/BT/CD i.e. /CD /A0 /BD/BT/CDis also Hermitian. But an upper triangular Hermitian matrix must be diagonal. The realness of eigenvalues follow from Lemma 2.5. Theorem 2.11 (TheJordan form). If a matrix /BThas /D7linearly independent eigenvectors, then it is similar to a matrix which is in Jordan form with /D7square blocks on the diagonal:/C5 /A0 /BD/BT/C5 /BP /BE/BI/BI/BI/BI/BI/BG /BU/BD /BC /BC /BM/BM/BM /BC/BC /BU/BE /BC /BM/BM/BM /BC ... /BC.../BM/BM/BM /BC/BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM/BM /BM/BC /BC /BC /BM/BM/BM /BU/D7 /BF/BJ/BJ/BJ/BJ/BJ/BH Eachblockhasexactly one /BD-dimensional eigenspace, oneeigenvalue, and /BD’sjustabovethe diagonal:/BU/CY /BP /BE/BI/BI/BI/BI/BI/BG /AL/CY /BD /BC /BM/BM/BM /BC/BC /AL/CY /BD /BM/BM/BM /BC .../BC.../BM/BM/BM /BC/BM/BM /BM/BM /BM/BM/BM /BM/BM/BM /BM/BM /BM/BM/BM /BM /BD/BC /BC /BC /BM/BM/BM /AL/CY /BF/BJ/BJ/BJ/BJ/BJ/BH Proof.You could read Appendix B of [132]. The proof is not difﬁcult but tedious. The only thing we need to remember is that this theorem leads to the following nice corollary. I mightcome back to prove this if needed later on. 12 Corollary 2.12. The following hold 1. /D6 /CP/D2/CZ /B4 /BT /B5/BP /C8/AL/CX /BI/BP/BC /D1 /B4 /AL/CX /B5/B7 /D1 /B4/BC/B5 /A0 /CS/CX/D1 /B4 /CE/BC /B5. 2. If /BTis Hermitian, then the /AL-eigenspace has dimension equal the multiplicity of /ALas a solution to equation /D4/BT /B4 /DC /B5/BP /BC. 3. In fact, in Hermitian case /BV /D2/BP /C4/CX /CE/AL/CXwhere /CE/AL/CXdenotes the /AL/CX-eigenspace. Proof.This follows directly from the Jordan form and our observation in Corollary 2.8. We are mostly concerned with the dimensions of eigenspaces, so we can think about /A3instead of /BT. Similar matrices have the same rank, so /BTand its Jordan form have the same rank. The Jordan form of /BThas rank equal the total number of non-zero eigenvalues on the diagonal plus the number of /BD’s in the Jordan blocks corresponding to the eigenvalue /BC, which is exactly /D1 /B4/BC/B5 /A0/CS/CX/D1 /B4 /CE/BC /B5. When /BTisHermitian,itisdiagonalizable. Everyeigenvectorcorresponding toan occurrence ofaneigenvalue /ALislinearly independent fromallothers (including theeigenvector correspond- ing to another instance of the same /AL). 2.1.6 The minimum polynomial Ifound the following very nice theorem stated without proof ina book called “Matrix Methods” by Richard Bronson. I’m sure we could ﬁnd a proof in either [71] or [46], but I wasn’t able toget them from the library. Here I present my little proof. Theorem 2.13. Suppose/BU/CZis a Jordan block of size /B4 /D0 /B7/BD /B5 /A2 /B4 /D0 /B7/BD /B5corresponding to the eigenvalue /AL/CZof /BT, i.e./BU/CZ /BP /BE/BI/BI/BI/BI/BI/BG /AL/CZ /BD /BC /BM/BM/BM /BC/BC /AL/CZ /BD /BM/BM/BM /BC ........./BM/BM/BM.../BM/BM/BM/BM/BM/BM/BM/BM/BM /BM/BM/BM/BM/BM/BM/BM /BD/BC /BC /BC /BM/BM/BM /AL/CZ /BF/BJ/BJ/BJ/BJ/BJ/BH Then, for any polynomial /D5 /B4 /AL /B5 /BE /BV /CJ /AL /CL/D5 /B4 /BU/CZ /B5/BP /BE/BI/BI/BI/BI/BI/BI/BI/BG /D5 /B4 /AL/CZ /B5 /D5 /BC/B4 /AL/CZ /B5 /BD/AX /D5 /BC/BC/B4 /AL/CZ /B5 /BE/AX /BM/BM/BM /D5 /B4 /D0 /B5/B4 /AL/CZ /B5 /D0 /AX/BC /D5 /B4 /AL/CZ /B5 /D5 /BC/B4 /AL/CZ /B5 /BD/AX /BM/BM/BM /D5 /B4 /D0 /A0 /BD/B5/B4 /AL/CZ /B5 /B4 /D0 /A0 /BD/B5/AX ........./BM/BM/BM.../BM/BM /BM/BM/BM /BM/BM /BM/BM/BM /BM/BM/BM /BM/BM/BM /BM/BM/BM /BM/BM/BM /BM/BM/BM /D5 /BC/B4 /AL/CZ /B5 /BD/AX/BC /BC /BC /BM/BM/BM /D5 /B4 /AL/CZ /B5 /BF/BJ/BJ/BJ/BJ/BJ/BJ/BJ/BH(2.1) Proof.We only need to consider the case /D5 /B4 /DC /B5 /BP /DC /CY/BN/CY /AL /BC, and then extend linearly into all polynomials. The case /CY /BP /BCis clear. Suppose equation (2.1) holds for /D5 /B4 /DC /B5 /BP /DC /CY /A0 /BD/BN/CY /AL /BD. Then, when /D5 /B4 /DC /B5/BP /DC /CYwe have 13 /D5 /B4 /BU/CZ /B5 /BP /BU /CY /A0 /BD/CZ /BU/CZ/BP /BE/BI/BI/BI/BI/BI/BI/BG /AL /CY /A0 /BD/CZ /A0/CY /A0 /BD/BD /A1/AL /CY /A0 /BE/CZ /A0/CY /A0 /BD/BE /A1/AL /CY /A0 /BF/CZ /BM/BM/BM /A0/CY /A0 /BD/D0 /A1/AL /CY /A0 /D0 /A0 /BD/CZ/BC /AL /CY /A0 /BD/CZ /A0/CY /A0 /BD/BD /A1/AL /CY /A0 /BE/CZ /BM/BM/BM /A0/CY /A0 /BD/D0 /A0 /BD /A1/AL /CY /A0 /D0/CZ........./BM/BM/BM.../BM /BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM/BM /BM /A0/CY /A0 /BD/BD /A1/AL /CY /A0 /BE/CZ/BC /BC /BC /BC /AL /CY /A0 /BD/CZ /BF/BJ/BJ/BJ/BJ/BJ/BJ/BH /BE/BI/BI/BI/BI/BI/BG /AL/CZ /BD /BC /BM/BM/BM /BC/BC /AL/CZ /BD /BM/BM/BM /BC ........./BM/BM/BM.../BM/BM/BM/BM/BM/BM/BM/BM/BM/BM /BM/BM/BM/BM/BM/BM /BD/BC /BC /BC /BM/BM/BM /AL/CZ /BF/BJ/BJ/BJ/BJ/BJ/BH/BP /BE/BI/BI/BI/BI/BI/BI/BG /AL /CY/CZ /A0/CY/BD /A1/AL /CY /A0 /BD/CZ /A0/CY/BE /A1/AL /CY /A0 /BE/CZ /BM/BM/BM /A0/CY/D0 /A1/AL /CY /A0 /D0/CZ/BC /AL /CY/CZ /A0/CY/BD /A1/AL /CY /A0 /BD/CZ /BM/BM/BM /A0/CY/D0 /A0 /BD /A1/AL /CY /A0 /D0 /B7/BD/CZ........./BM/BM/BM.../BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM/BM /A0/CY/BD /A1/AL /CY /A0 /BD/CZ/BC /BC /BC /BC /AL /CY/CZ /BF/BJ/BJ/BJ/BJ/BJ/BJ/BH Theminimum polynomial /D1 /B4 /AL /B5of an /D2 /A2 /D2matrix /BTover a complex vector space /CEis the monic polynomial of lowest degree such that /D1 /B4 /BT /B5/BP /BC. Lemma 2.14. With the terminologies just stated, we have 1. /D1 /B4 /AL /B5divides /D4/BT /B4 /AL /B5. 2. Every root of /D4/BT /B4 /AL /B5is also a root of /D1 /B4 /AL /B5. 3. /BTis diagonalizable iff /D1/BT /B4 /AL /B5has no multiple roots. 4. If /CU /AL/CX /CV /D7/CX /BP/BDare distinct eigenvalues of a Hermitian matrix /BT, then /D1 /B4 /AL /B5/BP /C9/D7/CX /BP/BD /B4 /AL /A0 /AL/CX /B5. Proof. 1. /D1 /B4 /AL /B5must divide every polynomial /D5 /B4 /AL /B5with /D5 /B4 /BT /B5/BP/BC, since otherwise /D5 /B4 /AL /B5/BP/CW /B4 /AL /B5 /D1 /B4 /AL /B5/B7 /D6 /B4 /AL /B5implies /D6 /B4 /BT /B5 /BP /BCwhile /D6 /B4 /AL /B5has smaller degree than /D1 /B4 /AL /B5. On the other hand, by Cayley-Hamilton Theorem, /D4/BT /B4 /BT /B5/BP /BC. 2. Notice that /BT/DC /BP /AL/DCimplies /BT /CX/DC /BP /AL /CX/DC. Thus for any eigenvalue /AL/CZof /BTwith corre- sponding eigenvector /DC, /DI/BC/BP /D1 /B4 /BT /B5 /DC /BP /C8/CX /CR/CX /BT /CX/DC /BP /C8/CX /CR/CX /AL /CX/CZ /DC /BP /D1 /B4 /AL/CZ /B5 /DC. This implies/AL/CZis a root of /D1 /B4 /AL /B5. 3. /B4 /B5 /B5. Suppose /C5 /A0 /BD/BT/C5 /BP /A3for some invertible matrix /C5, and /AL/BD /BN/BM/BM/BM /BN/AL/D7are distinct eigenvalues of /BT. By1and2,weonlyneedtoshow /BTisarootof /D1/BT /B4 /AL /B5/BP /C9/D7/CX /BP/BD /B4 /AL /A0 /AL/CX /B5. It is easy to see that for any polynomial /D5 /B4 /AL /B5, /D5 /B4 /BT /B5 /BP /C5/D5 /B4/A3/B5 /C5 /A0 /BD. In particular, since/D4/BT /B4/A3/B5 /BP /BCwe get the desired result./B4 /B4 /B5. Nowweassume /D1/BT /B4 /AL /B5hasnomultipleroot,whichimplies /D1/BT /B4 /AL /B5/BP /C9/D7/CX /BP/BD /B4 /AL /A0 /AL/CX /B5. By Proposition 2.2, we shall show that /BThas /D2linearly independent eigenvectors. Firstly, notice that if the Jordan form of /BTis/C5 /A0 /BD/BT/C5 /BP /BE/BI/BI/BI/BI/BI/BG /BU/BD /BC /BC /BM/BM/BM /BC/BC /BU/BE /BC /BM/BM/BM /BC ... /BC.../BM/BM/BM /BC/BM /BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM/BM /BM/BM /BM/BM /BM/BM/BM/BC /BC /BC /BM/BM/BM /BU/D7 /BF/BJ/BJ/BJ/BJ/BJ/BH 14 then, for any /D5 /B4 /AL /B5 /BE /BV /CJ /AL /CLwe have/C5 /A0 /BD/D5 /B4 /BT /B5 /C5 /BP /D5 /BC/BU/BU/BU/BU/BU/BS /BE/BI/BI/BI/BI/BI/BG /BU/BD /BC /BC /BM/BM/BM /BC/BC /BU/BE /BC /BM/BM/BM /BC ... /BC.../BM/BM/BM /BC/BM /BM /BM/BM /BM/BM /BM/BM /BM /BM/BM /BM/BM /BM/BM /BM /BM/BM /BM/BM /BM/BM/BC /BC /BC /BM/BM/BM /BU/D7 /BF/BJ/BJ/BJ/BJ/BJ/BH /BD/BV/BV/BV/BV/BV/BT/BP /BE/BI/BI/BI/BI/BI/BG /D5 /B4 /BU/BD /B5 /BC /BC /BM/BM/BM /BC/BC /D5 /B4 /BU/BE /B5 /BC /BM/BM/BM /BC ... /BC.../BM/BM/BM /BC/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM /BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM/BM /BM/BM/BM/BM/BM/BM/BM/BM/BC /BC /BC /BM/BM/BM /D5 /B4 /BU/D7 /B5 /BF/BJ/BJ/BJ/BJ/BJ/BH So, /C9/D7/CX /BP/BD /B4 /BT /A0 /AL/CX /C1 /B5 /BP /BCimplies /C9/D7/CX /BP/BD /B4 /BU/CZ /A0 /AL/CX /C1 /B5 /BP /BCfor all /CZ /BP /BD /BN/BM/BM/BM /BN/D7.I f /BTdoes not have /D2linearly independent eigenvectors, one of the blocks /BU/CZmust have size /BQ /BD. Applying Theorem 2.13 with /D5 /B4 /AL /B5 /BP /C9/D7/CX /BP/BD /B4 /AL /A0 /AL/CX /B5, we see that /D5 /B4 /BU/CZ /B5does not vanish since /D5 /BC/B4 /AL/CX /B5 /BI/BP/BC /BN /BK /CX /BE /CJ /D7 /CL. Contradiction! 4. Follows from 3 since a Hermitian matrix is diagonalizable. 2.2 Positivedeﬁnite matrices The purpose of this section is to develop several important background facts. The ﬁrst is the necessary and sufﬁcient conditions for a real symmetric matrix /BT(or Hermitian in general) to bepositive deﬁnite . This is essentially the conditions for a quadratic form on /CA /D2to have a minimum at some point. The second is the Sylvester law of inertia . Another is the Rayleigh’s principle. Lastly, some minimax and maximin principles related to the Rayleigh’s quotient shall be developed. These principles eventually lead to the theorem about interlacing of eigenvalues , which is very useful when our matrix is the adjacency matrix of a graph. 2.2.1 Some analysis Let us ﬁrst recall two key theorems from real analysis, stated without proofs. For /CU /BM /CA /D2/AX /CA, if for some /CP /BE /CA /D2 /BS/CU /BS/DC/CX /B4 /CP /B5/BP /BC, then /CPis called a stationary point of /CU. Theorem2.15(Thesecondderivative test). Suppose /CU /BM /CA /D2/AX /CAanditspartialderivatives up toandincludingorder /BEarecontinuousinaball /BU /B4 /CP/BN /D6 /B5(centeredat /CP /BE /CA /D2,radius /D6). Suppose that /CUhas a stationary point at /CP.F o r /CW /BP/B4 /CW/BD /BN/BM/BM/BM /BN/CW/D2 /B5, deﬁne /A1 /CU /B4 /CP/BN /CW /B5/BP /CU /B4 /CP /B7 /CW /B5 /A0 /CU /B4 /CP /B5; also deﬁne/C9 /B4 /CW /B5/BP /BD /BE/AX /D2/CG/CX/BN/CY /BP/BD /BS /BE/CU /BS/DC/CX /BS/DC/CY /B4 /CP /B5 /CW/CX /CW/CY then, 1. If /C9 /B4 /CW /B5 /BQ /BCfor /CW /BI/BP/BC, then /CUhas a strict local minimum at /CP. 2. If /C9 /B4 /CW /B5 /BO /BCfor /CW /BI/BP/BC, then /CUhas a strict local maximum at /CP. 15 3. If /C9 /B4 /CW /B5has a positive maximum and a negative minimum, then /A1 /CU /B4 /CP/BN /CW /B5changes sign in any ball /BU /B4 /CP/BN /AQ /B5such that /AQ/BO/D6. Note.(3.) says that at any close neighborhood of /CP, there are some points /CQand /CRsuch that/CU /B4 /CQ /B5 /BQ/CU /B4 /CP /B5and /CU /B4 /CR /B5 /BO/CU /B4 /CP /B5. Example2.16. Letuslookataquadraticform /BY /B4 /DC/BD /BN/BM/BM/BM /BN/DC/D2 /B5withallrealcoefﬁcients,i.e. every term of /BYhas degree at most /BE. Let /BTbe the matrix deﬁned by /CP/CX/CY /BP /BS /BE/BY/BP /BS /DC/CX /BS/DC/CY. Clearly, /BT is a real symmetric matrix. For any vector /CW /BE /CA /D2,/CW /CC/BT/CW /BP /A2/CW/BD /CW/BE /BM/BM/BM /CW/D2 /A3 /BE/BI/BI/BG /CP/BD/BD /CP/BD/BE /BM/BM/BM /CP/BD /D2/CP/BE/BD /CP/BE/BE /BM/BM/BM /CP/BE /D2/BM /BM/BM/BM/BM/BM /BM/BM/BM/BM /BM/BM/BM/BM/BM /BM/BM/BM/BM/CP/D2 /BD /CP/D2 /BE /BM/BM/BM /CP/D2/D2 /BF/BJ/BJ/BH /BE/BI/BI/BI/BG /CW/BD/CW/BE .../CW/D2 /BF/BJ/BJ/BJ/BH/BP /D2/CG/CX/BN/CY /BP/BD /CP/CX/CY /CW/CX /CW/CY/BP /BE /C9 /B4 /CW /B5 So, /BY /B4 /DC/BD /BN/BM/BM/BM /BN/DC/D2 /B5hasaminimumat /B4/BC /BN/BM/BM/BM /BN /BC/B5(whichisastationarypointof /BY)iff /CW /CC/BT/CW /BQ/BCfor all /CW /BI/BP/BC. Deﬁnition 2.17. A non-singular /D2 /A2 /D2Hermitian matrix /BTis said to be positive deﬁnite if/DC /A3/BT/DC /BQ /BCfor all non zero vector /DC /BE /BV /D2. /BTispositive semideﬁnite if we only require /DC /A3/BT/DC /AL/BC. The terms negative deﬁnite andnegative semideﬁnite can be deﬁned similarly. Note.Continuing with our example, clearly /BY /B4 /DC/BD /BN/BM/BM/BM /BN/DC/D2 /B5has a minimum at /B4/BC /BN/BM/BM/BM /BN /BC/B5iff /BTis positive deﬁnite. Also, since we already showed that if /BTis Hermitian, then /DC /A3/BT/DCis real, the deﬁnitions given above make sense. A function /CUis in /BV /BDon some domain /BW /AI /CA /D2if /CUand all its ﬁrst order derivatives are continuous on /BW.F o r /CP /BE /BW, /BH /CU /B4 /CP /B5/BM /BP/B4 /BS/CU /BS/DC/BD /B4 /CP /B5 /BN/BM/BM/BM /BN /BS/CU /BS/DC/D2 /B4 /CP /B5/B5. Theorem 2.18 (Lagrange’s multiplier rule). Suppose that /CU/BN /B3/BD /BN/BM/BM/BM /BN/B3/CZare /BV /BDfunctions on an open set /BWin /CA /D2containing a point /CP, that the vectors /BH /B3/BD /B4 /CP /B5 /BN/BM/BM/BM /BN /BH /B3/CZ /B4 /CP /B5are linearly independent, and that /CUtakes on its minimum among all points of /BW/BCat /DC/BC, where /BW/BCis the subset of /BWso that for all /DC /BE /BW/BC,/B3/CX /B4 /DC/BD /BN/BM/BM/BM /BN/DC/D2 /B5/BP/BC /BN /CX /BP/BD /BN/BM/BM/BM /BN/CZ Then, if /BY /BM /CA /D2 /B7 /CZ/AX /CAis deﬁned to be/BY /B4 /DC/BN /AL /B5/BP /CU /B4 /DC /B5 /A0 /CZ/CG/CX /BP/BD /AL/CX /B3/CX /B4 /DC /B5 then there exists /AL /BC/BE /CA /CZsuch that/BS/BY /BS/DC/CX /B4 /CP/BN /AL /BC/B5 /BP /BC /CX /BP/BD /BN/BM/BM/BM /BN/D2/BS/BY /BS/AL /BC/CY /B4 /CP/BN /AL /BC/B5 /BP /BC /CX /BP/BD /BN/BM/BM/BM /BN/CZ 16 Note.This theorem essentially says that the maxima (or minima) of /CUsubject to the side con- ditions /B3/BD /BP /A1/A1/A1 /BP /B3/CZ /BP/BCare among the maxima (or minima) of the function /BYwithout any constraints. Example2.19. Toﬁndthe maximumof /CU /B4 /DC /B5/BP /DC/BD /B7/BF /DC/BE /A0 /BE /DC/BFonthe sphere /BD/BG /A0 /B4 /DC /BE/BD /B7 /DC /BE/BE /B7/DC /BE/BF /B5/BP /BC,w el e t/BY /B4 /DC/BN /AL /B5/BP /DC/BD /B7/BF /DC/BE /A0 /BE /DC/BF /B7 /AL /B4 /DC /BE/BD /B7 /DC /BE/BE /B7 /DC /BE/BF /A0 /BD/BG/B5 Then, /BS/BY /BS/DC/BD /BP /BD/B7 /BE /AL/DC/BD, /BS/BY /BS/DC/BE /BP /BF/B7 /BE /AL/DC/BE, /BS/BY /BS/DC/BF /BP /A0 /BE/B7/BE /AL/DC/BF, and /BS/BY /BS/AL /BP /DC /BE/BD /B7 /DC /BE/BE /B7 /DC /BE/BF /A0 /BD/BG. Solving /BS/BY /BS/DC/CX /BP/BCweobtaintwosolutions /B4 /DC/BN /AL /B5/BP /B4 /BD /BN /BF /BN /A0 /BE /BN /A0 /BD /BP /BE/B5and /B4 /A0 /BD /BN /A0 /BF /BN /BE /BN /BD /BP /BE/B5. Which of these solutions give a maximum or a minimum ? We apply the second derivative test. Allsecond derivatives of/BYare /BCexcept /BS /BE/BY/BP /BS /DC /BE/BD /BP /BS /BE/BY/BP /BS /DC /BE/BE /BP /BS /BE/BY/BP /BS /DC /BE/BF /BP /BE /AL. /C9 /B4 /CW /B5 /BP/BE /AL /B4 /CW /BE/BD /B7 /CW /BE/BE /B7 /CW /BE/BF /B5has the same sign as /AL. Hence, the ﬁrst solution gives the maximum value of/BD/BG, the second solution gives the minimum value of /A0 /BD/BF. 2.2.2 Conditions for positive-deﬁniteness Nowweareready tospecify the necessary andsufﬁcient conditions foraHermitianmatrix tobe positive deﬁnite, or positive semideﬁnite for that matter. Theorem 2.20. Each of the following tests is a necessary and sufﬁcient condition for the real symmetric matrix /BTto be positive deﬁnite. (a) /DC /CC/BT/DC /BQ /BCfor all non-zero vector /DC. (b) All the eigenvalues of /BTsatisfy /AL/CX /BQ /BC. (c) All the upper left submatrices /BT/CZhave positive determinants. (d) IfweapplyGaussianeliminationon /BTwithoutrowexchanges, allthepivotssatisfy /D4/CX /BQ /BC. Note.(a) and (b) hold for Hermitian matrices also. Proof. /B4 /CP /B5 /CQ /B5. Suppose /DC/CXis a unit /AL/CX-eigenvector, then /BC /BO/DC /CC/CX /BT/DC/CX /BP /DC /CC/CX /AL/CX /DC/CX /BP /AL/CX./B4 /CQ /B5 /CP /B5. Since /BTisrealsymmetric,ithasafullsetoforthonormaleigenvectors /CU /DC/BD /BN/BM/BM/BM /BN/DC/D2 /CV by the Spectral theorem. For each /DC /BE /CA /D2,suppose /DC /BP /CR/BD /DC/BD /B7 /A1/A1/A1 /B7 /CR/D2 /DC/D2,then/BT/DC /BP /BT /B4 /CR/BD /DC/BD /B7 /A1/A1/A1 /B7 /CR/D2 /DC/D2 /B5/BP /CR/BD /AL/BD /DC/BD /B7 /A1/A1/A1 /B7 /CR/D2 /AL/D2 /DC/D2 Because the /DC/CXare orthonormal, we get/DC /CC/BT/DC /BP /B4 /CR/BD /DC /CC/BD /B7 /A1/A1/A1 /B7 /CR/D2 /DC /CC/D2 /B5/B4 /CR/BD /AL/BD /DC/BD /B7 /A1/A1/A1 /B7 /CR/D2 /AL/D2 /DC/D2 /B5/BP /AL/BD /CR /BE/BD /B7 /A1/A1/A1 /B7 /AL/D2 /CR /BE/D2 Thus, every /AL/CX /BQ /BCimplies /DC /CC/BT/DC /BQ /BC./B4 /CP /B5 /CR /B5. We know /CS/CT/D8 /BT /BP /AL/BD /BM/BM/BM /AL/D2 /BQ /BC. To prove the same result for all /BT/CZ, we look at a non-zero vector /DCwhose last /D2 /A0 /CZcomponents are /BC,then/DC /CC/BT/DC /BP /A2/DC /CC/CZ /BC /A3 /AK/BT/CZ /A3/A3 /A3 /AL/AK/DC/CZ/BC /AL/BP /DC /CC/CZ /BT/CZ /DC /CZ/CS/CT/D8 /BT/CZ /BQ /BCfollows by induction./B4 /CR /B5 /CS /B5. Without row exchanges, the pivot /CS/CZin Gaussian elimination is /CS/CT/D8 /BT/CZ /BP /CS/CT/D8 /BT/CZ /A0 /BD. This can also be proved easily by induction. 17 /B4 /CS /B5 /CP /B5. Gaussian elimination givesusa /C4/BW /CDfactorization of /BTwherealldiagonal entries of /C4and /CDare /BD’s. Also, the diagonal entries /CS/CXof /BWis exactly the /CX /D8/CWpivot /D4/CX. The fact that /BT is symmetric implies /C4 /BP /CD /CC,hence /BT /BP /C4/BW /C4 /CC,which gives/DC /CC/BT/DC /BP/B4 /DC /CC/C4 /B5/B4 /BW /B5/B4 /C4 /CC/DC /B5/BP /CS/BD /B4 /C4 /CC/DC /B5 /BE/BD /B7 /CS/BE /B4 /C4 /CC/DC /B5 /BE/BE /B7 /A1/A1/A1 /B7 /CS/D2 /B4 /C4 /CC/DC /B5 /BE/D2 Since /C4is fully ranked, /C4 /CC/DC /BI/BP/BCwhenever /DC /BI/BP/BC. So the pivots /CS/CX /BQ /BCimplies /DC /CC/BT/DC /BQ /BCfor all non-zero vectors /DC. 2.2.3 The Rayleigh’squotient and the variationalcharacterizations For a Hermitian matrix /BT, the following is known as the Rayleigh’s quotient :/CA /B4 /DC /B5/BP /DC /A3/BT/DC /DC /A3/DC Theorem 2.21 (Rayleigh-Ritz). Suppose /AL/BD /AL /AL/BE /AL /A1/A1/A1 /AL /AL/D2are the eigenvalues of a real symmetric matrix /BT. Then, the quotient /CA /B4 /DC /B5is maximized at any /AL/BD-eigenvector /DC /BP /DC/BDwith maximum value /AL/BD. /CA /B4 /DC /B5is minimized at any /AL/D2-eigenvector /DC /BP /DC/D2with minimum value /AL/D2, Proof.Let /C9be a matrix whose columns are a set of orthonormal eigenvectors /CU /DC/BD /BN/BM/BM/BM /BN/DC/D2 /CVof/BTcorresponding to /AL/BD /BN/BM/BM/BM /BN/AL/D2, respectively. Writing /DCas a linear combination of columns of/C9: /DC /BP /C9/DD,then since /C9 /CC/BT/C9 /BP/A3wehave/CA /B4 /DC /B5/BP /DC /CC/BT/DC /DC /CC/DC /BP /B4 /C9 /CC/DD /B5 /CC/BT /B4 /C9 /CC/DD /B5 /B4 /C9 /CC/DD /B5 /CC/B4 /C9 /CC/DD /B5 /BP /DD /CC/A3 /DC /DD /CC/DD /BP /AL/BD /DD /BE/BD /B7 /A1/A1/A1 /B7 /AL/D2 /DD /BE/D2 /DD /BE/BD /B7 /A1/A1/A1 /B7 /DD /BE/D2 Hence,/AL/BD /AL /CA /B4 /DC /B5/BP /AL/BD /DD /BE/BD /B7 /A1/A1/A1 /B7 /AL/D2 /DD /BE/D2 /DD /BE/BD /B7 /A1/A1/A1 /B7 /DD /BE/D2 /AL /AL/D2 Moreover, /CA /B4 /DC /B5/BP /AL/BDwhen /DD/BD /BI/BP/BCand /DD/CX /BP/BC /BN /BK /CX/BQ /BD. Thismeans /DC /BP /C9/DDisa /AL/BD-eigenvector. The case /CA /B4 /DC /B5/BP /AL/D2case is proved similarly. An equivalent statement of the principle is as follows. Corollary 2.22. Suppose /AL/BD /AL /AL/BE /AL/A1 /A1 /A1 /AL /AL/D2are the eigenvalues of a real symmetric matrix/BT. Over all non-zero unit vectors /DC /BE /CA /D2, /DC /CC/BT/DCis maximized at a unit /AL/BD-eigenvector, with maximum value /AL/BD, and minimized at a unit /AL/D2-eigenvector, with minimum value /AL/D2. Rayleigh’s principle essentially states that/AL/BD /BP/D1 /CP /DC/DC /BE /CA /D2 /CA /B4 /DC /B5and /AL/D2 /BP /D1/CX/D2/DC /BE /CA /D2 /CA /B4 /DC /B5 Whatabouttherestoftheeigenvalues ? Hereisasimpleanswer,statedwithoutproof. Theproof is simple enough. Theorem 2.23. Suppose /AL/BD /AL /AL/BE /AL/A1 /A1 /A1 /AL /AL/D2are the eigenvalues of a Hermitian matrix /BT, and/D9/BD /BN/BM/BM/BM /BN/D9/D2are the corresponding set of orthonormal eigenvectors. Then,/AL/CZ /BP /D1/CP/DC/BC /BI/BP /DC /BE /BV /D2/DC /BR /D9/BD /BN/BM/BM/BM /BN/D9/CZ /A0 /BD /CA/BT /B4 /DC /B5/AL/CZ /BP /D1/CX/D2/BC /BI/BP /DC /BE /BV /D2/DC /BR /D9/CZ /B7/BD /BN/BM/BM/BM /BN/D9/D2 /CA/BT /B4 /DC /B5 18 Thetheoremhas apitfall that sometimewedon’t knowtheeigenvectors. Thefollowing gen- eralization of Rayleigh’s principle, sometime referred to as the minimax and maximin principles for eigenvalues , ﬁll the hole by not requiring us to know that eigenvectors. Theorem 2.24 (Courant-Fisher). Let /CE/CZbe the set of all /CZ-dimensional subspaces of /BV /D2. Let/AL/BD /AL /AL/BE /AL/A1 /A1 /A1 /AL /AL/D2be the eigenvalues of a Hermitian matrix /BT. Then,/AL/CZ /BP /D1/CP/DC/CB /BE /CE/CZ /BE/BG/D1/CX/D2/DC /BE /CB/DC /BI/BP/BC /CA /B4 /DC /B5 /BF/BH/BP /D1/CX/D2/CB /BE /CE/D2 /A0 /CZ /B7/BD /BE/BG/D1/CP/DC/DC /BE /CB/DC /BI/BP/BC /CA /B4 /DC /B5 /BF/BH Note.It should be noted that the previous two theorems are often referred to as the variational characterization of the eigenvalues. Proof.Let /CD /BP/CJ /D9/BD /BN/D9/BE /BN/BM/BM/BM /BN/D9/D2 /CLbe the unitary matrix with unit eigenvectors /D9/BD /BN/BM/BM/BM /BN/D9/D2corre- sponding to the eigenvalues /AL/BD /BN/BM/BM/BM /BN/AL/D2. Let us ﬁrst ﬁx /CB /BE /CE/CZand let /CB /BCbe the image of /CB under theinvertible linear transformation represented by /CD /A3. Obviously, /CS/CX/D1 /B4 /CB /BC/B5/BP /CZ.W eh a v e already known that /CA /B4 /DC /B5is bounded, so it is safe to say the following, with /DC /BI/BP/BC /BN/DD /BI/BP/BCbeing implicit./CX/D2/CU/DC /BE /CB /CA /B4 /DC /B5 /BP /CX/D2/CU/DC /BE /CB /DC /A3/BT/DC /DC /A3/DC/BP /CX/D2/CU/DC /BE /CB /B4 /CD /A3/DC /B5 /A3/A3/B4 /CD /A3/DC /B5 /B4 /CD /A3/DC /B5 /A3/B4 /CD /A3/DC /B5/BP /CX/D2/CU/DD /BE /CB /BC /DD /A3/A3 /DD /DD /A3/DD/AK /CX/D2/CU/DD /BE /CB /BC/DD/BD /BP /A1/A1/A1 /BP /DD/CZ /A0 /BD /BP/BC /DD /A3/A3 /DD /DD /A3/DD/BP /CX/D2/CU/DD /BE /CB /BC/DD/BD /BP /A1/A1/A1 /BP /DD/CZ /A0 /BD /BP/BC /AL/BD /DD /BE/BD /B7 /A1/A1/A1 /B7 /AL/D2 /DD /BE/D2 /DD /BE/BD /B7 /A1/A1/A1 /B7 /DD /BE/D2/BP /CX/D2/CU/DD /BE /CB /BC/DD/BD /BP /A1/A1/A1 /BP /DD/CZ /A0 /BD /BP/BC /AL/CZ /DD /BE/CZ /B7 /A1/A1/A1 /B7 /AL/D2 /DD /BE/D2 /DD /BE/CZ /B7 /A1/A1/A1 /B7 /DD /BE/D2/AK /AL/CZ The inequality in line 4 is justiﬁed by the fact that there is a non zero vector /DD /BE /CB /BCsuch that/DD/BD /BP /A1/A1/A1 /BP /DD/CZ /A0 /BD /BP/BC. Togetthisvector, put /CZbasisvectors of /CB /BCintotherowsofa /CZ /A2 /D2matrix and do Gaussian elimination. Now, /CBwas chosen arbitrarily, so it is also true that/D7/D9/D4/CB /BE /CE/CZ /CX/D2/CU/DC /BE /CB /CA /B4 /DC /B5 /AK /AL/CZ Moreover, /CA /B4 /D9/CZ /B5 /BP /B4 /CD /A3/D9/CZ /B5 /A3/A3/B4 /CD /A3/D9/CZ /B5 /BP /CT/CZ /A3 /CT/CZ /BP /AL/CZ. Thus, the inﬁmum and supremum can be changed to minimum and maximum, and the inequality can be changed to equality. Theother equality can be proven similarly. 19 Thistheorem hasaveryimportant andbeautiful corollary, called the Interlacing ofeigenval- uesto be presented in the next section. Let us introduce a simple corollary. Corollary 2.25. Let /BT /BE /C5/D2be Hermitian, let /CZbe a given integer with /BD /AK /CZ /AK /D2, let/AL/BD /AL /AL/BE /AL /A1/A1/A1 /AL /AL/D2be the eigenvalues of /BT, and let /CB/CZbe a given /CZ-dimensional subspace of/BV /D2. The following hold (a) If there exists /CR/BDsuch that /CA /B4 /DC /B5 /AK /CR/BDfor all /DC /BE /CB/CZ,then /CR/BD /AL /AL/D2 /A0 /CZ /B7/BD /AL/A1 /A1 /A1 /AL /AL/D2. (b) If there exists /CR/BEsuch that /CA /B4 /DC /B5 /AL /CR/BEfor all /DC /BE /CB/CZ,then /AL/BD /AL/A1 /A1 /A1 /AL /AL/CZ /AL /CR/BE. Proof.It is almost straightforward from the Courant-Fisher theorem that (a)/CR/BD /AL /D1/CP/DC/BC /BI/BP /DC /BE /CB/CZ /CA /B4 /DC /B5 /AL /D1/CX/D2/CS/CX/D1 /B4 /CB /B5/BP /D2 /A0 /B4 /D2 /A0 /CZ /B7/BD/B5/B7/BD /D1/CP/DC/BC /BI/BP /DC /BE /CB /CA /B4 /DC /B5/BP /AL/D2 /A0 /CZ /B7/BD (b)/CR/BE /AK /D1/CX/D2/BC /BI/BP /DC /BE /CB/CZ /CA /B4 /DC /B5 /AK /D1/CP/DC/CS/CX/D1 /B4 /CB /B5/BP /CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB /CA /B4 /DC /B5/BP /AL/CZ 2.2.4 Applicationsof the variationalcharacterizations Throughout therestofthissection, weuse /C5/D2todenote thesetofall /D2 /A2 /D2matrices over /BV(i.e./C5/D2 /BP /BV /D2 /BE). The ﬁrst application of the variational characterization is a theorem by Weyl. Theorem 2.26 (Weyl, year?). Let /BT/BN /BU /BE /C5/D2be Hermitian and the eigenvalues /AL/CX /B4 /BT /B5 /BN/AL/CX /B4 /BU /B5, and /AL/CX /B4 /BT /B7 /BU /B5bearranged indecreasing order,i.e. /AL/BD /B4 /CG /B5 /AL/A1 /A1 /A1 /AL /AL/D2 /B4 /CG /B5,for /CG /BP /BT/BN /BU /BN /BT /B7/BU. For each /CZ /BP/BD /BN /BE /BN/BM/BM/BM /BN/D2we have/AL/CZ /B4 /BT /B5/B7 /AL/BD /B4 /BU /B5 /AL /AL/CZ /B4 /BT /B7 /BU /B5 /AL /AL/CZ /B4 /BT /B5/B7 /AL/D2 /B4 /BU /B5 Proof.By noticing that /AL/BD /B4 /BU /B5 /AL /CA/BU /B4 /DC /B5 /AL /AL/D2 /B4 /BU /B5, for all /DC /BE /BV /D2,weha v e/AL/CZ /B4 /BT /B7 /BU /B5 /BP /D1/CP/DC/CB /BE /CE/CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB /DC /A3 /B4 /BT /B7 /BU /B5 /DC /DC /A3 /DC/BP /D1/CP/DC/CB /BE /CE/CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB /B4 /CA/BT /B4 /DC /B5/B7 /CA/BU /B4 /DC /B5/B5/AL /D1/CP/DC/CB /BE /CE/CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB /B4 /CA/BT /B4 /DC /B5/B7 /AL/D2 /B4 /BU /B5/B5/BP /AL/CZ /B4 /BT /B5/B7 /AL/D2 /B4 /BU /B5 The other direction is proven similarly. Notice that if /BUis positive semideﬁnite, then /AL/BD /B4 /BU /B5 /AL /BC. We have the following trivial corollary, called the monotonicity theorem since it says that the eigenvalues keep increasing as positive semideﬁnite matrices are added. 20 Corollary 2.27 (Monotonicity Theorem). Suppose /BTand /BUare Hermitian with /BUbeing posi- tive semideﬁnite, and the eigenvalues of /BTand /BT /B7 /BUsorted in decreasing order, then/AL/CZ /B4 /BT /B5 /AK /AL/CZ /B4 /BT /B7 /BU /B5 Theorem 2.28 (Interlacing of eigenvalues). Let /BTbe a Hermitian matrix with eigenvalues/AL/BD /AL /AL/BE /AL/A1 /A1 /A1/AL /AL/D2. Let /BUbe the matrix obtained from /BTby removing row /CXand column /CX, for any /CX /BE /CJ /D2 /CL. Suppose /BUhas eigenvalues /AI/BD /AL/A1 /A1 /A1 /AL /AI/D2 /A0 /BD, then/AL/BD /AL /AI/BD /AL /AL/BE /AL /AI/BE /AL/A1 /A1 /A1 /AL /AI/D2 /A0 /BD /AL /AL/D2 Note.A proof of this theorem using Spectral Decomposition Theorem can also be given, but it is not very instructive. Proof.Wecan safely assume that /CX /BP /D2for theease ofpresentation. Wewouldlike to showthat as /BD /AK /CZ /AK /D2 /A0 /BD, /AL/CZ /AL /AI/CZ /AL /AL/CZ /B7/BD. Let /DC /BP /CJ /DD /CC/DC/D2 /CL /CC/BE /BV /D2where /DD /BE /BV /D2 /A0 /BD. Note that if/DC/D2 /BP/BCthen /DC /A3/BT/DC /BP /DD /A3/BU/DD. We ﬁrst use the maximin form of Courant-Fisher theorem to write/AL/CZ /BP /D1/CP/DC/CB /AI /BV /D2/CS/CX/D1 /B4 /CB /B5/BP /CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB /DC /A3/BT/DC /DC /A3/DC/AL /D1/CP/DC/CB /AI/CU /CT/D2 /CV /BR/CS/CX/D1 /B4 /CB /B5/BP /CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB /DC /A3/BT/DC /DC /A3/DC/BP /D1/CP/DC/CB /AI/CU /CT/D2 /CV /BR/CS/CX/D1 /B4 /CB /B5/BP /CZ /D1/CX/D2/BC /BI/BP /DC /BE /CB/DC/D2 /BP/BC /DC /A3/BT/DC /DC /A3/DC/BP /D1/CP/DC/CB /AI /BV /D2 /A0 /BD/CS/CX/D1 /B4 /CB /B5/BP /CZ /D1/CX/D2/BC /BI/BP /DD /BE /CB /DD /A3/BU/DD /DD /A3/DD/BP /AI/CZ Now,we use the minimax form of the theorem to obtain /AL/CZ /B7/BD /AK /AI/CZ./AL/CZ /B7/BD /BP /D1/CX/D2/CB /AI /BV /D2/CS/CX/D1 /B4 /CB /B5/BP /D2 /A0 /B4 /CZ /B7/BD/B5/B7/BD /D1/CP/DC/BC /BI/BP /DC /BE /CB /DC /A3/BT/DC /DC /A3/DC/AK /D1/CX/D2/CB /AI/CU /CT/D2 /CV /BR/CS/CX/D1 /B4 /CB /B5/BP /D2 /A0 /CZ /D1/CP/DC/BC /BI/BP /DC /BE /CB /DC /A3/BT/DC /DC /A3/DC/BP /D1/CX/D2/CB /AI/CU /CT/D2 /CV /BR/CS/CX/D1 /B4 /CB /B5/BP /D2 /A0 /CZ /D1/CP/DC/BC /BI/BP /DC /BE /CB/DC/D2 /BP/BC /DC /A3/BT/DC /DC /A3/DC/BP /D1/CX/D2/CB /AI /BV /D2 /A0 /BD/CS/CX/D1 /B4 /CB /B5/BP/B4 /D2 /A0 /BD/B5 /A0 /CZ /B7/BD /D1/CP/DC/BC /BI/BP /DD /BE /CB /DD /A3/BU/DD /DD /A3/DD/BP /AI/CZ 21 2.2.5 Sylvester’s law of inertia Material in this section follows closely that in the book Matrix Analysis by Horn and Johnson [57]. Deﬁnition 2.29. Let /BT/BN /BU /BE /C5/D2be given. If there exists a non-singular matrix /CBsuch that/AF /BU /BP /CB/BT /CB /A3,then /BUis said to be /A3-congruent to /BT./AF /BU /BP /CB/BT /CB /CC, then /BUis said to be /CC-congruent to /BT. Note.These two notion of congruence must be closely related; they are the same if /CBis a real matrix. When it is not important to distinguish between the two, we use the term congruence without a preﬁx. Since /CBwas required to be non-singular, congruent matrices have the same rank. Also note that, if /BTis Hermitian then so is /CB/BT /CB /A3;i f /BTis symmetric, then /CB/BT /CB /CCis also symmetric. Proposition 2.30. Both /A3-congruence and /CC-congruence are equivalent relations. Proof.It is easy to verify that the relations are reﬂexive, symmetric and transitive. Only need to notice that /CBis non-singular. The set /C5/D2, therefore, is partitioned into equivalence classes by congruence. As an abstract problem, we may seek a canonical representative of each equivalence class under each type ofcongruence. Sylvester’s lawofinertia gives us the afﬁrmative answer forthe/A3-congruence case, and thus also gives the answer for the set of real symmetric matrices. Deﬁnition 2.31. Let /BT /BE /C5/D2be a Hermitian matrix. The inertiaof /BTis the ordered triple/CX /B4 /BT /B5/BP /B4 /CX/B7 /B4 /BT /B5 /BN/CX/A0 /B4 /BT /B5 /BN/CX/BC /B4 /BT /B5/B5 where /CX/B7 /B4 /BT /B5is the number of positive eigenvalues of /BT, /CX/A0 /B4 /BT /B5is the number ofnegative eigen- values of /BT, and /CX/BC /B4 /BT /B5is the number of zero eigenvalues of /BT, all counting multiplicity. The signature of /BTis the quantity /CX/B7 /B4 /BT /B5 /A0 /CX/A0 /B4 /BT /B5. Note.Since /D6/CP /D2 /CZ /B4 /BT /B5/BP /CX/B7 /B4 /BT /B5/B7 /CX/A0 /B4 /BT /B5, the signature and the rank of /BTuniquely identify the inertia of /BT. Theorem 2.32 (Sylvester’s law of inertia). Let /BT/BN /BU /BE /C5/D2be Hermitian matrices. /BTand /BU are /A3-congruent if and only if /BTand /BUhave the same inertia. Proof. /B4 /B5 /B5. Firstly, for any Hermitian matrix /BV /BE /C5/D2, /BVcan be diagonalized by a unitary matrix /CD, i.e. /BV /BP /CD /A3 /CD /A3, with /A3being diagonal containing all eigenvalues of /BV. By multi- plying /CDwith a permutation matrix, we can safely assume that down the main diagonal of /A3, allpositive eigenvalues goﬁrst: /AL/BD /BN/BM/BM/BM /BN/AL/CX/B7,then thenegatives: /AL/CX/B7 /B7/BD /BN/BM/BM/BM /BN/AL/CX/B7 /B7 /CX/A0,andthe rest are /BC’s. Thus, if we set /BW /BP /CS/CX/CP/CV /B4 /D4 /CY /AL/BD /CY /BN/BM/BM/BM /BN /D4 /CY /AL/CX/B7 /B7 /CX/A0 /CY /BN /BC /BN/BM/BM/BM /BN /BC/B5, then/A3/BP /BW /BE/BI/BI /BI/BI/BI/BI/BI/BI/BI/BI/BI /BI/BI/BI/BI/BG /BD .../BD/A0 /BD .../A0 /BD/BC .../BC /BF/BJ/BJ /BJ/BJ/BJ/BJ/BJ/BJ/BJ/BJ/BJ /BJ/BJ/BJ/BJ/BH /BW /BP /BW/C1/BV /BW 22 with the entries not shown being /BC. /C1/BVis called the inertia matrix of /BV. Consequently, letting/CB /BP /CD/BW( /CBis clearly non-singular) weget/BV /BP /CD /A3 /CD /A3/BP /CD/BW /C1/BV /BW/CD /A3/BP /CB/C1/BV /CB /A3(2.2) Hence, if /BTand /BUhave the same inertia, then they could be written in the form (2.2) with possibly a different /CBfor each, but /C1/BT /BP /C1/BU. Since /A3-congruence is transitive, /BTis /A3-congruent to /BUas they are both congruent to /C1/BT./B4 /B4 /B5. Now, assume /BT /BP /CB/BU/CB /A3for some non-singular matrix /CB. /BTand /BUhave the same rank, so /CX/BC /B4 /BT /B5 /BP /CX/BC /B4 /BU /B5. We are left to show that /CX/B7 /B4 /BT /B5 /BP /CX/B7 /B4 /BU /B5. For convenience, let/CP /BP /CX/B7 /B4 /BT /B5and /CQ /BP /CX/B7 /B4 /BU /B5. Let /D9/BD /BN/BM/BM/BM /BN/D9/CPbe the orthonormal eigenvectors for the positive eigenvalues of /BT,sothat /CS/CX/D1 /B4 /CB /D4/CP/D2 /CU /D9/BD /BN/BM/BM/BM /BN/D9/CP /CV /B5/BP /CP.I f /DC /BP /CR/BD /D9/BD /B7 /A1/A1/A1 /B7 /CR/CP /D9/CP,then /DC /A3/BT/DC /BP/AL/BD /CY /CR/BD /CY /BE/B7 /A1/A1/A1 /B7 /AL/CP /CY /CR/CP /CY /BE/BQ /BC. But then/DC /A3/BT/DC /BP /DC /A3/CB/BU/CB /A3/DC /BP/B4 /CB /A3/DC /B5 /A3/BU /B4 /CB /A3/DC /B5 /BQ /BC so /DD /A3/BU/DD /BQ /BCfor all vector /DDin /CB /D4/CP/D2 /CU /CB /A3/D9/BD /BN/BM/BM/BM /BN/CB /A3/D9/CP /CV, which also has dimension /CP.B y Corollary 2.25, /CQ /AL /CP. Asimilar argument shows that /CP /AL /CQ, which completes the proof. Corollary 2.33. Given /DC /BE /CA /D2,i f /DC /CC/BT/DCcan be written as the sum of /D1products involving two linear factors, that is/DC /CC/BT/DC /BP /D1/CG/CZ /BP/BD /B4 /CG/CX /BE /CB/CZ /CQ/CX/BN/CZ /DC/CX /B5/B4 /CG/CY /BE /CC/CZ /CR/CY/BN/CZ /DC/CY /B5 Furtherassumethat /BThas /D4positive eigenvalues and /D5positive eigenvalues (counting multiplic- ities), then /D1 /AL /D1/CP/DC/B4 /D4/BN /D5 /B5. Proof.I have not been able to see why this corollary follows from Sylvester’s law yet. A proof of the corollary can be given, but that’s not the point. 23