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

F₁ = I, b₁ = - tr(F₁A)/1

F₂ = F₁A + b₁Ib₂ = - tr(F₂A)/2

....

F_n = F_n_-1A+ b_n_-1Ib_n = - tr(F_nA)/n.

Then

(a) the characteristic polynomial of A is

p(x) = xⁿ + b₁xⁿ^-1 + b₂xⁿ^-2 + ···+ b_n_-1x + b_n;

(b) the matrix B(x) given by

B(x) = xⁿ^-1F₁ + xⁿ^-2F₂ + ···+ xF_n_-1 + F_n

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 c₁, c₂,...,c_n are the zeros of the polynomial

p(x) = xⁿ + a₁xⁿ^-1 + a₂xⁿ^-2 + ···+ a_n

(*)

then the sum s_k of their k-th power

s_k = c^k₁ + c^k₂ + ···+ c^k_n

satisfies the recursive relations

ka_k = -(s_k + s_k_-1a₁ + s_k_-2a₂ + ···+ s₁a_k_-1)

(3) Every eigenvalue of A^k is of the form c^k for some eigenvalue c of A so that the trace tr(A^k) of A^k 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 F_k, we obtain

F_k = b_k_-1I + b_k_-2A + b_k_-3A² + ···+ b₁A^k^-2 +A^k^-1

(**)

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

kb_k = -tr F_kA = -tr(b_k_-1A + b_k_-2A² + ···+ A^k)

= - (a_k_-1s₁ + a_k_-2s₂ + ···+ a₁s_k_-1 + s_k) = ka_k,

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

F_nA = b_n_-1A + b_n_-2A² + ···+b₁Aⁿ^-1 + Aⁿ = -b_nI,

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

xⁿF₁ + xⁿ^-1(F₂ - F₁A) + xⁿ^-2(F₃ - F₂A) + ···+x(F_n - F_n_-1A) + (-F_nA),

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 F₁);

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 F₁A);

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

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

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

g. F₂ is to be placed in range B9..E12;

h. Copy the formulas from L4..Q7 to L9 (F₂A and b₂ are shown);

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