Bounds for Polynomial’s Roots from Hessenberg Matrices and Gershgorin’s Disks

Mamoudou Amadou Bondabou, Ousmane Moussa Tessa, Maimouna Salou

Département de Mathématiques et d’informatique, Université A. Moumouni, Niamey, Niger.

DOI: 10.4236/apm.2021.1112062                

Abstract

The goal of this study is to propose a method of estimation of bounds for roots of polynomials with complex coefficients. A well-known and easy tool to obtain such information is to use the standard Gershgorin’s theorem, however, it doesn’t take into account the structure of the matrix. The modified disks of Gershgorin give the opportunity through some geometrical figures called Ovals of Cassini, to consider the form of the matrix in order to determine appropriated bounds for roots. Furthermore, we have seen that, the Hessenbeg matrices are indicated to estimate good bounds for roots of polynomials as far as we become improved bounds for high values of polynomial’s coefficients. But the bounds are better for small values. The aim of the work was to take advantages of this, after introducing the Dehmer’s bound, to find an appropriated property of the Hessenberg form. To illustrate our results, illustrative examples are given to compare the obtained bounds to those obtained through classical methods like Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds.

Keywords

Bounds for Roots of Polynomials, Gershgorin, Frobenius Companion Matrix, Hessenberg Matrices, Ovals of Cassini

1. Introduction

The estimation of complex roots of a polynomial is a long standing classical problem. A convenient way to obtain information on the location of the zeros of a polynomial is by locating the eigenvalues of its companion matrix. A well-known and easy tool to obtain such information is that of the Gershgorin disks, centered at the diagonal elements of the matrix, however, the classical form of the Gershgorin’s theorem doesn’t take into account the structure of the matrix [1].

This is why some methods, such as the modified disks of Gershgorin, through some geometrical figures called Ovals of Cassini, prospect estimation of bounds by looking in details of the elements in the matrix.

We first present Frobenius companion matrices and some important properties such as Frobenius decomposition’s theorem. Secondly, we will introduce Fiedler matrices and the Gershgorin’s theorem in its general form. We introduce classical bounds for roots like Cauchy’s bounds, Montel’s bounds, Dehmer’s bounds and Carmichel-Mason’ bounds, which are going to be used for comparisons. Some applications to classical companion matrices are presented to estimate bounds for roots of polynomials. We introduce furthermore, bounds for roots with Hessenbeg matrices. We have seen that, the Hessenbeg matrix form is appropriated to estimate good bounds for roots of polynomials as far as it gives improved bounds for high values of polynomial’s coefficients. But it is more indicated for estimation of bounds for small values of coefficients for a given polynomial [2].

Indeed, as principal issue of this work, we present some studies on polynomials in case of very small values of polynomial’s coefficients when ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$.

In the third part, through illustrative examples, we make a comparison of classical bounds to those obtained with the special hessenberg matrix form in order to compare the pertinence of the studied property. We can see that, the used classical methods always provide bounds higher than 1.

2. Generalities on Frobenius Companion Matrices Gershgorin’s Theorem

2.1. Forms of the Frobenius Companion Matrices

Let $P\left(X\right)$ be a polynomial:

$P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0\in ℂ\left[X\right]$

( $a_0\ne 0$, because when $a_0=0$, then we have an evident root which is 0, we exclude this case, to studie non obvious cases).

Let $C\left(P\right)$ be a matrix:

$C\left(P\right):=\left(\begin{array}{ccccc}0& \cdots & 0& 0& -a_0\\ 1& 0& \cdots & 0& -a_1\\ ⋮& \ddots & \ddots & ⋮& ⋮\\ 0& \cdots & 1& \ddots & -a_{n-2}\\ 0& \cdots & 0& 1& -a_{n-1}\end{array}\right)$ (1)

Let $P_{C\left(P\right)}\left(X\right)$ be, the characteristic polynomial of the matrix $C\left(P\right)$, $I_n$ is the identity matrix of degree n. The characteristic polynomial $P_{C\left(P\right)}\left(X\right)$ of the matrix $C\left(P\right)$ coincides with $P\left(X\right)$ :

$P_{C\left(P\right)}\left(X\right):=\det \left(X{I}_n-C\left(P\right)\right)=P\left(X\right).$

With the help of the expansion with respect to the first column it is easy to verify by induction that:

$\det \left(X{I}_n-C\left(P\right)\right)=P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$.

