Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 261

Once the characteristic polynomial of A has been computed, its inverse can be computed
by forming the n

1 successive powers of A ,namely, A , A 2 , A 3 , ... , A n− 1 , multiplying them
by the coefficients of φ A ( x ) , and adding the products together. These powers of A can be
computed using a prefix circuit having O ( n ) instances of the associative matrix multiplication
operator and depth O (log n ) measured in the number of instances of this operator. We have
defined M matrix ( n , K ) to be the size of the smallest n

−

n matrix multiplication circuit with
depth K log n (Definition 6.3.1 ). Thus, the successive powers of A can be computed by a
circui t of size O ( nM matrix ( n , K )) and depth O (log 2 n ) . The size bound can be improved to

×

O ( √ nM matrix ( n , K )) . (See Problem 6.15 .)
To complete the derivation of the Csanky algorithm we must produce the coefficients of
the characteristic polynomial of A . For this we invoke Leverrier's theorem . This theorem uses
the notion of the trace of a matrix A , that is, the sum of the elements on its main diagonal,
denoted tr ( A ) .

THEOREM 6.5.5 (Leverrier) The coefficients of the characteristic polynomial of the n × n matrix
A satisfy the following identity, where s r = tr ( A r ) for 1 ≤ r ≤ n :

⎡ ⎤ ⎡ ⎤ ⎡ ⎤

1 0 0 ··· 0 c n− 1

c n− 2
c n− 3
.
c 0

s 1
s 2
s 3
.
s n

⎣ ⎦ ⎣ ⎦ ⎣ ⎦

s 1 20 ··· 0

s 2 s 1 3 0

= −

(6.13)

. .

. . .

s n− 1 ··· s 2 s 1 n

Proof The degree- n characteristic polynomial φ A ( x ) of A can be factored over a field of
characteristic zero. If λ 1 , λ 2 , ... , λ n are its roots, we write

n

φ A ( x )= ( x − λ i )

i = 1

− j = 1 λ j .

From expanding this expression, it is clear that the coefficient c n− 1 of x n− 1 is

Similarly, expanding det( xI

− A ) , c n− 1 is the negative sum of the diagonal elements of A ,

tr ( A ) . It follows that tr ( A )= j = 1 λ j .
The λ j 's are called the eigenvalues of A , that is, values such that there exists an n -vector
u (an eigenvector )suchthat A u = λ j u . It follows that A r u = λ j u .Itcanbeshown
that λ 1 , ... , λ n are precisely the eigenvalues of A r ,so Π j = 1 ( x

that is, c n− 1 =

−

λ j ) is the characteristic −

polynomial of A r .Since s r = tr ( A r ) , s r = j = 1 λ j .
Let s 0 = 1and s k = 0for k< 0. Then, to complete the proof of ( 6.13 ), we must show
that the following identity holds for 1

≤ i ≤ n :

s i− 1 c n− 1 + s i− 2 c n− 2 + ··· + s 1 c n−i + 1 + ic n−i = − s i

Moving s i to the left-hand side, substituting for the traces, and using the definition of the
characteristic polynomial yield

− λ n−i
j

+ λ j c 1 + c 0

n

c n−i + λ n−i− 1 φ A ( λ j ) c n−i− 1 + ···

j

ic n−i + = 0

λ n−i
j

j = 1