Bounds for Polynomial’s Roots from Fiedler and Sparse Companion Matrices for Submultiplicative Matrix Norms ()
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
consist of finding the eigenvalues of a companion matrix [4]. To approximate the roots of
, 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
, 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
.
2. Bounds for Roots of Polynomial Based on Fiedler Companion Matrices
2.1. Generalities on Fiedler Companion Matrices
Let P be a polynomial
,
.
Let A be the associated companion matrix of
.
Definition 1: A Fiedler companion matrix is the pattern of
different matrices which have exactly the zeros of polynomial
as eigenvalue [2] [4] [7].
The first and the second Frobenius companion matrices,
and
of polynomial
, are Fiedler matrices:
(1)
Some important properties of Fiedler matrices:
1) All Fiedler matrices are similar and so all of them have
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
consist in applying the following Gershgorin’s theorem to Fiedler companion matrices, for any
, root of
, to determine the nonnegative numbers
and
depending on the coefficients of
such as [7]:
(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:
be an-by-n complex matrix,
an eigenvalue of matrix A.
the modulus of non diagonal elements of the column j.
All the eigenvalues
of A are located in the union of the disks:
For each eigenvalue
we have:
(3)
This is equivalent to the 1-norm:
. In the same way, we obtain the ∞-norm,
[1]:
(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
be a monic polynomial,
,
and
any root of
. Then
satisfies the following classical inequalities [7]:
1) Cauchy’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix
with the ∞-norm, gives:
(5)
2) Montel’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
(6)
3) Carmichel-Mason’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
(7)
The 2-norm is:
.
4) Frobenius’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
(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
and
: a good choice of a Fiedler Matrix can give improved values of bounds;
2) By using
instead of
, we obtain:
Cauchy’s bounds for the
;
Montel’s bounds for the
.
3) From the symmetric property of
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
.
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
of the constant entries set to 1, the remaining
constant entries are zero. As noted in [1], while a companion matrix must have at least
nonzero entries, there are companion matrices that have more than
nonzero entries. As such, we will say that a companion matrix is Sparse if it has exactly
nonzero entries. Sparse companion matrices have also been called intercyclic companion matrices because of an associated digraph structure as noted in [1].
If the
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
:
(9)
We have:
●
has
entries set to 1 et n entries with the value
;
●
entries of
are set to 0;
●
entries are nonzeros in case
.
Theorem 3. Let A be a
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
matrices K with
zero entries, such that C has
on its kth subdiagonal, for
[1].
(10)
This form of matrix will be used to determin new bounds for roots of polynomials (
is the
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
be the following matrix:
(11)
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,
.
Let
be a Fiedler companion matrix of P in the Hessenberg form with
appearing in row n for some
but
is in row
.
Let
be a Fiedler companion matrix in the form of Hessenberg.
Let
so that:
(12)
Then for all
:
(13)
Thus for submultiplicative matrix norms, we have:
(14)
Proof.:
Equation (12) and (13) are respectively from theorems 4.1 and 4.2 in [1].
For
and
. Then
.
There are no other coefficients of P in the same row as
in
but there may be more coefficients in the same row as
in
. Therefore
and
. Thus
.
Suppose
. Then
Suppose
. Then
Since the ∞-norm is a matrix norm, we have
for any matrix. [1]
That means:
If
,
and
.
is submultiplicative.
Consequently we have:
for every eigenvalue
of matrix C. [1]
Since the eigenvalues of a companion matrix
are the same as the roots of P, this method can be used to find bounds for the roots of P.
So that:
.
Through illustrative examples in case of polynomial by degree
, 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
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
, with
.
It is about to use theorems 4 to determin a best formula which gives good bounds.
● First case:
.
By application of theorem 4, we obtain:
then
.
Then
.
This is Cauchy’s bound applied to
with the ∞-norm.
● Second case:
but
.
By application of theorem 4, we obtain:
then
.
Then
.
.
● Third case:
but
.
By application of theorem 4, we obtain:
then
Then
.
.
● Fourth case:
but
.
By application of theorem 4, we obtain:
then
Then
.
.
● Fifth case:
By application of 4, we obtain:
then
Then
: this is Montel’s bounds applied to
with the 1-norm.
Table 1 presentes the different cases of bounds for degree
.
4.2. Examples of Polynomials for n = 5
Example 2:
Let
,
We have:
.
Then:
1) By application of theorem 4, we obtain:
.
2) Cauchy’s bounds: Gerschgorin’s theorem, applied to the second compagnon matrix
with the ∞-norm, gives:
Table 1. Bounds for polynomials by degree
.
3) Montel’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
4) Carmichel-Mason’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
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
We have:
,
.
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
.
2) Cauchy’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix
with the ∞-norm, gives:
3) Montel’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
4) Carmichel-Mason’s bound: Gerschgorin’s theorem, applied to the second compagnon matrix
with
, gives:
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
:
1) When
, the obtained Sparse matrices
are similar to a Frobenius matrix. This occurs when
. In this case, the theorem gives the same result as Cauchy’s bounds;
2) When
, the obtained matrices
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
.
Examples of bounds have been evaluated in case of polynomials by degree
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
. 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
.
Through illustrative examples for degree
, 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
.