The given $n\times n$ matrix $C\left(P\right)$ is called “Frobenius matrix” or the “standard Frobenius companion matrix of the polynomial $P\left(X\right)$ ”.

Definition 1. [3]

We define a “companion matrix” to be an $n\times n$ matrix A over $\mathbb{F}\left[a_0\mathrm{,}{a}_1\mathrm{,}\cdots \mathrm{,}{a}_{n-1}\right]$ with $\left(n^2-n\right)$ entries constant in $\mathbb{F}$ and the remaining entries $-a_0\mathrm{,}-a_1\mathrm{,}\cdots \mathrm{,}-a_{n-1}$ such that the characteristic polynomial of A is $P\left(X\right)$. We say that two companion matrices A and B are equivalent if either A or A^T can be obtained from B via a permutation similarity.

There are many other Frobenius companion matrices. In this paper, we notice:

$\mathcal{F}\left(P\right)$ is the classical Frobenius companion matrix associated to the polynomial $P\left(X\right)$ :

$\mathcal{F}\left(P\right)=\left(\begin{array}{ccccc}0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 1\\ -a_0& -a_1& -a_2& \cdots & -a_{n-1}\end{array}\right)$ (2)

$C_1\left(P\right)$ is the first Frobenius companion matrix associated to the polynomial $P\left(X\right)$ :

$C_1\left(P\right)=\left(\begin{array}{ccccc}-a_{n-1}& -a_{n-2}& \cdots & -a_1& -a_0\\ 1& 0& \cdots & 0& 0\\ 0& 1& \ddots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1& 0\end{array}\right)$ (3)

$C_2\left(P\right)$ is the second Frobenius companion matrix associated to the polynomial $P\left(X\right)$ :

$C_2\left(P\right)=\left(\begin{array}{ccccc}-a_{n-1}& 1& 0& \cdots & 0\\ -a_{n-2}& 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮& 0\\ -a_1& 0& 0& \ddots & 1\\ -a_0& 0& 0& \cdots & 0\end{array}\right)$ (4)

Companion matrices have a great interest in that they offer the possibility of elegant demonstrations.

2.2. Statement of the Gershgorin’s Theorem

A common way to obtain inclusion areas for the zeros of a polynomial is to find eigenvalue inclusion areas for a companion matrix of the polynomial, whose eigenvalues are precisely the zeros of the polynomial.

In this section, it is about locating zeros of polynomials from the Gershgorin’s disks. These disks are estimated by using the diagonal elements of the matrix. The radii are then calculated from the polynomial’s coefficients. Gershgorin’s theorem states that the union of these disks contains all eigenvalues.

We formally state here Gershgorin’s theorem as lemma and its application to companion matrices.

Lemma 1. For a given matrix A of dimension $n\times n$ with complex elements $a_{ij}$, all the eigenvalues are located in the union of the following n disks so that: [1].

Considering the rows:

${\displaystyle \underset{i=1}{\overset{n}{\cup }}}\left\{z\in ℂ:\left|z-a_{ii}\right|\le {\displaystyle \underset{j=1,j\ne i}{\overset{n}{\sum }}}\left|a_{ij}\right|\right\}$ (5)

Considering the columns:

${\displaystyle \underset{j=1}{\overset{n}{\cup }}}\left\{z\in ℂ:\left|z-a_{ii}\right|\le {\displaystyle \underset{i=1,i\ne j}{\overset{n}{\sum }}}\left|a_{ij}\right|\right\}$ (6)

Proof. Let $\lambda$ be an eigenvalue of a complex $n\times n$ matrix A and whose corresponding eigenvectors are x.

So we have $Ax=\lambda x$.

If x is an eigenvector, it has at least one of its components that is non-zero. Let $x_k$ be the component of x having the greatest absolute value, such that $\left|x_k\right|\ge \left|x_i\right|$ for all $i=1,2,\cdots ,n$ and $x_k\ne 0$.

As ${\left(Ax\right)}_k={\left(\lambda \mathrm{.}x\right)}_k$, we have:

$\lambda .x_k=a_{kk}{x}_k+{\displaystyle {\sum }_{j=1,j\ne k}^n}{a}_{kj}{x}_j$,

hence $\left(\lambda -a_{kk}\right)x_k={\displaystyle {\sum }_{j=1,j\ne k}^n}{a}_{kj}{x}_j$.

