What is the fastest way to find the characteristic polynomial of a matrix?

Question

Finding the characteristic polynomial of a matrix of order $n$ is a tedious and boring task for $n > 2$.

I know that:

• the coefficient of $\lambda^n$ is $(-1)^n$,
• the coefficient of $\lambda^{n-1}$ is $(-1)^{n-1}(a_{11} + a_{22} + \dots + a_{nn})$,
• the constant term is $\det{A}$.

When finding the coefficient of the linear term $\lambda$ of the characteristic polynomial of a $3\times 3$ matrix, one has to calculate the determinant of the matrix $A - \lambda I_n$ anyway. (But you don't have to sum all the terms, only the linear terms.)

Does anybody know a faster way?

Answer 1

Once upon a less enlightened time, when people were less knowledgeable in the intricacies of algorithmically computing eigenvalues, methods for generating the coefficients of a matrix's eigenpolynomial were quite widespread. One of the more prominent methods for computing the coefficients was a method ascribed to both the Frenchman Leverrier, and the Russian Faddeev (who was an (co-)author of one of the oldest references on the practice of numerical linear algebra).

The (Faddeev-)Leverrier method is a method that will require you to do a number of matrix multiplications to generate the coefficients of the characteristic polynomial. Letting the $n\times n$ matrix $\mathbf A$ have the monic characteristic polynomial $(-1)^n \det(\mathbf A-\lambda\mathbf I)=\lambda^n+c_{n-1}\lambda^{n-1}+\cdots+c_0$, the algorithm proceeds like so:

$\mathbf C=\mathbf A;$
$\text{for }k=1,\dots,n$

$\text{if }k>1$
$\qquad \mathbf C=\mathbf A\cdot(\mathbf C+c_{n-k+1}\mathbf I);$

$c_{n-k}=-\dfrac{\mathrm{tr}(\mathbf C)}{k};$

$\text{end for}$

If your computing environment can multiply matrices, or take their trace (sum of the diagonal elements, $\mathrm{tr}(\cdot)$), then you can easily program (Faddeev-)Leverrier. The method works nicely in exact arithmetic, or in hand calculation (assuming you have the stamina to repeatedly multiply matrices), but is piss-poor in inexact arithmetic, as the method tends to greatly magnify rounding errors in the matrix, ever yielding coefficients that become increasingly inaccurate as the iteration proceeds. But, for the simple $3\times 3$ case envisioned by the OP, this should work nicely.

People interested in this old, retired method might want to see this paper.

Answer 2

By hand, I think Ted Shifrin's method is fastest.

By computer, evaluate $\det (\lambda \cdot \mathrm{Id}- A)$ for $n$ values of $\lambda$, and find the characteristic polynomial by Lagrange interpolation.

Answer 3

This may or may not make you happy. The coefficient of $\lambda^{n-k}$ is $(-1)^{n-k}$ times the sum of all the principal $k\times k$ minors, i.e., the determinants of all $k\times k$ submatrices built using the same rows and columns. Note that this generalizes your observations for $k=n$ and $k=1$.

Answer 4

You can use the Cayley-Hamilton theorem, which says that the matrix $A$ is a root of the minimal polynomial, which divides the characteristic polynomial. In facts, the minimal polynomial has the same roots than the characteristic, except those roots may have lower multiplicity. In particular, if the eigenvalues of $A$ are distinct, then the two polynomials are equals.

You compute the $n=\dim$ powers: $I, A, A^2, A^3,...,A^n$, and then look for coefficients $c_i$ such that $A^n = c_{n-1}A^{n-1}+...+c_1A^1+c_0I$, then the minimal polynomial is $\det(\lambda I - A) = P(X) = \lambda^n-c_{n-1}\lambda^{n-1}-...-c_1\lambda-c_0$.

For example, if $A=\begin{pmatrix} 0&1&0\\1&0&0\\0&0&2\end{pmatrix}$, then $A^2=\begin{pmatrix} 1&0&1\\0&1&0\\0&0&4\end{pmatrix}$, and $A^3=\begin{pmatrix} 0&1&0\\1&0&0\\0&0&8\end{pmatrix}$,

so that $A^2-I=\begin{pmatrix} 0&0&0\\0&0&0\\0&0&3\end{pmatrix}$ and $A^3-A=\begin{pmatrix} 0&0&0\\0&0&0\\0&0&6\end{pmatrix}$, thus $A^3-A=2(A^2-I)$, and

the minimal polynomial is $\lambda^3-\lambda-2(\lambda^2-1)=(\lambda^2-1)(\lambda-2)=(\lambda+1)(\lambda-1)(\lambda-2)$. All the roots being simple, the minimal polynomial is also the characteristic polynomial, and $\chi_A(\lambda)=\det(\lambda I-A)=\lambda^3-2\lambda^2-\lambda+2$.

The search of the coefficients $c_i$ may be done in a systematic way, similar to the Gauss method. However the system is overdetermined, with $n \times n$ equations, and is usually quicker to solve than you think, especially for matrices found in homework.

The eigenvalues will almost always be distinct (so the characteristic and minimal polynomials will be the same), except maybe for matrices found in homework. For these, is is better to look to the power matrix $A^k, k \le n$ as you compute them, and look if they are linear combinations of the previous ones.

For example if $A=\begin{pmatrix} 0&1&1\\1&0&1\\1&1&0\end{pmatrix}$, then $A^2=\begin{pmatrix} 2&1&1\\1&2&1\\1&1&2\end{pmatrix}$, and $A^2=A+2I$. So the minimal polynomial is $\lambda^2-\lambda-2 = (\lambda+1)(\lambda-2)$. The characteristic polynomial being a polynomial of degree 3 with the same roots, it can either be $(\lambda+1)^2(\lambda-2)$ or $(\lambda+1)(\lambda-2)^2$. The multiplicity $\nu_i$ of $(x-\lambda_i)$ in $\chi_A(x) = \prod (x-\lambda_i)^{\nu_i}$, is the dimension of the associated eigenspace $E_{\lambda_i}=\ker (A-\lambda_i I)=\{x\mid Ax=\lambda_i x\}$. In our case, $E_{-1} = \ker(A+I) = \ker \begin{pmatrix} 1&1&1\\1&1&1\\1&1&1\end{pmatrix}=2$, so $\chi_A(\lambda)=(\lambda+1)^2(\lambda-2)$.

I don't know if the method is less tedious, but I find it less boring.

Answer 5

I believe the fastest way known is the Pernet-Storjohann randomized algorithm with complexity $O(n^\theta)$, where $\theta$ is an admissible exponent for the complexity of matrix multiplication in terms of field operations. On the other hand, it is known that the complexity of the product of two matrices is bounded above by the complexity of the the characteristic polynomial, so the Pernet-Storjohann complexity is "sharp".