Gershgorin District

Gerschgorin circles are used in numerical linear algebra , a branch of mathematics , to estimate eigenvalues . With their help, areas can easily be specified in which the eigenvalues ​​of a matrix are located and, under special conditions, even how many eigenvalues ​​are contained in them.

They are named after the Belarusian mathematician Semjon Aronowitsch Gershgorin .

definition

Let a square matrix with entries from (i.e. ), then the Gershgorin circle belonging to the -th diagonal element is defined as follows: ${\displaystyle A}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle i}$ ${\displaystyle a_{ii}}$

${\displaystyle {\bar {S}}_{i}:={\bar {S}}\left(a_{ii},\sum _{j=1,j\neq i}^{n}\left|a_{ij}\right|\right)}$ For ${\displaystyle i=1,\ldots ,n}$

wherein with the closed circular disc with radius around the point referred to. ${\displaystyle {\bar {S}}(x,r)}$ ${\displaystyle x\in \mathbb {C} ,r\in \mathbb {R^{+}} }$ ${\displaystyle r}$ ${\displaystyle x}$

Since the set of eigenvalues ​​(the spectrum ) of is identical to that of , another family of circles with the same properties can also be determined column by column: ${\displaystyle A}$ ${\displaystyle A^{T}}$

${\displaystyle {\bar {S}}_{j}:={\bar {S}}\left(a_{jj},\sum _{i=1,i\neq j}^{n}\left|a_{ij}\right|\right)}$ For ${\displaystyle j=1,\ldots ,n}$

Estimation of eigenvalues

The following applies:

• The spectrum of is a subset of ${\displaystyle A}$ ${\displaystyle \textstyle \bigcup _{i=1}^{n}{\bar {S}}_{i}}$
• If there is a subset of such that: ${\displaystyle I}$ ${\displaystyle \{1,\ldots ,n\}}$

${\displaystyle \bigcup _{i\in I}{\bar {S}}_{i}\cap \bigcup _{i\notin I}{\bar {S}}_{i}=\emptyset }$

then contains exactly eigenvalues ​​(including multiples) of the matrix . ${\displaystyle \textstyle \bigcup _{i\in I}{\bar {S}}_{i}}$ ${\displaystyle \left|I\right|}$ ${\displaystyle A}$

Or more memorable: Every connected component of the union of all Gerschgorin circular disks contains as many eigenvalues ​​as diagonal elements of the matrix . ${\displaystyle A}$

Due to the possibility of calculating the circles both line by line and column by column (the eigenvalues ​​of the transposed matrix are the same), two estimates per diagonal element can be found for non-symmetrical matrices.

Examples

Gershgorin circles to matrix A.

To the matrix

${\displaystyle A={\begin{pmatrix}2&1&0.5\\0.2&5&0.7\\1&0&6\end{pmatrix}}}$

there are the following Gerschgorin circles (columns and rows):

• ${\displaystyle {\bar {S}}(2,1.2)}$and to the diagonal element ${\displaystyle {\bar {S}}(2,1.5)}$ ${\displaystyle a_{11}}$
• ${\displaystyle {\bar {S}}(5,1)}$and to the diagonal element ${\displaystyle {\bar {S}}(5,0.9)}$ ${\displaystyle a_{22}}$
• ${\displaystyle {\bar {S}}(6,1.2)}$and to the diagonal element ${\displaystyle {\bar {S}}(6,1)}$ ${\displaystyle a_{33}}$

Since the set average is empty, there is exactly one eigenvalue in and exactly two in. ${\displaystyle {\bar {S}}(2,1.2)\cap {\bigl (}{\bar {S}}(5,1)\cup {\bar {S}}(6,1.2){\bigr )}=\emptyset }$ ${\displaystyle {\bar {S}}(2,1.2)}$ ${\displaystyle {\bar {S}}(5,0.9)\cup {\bar {S}}(6,1)}$

The actual eigenvalues ​​of the matrix are rounded off 1.8692, 4.8730 and 6.2578 and actually contained in the areas indicated above. ${\displaystyle A}$

The matrix

${\displaystyle B={\begin{pmatrix}8&0&1\\0&7&0\\1&0&5\\\end{pmatrix}}}$

is symmetric and real , so all eigenvalues ​​are real and there are the following real intervals (Gerschgorin circles):

• ${\displaystyle \lbrack 7,9\rbrack ={\bar {S}}(8,1)}$ to the diagonal element ${\displaystyle b_{11}}$
• ${\displaystyle \lbrack 7,7\rbrack ={\bar {S}}(7,0)}$ to the diagonal element ${\displaystyle b_{22}}$
• ${\displaystyle \lbrack 4,6\rbrack ={\bar {S}}(5,1)}$ to the diagonal element ${\displaystyle b_{33}}$

Since only the diagonal element in the second column and row of this matrix is different from zero, one eigenvalue can be easily determined with, the other two lie in the intervals and , thus, can be directly identified as positive definite . The actual eigenvalues ​​of the matrix are roughly 4.6972, 7 and 8.3028. ${\displaystyle b_{22}}$ ${\displaystyle b_{22}=7}$ ${\displaystyle \lbrack 7,9\rbrack }$ ${\displaystyle \lbrack 4,6\rbrack }$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle \{7,\,{\tfrac {13\pm {\sqrt {13}}}{2}}\}}$

use

The Gerschgorin circles offer a simple possibility in numerics to determine the properties of matrices. Contains e.g. If, for example, no Gerschgorin circle has the zero point, the matrix can be inverted . This property is summarized in the term of the strictly diagonally dominant matrix . In the same way, with symmetrical or Hermitian matrices, the definiteness can often be roughly estimated with the help of the Gerschgorin circles.

See also

• Gerschgorin's Theorem : Application to polynomial zeros
• Courant-Fischer theorem : alternative characterization of the eigenvalues ​​of symmetrical or Hermitian matrices

literature

• Gerschgorin, S. On the delimitation of the eigenvalues ​​of a matrix . Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 6, pages 749-754, 1931 [1]
• Varga, RS Geršgorin and His Circles. Springer, Berlin 2004. ISBN 3540211004 . Errata (PDF; 38 kB).