Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 GeneralizedFiedlerMatrix

Source Notebook

Generate the generalized Fiedler companion matrix of a univariate polynomial

Contributed by: Jan Mangaldan

ResourceFunction["GeneralizedFiedlerMatrix"][poly,x]

gives the Fiedler companion matrix of poly, treated as a polynomial in x.

ResourceFunction["GeneralizedFiedlerMatrix"][perm,poly,x]

gives the generalized Fiedler companion matrix associated with the permutation perm.

Details and Options

The Fiedler companion matrix of a univariate polynomial is a pentadiagonal matrix whose characteristic polynomial is a scalar multiple of the original polynomial.
The generalized Fiedler companion matrix of a univariate polynomial is a sparse matrix whose characteristic polynomial is a scalar multiple of the original polynomial.
The permutation perm can be in a disjoint cycle or permutation list representation.

Examples

Basic Examples (2) 

Generate a Fiedler companion matrix:

In[1]:=
ResourceFunction["GeneralizedFiedlerMatrix"][ 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[1]=

The characteristic polynomial of this matrix is a constant multiple of the original polynomial:

In[2]:=
CharacteristicPolynomial[%, x]
Out[2]=

Scope (3) 

Generate the regular Fiedler matrix:

In[3]:=
ResourceFunction["GeneralizedFiedlerMatrix"][ 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[3]=

Use a different permutation:

In[4]:=
ResourceFunction["GeneralizedFiedlerMatrix"][{3, 1, 4, 5, 2}, 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[4]=

Use a disjoint cycle representation of a permutation:

In[5]:=
ResourceFunction["GeneralizedFiedlerMatrix"][ Cycles[{{1, 3, 4, 5, 2}}], 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[5]=

Applications (2) 

Numerically find the roots of a polynomial by computing the eigenvalues of its Fiedler companion matrix:

In[6]:=
Eigenvalues[ N[ResourceFunction["GeneralizedFiedlerMatrix"][ 1 + 2 x + 3 x^2 + 4 x^3, x]]]
Out[6]=

Compare with the result of NSolve:

In[7]:=
x /. NSolve[1 + 2 x + 3 x^2 + 4 x^3 == 0, x]
Out[7]=

Properties and Relations (2) 

Different permutations may yield the same companion matrix:

In[8]:=
ResourceFunction["GeneralizedFiedlerMatrix"][Cycles[{{2, 4, 3, 5}}], 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[8]=
In[9]:=
ResourceFunction["GeneralizedFiedlerMatrix"][ Cycles[{{1, 4, 3}, {2, 5}}], 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[9]=

The Frobenius companion matrix (with polynomial coefficients placed on the first row) is a special case of the generalized Fiedler matrix:

In[10]:=
ResourceFunction["GeneralizedFiedlerMatrix"][Range[5, 1, -1], 5 + 4 x + 3 x^2 + 2 x^3 + x^4 + x^5, x] // MatrixForm
Out[10]=

Version History

  • 1.0.0 – 31 December 2020

Source Metadata

  • Citation:
    • De Terán, F., Dopico, F., Mackey, D.S., "Fiedler companion linearizations for rectangular matrix polynomials." Linear Algebra and its Applications, vol. 437, 957-991, 2012. DOI: 10.1016/S0024-3795(03)00548-2
    • Fiedler, M., "A note on companion matrices." Linear Algebra and its Applications, vol. 372, 325–331, 2003. DOI: 10.1016/S0024-3795(03)00548-2

Related Resources

License Information