Physics 116A Winter 2011

The Characteristic Polynomial

1. Coefficients of the characteristic polynomial

Consider the eigenvalue problem for an n × n matrix A,

v = λ~
A~ v, v 6= 0 .
~ (1)

The solution to this problem consists of identifying all possible values of λ (called the
eigenvalues), and the corresponding non-zero vectors ~ v (called the eigenvectors) that
satisfy eq. (1). Noting that I~
v=~v , one can rewrite eq. (1) as

(A − λI)~
v = 0. (2)

This is a set of n homogeneous equations. If A − λI is an invertible matrix, then one

can simply multiply both sides of eq. (2) by (A − λI)−1 to conclude that ~ v = 0 is the
unique solution. By definition, the zero vector is not an eigenvector. Thus, in order
to find non-trivial solutions to eq. (2), one must demand that A − λI is not invertible,
or equivalently,
p(λ) ≡ det(A − λI) = 0 . (3)
Eq. (3) is called the characteristic equation. Evaluating the determinant yields an nth
order polynomial in λ, called the characteristic polynomial, which we have denoted
above by p(λ).
The determinant in eq. (3) can be evaluated by the usual methods. It takes the
form,
 
a11 − λ a 12 · · · a1n

 
 a21
 a22 − λ · · · a2n 
p(λ) = det(A − λI) =  .. .. .. .. 
 . . . . 

 an1 an2 · · · ann − λ
 
= (−1)n λn + c1 λn−1 + c2 λn−2 + · · · + cn−1 λ + cn , (4)

where A = [aij ]. The coefficients ci are to be computed by evaluating the determi-

nant. Note that we have identified the coefficient of λn to be (−1)n . This arises from
one term in the determinant that is given by the product of the diagonal elements.
It is easy to show that this is the only possible source of the λn term in the charac-
teristic polynomial. It is then convenient to factor out the (−1)n before defining the
coefficients ci .

1
 Two of the coefficients are easy to obtain. Note that eq. (4) is valid for any value
of λ. If we set λ = 0, then eq. (4) yields:
p(0) = det A = (−1)n cn .
Noting that (−1)n (−1)n = (−1)2n = +1 for any integer n, it follows that

cn = (−1)n det A

One can also easily work out c1 , by evaluating the determinant in eq. (4) using the
cofactor expansion. This yields a characteristic polynomial of the form,
p(λ) = det(A − λI) = (a11 −λ)(a22 −λ) · · · (ann −λ) + c2′ λn−2 + c3′ λn−3 + · · ·+cn′ . (5)
The term (a11 − λ)(a22 − λ) · · · (ann − λ) is the product of the diagonal elements of
A − λI. It is easy to see that none of the remaining terms that arise in the cofactor
expansion [denoted by c2′ λn−2 + c3′ λn−3 + · · · + cn′ in eq. (5)] are proportional to λn or
λn−1 .∗ Moreover,
(a11 − λ)(a22 − λ) · · · (ann − λ) = (−λ)n + (−λ)n+1 [a11 + a22 + · · · + ann ] + · · · ,
 
= (−1)n λn − λn−1 (Tr A) + · · · ,
where · · · contains terms that are proportional to λp , where p ≤ n − 2. This means
that the terms in the characteristic polynomial that are proportional to λn and λn−1
arise solely from the term (a11 − λ)(a22 − λ) · · · (ann − λ). The term proportional to
−(−1)n λn−1 is the trace of A, which is defined to be equal to the sum of the diagonal
elements of A. Comparing eqs. (4) and (5), it follows that:

c1 = −Tr A
Expressions for c2 , c3 , . . . , cn−1 are more complicated. For example, eqs. (4) and (5)
yield
Xn Xn
c2 = aii ajj + c2′ .
i=1 j=1
i<j

For the moment, I will not explicitly evaluate c2 , c3 , . . . , cn−1 . In the Appendix to
these notes, I will provide explicit expressions for these coefficients in terms of traces
of powers of A. It follows that the general form for the characteristic polynomial is:
p(λ) = det(A − λI)
 
= (−1)n λn − λn−1 Tr A + c2 λn−2 + · · · + (−1)n−1 cn−1 λ + (−1)n det A . (6)
∗
In computing the cofactor of the ij element, one crosses out row i and column j of the ij element
and evaluates the determinant of the remaining matrix [multiplied by the sign factor (−1)i+j ].
Except for the product of diagonal elements, there is always one factor of λ in each of the rows and
columns that is crossed out. This implies that the maximal power one can achieve outside of the
product of diagonal elements is λn−2 .

2
 By the fundamental theorem of algebra, an nth order polynomial equation of
