Bounds for Polynomial’s Roots from Fiedler and Sparse Companion Matrices for Submultiplicative Matrix Norms

Mamoudou Amadou Bondabou¹, Ousmane Moussa Tessa¹, Amidou Morou²

¹Département de Mathématiques et d’Informatique, Université Abdou Moumouni, Niamey, Niger.
²Institut de Recherche sur l’Enseignement des Mathématiques, Université A. Moumouni de Niamey, Niamey, Niger.

DOI: 10.4236/alamt.2021.111001                

Abstract

We use submultiplicative companion matrix norms to provide new bounds for roots for a given polynomial P(X) over the field C[X]. From a n×n Fiedler companion matrix C, sparse companion matrices and triangular Hessenberg matrices are introduced. Then, we identify a special triangular Hessenberg matrix L_r, supposed to provide a good estimation of the roots. By application of Gershgorin’s theorems to this special matrix in case of submultiplicative matrix norms, some estimations of bounds for roots are made. The obtained bounds have been compared to known ones from the literature precisely Cauchy’s bounds, Montel’s bounds and Carmichel-Mason’s bounds. According to the starting formel of L_r, we see that the more we have coefficients closed to zero with a norm less than 1, the more the Sparse method is useful.

Keywords

Fiedler Matrices, Polynomial’s Roots, Bounds for Polynomials, Companion Matrices, Sparse Companion Matrices, Hessenberg Matrices, Submultiplicative Matrix Norm

1. Introduction

Approximating of roots for polynomials has been subject of several studies in mathematics and physics especially stability studies of dynamic system and automatism. There are various techniques for approximating the roots of a polynomial [1]. Some algorithms for determining the roots of a polynomial [2] rely on a good first approximation by using the coefficients of the polynomial [3]. Other methods for finding the roots of a polynomial $P\left(x\right)$ consist of finding the eigenvalues of a companion matrix [4]. To approximate the roots of $P\left(x\right)$, one can also apply Gershgorin’s Theorem [5] or use matrix norms on a companion matrix to find disks in the complex plane to locate the eigenvalues [6].

In this study, from special companion matrices of a given polynomial $P\left(x\right)$, improved methods of estimation of bounds for roots are developed by applying Gershgorin’s Theorem.

We first present Fiedler companion matrices and known bounds for polynomials. Secondly, from Fiedler matrices, we introduce sparse companion matrices and then triangular Hessenberg matrices. The methodology of providing a sharp bound for polynomial’s roots consists of identifying a special form of Hessenberg matrix that could give an improved value of bound in case of submultiplicative matrix norms. In the third part, through illustrative examples, we make a comparison of classical bounds to those obtained with the Sparse method.

Indeed, the Sparse method is well appropriated to estimate bounds: it gives the opportunity to estimate improved bounds for high as well as minor values of coefficients for polynomial’s degree $n=5$.

2. Bounds for Roots of Polynomial Based on Fiedler Companion Matrices

2.1. Generalities on Fiedler Companion Matrices

Let P be a polynomial $\in ℂ\left[X\right]$, $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$.

Let A be the associated companion matrix of $P\left(X\right)$.

Definition 1: A Fiedler companion matrix is the pattern of $2^{n-1}$ different matrices which have exactly the zeros of polynomial $P\left(X\right)$ as eigenvalue [2] [4] [7].

The first and the second Frobenius companion matrices, $C_1\left(P\right)$ and $C_2\left(P\right)$ of polynomial $P\left(X\right)$, are Fiedler matrices:

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

Some important properties of Fiedler matrices:

1) All Fiedler matrices are similar and so all of them have $P\left(X\right)$ as charactéristic polynomial [2];

2) Due to a symmetric property of the basis factors of Fiedler matrices, the transpose of any Fiedler matrix is another Fiedler matrix [7].

2.2. Principe of Providing Bounds for Polynomials Roots

The method of providing bounds for roots of polynomial $P\left(X\right)$ consist in applying the following Gershgorin’s theorem to Fiedler companion matrices, for any $\lambda \in ℂ$, root of $P\left(X\right)$, to determine the nonnegative numbers $L\left(P\right)$ and $U\left(P\right)$ depending on the coefficients of $P\left(X\right)$ such as [7]:

