Gershgorin’s Circle Theorem for Estimating the Eigenvalues ...

1 Gershgorin s Circle Theorem forEstimating the Eigenvalues of aMatrix with Known Error BoundsAuthor:DavidMarquisAdvisors:Profes sor HansDe MoorDr. KathrynPorterReader:Dr. MichaelNathansonMay 15, 2016 Figure 1: Semyon Aranovich GershgorinAbstractSquare matrices are characterized by their Eigenvalues , so we would like to be able to producethe Eigenvalues for any square matrix. Cofactor expansion is an algorithm used to producewhat is known as the characteristic polynomial of a matrixA, the roots of which are theeigenvalues ofA. However, the algorithm for cofactor expansion is computationally intensiveand as the output is annthdegree polynomial, we do not have any guaranteed method tofind the roots for large Aranovich Gershgorin (1901-1933), was a mathematician who worked mainly inthe study of differential equations.

2 Among his accomplishments were a degree from thePetrograd Technological Institute, a professorship at the Leningrad Institute of MechanicalEngineering, and he became head of the Division of Mechanics at the Turbine 1931, he authored a paper titled Uber die Abgrenzung der Eigenwerte einer Matrixinwhich he gave the proof of what has come to be called the Gershgorin Circle Theorem withprovided a simple method to estimate the Eigenvalues of a complex matrix with known linear algebra, linear systems of equations in the form of matrices are :A matrixis ann marray of elements from a vector space. In this essay, wewill only consider matrices with entries from the complex example of a matrix is i087 12 12 3 + 45 3 i Matrices can easily represent a system ofnequations inmvariables.

3 A matrix that has thesame number of rows and columns, is called a square matrix. One way we can study such amatrix is to find its Eigenvalues and :An eigenvectoris a column vector which when multiplied on the left by a ma-trix results in a scalar multiple of the original vector orAx= x. Although the equationA~0 = ~0 is true for allAand , we define~0 to not be an eigenvector for any :The value is what is known as the eigenvalueassociated with the matrixA=[3 2 12]has Eigenvalues 1= 4 and 2= 1. The corresponding eigenvectors arex1=[ 21]andx2=[11]and all scalar multiples of either. This is because[3 2 12][ 21]=[ 84]= 4[ 21]and[3 2 12][11]=[11]= 1[11]ThusAx1= 1x1andAx2= and eigenvectors characterize a matrix. Another related value associated witha matrix is its determinant. Although for this paper, we won t need to examine the deter-minants of any matrices, we will need to know the algorithm for finding determinants as itleads us to an algorithm for finding general method for finding the determinant of a matrix is called cofactor expansion.

4 Fora matrixR= [ri,j], the minorMk,lof the entryrk,lis the determinant of the matrix thatis left after removing thekthrow andlthcolumn fromR. The cofactorCk,lofrk,lis then( 1)k+lMk, the cofactor produced then requires one to evaluate the determinant of a matrix onedimension smaller than the previous matrix, we then perform cofactor expansion of thatminor. We continue this process until all of the determinants are of 2 2 matrices. Theformula to evaluate the determinant of a 2 2 matrix is[a bc d]=ad bcBy selecting a row or column ofRand for that row or column, summing the product of eachentry with its cofactor, we find the determinant equationAx= xis equivalent to the equationAx= IxwhereI, the identity matrix,is the matrix with the same dimension asAwhose entries are 1 s along the main diagonaland 0 elsewhere.

5 Then, we can subtractAxfrom both sides and factorxfrom both termsto get( I A)x= 0 Becausex6=~0, ( I A) must be singular, sodet( I A) = 0 Solving for which values of satisfy the above equation produces the Eigenvalues Eigenvalues in certain matrices are very easy to :An upper triangular matrixis a square matrix with all entries below the maindiagonal equal to illustrate, if you replace each ? with any complex number, then the following matrix willbe upper triangular ? ? ? ? ?0 ? ? ? ?0 0 ? ? ?0 0 0 ? ?0 0 0 0 ? Theorem :The Eigenvalues of a triangular matrix (upper, lower or diagonal) are exactlythe entries on the main is because, for a matrix [ai,j] if you imagine performing cofactor expansion on the firstcolumn of ( I A), there will only be one non-zero term to sum and it will be ( a1,1)times the determinant of the minor.