We will take the absolute value on either side of the equality and use the triangular inequality while dividing by $\left|x_k\right|$.

Since $\left|x_j\right|/\left|x_k\right|<1$ for every $j\ne k$, we become:

$\left|\lambda -a_{kk}\right|\le {\displaystyle \underset{j=1,j\ne k}{\overset{n}{\sum }}}\left|a_{kj}\right|\frac{\left|x_j\right|}{\left|x_k\right|}\le {\displaystyle \underset{j=1,j\ne k}{\overset{n}{\sum }}}\left|a_{kj}\right|$

$\lambda$ is then located in the disk $a_{kk}$.

Without knowing the eigenvectors, we do not know to which k each eigenvalue corresponds. We must therefore take the union of all these disks to obtain a region which guarantees to contain all the eigenvalues in a safe way.

2.3. Application to Classical Companion Matrices

The proof of the theorem doesn’t take into account any particular property of the matrix A. It can be then interesting to consider some properties of matrices and to study the advantages related to these particularities.

Since our study concerns Fiedler companion matrices, we will first consider the particular properties of companion matrices by using explicit forms.

We consider the classical companion matrix $C\left(P\right)$ :

$C\left(P\right)=\left(\begin{array}{ccccc}0& \cdots & 0& 0& -a_0\\ 1& 0& \cdots & 0& -a_1\\ ⋮& \ddots & \ddots & ⋮& ⋮\\ 0& \cdots & 1& \ddots & -a_{n-2}\\ 0& \cdots & 0& 1& -a_{n-1}\end{array}\right)$ (7)

It is already known that the eigenvalues of the matrix $C\left(P\right)$ are roots of its characteristic polynomial $P\left(X\right)\in ℂ\left[X\right]$ :

$P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$, $a_0\ne 0$.

Gershgorin’s theorem applies to the matrix $C\left(P\right)$ guarantees that all the zeros of the polynomial $P\left(X\right)$ belong to ${\Gamma }^{\left(0\right)}$ which is the union of n disks such as:

${\Gamma }^{\left(0\right)}={\displaystyle {\cup }_{j=1}^n}{\Gamma }_j$.

where:

$\begin{array}{l}{\Gamma }_1=\left\{X\in ℂ:\left|X\right|\le \left|a_0\right|\right\}\\ ⋮\\ {\Gamma }_j=\left\{X\in ℂ:\left|X\right|\le 1+\left|a_{j-1}\right|\right\}\text{for}2\le j\le n-1\\ ⋮\\ {\Gamma }_n=\left\{X\in ℂ:\left|X+a_{n-1}\right|\le 1\right\}\end{array}$

Let $\lambda$ be a zero of the polynomial $P\left(X\right)$.

The inequalities allow us to say that for any zero $\lambda$ of $P\left(X\right)$, we have:

$\left|\lambda \right|\le \left|{\Gamma }^{\left(0\right)}\right|=\max \left\{\left|a_0\right|,1+\left|a_1\right|,\cdots ,1+\left|a_{n-1}\right|\right\}$ (8)

The obtained bound is better than the bound of Cauchy namely:

$\left|\lambda \right|\le 1+\max \left\{\left|a_0\right|,\left|a_1\right|,\cdots ,\left|a_{n-1}\right|\right\}$

Example 1:

Let $P\left(X\right)=X^8-X^7-3X^6-2X^5-2X^4-4X^3-3X^2-5X-3$ be a complex polynomial.

By applying Gershgorin’s theorem, we have:

$\begin{array}{l}{\Gamma }_1=\left\{X\in ℂ:\left|X\right|\le 3\right\}\\ {\Gamma }_2=\left\{X\in ℂ:\left|X\right|\le 1+5=6\right\}\\ {\Gamma }_3=\left\{X\in ℂ:\left|X\right|\le 1+3=4\right\}\\ {\Gamma }_4=\left\{X\in ℂ:\left|X\right|\le 1+4=5\right\}\end{array}$

$\begin{array}{l}{\Gamma }_5=\left\{X\in ℂ:\left|X\right|\le 1+2=3\right\}\\ {\Gamma }_6=\left\{X\in ℂ:\left|X\right|\le 1+2=3\right\}\\ {\Gamma }_8=\left\{X\in ℂ:\left|X-1\right|\le 1\right\}\end{array}$