$L\left(P\right)\le \left|\lambda \right|\le U\left(P\right)\mathrm{.}$ (2)

We formally state the Gershgorin’s theorems and its application to companion matrices, in order to introduce the 1-norm and the ∞-norm.

Theorem 1. (Gershgorin’s Theorem and the 1-norm and ∞-norm) [6].

Let: $A=\left(a_{ij}\right)$ be an-by-n complex matrix, $\lambda \in ℂ$ an eigenvalue of matrix A.

$C_j={\displaystyle \underset{i=1,i\ne j}{\overset{n}{\sum }}\left|a_{ij}\right|}$ the modulus of non diagonal elements of the column j.

All the eigenvalues $\lambda$ of A are located in the union of the disks:

$\left|\lambda -a_{jj}\right|\le C_j,\left(j=1,2,\cdots ,n\right).$

For each eigenvalue $\lambda$ we have:

$\left|\lambda \right|\le \left|a_{jj}\right|+C_j=\underset{1\le j\le n}{\max }{\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|a_{ij}\right|.$ (3)

This is equivalent to the 1-norm: ${\Vert A\Vert }_1$. In the same way, we obtain the ∞-norm, ${\Vert A\Vert }_{\infty }$ [1]:

$\left|\lambda \right|\le \left|a_{ii}\right|+R_i=\underset{1\le i\le n}{\max }{\displaystyle \underset{j=1}{\overset{n}{\sum }}}\left|a_{ij}\right|$ (4)

2.3. Classical Bounds for Complex Polynomials Based on Gershgorin’s Theorems

The inequalities of theorem 1 have been used to get following classical bounds. [5]

Theorem 2. Let $P\left(X\right)=X^n+a_{n-1}{X}^{n-1}+\cdots +a_{1}X+a_0$ be a monic polynomial, $P\left(X\right)\in ℂ\left[X\right]$, $a_0\ne 0$ and $\lambda$ any root of $P\left(X\right)$. Then $\lambda$ satisfies the following classical inequalities [7]:

1) Cauchy’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with the ∞-norm, gives:

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

2) Montel’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_1$, gives:

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

3) Carmichel-Mason’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_2$, gives:

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

The 2-norm is: ${\Vert A\Vert }_2={\sigma }_{\max }\left(A\right)$.

4) Frobenius’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_F$, gives:

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

Some properties of the norms:

1) From Gerschgorin’s theorem, we can easily see that, bounds for roots of polynomials depend on the selected companion matrix for ${\Vert \mathrm{.}\Vert }_1$ and ${\Vert \mathrm{.}\Vert }_{\infty }$ : a good choice of a Fiedler Matrix can give improved values of bounds;

2) By using $C_1\left(P\right)$ instead of $C_2\left(P\right)={\left(C_1\left(P\right)\right)}^{\text{T}}$, we obtain:

Cauchy’s bounds for the ${\Vert \mathrm{.}\Vert }_1$ ;

Montel’s bounds for the ${\Vert \mathrm{.}\Vert }_{\infty }$.

3) From the symmetric property of $M_i$ factors we can conclude that for determination of the sharpest bounds of the 1-norm and the ∞-norm, we need to analyze only the ∞-norm of all Fiedler matrices and their inverses because this includes also the bounds coming from the 1-norm as far as ${\Vert \mathrm{.}\Vert }_1={\Vert {\mathrm{.}}^{\text{T}}\Vert }_{\infty }$.

As far as the value of the bound for roots of a polynomial depends on the seleted companion matrix, let us introduced types of companion matrices that can hopefully improved the bound’s value.

3. Sparse Companion Matrices

With the Fiedler method, developped in paragraph 2, bounds for roots of polynomials were determined by using the Fiedler companion matrices based on the products of block diagonal matrices introduced by Fiedler. Here we will take advantage of particular matrices called Sparse matrices in their special form precisely the Hessenberg form of the Fiedler companion matrices.

3.1. Generalties on Sparse Companion Matrices

