menu

PLANETCALC Online calculators

languagesearchLogin
homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightlinear algebra

Characteristic polynomial

This online calculator calculates coefficients of characteristic polynomial of a square matrix using Faddeev–LeVerrier algorithm

person_outlineTimurschedule2019-06-17 05:34:04

In linear algebra, the characteristic polynomial of a n×n square matrix A is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. The polynomial pA(λ) is monic (its leading coefficient is 1) and its degree is n. The calculator below computes coefficients of a characteristic polynomial of a square matrix using Faddeev–LeVerrier algorithm. Some theory and formulas can be found below the calculator.

PLANETCALC, Characteristic polynomial

Characteristic polynomial

Digits after the decimal point: 2
Characteristic polynomial
 

Characteristic polynomial

Given a square matrix A, we want to find a polynomial whose zeros are the eigenvalues of A. For a diagonal matrix A, the characteristic polynomial is easy to define: if the diagonal entries are a1, a2, a3, etc. then the characteristic polynomial will be:

(t-a_1)(t-a_2)(t-a_3)\cdots,

This works because the diagonal entries are also the eigenvalues of this matrix.

For a general matrix A, one can proceed as follows. A scalar λ is an eigenvalue of A if and only if there is an eigenvector v ≠ 0 such that

A \mathbf{v} = \lambda \mathbf{v},

or

(\lambda I - A)\mathbf{v} = 0\,

(where I is the identity matrix).

Since v is non-zero, this means that the matrix λ I − A is singular (non-invertible), which in turn means that its determinant is 0. Thus the roots of the function det(λ I − A) are the eigenvalues of A, and it is clear that this determinant is a polynomial in λ.1

In matrix form polynomial in λ looks like this:

p(\lambda)=det \begin{bmatrix}\lambda - a_{11}&a_{12}&\dots &a_{1n}\\a_{21}&\lambda - a_{22}&\dots &a_{2n}\\ \dots & \dots & \dots & \dots \\a_{n1}&a_{n2}&\dots &\lambda - a_{nn}\end{bmatrix}

In scalar form

p(\lambda )\equiv \det(\lambda I_{n}-A)=\sum _{k=0}^{n}c_{k}\lambda ^{k}~,

where, cn = 1 and c0 = (−1)n det A.

The coefficients can be found using recursive Faddeev–LeVerrier algorithm (first published in 1840 by Urbain Le Verrier, in present form redeveloped by Dmitry Konstantinovich Faddeev and others).

Faddeev–LeVerrier algorithm

The coefficients of the characteristic polynomial are determined recursively from the top down, by dint of the auxiliary matrices M2,

{\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}}

Thus,

{\displaystyle M_{1}=I~, \quad c_{n-1}=-\mathrm {tr} A=-c_{n}\mathrm {tr} A;} \\{\displaystyle M_{2}=A-I\mathrm {tr} A, \\ \quad c_{n-2}=-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}=-{\frac {1}{2}}(c_{n}\mathrm {tr} A^{2}+c_{n-1}\mathrm {tr} A);} \\{\displaystyle M_{3}=A^{2}-A\mathrm {tr} A-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}I,} \\{\displaystyle c_{n-3}=-{\tfrac {1}{6}}{\Bigl (}(\operatorname {tr} A)^{3}-3\operatorname {tr} (A^{2})(\operatorname {tr} A)+2\operatorname {tr} (A^{3}){\Bigr )}=-{\frac {1}{3}}(c_{n}\mathrm {tr} A^{3}+c_{n-1}\mathrm {tr} A^{2}+c_{n-2}\mathrm {tr} A);}

etc.,

{\displaystyle M_{m}=\sum _{k=1}^{m}c_{n-m+k}A^{k-1}~,} \\{\displaystyle c_{n-m}=-{\frac {1}{m}}(c_{n}\mathrm {tr} A^{m}+c_{n-1}\mathrm {tr} A^{m-1}+...+c_{n-m+1}\mathrm {tr} A)=-{\frac {1}{m}}\sum _{k=1}^{m}c_{n-m+k}\mathrm {tr} A^{k}~;...}

The calculator uses this algorithm to compute the coefficients. It can also output auxiliary matrix M for each step.

  1. Wikipedia - Characteristic polynomial ↩

  2. Wikipedia - Faddeev–LeVerrier algorithm ↩

Similar calculators

local_offer #algebra #matrix Algebra characteristic polynomial Faddeev–LeVerrier algorithm linear algebra Math matrix
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Characteristic polynomial

Comments