So ${\Gamma }^{\left(0\right)}={\Gamma }_2\cup {\Gamma }_8={\Gamma }_2=\left\{X\in ℂ:\left|X\right|\le 6\right\}$.

Then, all the zeros of the polynomial $P\left(X\right)$ are therefore included in the disk: ${\Gamma }^{\left(0\right)}\left\{X\in ℂ\mathrm{<mo>\; :\; </mo>}\left|X\right|\le 6\right\}$.

3. Modified Disks of Gershgorin

3.1. Improved Bounds for Roots of Polynomials by Modifying the Disks of Gershgorin for Companion Matrices

The general form of the Gershgorin’s theorem doesn’t exploit the specific structure of the matrix. By rewriting the equations from which we obtain the Gershgorin’s disks and by exploiting them, we can obtain improved forms of those disks. More generally, we consider x and $\lambda$ respectively eigenvalue and eigenvector of the companion matrix $C\left(P\right)$, we have:

$\lambda x=C\left(P\right)x$.

From this equality follows the equations:

$\begin{array}{l}\lambda x_1=-a_0{x}_n\\ \lambda x_2=x_1-a_1{x}_n\\ \lambda x_j=x_{j-1}-a_{j-1}{x}_n\text{where}\left(3\le j\le n-2\right)\\ \lambda x_{n-1}=x_{n-2}-a_{n-2}{x}_n\\ \lambda x_n=x_{n-1}-a_{n-1}{x}_n\end{array}$

This set of equations is used to modify the ${\Gamma }^{\left(0\right)}$ disks of Gershgorin in order to obtain ${\Gamma }^{\left(1\right)}$ which allows to obtain an improvement of the bounds of the roots for polynomials. For this, we first make changes on ${\Gamma }_1$ to ${\Omega }_1$ and then ${\Gamma }_2$ to ${\Omega }_2$ respectively. Each step produces a new set of zero inclusions that are summarized in the following theorem [1].

Theorem 2. Let $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$, $a_0\ne 0$, be a polynomial $\in ℂ\left[X\right]$. All the zeros $\lambda$ of $P\left(X\right)$ can be found in the set ${\Gamma }^{\left(1\right)}$ where:

${\Gamma }^{\left(1\right)}={\Omega }_1\cup \left({\displaystyle {\cup }_{j=2}^n}{\Gamma }_j\right).$

We then have: $\left|\lambda \right|\le \left|{\Gamma }^{\left(1\right)}\right|=\max \left\{\gamma ,1+\left|a_1\right|,\cdots ,1+\left|a_{n-1}\right|\right\}$ where $\left|{\Omega }_1\right|=\gamma$.

Likewise, all the zeros $\lambda$ of $P\left(X\right)$ can be found in the set ${\Gamma }^{\left(2\right)}$ where:

${\Gamma }^{\left(2\right)}={\Omega }_1\cup {\Omega }_2\cup \left({\displaystyle {\cup }_{j=3}^n}{\Gamma }_j\right).$

We also then have: $\left|\lambda \right|\le \left|{\Gamma }^{\left(2\right)}\right|=\max \left\{\gamma ,\delta ,\cdots ,1+\left|a_{n-1}\right|\right\}$ where $\left|{\Omega }_2\right|=\delta$.

Proof. In order to change respectively ${\Gamma }_1$ to ${\Omega }_1$ and then ${\Gamma }_2$ to ${\Omega }_2$, some steps are required. Each step allows to calculate a bound on the moduli of the zeros for the obtained modified set.

First modified disk ${\Omega }_1$

We consider the vector x to be the eigenvector with the greatest absolute value. About this modification, we start from the equation $\lambda x_1=-a_0{x}_n$. We eliminate $x_n$ in the equation $\lambda x_n=x_{n-1}-a_{n-1}{x}_n$.

It gives: $\lambda \left(\lambda +a_{n-1}\right)x_1=-a_0{x}_{n-1}$. So if $x_1$ has the greatest coefficient’s absolute value of the eigenvector x, we obtain $\left|\lambda \right|\le \left|a_0\right|$ in addition to the inequality.

We obtain another inequality that must be satisfied by $\lambda$ precisely $\left|\lambda \right|\left|\lambda +a_{n-1}\right|\le \left|a_0\right|$.

We then define:

$K_1=\left\{z\in ℂ\mathrm{<mo>\; :\; </mo>}\left|z\right|\left|z+a_{n-1}\right|\le \left|a_0\right|\right\}$.