We’ve seen that the Frobenius matrix is itself a Fiedler matrix. Sparse companion matrices has been recently characterized and they includes the Fiedler matrices as a special case.

Definition 2: the Frobenius companion matrix has exactly $n-1$ of the constant entries set to 1, the remaining ${\left(n-1\right)}^2$ constant entries are zero. As noted in [1], while a companion matrix must have at least $2n-1$ nonzero entries, there are companion matrices that have more than $2n-1$ nonzero entries. As such, we will say that a companion matrix is Sparse if it has exactly $2n-1$ nonzero entries. Sparse companion matrices have also been called intercyclic companion matrices because of an associated digraph structure as noted in [1].

If the $\left(n-1\right)$ nonzero constant entries of a sparse companion are set to 1, then this companion matrix is called unit sparse.

Example 1. For the Frobenius companion matrix $C_1\left(P\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& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& 0\end{array}\right)$ (9)

We have:

● $C_1\left(P\right)$ has $n-1$ entries set to 1 et n entries with the value $a_i$ ;

● ${\left(n-1\right)}^2$ entries of $C_1\left(P\right)$ are set to 0;

● $\left(2n-1\right)$ entries are nonzeros in case $a_i\ne \mathrm{0,}\forall i$.

Theorem 3. Let A be a $\left(n\times n\right)$ complex matrix. A is a unit sparse companion matrix if and only if A is equivalent to a unit lower Hessenberg matrix C for some $\left(n-m\right)\times \left(m+1\right)$ matrices K with $m\left(n-1-m\right)$ zero entries, such that C has $-a_{n-1-k}$ on its k^th subdiagonal, for $0\le k\le n-1$ [1].

$C=\left(\begin{array}{ccc}0& I_m& 0\\ & K& I_{n-m-1}\\ & & 0\end{array}\right)$ (10)

This form of matrix will be used to determin new bounds for roots of polynomials ( $I_m$ is the $m\times m$ identity matrix).

3.2. Improved Bounds for Roots of Polynomials by Using Fiedler Companion Matrices in Their Hessenberg Form in Case of Submultiplicative Matrix Norm

Due to the particular form of the unit lower Hessenberg matrix, that gives good possibilities for operations, it is important to check for a matrix in this form that provides good bounds. Thus, Vander Meulen establishes in [2] that there is a particular Fiedler matrix which provides the best upper bound for over all Fiedler matrices for the ∞-norm. This is obtained by using the following Hessenberg matrix.

Let $L_b$ be the following matrix:

$L_b=\left(\begin{array}{cccc}0& & I_b& 0\\ & & -a_{n-1}& \\ & 0& ⋮& I_{n-b-1}\\ & & -a_{b+1}& \\ -a_0& \dots & -a_b& 0\end{array}\right)$ (11)

$L_b$ is a Fiedler companion matrix in the form of Hessenberg [1]. This matrix is supposed to provide a good majoration of the eigenvalue for the infiny norm.

Theorem 4. Let P 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$ .

Let $F_b$ be a Fiedler companion matrix of P in the Hessenberg form with $a_b$ appearing in row n for some $b\in \left\{\mathrm{0,1,2,}\cdots \mathrm{,}n-2\right\}$ but $a_{b+1}$ is in row $a_{b+1}$.

Let $L_b$ be a Fiedler companion matrix in the form of Hessenberg.

Let $r\in \mathbb{N}$ so that:

$r=\max \left\{k|{\displaystyle \underset{i=0}{\overset{k-1}{\sum }}}\left|a_i\right|<1\right\},r=0\text{if}\left|a_0\right|\ge 1.$ (12)

Then for all $b\in \left\{\mathrm{0,1,2,}\cdots \mathrm{,}n-2\right\}$ :

${\Vert L_r\Vert }_{\infty }\le {\Vert L_b\Vert }_{\infty }\le {\Vert F_b\Vert }_{\infty }\mathrm{.}$ (13)

Thus for submultiplicative matrix norms, we have:

$\left|\lambda \right|\le {\Vert L_r\Vert }_{\infty }$ (14)

Proof.:

Equation (12) and (13) are respectively from theorems 4.1 and 4.2 in [1].

For $K=\max \left\{\left|a_i\right|,|i>b\right\}$ and $g=\max \left\{i|,\left|a_i\right|=K\right\}$. Then ${\Vert L_b\Vert }_{\infty }=\max \left\{1+K,{\displaystyle \underset{j=0}{\overset{b}{\sum }}\left|a_j\right|}\right\}$.

There are no other coefficients of P in the same row as $a_g$ in $L_b$ but there may be more coefficients in the same row as $a_g$ in $F_b$. Therefore ${\Vert F_b\Vert }_{\infty }\ge 1+K$ and ${\Vert F_b\Vert }_{\infty }\ge {\displaystyle \underset{j=0}{\overset{b}{\sum }}\left|a_j\right|}$. Thus ${\Vert F_b\Vert }_{\infty }\ge {\Vert L_b\Vert }_{\infty }$.

Suppose $b>r$. Then

$\begin{array}{c}{\Vert L_b\Vert }_{\infty }=\max \left\{{\displaystyle \underset{i=0}{\overset{b}{\sum }}\left|a_i\right|},1+\left|a_{b+1}\right|,1+\left|a_{b+2}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}\\ =\max \left\{{\displaystyle \underset{i=0}{\overset{r}{\sum }}\left|a_i\right|}+{\displaystyle \underset{i=r+1}{\overset{b}{\sum }}}\left|a_i\right|,1+\left|a_{b+1}\right|,1+\left|a_{b+2}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}\\ \ge \max \left\{{\displaystyle \underset{i=0}{\overset{r}{\sum }}\left|a_i\right|},1+\left|a_{r+1}\right|,1+\left|a_{r+2}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}={\Vert L_r\Vert }_{\infty }\end{array}$

Suppose $b<r$. Then

$\begin{array}{c}{\Vert L_b\Vert }_{\infty }=\max \left\{{\displaystyle \underset{i=0}{\overset{b}{\sum }}\left|a_i\right|},1+\left|a_{b+1}\right|,1+\left|a_{b+2}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}\\ =\max \left\{1+\left|a_{b+1}\right|,1+\left|a_{b+2}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}\\ \ge \max \left\{1+\left|a_r\right|,1+\left|a_{r+1}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}\\ \ge \max \left\{{\displaystyle \underset{i=0}{\overset{r}{\sum }}\left|a_i\right|},1+\left|a_{r+1}\right|,1+\left|a_{r+2}\right|,\cdots ,1+\left|a_{n-1}\right|\right\}={\Vert L_r\Vert }_{\infty }\end{array}$

Since the ∞-norm is a matrix norm, we have ${\Vert A\cdot B\Vert }_{\infty }\le {\Vert A\Vert }_{\infty }\cdot {\Vert B\Vert }_{\infty }$ for any matrix. [1]

That means:

If $A=a_{ij}$, $B=b_{ij}$ and $AB={\left(ab\right)}_{ij}$.

${\Vert AB\Vert }_{\infty }=\underset{1\le i\le n}{\max }{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left|{\left(ab\right)}_{ij}\right|}\le \left(\underset{1\le i\le n}{\max }{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left|a_{ij}\right|}\right)\cdot \left(\underset{1\le i\le n}{\max }{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left|b_{ij}\right|}\right)={\Vert A\Vert }_{\infty }\cdot {\Vert B\Vert }_{\infty }$

$\Rightarrow {\Vert \mathrm{.}\Vert }_{\infty }$ is submultiplicative.

Consequently we have: $\left|\lambda \right|\le \Vert C\Vert$ for every eigenvalue $\lambda$ of matrix C. [1]

Since the eigenvalues of a companion matrix $C\left(P\right)$ are the same as the roots of P, this method can be used to find bounds for the roots of P.

So that: $\left|\lambda \right|\le {\Vert L_r\Vert }_{\infty }\le {\Vert L_b\Vert }_{\infty }\le {\Vert F_b\Vert }_{\infty }$. $\square$

Through illustrative examples in case of polynomial by degree $n=5$, we can try to see how sharp this theorem is.