the form p(λ) = 0 possesses precisely n roots. Thus, the solution to p(λ) = 0 has
n potentially complex roots, which are denoted by λ1 , λ2 , . . . , λn . These are the
eigenvalues of A. If a root is non-degenerate (i.e., only one root has a particular
numerical value), then we say that the root has multiplicity one—it is called a simple
root. If a root is degenerate (i.e., more than one root has a particular numerical
value), then we say that the root has multiplicity p, where p is the number of roots
with that same value—such a root is called a multiple root. For example, a double
root (as its name implies) arises when precisely two of the roots of p(λ) are equal.
In the counting of the n roots of p(λ), multiple roots are counted according to their
multiplicity.
In principle, one can always factor a polynomial in terms of its roots.† Thus,
eq. (4) implies that:

p(λ) = (−1)n (λ − λ1 )(λ − λ2 ) · · · (λ − λn ) ,

where multiple roots appear according to their multiplicity. Multiplying out the n
factors above yields

n
X n X
X n
 n
n n−1 n−2
p(λ) = (−1) λ − λ
 λi + λ λi λj + . . .
i=1 i=1 j=1
i<j

n X
X n n
X
n−k

+λ ··· λii λi2 · · · λik + · · · + λ1 λ2 · · · λn 
. (7)
| {z }
i1 =1 i2 =1 ik =1
k factors
i1 <i2 <···<ik

Comparing with eq. (6), it immediately follows that:

n
X
Tr A = λi = λ1 + λ2 + · · · + λn , det A = λ1 ·λ2 ·λ3 · · · λn
i=1

The coefficients c2 , c3 , . . . , cn−1 are also determined by the eigenvalues. In general,

n X
X n n
X
ck = (−1)k ··· λi1 λi2 · · · λik , for k = 1, 2, . . . , n . (8)
| {z }
i1 =1 i2 =1 ik =1
k factors
i1 <i2 <···<ik

†
I say in principle, since in practice it may not be possible to explicitly determine the roots
algebraically. According to a famous theorem of algebra, no general formula exists (like the famous
solution to the quadratic equation) for an arbitrary polynomial of fifth order or above. Of course,
one can always determine the roots numerically.

3
2. The Cayley-Hamilton Theorem

Theorem: Given an n × n matrix A, the characteristic polynomial is defined

by p(λ) = det(A − λI) = (−1)n [λn + c1 λn−1 + c2 λn−2 + · · · + cn−1 λ + cn ], it follows
that‡  
p(A) = (−1)n An + c1 An−1 + c2 An−2 + · · · + cn−1 A + cn I = 0 , (9)
where A0 ≡ I is the n × n identity matrix and 0 is the n × n zero matrix.

False proof: The characteristic polynomial is p(λ) = det(A−λI). Setting λ = A,

we get p(A) = det(A − AI) = det(A − A) = det(0) = 0. This “proof” does not make
any sense. In particular, p(A) is an n × n matrix, but in this false proof we obtained
p(A) = 0 where 0 is a number.

Correct proof: Recall that the classical adjoint of M, denoted by adj M, is the
transpose of the matrix of cofactors. In class, we showed that the cofactor expansion
of the determinant is equivalent to the equation§

M adj M = I det M . (10)

In particular, setting M = A − λI, it follows that

(A − λI) adj(A − λI) = p(λ)I , (11)

where p(λ) = det(A − λI) is the characteristic polynomial. Since p(λ) is an nth-order
polynomial, it follows from eq. (11) that adj(A − λI) is a matrix polynomial of order
n − 1. Thus, we can write:

adj(A − λI) = B0 + B1 λ + B2 λ2 + · · · + Bn−1 λn−1 ,

where B0 , B1 , . . . , Bn−1 are n × n matrices (whose explicit forms are not required in
these notes). Inserting the above result into eq. (11) and using eq. (4), one obtains:
 
(A−λI)(B0 +B1 λ+B2 λ2 +· · ·+Bn−1 λn−1 ) = (−1)n λn + c1 λn−1 + · · · + cn−1 λ + cn I .
(12)
k
Eq. (12) is true for any value of λ. Consequently, the coefficient of λ on the left-hand
side of eq. (12) must equal the coefficient of λk on the right-hand side of eq. (12), for
k = 0, 1, 2, . . . , n. This yields the following n + 1 equations:

AB0 = (−1)n cn I , (13)

−Bk−1 + ABk = (−1)n cn−k I , k = 1, 2, . . . , n − 1 , (14)
−Bn−1 = (−1)n I . (15)
‡
In the expression for p(λ), we interpret cn to mean cn λ0 . Thus, when evaluating p(A), the
coefficient cn multiplies A0 ≡ I.
§
If det M 6= 0, then we may divide both sides of eq. (10) by the determinant and identify
M −1 = adj M/det M , since the inverse satisfies M M −1 = I.