6 The determinant of that minor is then ( a2,2) timesthe determinant of its minor, et cetera until we get the factored characteristic polynomial( a1,1)( a2,2)..( an,n) = 0. Thus the Eigenvalues of a triangular matrix are the valuesalong its main 1:Determine the Eigenvalues of the matrix 2 3 + Because this is an upper triangular matrix, we can easily tell that the Eigenvalues are 2, 0,and 2:Determine the Eigenvalues of the matrix 102301110 1 13 It is incorrect to claim that the Eigenvalues are 10, 11, & 13 because this matrix has non-zeroentries both above and below the main diagonal, that claim would be false. We have to findthe solutions to the characteristic equation det( I A) = 0 or 10 2 30 11 101 13 = 0 Performing cofactor expansion on the first column we obtain( 10)(( 11)( 13) ((1)( 1))) = 0( 10)( 2 24 + 144) = 0which when factored is( 10)( 12)( 12) = 0and finally tells us that the Eigenvalues of this matrix are 10 and Eigenvalues in this way is computationally intensive even for a small matrix, soas the size of the matrix becomes very large, a significant amount of processing power isnecessary to find the also that for the matrix 10 230 11 100 13 (notice thata3,2was changed from a 1 to a 0) we can see that the Eigenvalues are 10, 11,and 13.

7 So it would seem that small changes to the values of the entries may only result insmall changes to the Eigenvalues . From this observation, back in 1931, Semyon AronovichGershgorin devised a method to estimate the Eigenvalues of a square matrix with a knownerror s Circle TheoremThe concept of the Gershgorin Circle Theorem is that one can take the diagonal entries of ann nmatrix as the coordinates in the complex plane. These points then act as the centersofndiscs which have radii of the sum of the magnitudes of then 1 other entries from thesame row. Then, all of the Eigenvalues of this matrix will lie within the union of these now state the Theorem formally preceded by a :IfAis ann nmatrix with complex entriesai,jthenri(A) = i6=j|ai,j|isdefined as the sum of the magnitudes of the non-diagonal entries of theithrow.

8 Then aGershgorin discis the discD(ai,i,ri(A)) centered ataiion the complex plane with radiusri(A). Theorem :Every eigenvalue of a matrix lies within at least one Gershgorin (Varga 2010).Let be an eigenvalue of a matrixAand letx= (xj) be its corre-sponding non-zero eigenvector. Sincexis an eigenvector ofA, we can rewriteAx= xusing sigma notation as inner product of each row ofAwithx: jaijxj= xiSubtractingaiixifrom both sides splits the sum: i6=jaijxj= xi aiixiDue to the fact thatx6= 0, we know there is somek Nsuch that0<|xk|= max{|xi|:i N}With thisk, we see i Nakixi= xkwhich is the same as i6=jakixi= ( ak,k)xkUsing the triangle inequality,| ak,k||xk|= i6=j|aai||xi| i6=j|aki||xk|=|xk|rk(A)where i6=j|aki||xk|=|xk|rk(A) comes from the definition of a Gershgorin Disc.

9 Finally,since|xk|is greater than 0 we can divide by|xk|, to get| akk| rk(A)As an example, consider the graph of the Gershgorin discs for our sample matrixA= 102301110 1 13 Since the entries on the main diagonal are 10+0i, 11+0i, and 13+0i, those will be the centersof the three discs in the complex plane. Those three discs will have radii of|2|+|3|= 5,|0|+|1|= 1, and|0|+|1|= 1 respectively seeFigure inFigure 2, that the two smaller discs are contained within the larger disc. This leadsus to an important corollary to Gershgorin s Circle 2: The Gershgorin discs for matrix ACorollary 1:If Sis a union ofmdiscsRisuch that Sis disjoint from all other discs, then Scontains preciselymeigenvalues (counting multiplicities) ofAProof of Corollary 1: (Ortega 1990).LetAbe ann nmatrix.

10 Then, we can create afamily of matricesA(t) =tB+DwhereDis the same asAwith all the off-diagonal entriesreduced to zero andBis the same asAwith all the diagonal entries reduced to zero allalong the interval 0 t 1. Then, each Gershgorin disc ofA(t) will have the same centerof a disc fromA, but with its radius scaled byt. Now if we letRi(t) be the disc withcenterai,iand radiust j6=i|ai,j|and define S= mi=1Ri, we can then set S(t) = mi=1Ri(t)and S(t) = ni=m+1Ri. From our assumptions, the sets Sand Sare disjoint and therefore S(t) and S(t) are disjoint throughout the interval oft. We can see that S(0) containsmeigenvalues ofA0. Since Gershgorin s Circle Theorem tells us that all Eigenvalues ofAtarecontained in S S. However, since S S= and an eigenvalue cannot jump from oneset to the other, S(0) containing exactlymeigenvalues implies that S(t) contains exactlymeigenvalues for the entire interval demonstrate this corollary, seefigure 3which depicts a subset of the Gershgorin discs forsome matrix (with the actual locations of the Eigenvalues marked with x s).