${\Omega }_1={\Gamma }_1\cap K_1$.

The limit of $K_1$ is a quartic curve known as the oval of Cassini. It consists of either one or two loops. Ovals of Cassini also appear in a different and slightly more complicated eigenvalue inclusion set. We can therefore choose to replace ${\Gamma }_1$ by ${\Omega }_1$ in Gershgorin’s theorem.

Since ${\Omega }_1\subseteq {\Gamma }_1$, we clearly have ${\Gamma }^{\left(1\right)}\subseteq {\Gamma }^{\left(0\right)}$. The new obtained set of inclusions is smaller than ${\Gamma }^{\left(0\right)}$. We can expect this to happen when $\left|a_0\right|$ is large enough for ${\Gamma }_1$ to dominate ${\Gamma }^{\left(0\right)}$.

By changing ${\Omega }_0$ to ${\Omega }_1$, from ${\Gamma }^{\left(0\right)}=\left({\displaystyle {\cup }_{j=1}^n}{\Gamma }_j\right)$, we then get:

${\Gamma }^{\left(1\right)}={\Omega }_1\cup \left({\displaystyle {\cup }_{j=2}^n}{\Gamma }_j\right).$

Let $\gamma \in ℝ$, so that $\left|{\Omega }_1\right|=\gamma$. It follows that from equation 8 we can conclude that:

$\left|\lambda \right|\le \left|{\Gamma }^{\left(1\right)}\right|=\max \left\{\left|{\Omega }_1\right|,1+\left|a_1\right|,\cdots ,1+\left|a_{n-1}\right|\right\}=\max \left\{\gamma ,1+\left|a_1\right|,\cdots ,1+\left|a_{n-1}\right|\right\}$.

Hence the first part of the theorem.

Second modified disk ${\Omega }_2$

In the same way, we use the equation $\lambda x_1=-a_0{x}_n$. We eliminate $x_n$ in the equation $\lambda x_n=x_{n-1}-a_{n-1}{x}_n$. Then, we use it to replace $x_n$ by $\frac{-\lambda x_1}{{\alpha }_0}$ in the equation $\lambda x_2=x_1-a_1{x}_n$.

It gives $\lambda x_2=\left(1+\frac{a_1}{a_0}\lambda \right)x_1$.

Since $\left|x_2\right|\ge \left|x_j\right|$ for every j, then we have $\left|\lambda \right|\left|x_2\right|=\left|1+\frac{a_1}{a_0}\lambda \right|\left|x_x\right|$.

When we divide by $\left|x_2\right|$, it gives $\left|\lambda \right|\le \left|1+\frac{a_1}{a_0}\lambda \right|$.

This helps to define a new set $K_2=\left\{z\in ℂ\mathrm{<mo>\; :\; </mo>}\left|z\right|\le \left|1+\frac{a_1}{a_0}\lambda \right|\right\}$ and $\lambda \in K_2$.

However, since we have $\left|x_2\right|\ge \left|x_1\right|$ for every j, we have from $\lambda x_2=x_1-a_1{x}_n$ that $\lambda \in {\Gamma }_2$. It is a disk centered at the origin with radius $1+a_2$.

We conclude that, in this case, $\lambda \in {\Gamma }_2\cap K_2$. We define a set ${\Omega }_2$ so that ${\Omega }_2=\lambda \in {\Gamma }_2\cap K_2$. Similarly to the set ${\Gamma }^{\left(1\right)}$, from the equality ${\Gamma }^{\left(2\right)}={\Omega }_1\cup {\Omega }_2\cup \left({\displaystyle {\cup }_{j=3}^n}{\Gamma }_j\right)$, we can deduce that:

$\begin{array}{c}\left|\lambda \right|\le \left|{\Gamma }^{\left(2\right)}\right|=\max \left\{\left|{\Omega }_1\right|,\left|{\Omega }_2\right|,1+\left|a_2\right|,\cdots ,1+\left|a_{n-1}\right|\right\}\\ =\max \left\{\gamma ,\delta ,1+\left|a_2\right|,\cdots ,1+\left|a_{n-1}\right|\right\},\end{array}$

where $\left|{\Omega }_1\right|=\gamma$ and $\left|{\Omega }_2\right|=\delta$.

The theorem is proved.

From this theorem, we consider estimated values of the litteratur for our illustrative examples.