4
Using eqs. (13)–(15), we can evaluate the matrix polynomial p(A).
 
p(A) = (−1)n An + c1 An−1 + c2 An−2 + · · · + cn−1 A + cn I
= AB0 + (−B0 + B1 A)A + (−B1 + B2 )A2 + · · · + (−Bn−2 + Bn−1 A)An−1 − Bn−1 An
= A(B0 − B0 ) + A2 (B1 − B1 ) + A3 (B2 − B2 ) + · · · + An−1 (Bn−2 − Bn−2 ) + An (Bn−1 − Bn−1 )
= 0,

which completes the proof of the Cayley-Hamilton theorem.

It is instructive to illustrate the Cayley-Hamilton theorem for 2 × 2 matrices. In
this case,
p(λ) = λ2 − λTr A + det A .
Hence, by the Cayley-Hamilton theorem,

p(A) = A2 − A Tr A + I det A = 0 .

Let us take the trace of this equation. Since Tr I = 2 for the 2 × 2 identity matrix,

Tr(A2 ) − (Tr A)2 + 2 det A = 0 .

It follows that
 
det A = 1
2
(Tr A)2 − Tr(A2 ) , for any 2 × 2 matrix .

You can easily verify this formula for any 2 × 2 matrix.

Appendix: Identifying the coefficients of the characteristic polynomial in

terms of traces

The characteristic polynomial of an n × n matrix A is given by:

 
p(λ) = det(A − λI) = (−1)n λn + c1 λn−1 + c2 λn−2 + · · · + cn−1 λ + cn .

In Section 1, we identified:

c1 = −Tr A , cn = (−1)n det A . (16)

One can also derive expressions for c2 , c3 , . . . , cn−1 in terms of traces of powers of A.
In this appendix, I will exhibit the relevant results without proofs (which can be
found in the references at the end of these notes). Let us introduce the notation:

tk = Tr(Ak ) .

Then, the following set of recursive equations can be proven:

t1 + c1 = 0 and tk + c1 tk−1 + · · · + ck−1 t1 + kck = 0 , k = 2, 3, . . . , n . (17)

5
These equations are called Newton’s identities. A nice proof of these identities can
be found in ref. [1]. The equations exhibited in eq. (17) are called recursive, since
one can solve for the ck in terms of the traces t1 , t2 , . . . , tk iteratively by starting
with c1 = −t1 , and then proceeding step by step by solving the equations with
k = 2, 3, . . . , n in successive order. This recursive procedure yields:

c1 = −t1 ,
1 2
c2 = (t
2 1
− t2 ) ,
c3 = − 61 t31 + 21 t1 t2 − 13 t3 ,
1 4
c4 = t
24 1
− 41 t21 t2 + 31 t1 t3 + 81 t22 − 14 t4 ,
etc.

The results above can be summarized by the following equation [2],

m−1 m−1 m−2 m−2 m−2
tm 1 X X ti tj 1 X X X ti tj tk (−1)m tm
1
cm = − + − +· · ·+ , m = 1, 2, . . . , n .
m 2! i=1 j=1 ij 3! i=1 j=1 k=1 ijk m!
i+j=m i+j+k=m

Note that by using cn = (−1)n det A, one obtains a general expression for the deter-
minant in terms of traces of powers of A,
 
n−1 n−1 n−2 n−2 n−2
n
 tn 1 X X ti tj
n 1 X X X ti tj tk (−1)n tn1 
det A = (−1) cn = (−1) − +
 − +···+ ,
n 2! i=1 j=1 ij 3! i=1 j=1 ijk n! 
k=1
i+j=n i+j+k=n

where tk ≡ Tr(Ak ). One can verify that:

 
det A = 21 (Tr A)2 − Tr(A2 ) , for any 2 × 2 matrix ,
 
det A = 61 (Tr A)3 − 3 Tr A Tr(A2 ) + 2 Tr(A3 ) , for any 3 × 3 matrix ,
etc.

The coefficients of the characteristic polynomial, ck , can also be expressed directly in

terms of the eigenvalues of A, as shown in eq. (8).

BONUS MATERIAL

One can derive another closed-form expression for the ck . To see how to do this,
let us write out the Newton identities explicitly.

6
 Eq. (17) for k = 1, 2, . . . , n yields:
