Calculation of the Characteristic Polynomial and the Adjoint Matrix at the Same Time Leverrier-Souriau-Frame-Faddeev Method


Let A be an n-by-n matrix. The four people mentioned in the title discovered (and rediscovered), in a course over a century, a method by which the characteristic polynomial of A together with its adjoint matrix can be computed without actually expanding the determinant of any matrices. The construction proceeds as follows:

Define

F1 = I, b1 = - tr(F1A)/1

F2 = F1A + b1Ib2 = - tr(F2A)/2

....

Fn = Fn-1A+ bn-1Ibn = - tr(FnA)/n.
 

Then

(a) the characteristic polynomial of A is

p(x) = xn + b1xn-1 + b2xn-2 + ···+ bn-1x + bn

(b) the matrix B(x) given by

B(x) = xn-1F1 + xn-2F2 + ···+ xFn-1 + Fn

satisfies

B(x) (xI - A) = p(x)I

so that if x is not an eigenvalue of A, then B(x)/p(x) is the inverse of (xI - A). B(x) is known as the adjoint matrix of A.

The proof of this formula is based on the following facts:

(1) The Cayley-Hamilton Theorem: p(A) is the zero matrix if p is the characteristic polynomial of A.

(2) Newton's formula for sums of zeros of a polynomial: if c1, c2,...,cn are the zeros of the polynomial

p(x) = xn + a1xn-1 + a2xn-2 + ···+ an
                       (*)

then the sum sk of their k-th power

sk = ck1 + ck2 + ···+ ckn

satisfies the recursive relations

kak = -(sk + sk-1a1 + sk-2a2 + ···+ s1ak-1

(3) Every eigenvalue of Ak is of the form ck for some eigenvalue c of A so that the trace tr(Ak) of Ak is the sum of k-th powers of the eigenvalues of A.

We now give the actual proof of the theorem. Assume that the characteristic polynomial of A takes the form (*). After successive substitution from the definition of Fk, we obtain

Fk = bk-1I + bk-2A + bk-3A2 + ···+ b1Ak-2 +Ak-1
                            (**)

for k = 2,3,...,n. Therefore, one shows by induction, together with facts (2) and (3), that

kbk = -tr FkA = -tr(bk-1A + bk-2A2 + ···+ Ak
= - (ak-1s1 + ak-2s2 + ···+ a1sk-1 + sk) = kak

where each sk is the sum of the k-th powers of all eigenvalues of A. Hence (a) is proved. Formula (**) also shows

FnA = bn-1A + bn-2A2 + ···+b1An-1 + An = -bnI

the last equality being the consequence of fact (1). Expanding the left-hand side of (b), we have

xnF1 + xn-1(F2 - F1A) + xn-2(F3 - F2A) + ···+x(Fn - Fn-1A) + (-FnA), 

from which the desired result follows.

The above construction can be carried out in a spreadsheet program. We now show how this is done in case n = 4:

a. Place the index 1 at cell A6 (k = 1);

b. Enter the identity matrix in B4..E7 (this is F1);

c. Set the matrix A in G4..J7 (after the worksheet is completed, this is the only range that needs to be changed to see different output for different A);

c. At cell L4 enter the formula

+$B1*G$4+$C1*G$5+$D1*G$6+$E1*G$7; 

d. Copy the formula from L4 to L4..O7 (this will give the product F1A);

e. Cell Q7 is to reflect the value of b1, so the formula is

-(L4+M5+N6+O7)/A

f. At cell A11 enter the formula +A6+1 (k is increased by 1);

g. F2 is to be placed in range B9..E12;

h. Copy the formulas from L4..Q7 to L9 (F2A and b2 are shown);

i. Copy the formulas from A9..Q22 to A14 (repeat steps f-h for k = 3,4,5).