Gershgorin Disks and Bounds on Roots of Polynomials

Gershgorin Disks

Let {A =(a_{ij})} be a complex matrix. Define

{\displaystyle R_i =\sum_{j \neq i} |a_{ij}|}

be the sum of non-diagonal entries of the {i}-th row.

{D_i = B(a_{ii}, R_i)=\{|z-a_{ii}|\le R_i}\} be the closed disk of radius {R_i} around {a_{ii}.} These are called Gershgorin disks.

Theorem: Every eigen value of {A} is contained in some Gershgorin disk {D_i.}

Proof: Given an eigenvalue {\lambda}, take an eigenvector {(x_i)} and normalize to make the largest coordinate in absolute value to be 1. If this is the coordinate {i}, we get

\displaystyle \sum_{j}a_{ij}x_j =\lambda x_i = \lambda

\displaystyle |\lambda- a_{ii}| =|\sum_{j\neq i}a_{ij}x_j | \le \sum_{j \neq i} |a_{ij}| =R_i

Duality: Observing that the eigenvalues of the transpose {A^{T}} are the same, we also get that eigenvalues are contained in the dual Gershgorin disks {D_{i}' = B(a_{ii}, R'_i)} where

{\displaystyle R'_i =\sum_{j \neq i} |a_{ji}|.}

Bounds of Lagrange and Cauchy on roots of Polynomials:

\displaystyle A=\left[\begin{array}{ccccc} 0 & 0 & \ldots & 0 & -a_{0} \\ 1 & 0 & \ldots & 0 & -a_{1} \\ 0 & 1 & \ldots & 0 & -a_{2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 1 & -a_{n-1} \end{array}\right]

is called the companion matrix of the polynomial

{ P(x)=a_{0}+a_{1} t+\cdots+a_{n-1} t^{n-1}+t^{n}. }

That is the characteristic polynomials of this matrix {A} is the polynomial {P(x).}

Considering the Gershgorin disks/bounds for the companion matrix and its trasnpose, we the following bounds on the roots of polynomials:

\displaystyle \text{ Lagrange:}~~~ |\rho_i| \le \max \left\{1, \sum_{i=0}^{n-1}\left|{a_{i}}\right|\right\}

\displaystyle \text{ Cauchy:}~~~ |\rho_i|\le 1+\max \left\{\left|{a_{n-1}}\right|,\left|{a_{n-2}}\right|, \dots,\left|{a_{0}}\right|\right\}

By applying these bounds of {P(tx)} for a scalar {t}, we get

\displaystyle |\rho_i| \le \min _{t \in \mathbb{R}_{+}}\left(\max \left\{t, \sum_{i=0}^{n-1}\left|{a_{i}}\right| t^{i-n+1}\right\}\right)

\displaystyle |\rho_i| \le \min _{t \in \mathbb{R}_{+}}\left(t+\max _{0 \leq i \leq n-1}\left(\left|{a_{i}}\right| t^{i-n+1}\right)\right)

Posted in $.

Leave a comment