Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 TridiagonalCompanionMatrix

Source Notebook

Generate the tridiagonal companion matrix of a univariate polynomial

Contributed by: Jan Mangaldan

ResourceFunction["TridiagonalCompanionMatrix"][poly,x]

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

Details

ResourceFunction["TridiagonalCompanionMatrix"] produces a tridiagonal matrix whose characteristic polynomial is a scalar multiple of the original polynomial.
ResourceFunction["TridiagonalCompanionMatrix"] returns a SparseArray object.

Examples

Basic Examples (2) 

Generate a tridiagonal companion matrix:

In[1]:=
ResourceFunction["TridiagonalCompanionMatrix"][ 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 (2) 

Tridiagonal companion matrix of a polynomial with complex coefficients:

In[3]:=
ResourceFunction[ "TridiagonalCompanionMatrix"][(x - 1 - I)^2 (x + I) (x + 1), x] // MatrixForm
Out[3]=

Tridiagonal companion matrix of a polynomial with symbolic coefficients:

In[4]:=
ResourceFunction["TridiagonalCompanionMatrix"][x^4 + b x^3 + c, x] // MatrixForm
Out[4]=

Applications (2) 

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

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

Compare with the result of NSolve:

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

Properties and Relations (4) 

A polynomial with real coefficients whose roots are all real has a symmetric tridiagonal companion matrix:

In[7]:=
ResourceFunction["TridiagonalCompanionMatrix"][ 24 - 96 x + 72 x^2 - 16 x^3 + x^4, x] // MatrixForm
Out[7]=
In[8]:=
{SymmetricMatrixQ[%], Eigenvalues[%]}
Out[8]=

If the polynomial has repeated roots, then the companion matrix is symmetric and block diagonal:

In[9]:=
ResourceFunction["TridiagonalCompanionMatrix"][(x^2 - x - 1)^2, x] // MatrixForm
Out[9]=
In[10]:=
{SymmetricMatrixQ[%], Eigenvalues[%]}
Out[10]=

A polynomial with real coefficients and complex roots will have a tridiagonal companion matrix with negative entries in its superdiagonal:

In[11]:=
ResourceFunction[ "TridiagonalCompanionMatrix"][(x^2 - 6 x + 25) (x^2 + x + 1), x] // MatrixForm
Out[11]=
In[12]:=
Eigenvalues[%]
Out[12]=

If the polynomial has repeated roots, the superdiagonal will also have zero entries:

In[13]:=
ResourceFunction["TridiagonalCompanionMatrix"][(x^2 - 6 x + 25)^2, x] // MatrixForm
Out[13]=
In[14]:=
Eigenvalues[%]
Out[14]=

Version History

  • 1.0.0 – 04 February 2021

Source Metadata

  • Citation:
    • Fiedler M., "Expressing a polynomial as characteristic polynomial of a symmetric matrix." Linear Algebra and its Applications, vol. 141, 265–270, 1990. DOI: 10.1016/0024-3795(90)90323-5
    • Schmeisser G., "A real symmetric tridiagonal matrix with a given characteristic polynomial." Linear Algebra and its Applications, vol. 193, 11–18, 1993. DOI: 10.1016/0024-3795(93)90268-S

Related Resources

License Information