c1 = −t1 ,
t1 c1 + 2c2 = −t2 ,
t2 c1 + t1 c2 + 3c3 = −t3 ,
.. ..
. .
tk−1 c1 + tk−2 c2 + · · · + t1 ck−1 + kck = −tk ,
.. ..
. .
tn−1 c1 + tn−2 c2 + · · · + t1 cn−1 + ncn = −tn .
Consider the first k equations above (for any value of k = 1, 2, . . . , n). This is a
system of linear equations for c1 , c2 , . . . , ck , which can be written in matrix form:
    
1 0 0 ··· 0 0 c1 −t1
 t1
 2 0 ··· 0 0   c2   −t2 
   
 t2
 t1 3 ··· 0 0  c3   −t3 
   

 .. .. .. . . .. ..   ..  =  ..  .
 . . . . . . .   . 
   

tk−2 tk−3 tk−4 · · · k − 1 0 ck−1  −tk−1 
tk−1 tk−2 tk−3 · · · t1 k ck −tk
Applying Cramer’s rule, we can solve for ck in terms of t1 , t2 , . . . , tk [3]:
 
 1 0 0 ··· 0 −t1 

 t1
 2 0 ··· 0 −t2 
 t2
 t1 3 ··· 0 −t3 
 .. .. .. . .. .. .. 
 . . . . . 

tk−2 tk−3 tk−4 · · · k − 1 −tk−1 

tk−1 tk−2 tk−3 · · · t1 −tk 
ck =   .
 1 0 0 ··· 0 0
 t1
 2 0 · · · 0 0
 t2
 t1 3 ··· 0 0
 .. .. .. . .. .. .. 
 . . . . . 

tk−2 tk−3 tk−4 · · · k − 1 0

tk−1 tk−2 tk−3 · · · t1 k
The denominator is the determinant of a lower triangular matrix, which is equal to
the product of its diagonal elements. Hence,
 
 1 0 0 ··· 0 −t1 

 t1
 2 0 ··· 0 −t2 
1  t2
 t1 3 ··· 0 −t3 
ck =  .. .. .. .. .
.. ..  .
k!  . . . . . 

tk−2 tk−3
 tk−4 · · · k − 1 −tk−1 
tk−1 tk−2 tk−3 · · · t1 −tk 

7
It is convenient to multiply the kth column by −1, and then move the kth column over
to the first column (which requires a series of k − 1 interchanges of adjacent columns).
These operations multiply the determinant by (−1) and (−1)k−1 respectively, leading
to an overall sign change of (−1)k . Hence, our final result is:¶
 
 t1
 1 0 0 ··· 0 
 t2
 t1 2 0 ··· 0 
(−1)k  t3 t2 t1 3 ··· 0 
ck =  .. .. .. .. .. ..  , k = 1, 2, . . . , n .
k!  . . . . . . 
 
tk−1 tk−2 tk−3 tk−4 · · · k − 1
 
 tk tk−1 tk−2 tk−3 · · · t1 
We can test this formula by evaluating the the first three cases k = 1, 2, 3:
 
1 t1 1  1 2
c1 = −t1 , c2 =  = (t − t2 ) ,
2! t2 t1  2 1
 
t1 1 0 
1    
c3 = − t2 t1 2  = 61 −t31 + 3t1 t2 − 2t3 ,
3! 
t3 t2 t1 
which coincide with the previously stated results. Finally, setting k = n yields the
determinant of the n × n matrix A, det A = (−1)n cn , in terms of traces of powers
of A,  
 t1
 1 0 0 ··· 0 
 t2
 t1 2 0 ··· 0 
1  t3 t2 t1 3 ··· 0 
det A =  .. .. .. .. .. ..  ,
n!  . . . . . . 

tn−1 tn−2 tn−3 tn−4 · · · n − 1
 
 tn tn−1 tn−2 tn−3 · · · t1 
where tk ≡ Tr(Ak ). Indeed, one can check that our previous results for the determi-
nants of a 2 × 2 matrix and a 3 × 3 matrix are recovered.

REFERENCES
1. Dan Kalman, A Matrix Proof of Newton’s Identities, Mathematics Magazine 73,
313–315 (2000).
2. H.K. Krishnapriyan, On Evaluating the Characteristic Polynomial through Sym-
metric Functions, J. Chem. Inf. Comput. Sci. 35, 196–198 (1995).
3. V.V. Prasolov, Problems and Theorems in Linear Algebra (American Mathematical
Society, Providence, RI, 1994).
¶
This result is derived in section 4.1 on p. 20 of ref. [3]. However, the determinantal expression
given in ref. [3] for σk ≡ (−1)k ck contains a typographical error—the diagonal series of integers,
1, 1, 1, . . . , 1, appearing just above the main diagonal of σk should be replaced by 1, 2, 3, . . . , k − 1.