3.2. Improved Bound from the Hessenberg Matrices and Classical Usal Bounds of Roots for Polynomials

We announce the following theorem as principal result of this work. The first part of the theorem was already part of former issued paper [2]. The originality of the theorem comes from the fact that, by using the Hessenberg form, in the special case that ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$, we can automatically deduce a general constant bound for this kind of polynomials.

Theorem 3. (Hessenberg [2], [4] ).

Let $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$, $a_0\ne 0$, be a polynomial $\in ℂ\left[X\right]$. Any zero $\lambda$ of $P\left(X\right)$ satisfies the relation:

$\left|\lambda \right|\le {\Vert L_r\Vert }_{\infty }$ where $L_r=\left(\begin{array}{cccc}0& & I_r& 0\\ & & -a_{n-1}& \\ & 0& ⋮& I_{n-r-1}\\ & & -a_{r+1}& \\ -a_0& \cdots & -a_r& 0\end{array}\right)$

$r=\max \left\{k|{\displaystyle {\sum }_{i=0}^{k-1}}\left|a_i\right|<1\right\}$, $r=0$ if $\left|a_0\right|\ge 1$.

When: ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$ then $\left|\lambda \right|\le 1$.

Proof. The estimation of the general bound for $\left|\lambda \right|$ can be found in [2].

What to be proved is the case: ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$ then $\left|\lambda \right|\le 1$ ?

In this case, since ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$, from the first part of the theorem, we have for the matrix $L_{n-1}$ : $L_{n-1}=\mathcal{F}\left(P\right)$.

It follows that: $\left|\lambda \right|\le \max \left\{\mathrm{1\; <mo>\; ;\; </mo>}\left|a_1\right|+\left|a_2\right|+\cdots +\left|a_{n-1}\right|\right\}=1$.

We introduce the following theorem as a specific case of the modified disks of Gershgorin in which $\gamma$ and $\delta$ are computed. It will be followed by other theorems of the litteratur that will be used for comparison to estimate bounds for roots of some given polynomials.

Theorem 4. (Ovals of Cassini [1] ).

Let $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$, $a_0\ne 0$, be a polynomial $\in ℂ\left[X\right]$. Any zero $\lambda$ of $P\left(X\right)$ satisfies the relation $\lambda \le \left|\Gamma \right|$ where:

$\Gamma =\max \left\{\gamma ,\delta ,1+\left|a_2\right|,\cdots ,1+\left|a_{n-1}\right|\right\}$ (9)