4. Illustrative Examples

4.1. Determination of Bounds for Roots of Polynomials for n = 5

In this section we make a particular study on polynomial for degree $n=5$ by using theorem 4 about sparse companion matrices. The result will be compared to bounds from Cauchy, Montel nd Carmichel-Mason’s theorems [3].

Let $P\left(X\right)=X^5+a_4{X}^4+a_3{X}^3+a_2{X}^2+a_{1}X+a_0\in ℂ\left[X\right]$, with $a_0\ne 0$.

It is about to use theorems 4 to determin a best formula which gives good bounds.

● First case: $\left|a_0\right|\ge 1$.

By application of theorem 4, we obtain: $r=0$ then $\left|\lambda \right|\le {\Vert L_0\Vert }_{\infty }$.

$L_0=C_2\left(P\right)=\left(\begin{array}{ccccc}-a_4& 1& 0& 0& 0\\ -a_3& 0& 1& 0& 0\\ -a_2& 0& 0& 1& 0\\ -a_1& 0& 0& 0& 1\\ -a_0& 0& 0& 0& 0\end{array}\right)$

Then $\left|\lambda \right|\le {\Vert L_0\Vert }_{\infty }=\max \left\{1+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_3\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_2\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_1\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|\right\}$.

This is Cauchy’s bound applied to $C_2\left(P\right)$ with the ∞-norm.

● Second case: $\left|a_0\right|<1$ but $\left|a_0\right|+\left|a_1\right|\ge 1$.

By application of theorem 4, we obtain: $r=1$ then $\left|\lambda \right|\le {\Vert L_1\Vert }_{\infty }$.

$L_1=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& -a_4& 1& 0& 0\\ 0& -a_3& 0& 1& 0\\ 0& -a_2& 0& 0& 1\\ -a_0& -a_1& 0& 0& 0\end{array}\right)$

Then $\left|\lambda \right|\le {\Vert L_1\Vert }_{\infty }=\max \left\{\mathrm{1\; <mo>\; ;\; </mo>1}+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_3\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_2\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|\right\}$.

$\Rightarrow \left|\lambda \right|\le \max \left\{1+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_3\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_2\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|\right\}$.

● Third case: $\left|a_0\right|+\left|a_1\right|<1$ but $\left|a_0\right|+\left|a_1\right|+\left|a_2\right|\ge 1$.

By application of theorem 4, we obtain: $r=2$ then $\left|\lambda \right|\le {\Vert L_2\Vert }_{\infty }$

$L_2=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& -a_4& 1& 0\\ 0& 0& -a_3& 0& 1\\ -a_0& -a_1& -a_2& 0& 0\end{array}\right)$

Then $\left|\lambda \right|\le {\Vert L_2\Vert }_{\infty }=\max \left\{\mathrm{1\; <mo>\; ;\; </mo>1}+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_3\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|+\left|a_2\right|\right\}$.

$\Rightarrow \left|\lambda \right|\le \max \left\{1+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>1}+\left|a_3\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|+\left|a_2\right|\right\}$.

● Fourth case: $\left|a_0\right|+\left|a_1\right|+\left|a_2\right|<1$ but $\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|\ge 1$.

By application of theorem 4, we obtain: $r=3$ then $\left|\lambda \right|\le {\Vert L_3\Vert }_{\infty }$

$L_3=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& -a_4& 1\\ -a_0& -a_1& -a_2& -a_3& 0\end{array}\right)$

Then $\left|\lambda \right|\le {\Vert L_3\Vert }_{\infty }=\max \left\{1+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|\right\}$.

$\Rightarrow \left|\lambda \right|\le \max \left\{1+\left|a_4\right|\mathrm{<mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|\right\}$.

● Fifth case: $\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|<1$

By application of 4, we obtain: $r=4$ then $\left|\lambda \right|\le {\Vert L_4\Vert }_{\infty }$

$L_4=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ -a_0& -a_1& -a_2& -a_3& -a_4\end{array}\right)$

