Condition numbers for inversion of Fiedler companion matrices

Fernando De Terán, Froilán M. Dopico, Javier Pérez

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)944-981
Number of pages38
JournalLinear Algebra and Its Applications
Volume439
Issue number4
DOIs
StatePublished - 2013

Keywords

  • Condition numbers
  • Fiedler companion matrices
  • Frobenius companion matrices
  • Inverses of Fiedler companion matrices
  • Polynomials
  • Singular values
  • Staircase matrices

Fingerprint

Dive into the research topics of 'Condition numbers for inversion of Fiedler companion matrices'. Together they form a unique fingerprint.

Cite this