Math Physics ML

A matrix Spectrum Localization Theorem

This page illustrates a Theorem of spectrum localization for a matrix using its coefficients.
This result, also known as the Gershgorin circle theorem, is applicable to square matrices with complex coefficients.
Beyond its intrinsic elegance, the theorem is also applicable to the resolution of linear equations in n variables for ill-conditioned matrices. The simulation below allows you to pick any set of complex coefficients for a matrix and to see the associated bounding of the corresponding spectrum, circles in blue show the subsets of the plane where the eigenvalues (in red) are bounded to be.
(The proper statement of the result and the proof are given below).

Matrix Size:

Draw

Enter numbers of the form a+ib with a,b
decimal numbers. Write 0+1i rather than i
(I'll modify the terrifying regex one day).

Note : for big matrices, exact
eigenvalue computation may fail

Theorem (S. Gershgorin, 1931):

Let `M` be a complex square matrix of size `n \in \mathbb{N}`.
We define for each `k\in{1,\ldots,n}`:

`D_k = {x\in\mathbb{C} ; |x-a_{kk}|\leq sum_(i=1, i\ne k)^n |a_{ki}|}.`

Then, the spectrum `Sp(M)` of `M` verifies the localization condition:

`Sp(M) \subset \bigcup_{k=1}^n D_k.`

Proof:

Let `M` be a complex square matrix of size `n \in \mathbb{N}`, and `\lambda\in\mathbb{C}` one of its eigenvalues associated to the eigenvector `x=(x_k)_{1\leq k\leq n}\in\mathbb{C}^n`.
Let `k_0\in{1,\ldots,n}` be the index suh that `\forall k\in{1,\ldots,n}`, ` x_k \leq x_{k_0}`.
We have then :

`sum_(i=1, i\ne k_0)^n a_{k_0i}x_i = (\lambda - a_{k_0k_0}) x_{k_0k_0}.`

Hence

`|\lambda - a_{k_0k_0}| \leq sum_(i=1, i\ne k_0)^n |a_{k_0i}x_i/x_{k_0}|.`

Finally

`|\lambda - a_{k_0k_0}| \leq sum_(i=1, i\ne k_0)^n |a_{k_0i}|.`

If we define for each `k\in\{1,\ldots,n\}`:

`D_k = {x\in\mathbb{C} ; |x-a_{kk}|\leq sum_(i=1, i\ne k)^n |a_{ki}|}`

the theorem follows.

`\square`

Applications

If the localizing discs of the matrix `M` you chose do not contain the origin, this directly means 0 is not an eigenvalue of `M`, thus `M` is invertible / non singular (This is equivalent to the Hadamard theorem on diagonally dominant Matrices).

When trying to solve numerically a general `Mx=y` linar equation, rounding errors are generally amplified by the so-called conditioning number of `M`:
`\kappa(M) = ∥M∥ ∥M^{-1}∥.`

A prior step of preconditioning can be applied to the equation in order to reduce `\kappa(M)`: we want to find a matrix `P` such that `P \approx M^{-1}` in order to solve `PMx = Py`, the matrix `PM`, being close to the identity, has then a lower conditioning number than the initial `M`.

The Gershgorin circle theorem can then be applied to bounding the spectrum of `PM`, thus providing information on the quality of our choice for `P` and allowing us to find our approximate inverse iteratively.

Note that while the union of all discs does contain the spectrum, each disc is not necessarily associated, as in the proof of the theorem, to its particular eigenvalue and thus does not necessarily contain exactly one eigenvalue.