TY - JOUR

T1 - Condition numbers for inversion of Fiedler companion matrices

AU - De Terán, Fernando

AU - Dopico, Froilán M.

AU - Pérez, Javier

N1 - Funding Information:
This work was partially supported by the Ministerio de Economía y Competitividad of Spain through grant MTM-2009-09281. Corresponding author. Tel.: +34 916249446; fax: +34 916249129. E-mail addresses: [email protected] (F. De Terán), [email protected] (F.M. Dopico), [email protected] (J. Pérez).

PY - 2013

Y1 - 2013

N2 - The Fiedler matrices of a monic polynomial p(z) of degree n are n × n matrices with characteristic polynomial equal to p(z) and whose nonzero entries are either 1 or minus the coefficients of p(z). Fiedler matrices include as particular cases the classical Frobenius companion forms of p(z). Frobenius companion matrices appear frequently in the literature on control and signal processing, but it is well known that they posses many properties that are undesirable numerically, which limit their use in applications. In particular, as n increases, Frobenius companion matrices are often nearly singular, i.e., their condition numbers for inversion are very large. Therefore, it is natural to investigate whether other Fiedler matrices are better conditioned than the Frobenius companion matrices or not. In this paper, we present explicit expressions for the condition numbers for inversion of all Fiedler matrices with respect the Frobenius norm, i.e., AF=∑ij| aij|2. This allows us to get a very simple criterion for ordering all Fiedler matrices according to increasing condition numbers and to provide lower and upper bounds on the ratio of the condition numbers of any pair of Fiedler matrices. These results establish that if |p(0)|≤1, then the Frobenius companion matrices have the largest condition number among all Fiedler matrices of p(z), and that if |p(0)|>1, then the Frobenius companion matrices have the smallest condition number. We also provide families of polynomials where the ratio of the condition numbers of pairs of Fiedler matrices can be arbitrarily large and prove that this can only happen when both Fiedler matrices are very ill-conditioned. We finally study some properties of the singular values of Fiedler matrices and determine how many of the singular values of a Fiedler matrix are equal to one.

AB - The Fiedler matrices of a monic polynomial p(z) of degree n are n × n matrices with characteristic polynomial equal to p(z) and whose nonzero entries are either 1 or minus the coefficients of p(z). Fiedler matrices include as particular cases the classical Frobenius companion forms of p(z). Frobenius companion matrices appear frequently in the literature on control and signal processing, but it is well known that they posses many properties that are undesirable numerically, which limit their use in applications. In particular, as n increases, Frobenius companion matrices are often nearly singular, i.e., their condition numbers for inversion are very large. Therefore, it is natural to investigate whether other Fiedler matrices are better conditioned than the Frobenius companion matrices or not. In this paper, we present explicit expressions for the condition numbers for inversion of all Fiedler matrices with respect the Frobenius norm, i.e., AF=∑ij| aij|2. This allows us to get a very simple criterion for ordering all Fiedler matrices according to increasing condition numbers and to provide lower and upper bounds on the ratio of the condition numbers of any pair of Fiedler matrices. These results establish that if |p(0)|≤1, then the Frobenius companion matrices have the largest condition number among all Fiedler matrices of p(z), and that if |p(0)|>1, then the Frobenius companion matrices have the smallest condition number. We also provide families of polynomials where the ratio of the condition numbers of pairs of Fiedler matrices can be arbitrarily large and prove that this can only happen when both Fiedler matrices are very ill-conditioned. We finally study some properties of the singular values of Fiedler matrices and determine how many of the singular values of a Fiedler matrix are equal to one.

KW - Condition numbers

KW - Fiedler companion matrices

KW - Frobenius companion matrices

KW - Inverses of Fiedler companion matrices

KW - Polynomials

KW - Singular values

KW - Staircase matrices

UR - http://www.scopus.com/inward/record.url?scp=84879883895&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2012.09.020

DO - 10.1016/j.laa.2012.09.020

M3 - Article

AN - SCOPUS:84879883895

SN - 0024-3795

VL - 439

SP - 944

EP - 981

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 4

ER -