Then $\left|\lambda \right|\le {\Vert L_4\Vert }_{\infty }=\max \left\{\mathrm{1\; <mo>\; ;\; </mo>}\left|a_0\right|+\left|a_1\right|+\left|a_2\right|+\left|a_3\right|+\left|a_4\right|\right\}$ : this is Montel’s bounds applied to $C_2\left(P\right)$ with the 1-norm.

Table 1 presentes the different cases of bounds for degree $n=5$.

4.2. Examples of Polynomials for n = 5

Example 2:

Let $P\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$.

Then:

1) By application of theorem 4, we obtain:

$\left|\lambda \right|\le {\Vert L_0\Vert }_{\infty }=\max \left\{1+4;1+3;1+2;1+1;5\right\}=5$.

2) Cauchy’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with the ∞-norm, gives:

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

$\Rightarrow \left|\lambda \right|\le \max \left\{\left|5\right|,1+\left|1\right|,1+\left|2\right|,1+\left|3\right|,1+\left|4\right|\right\}$

Table 1. Bounds for polynomials by degree $n=5$.

$\Rightarrow \left|\lambda \right|\le \max \left\{5,2,3,4,5\right\}$

$\Rightarrow \left|\lambda \right|\le 5$

3) Montel’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_1$, gives:

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

$\Rightarrow \left|\lambda \right|\le \max \left\{1,5+1+2+3+4\right\}$

$\Rightarrow \left|\lambda \right|\le 15$

4) Carmichel-Mason’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_2$, gives:

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

$\Rightarrow \left|\lambda \right|\le \sqrt{1+{\left|a_0\right|}^2+\cdots +{\left|a_4\right|}^2}$

$\Rightarrow \left|\lambda \right|\le \sqrt{1+5^2+1^2+2^2+3^2+4^2}$

$\Rightarrow \left|\lambda \right|\le \sqrt{56}\approx 7.48$

The roots and their bounds for example 2 are illustrated in Table 2, Table 3 and Figure 1 [6].

We can see that, the Sparse companion matrix becomes interesting in case of small value of polynomial’s coefficients. Let us then choose a polynomial with small values.

Example 3:

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

We have: $a_0=0.05\Rightarrow \left|a_0\right|<1$, $\left|a_0\right|\ne 0$.

$\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$

Table 2. Bounds for the given polynomial P.

Table 3. Roots of given polynomial P computed through Scilab.

Figure 1. Bounds for polynomial of example 1.

Then:

1) By application of theorem 4, we have the fifth case of Sparse and obtain $\left|\lambda \right|\le \max \left\{1;\left|a_0\right|+\cdots +\left|a_4\right|\right\}=1$.

2) Cauchy’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with the ∞-norm, gives:

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

$\Rightarrow \left|\lambda \right|\le \max \left\{\left|0.05\right|,1+\left|0.01\right|,1+\left|0.02\right|,1+\left|0.03\right|,1+\left|0.04\right|\right\}$

$\Rightarrow \left|\lambda \right|\le \max \left\{0.05,1.01,1.02,1.03,1.04\right\}$

$\Rightarrow \left|\lambda \right|\le 1.04$

3) Montel’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_1$, gives:

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

$\Rightarrow \left|\lambda \right|\le \max \left\{1,0.05+0.01+0.02+0.03+0.04\right\}$

$\Rightarrow \left|\lambda \right|\le 1$

4) Carmichel-Mason’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix $C_2\left(P\right)$ with ${\Vert \mathrm{.}\Vert }_2$, gives:

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

$\Rightarrow \left|\lambda \right|\le \sqrt{1+{\left|a_0\right|}^2+\cdots +{\left|a_4\right|}^2}$

$\Rightarrow \left|\lambda \right|\le \sqrt{1+{0.05}^2+{0.01}^2+{0.02}^2+{0.03}^2+{0.04}^2}$

$\Rightarrow \left|\lambda \right|\le \sqrt{1.0055}\approx 1.0027462291$

The roots and their bounds for example 2 are illustrated in Table 4, Table 5 and Figure 2 [6].

Table 4. Summary of the bounds for the given polynomial P.

Table 5. Roots of given polynomial P computed through Scilab.

