Gershgorin’s Theorem for Estimating Eigenvalues - UPS

1 Gershgorin s Theorem for Estimating EigenvaluesSean (c) 2007 Sean is granted to copy, distribute and/or modify this document under theterms of the GNU Free Documentation License, Version or any later versionpublished by the Free Software Foundation; with no Invariant Sections, noFront-Cover Texts, and no Back-Cover Texts. A copy of the license is included in thesection entitled GNU Free Documentation License .2 One of the most important things you can know about a matrix is its eigenvalue (orcharacteristic value).

2 By pure inspection it is nearly impossible to see the way for Estimating Eigenvalues is to find the trace of the matrix. The trace merelytells us what all the Eigenvalues add up to. It doesn t give us any range for the eigenval-ues. Even if we have a very small trace we can still theoretically have two eigenvalueswhose absolute values are very large but have an opposite sign. In order to figure outwhat range the Eigenvalues of a certain matrix would be in we can use Gershgorin Strictly Diagonally Dominant MatricesBefore we get to Gershgorin s Theorem it is convenient to introduce a condition formatrices known as Strictly Diagonally Dominant.

3 While Gershgorin s Theorem can beproven by other means, it is simplest to solve it using knowledge of Strictly DiagonallyDominant Strictly Diagonally Dominant, here on referred to as SDD, matrix is defined asfollows:Definition1 (Strictly Diagonally Dominant Matrices)MatrixAnnis Strictly Diagonally Dominant if:|Aii|> j6=i|Aij|fori= 1,2,..,nExample1A= 6 1 2 2 1 5 1 21 1 8 5 1 0 0 3 It is fairly easy to see that each row satisfies the inequality|Aii|> j6=i|Aij|row 1|6|>| 1|+|2|+|2|row 2|5|>| 1|+| 1|+|2|row 3| 8|>|1|+|1|+|5|row 4|3|>| 1|+|0|+|03 Theorem (Nonsingularity of SDD Matrices)Strictly diagonally dominant matrices are always Suppose that matrixAnnis SDD and singular, then there exists au unsuch thatAu=bwhere b is the 0 vector whileu6= 0 (Definition NM[67]).

4 A = Ann u= b=~0In the vectoruthere is a dominant element in positionuiwhere its absolute valueis either equal to or larger than the absolute value any other element inu. Lets callthis maximum value .Every element inucannot be . If this were the case then rowimultiplied byuwould not result in a 0 element for b which is needed in order for b to be the 0 vector.(1)|u1|=|u2|=..=|un|= (premise)(2)Ai1u1+Ai2u2+..+Ainun= 0 (row, column multiplication)(3) Ai1 Ai2 .. Ain = 0(substitution)(4) ( Ai1 Ai2.)

5 Ain) = 0(distributivity)(5) Ai1 Ai2 .. Ain= 0(multiplicative inverse)(6)|Ai1|=|Ai2|+..+|Ain|(check f or SDD)(6) contradicts the premise thatAnnis SDD thus every entry ofuncannot be .In order forb1to equal 0 thenn i=1A1iui= 0. Because|A11|> j6=i|Aij|, then positionu1cannot be . Ifu1cannot be then what about positionu2? For the same reasonu1cannot be due to the the magnitude ofAiiin row 1 ofA,u2cannot be due tothe magnitude ofAiiin row 2 ofA. This logic then continues fromu2untilun. As aresult no element inucan be the maximum element and all elements inucannot bethe maximum element.

6 Therefore there is no vectoruthat we can create such thatAu= there is nouother than the 0 vector that can be created such thatAu= 0, thenAis nonsingular (Definition NM[67]), a contradiction to our In knowing that matrix A is nonsingular provided that A is SDD we can now moveon to Gershgorin s Gershgorin s TheoremTheorem (Gershgorin s Theorem Round 1)Every eigenvalue of matrixAnnsatisfies:| Aii| j6=i|Aij|i {1,2, .., n}Proof Suppose that is an eigenvalue of the matrixA. The matrix I Ais SDD if| Aii|> j6=i|Aij|for everyi.

7 If Theorem is not satisfied then I Ais SDD. If I AisSDD then it is nonsingular by Theorem and as a result is not an eigenvalue. If is to be an eigenvalue then Theorem must hold. In analyzing this Theorem we see that every eigenvalue of the matrixAmust bewithin a distancedofAiifor somei. Since in general Eigenvalues are elements ofC, wecan visualize an eigenvalue as a point in the complex plane, where that point has to bewithin distancedofAiifor somei. This brings us to Definition (Gershgorin s disc)Letdi= j6=i|Aij|.

8 Then the setDi={z C:|z Aii di}is called theithGershgorin disc of the matrix A. This disc is the interior plus the boundary of a circle has a radiusdiand is centered at (the real part ofAii, the imaginary partofAii) [1 21 1]As a result of matrixAwe have Eigenvalues 3, 3 .From the rows of matrixAwe get a disc with radius 2 centered at (1,0) and a disc ofradius 1 centered at (-1,0). Plotting both the discs and the Eigenvalues complex planewe get:Figure Definition we see that for the matrixAnnthere arendiscs in the complexplane, each centered on one of the diagonal entries of the matrixAnn.

9 From we know that every eigenvalue must lie within one of these discs. However it doesnot say that each disc has an [1 12 1]6As a result of matrixAwe have eigenvaluesi, the rows of matrixAwe get a disc with radius 1 centered at (1,0) and a disc ofradius 2 centered at (-1,0). Plotting both the discs and the Eigenvalues in the complexplane we get:Figure is clearly visible that all of the Eigenvalues fall within the disc defined by the 2ndrow and none fall within the disc defined by the 1st (Gershgorin in Respect to Columns)Every eigenvalue of a matrix A must lie in a Gershgorin disc corresponding to thecolumns of Theorem and the resulting definition 2 gives us Gershgorin discs that correspondto the rows ofA, whereAis the matrix whose Eigenvalues we are looking for.

10 If wetranspose matrixAwe then get the columns of matrixAas the rows of matrixAt. Aswe know from Theorem ETM[421] the Eigenvalues ofAare the same as the eigenvaluesofAtadditionally matrixAtmust also obey Theorem this all together we have the set of Eigenvalues that are in bothAandAt. Because the rows ofAtcorrespond to the columns ofA, the Eigenvalues fall insideGershgorin discs corresponding to the the columns ofAdue toAtobeying Now we come to one of the most interesting properties of Gershgorin (Gershgorin s Theorem Round 2)A SubsetGof the Gershgorin discs is called a disjoint group of discs if no disc in thegroupGintersects a disc which is not inG.