An insight into the Gershgorin circle theorem

2 minute read

Eigenvalues and eigenvectors often appear in the mathematics of machine learning, in areas such as Principle Component Analysis (PCA) and Singular Value Decomposition (SVD). Eigen means “own” or “self” in German, and an eigenvector is a special linear transformation of a matrix. Assuming you more or less know what they are (if not, 3Blue1Brown’s YouTube video explains the visual interpretation really well), I’m going to explain the more niche topic of “how to find all the eigenvalues” in this short post.

Image by Ricardo Gomez Angel via Unsplash
Photo by Ricardo Gomez Angel on Unsplash

The Gershgorin circle theorem

The Gershgorin circle theorem, also known as the Gershgorin disk theorem, tells you where the eigenvalues are in a complex plane.

Let’s use a simple example of a 4 by 4 matrix to illustrate the idea.

\[A = \begin{bmatrix} \alpha_{00} & \alpha_{01} & \alpha_{02} & \alpha_{03}\\ \alpha_{10} & \alpha_{11} & \alpha_{12} & \alpha_{13}\\ \alpha_{20} & \alpha_{21} & \alpha_{22} & \alpha_{23}\\ \alpha_{30} & \alpha_{31} & \alpha_{32} & \alpha_{33}\\ \end{bmatrix}\]

We place the diagonal entries of this matrix in a complex plane.

Gershgorin circle1

Now, calculate the sum of the absolute values of the non-diagonal entries for each row.

\[\rho_0 = |\alpha_{01}| + |\alpha_{02}| + |\alpha_{03}| \\ \rho_1 = |\alpha_{10}| + |\alpha_{12}| + |\alpha_{13}| \\ \rho_2 = |\alpha_{20}| + |\alpha_{21}| + |\alpha_{23}| \\ \rho_3 = |\alpha_{30}| + |\alpha_{31}| + |\alpha_{32}|\]

Then draw a circle around each diagonal entry with radius $\rho$ as follows:

Gershgorin circle2

Gershgorin circle theorem basically says that all the eigenvalues of the matrix $A$ can be found in the union of these circles.

You can see that the size of the circle is based on the off-diagonal entries. If the norm of the off-diagonal entries is small, you can more accurately find the eigenvalue. It is not necessarily the case that each eigenvalue is in each circle. It could be the case that one circle contains more than one eigenvalue.

I hope this very short post gave you some insights into how to find eigenvalues using the Gershgorin circle theorem.

Subscribe to my blog

* indicates required
Thank you for reading my blog post! If you liked it, please subscribe to receive new posts. I won't give your address to anyone else, won't send you any spam, and you can unsubscribe at any time.

Tags: ,