Figure 2. Bounds for polynomial of example 2.

4.3. Results

In this section, we investigate about the Sparse method of providing improved bounds of roots for polynomials. We compare bounds of roots of polynomial obtained by the Sparse method, to those found in the literature. According to the starting formel given in (12), we saw that the more we have coefficients closed to zero with a norm less than 1, the more the Sparse method is useful. Indeed for

$r=\max \left\{k|{\displaystyle \underset{i=0}{\overset{k-1}{\sum }}\left|a_i\right|}<1\right\}$ :

1) When $r=0$, the obtained Sparse matrices $L_0$ are similar to a Frobenius matrix. This occurs when $\left|a_0\right|\ge 1$. In this case, the theorem gives the same result as Cauchy’s bounds;

2) When $r=n-1$, the obtained matrices $L_{n-1}$ are also similar to a Frobenius matrix. But in this case, the theorem become very useful and brings very interesting bounds with high effectiveness of use. This occurs when ${\displaystyle \underset{i=0}{\overset{n-1}{\sum }}\left|a_i\right|}<1$.

Examples of bounds have been evaluated in case of polynomials by degree $n=5$ to illustrate how sharp the Sparse method is. In those examples, we saw that:

1) For high value of given polynomial’s coefficients, Cauchy gives similar bounds as the Sparse form. Those obtained bounds are better than Montel and Carmichel-Mason’s bounds;

2) For very minor values of the polynomial’s coefficients, the sharpest bounds are the Sparse and Montel’s ones.

In the above studied cases, each considered classical method couldn’t give itself sharpest bounds for high and minor values of the given polynomial’s coefficients. Those methods are appropriated for high values or minor values of the coefficients but not for both of them. By using the Sparse matrices, the obtained bounds belong each time to the sharpest ones in the cases of high and minor coefficient’s values of a the given polynomials.

5. Conclusions

Explicit expressions of bounds of roots for polynomials are obtained by using Sparse Fiedler companion matrices for the ${\Vert \mathrm{.}\Vert }_{\infty }$. Classical bounds obtained by using Gershgorin’s Theorem (Cauchy’s bounds, Montel’s bounds, Carmichel-Mason’s bounds) and those obtained by using Sparse companion matrices are presented and compared. By using special Sparse matrices, the obtained bounds belong each time to the sharpest ones in the cases of high and minor coefficient’s values of the given polynomials due to a good estimation of the unit lower Hessenberg matrices for $r=\max \left\{k|{\displaystyle \underset{i=0}{\overset{k-1}{\sum }}\left|a_i\right|}<1\right\}$.

Through illustrative examples for degree $n=5$, we can see that the more the coefficients of the polynomial are closed to zero with a norm less than 1, the more the Sparse method is useful. Anyway, Sparse bounds belong to the best bounds for roots in the cases of the studied polynomials. The considered classical methods couldn’t give the sharpest bounds for high and minor values of the given polynomial’s coefficients. Those methods are appropriated for high values or minor values of the coefficients but not for both of them. The use of the Sparse method gives the opportunity to obtain at one time good bounds for a given polynomial in comparison to the considered classical methods, which give partially good bounds.

Next steps should include other degrees of polynomials for degrees $n>5$.

Conflicts of Interest

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

References

[1]	Meulen, K.N.V. 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
[2]	Eastman, B., Kim, I.J., Shader, B.L. and Meulen, K.N.V. (2014) Companion Matrices Patterns. Linear Algebra and Its Applications, 463, 255-272. https://doi.org/10.1016/j.laa.2014.09.010
[3]	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
[4]	Fiedler, M. (2003) A Note on Companion Matrices. Linear Algebra and Its Applications, 372, 325-331. https://doi.org/10.1016/S0024-3795(03)00548-2
[5]	Mignotte, M. (1992) Mathematics for Computer Algebra. Springer Verlag, New York. https://doi.org/10.1007/978-1-4613-9171-5
[6]	Melman, A. (2012) Modified Gershgorin Disks for Companion Matrices. Society for Industrial and Applied Mathematics, 54, 355-373. https://doi.org/10.1137/100797667
[7]	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