$\gamma =\{\begin{array}{ll}\frac{1}{2}\left(\left|a_{n-1}\right|+\sqrt{{\left|a_{n-1}\right|}^2+4\left|a_0\right|}\right)\hfill & \left(\left|a_0\right|>1+\left|a_{n-1}\right|\right)\hfill \\ 0\hfill & \left(\left|a_0\right|\le 1+\left|a_{n-1}\right|\right)\hfill \end{array}$

$\delta =\{\begin{array}{ll}1+\frac{a_1}{\left|a_0\right|-\left|a_1\right|}\hfill & \left(\left|a_0\right|>1+\left|a_1\right|\right)\hfill \\ 1+\left|a_1\right|\hfill & \left(\left|a_0\right|\le 1+\left|a_1\right|\right)\hfill \end{array}$

Proof. The Equation (9) comes from the theorem 2. Values of $\Gamma$ and $\delta$ have been taken from [1] for our illustrative examples.

Theorem 5. (Dehmer [5] ).

Let $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$, $a_0\ne 0$, be a polynomial $\in ℂ\left[X\right]$. Any zero $\lambda$ of $P\left(X\right)$ satisfies the relation:

$\left|\lambda \right|\le \frac{1+{\varphi }_2}{2}+\frac{\sqrt{{\left({\varphi }_2-1\right)}^2+4M_1}}{2}\mathrm{.}$

$M_1\mathrm{<mo>\; :\; </mo>}=\underset{0\le i\le n-2}{\max }\left|a_j\right|\text{et}{\varphi }_2\mathrm{<mo>\; :\; </mo>}=\left|a_{n-1}\right|$

Proof. This bound is the usual bound found in the litteratur as Dehmer bound. It can be found in [5].

Theorem 6. (Cauchy, Montel and Carmichel-Mason [6] ).

Let $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$, $a_0\ne 0$, be a polynomial $\in ℂ\left[X\right]$. Any zero $\lambda$ of $P\left(X\right)$ satisfies the relation:

• Cauchy’s bound:

$\left|\lambda \right|\le \max \left\{\left|a_0\right|,1+\left|a_1\right|,\cdots ,1+\left|a_{n-1}\right|\right\}.$

• Montel’s bound:

$\left|\lambda \right|\le \max \left\{1,\left|a_0\right|+\left|a_1\right|+\cdots +\left|a_{n-1}\right|\right\}.$

• Carmichel-Mason’s bound:

$\left|\lambda \right|\le \sqrt{1+{\left|a_0\right|}^2+\cdots +{\left|a_{n-1}\right|}^2}\mathrm{.}$

Proof. Cauchy’s bound, Montel’s bound and Carmichel-Mason’s bound are classical bounds that are usually found in the litteratur. We do not prove them in this paper [6].

3.3. Illustrative Examples for Polynomials by Degree n = 5

In this section we will take some examples to illustrate the sharpness of the theorems on modified disks of Gershgorin for companion matrices. We will make a particular study on polynomial for degree $n=5$ by using following bounds: Ovals of Cassini, Hessenberg, Dehmer, Cauchy, Montel and Carmichel-Mason. All the bounds that are going to be used are listed in Figure 1. Illustrative examples have been given in this section.

Example 2. Let $P_1\left(X\right)=X^5+4X^4+3X^3+2X^2+X+5\in ℂ\left[X\right]$. We have: $a_0=5\Rightarrow \left|a_0\right|>1$.

The roots and their bounds of polynomial $P_1\left(X\right)$ are illustrated in Table 1 and Table 2.

Example 3. Soit $P_2\left(X\right)=X^5-10X^4+30X^3-20X^2-31X+30\in ℂ\left[X\right]$. The roots and their bounds of the polynomial $P_2\left(X\right)$ are illustrated in Table 3 and Table 4.

Example 4. Soit $P_3\left(X\right)=X^5-19X^4+126X^3-346X^2+385X-147\in ℂ\left[X\right]$. The roots and their bounds of polynomial $P_3\left(X\right)$ are illustrated in Table 5 and Table 6.

Table 1. Bounds for roots of polynomial $P_1$.

Table 2. Roots of $P_1$ computed with Scilab.

Table 3. Summary of the bounds of the polynomial $P_2$.

Table 4. Estimation of the bounds of the zeros of $P_2$ (Traces matrices of Graeffe [7] ).

Figure 1. Summary of bounds for roots by degree $n=5$.

Table 5. Summary of the bounds of the polynomial for $P_3$.

Table 6. Estimation of the bounds of the zeros of $P_3$ (Traces Matrices of Graeffe [7] ).

We can see that the sparse companion matrices become interesting for use, in case of small values of the coefficients of polynomials. This is why we make a closer look at these cases.

Example 5. Let

$P_4\left(X\right)=X^5+0.04X^4+0.03X^3+0.02X^2+0.01X+0.05\in ℂ\left[X\right]$.

if $a_0=0.05$, then $\left|a_0\right|<1$, $\left|a_0\right|\ne 0$ and

$\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|+\left|a_4\right|=0.05+0.01+0.02+0.03+0.04=0.15$.

The roots and their bounds of the polynomial $P_4\left(x\right)$ are illustrated in Table 7 and Table 8.

Example 6. Let

$P_5\left(X\right)=X^5-{10}^{\left(-5\right)}{X}^4+{10}^{\left(-6\right)}{X}^3-{10}^{\left(-7\right)}{X}^2+{10}^{\left(-8\right)}X-{10}^{\left(-9\right)}\in ℂ\left[X\right]$.

We have:

$\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|+\left|a_4\right|={10}^{\left(-9\right)}+{10}^{\left(-8\right)}+{10}^{\left(-7\right)}+{10}^{\left(-6\right)}+{10}^{\left(-5\right)}<1$.

The roots and their bounds of the polynomial $P_3\left(X\right)$ are illustrate in Table 9 and Table 10.

Table 7. Summary of the bounds of the polynomial for $P_4$.

Table 8. Roots of polynomial $P_4$ computed with Scilab.

Table 9. Summary of the bounds of the polynomial for $P_3$.

Table 10. Roots of polynomial $P_4$ computed with Scilab.

4. Conclusions

We have studied several methods of estimating bounds for zeros of a polynomial. We first present different matrices that are used in this paper. We begin by presenting companion matrices and cyclic matrices in order to introduce Frobenius companion matrices and Frobenius decomposition’s theorem of matrices into diagonal block of companion matriices. We also present Fiedler matrices and then we introduce the Gershgorin’s theorem. As the standard Gershgorin’s theorem doesn’t exploit the specific structure of the matrix, we apply it to a Frobenius companion matrix, that is also a Fiedler matrix after modifying the first and the second Gershgorin disks. The obtained new union of disks after the modification, called ovals of Cassini, allows us to estimate news expression of bounds for roots for a given polynomials [1].

Furthermore, the classical bounds resulting from the application of Gershgorin’s theorem like Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds are presented.

Otherwise explicit expressions of bounds of the zeros of the polynomials have been presented by using Hessenberg matrices for the $\infty$ -norm. The estimation of bound in the Hessenberg form is made through the estimation of the variable $r=\max \left\{k|{\displaystyle {\sum }_{i=0}^{k-1}}\left|a_i\right|<1\right\}$. We have already found in precedent studies that the more the coefficents are closed to zeros with a norm lower than 1, the more the approach by the Hessenberg matrices is indicated. This justifies why we study forms of polynomials in special cases of polynomial’s coefficients when ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$. In this cases, the roots of the polynomials satisfy automatically the relation $\left|\lambda \right|\le 1$. All the forms of the bounds have been listed in a table in order to start a comparison through manual computation.

As experimental part of this paper, we take many illustrative examples of polynomials for degrees $n=5$, in order to compare our obtained bounds to absolute values of the exact roots. Bounds for the roots from our improved methods of the given polynomials have been manually computed. The exact roots have been computed with the software SCILAB and the Traces matrices of Graeffe [7] and then compared to our computed bounds. From our examples, we confirm that none of the classical methods gives alone the best value for both small values and high values of the polynomial’s coefficients. Some methods are indicated for small values while others are indicated for high values of these coefficients. But the Hessenberg method makes it possible to obtain good estimation of the bounds especially for small values of the coefficients. The Dehmer’s bound belongs also to the best in cases of some high value of polynomial’s coefficients. In all the cases, we note that no method makes it possible to estimate a bound which is lower than 1. However, in the case when ${\displaystyle {\sum }_{i=0}^{n-1}}\left|a_i\right|<1$, we need to be able to estimate bounds strictly less than 1 since the absolute values of the roots are less than 1. Hence a study on polynomials to find special formula that gives a bound less than 1 is indicated. As future research topic, it will be interesting to find forms of matrices and methods that can provide bounds strictly less than 1 for a polynomials if there is any.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Melman, A. (2012) Modified Gershgorin Disks for Companion Matrices. Society for Industrial and Applied Mathematics SIAM, 54, 355-373. https://doi.org/10.1137/100797667
[2]	Bondabou, M.A., Tessa, O.M. and Morou, A. (2021) Bounds for Polynomial’s Roots from Fiedler and Sparse Companion Matrices for Submultiplicative Matrix Norms. Advances in Linear Algebra and Matrix Theory, 11, 1-13. https://doi.org/10.4236/alamt.2021.111001
[3]	Eastman, B., Kim, I.J., Shader, B.L. and Vander Meulen, K.N. (2014) Companion Matrices Patterns. Linear Algebra and Its Applications, 463, 255-272. https://doi.org/10.1016/j.laa.2014.09.010
[4]	Vander Meulen, K.N. and Vanderwoerd, T. (2018) Bounds on Polynomial Roots Using Intercyclic Companion Matrices. Linear Algebra and Its Applications, 539, 94-116. https://doi.org/10.1016/j.laa.2017.11.002
[5]	Dehmer, M. and Tsoy, Y.R. (2012) The Quality of Zero Bounds for Complex Polynomials. PLoS ONE, 7, e39537. https://doi.org/10.1371/journal.pone.0039537
[6]	De Terán, F., Dopico, F.M. and Pérez, J. (2014) New Bounds for Roots of Polynomials Based on Fiedler Companion Matrices. Linear Algebra and Its Applications, 451, 197-230. https://doi.org/10.1016/j.laa.2014.03.013
[7]	Tessa, O.M. and Salou, M. (2014) Estimated Bounds for Zeros of Polynomials from Traces of Graeffe. Advances in Linear Algebra & Matrix Theory, 4, 210-215.