Recurrence Equations for Matrix Determinant

Context: I'm reading this paper http://portal.acm.org/citation.cfm?id=1382468

Definitions:

$B_1 = I$

$B_{k+1} = AB_k - \frac{1}{k} tr (AB_k)I$

$det(A) = \frac{(-1)^n}{n} tr(AB_n)$

Question: How does this formula for the determinant work?

I understand: (1) the definition of determinant via permutations

(2) the definition of determinant via minors $det(A) = \sum_i (-1)^{i+j} a_{i,j}det(A_{i,j})$

(3) the Cayley-Hamilton Theorem: $p(s) = det(sI-A)$, $p(A)=0$.

What I fail to understand: how the above recurrence works. If you could tell me the key idea (or give me a term to google for), I can finish the derivation myself.

Thanks!

-
I have a feeling that this might belong better on math.stackexchange.com – Yemon Choi Mar 12 2011 at 8:23
Is that "det" sitting by itself on the left side of your 3rd equation supposed to be $\det A$? – Gerry Myerson Mar 12 2011 at 11:32
@Gerry: good call. Change accepted. – LowerBounds Mar 12 2011 at 14:41
Shouldn't there be an $I$ in your recurrence relation? – Thierry Zell Mar 12 2011 at 17:28
@ Thierry: I don't see where I'm missing an $I$, can you make the edit? – LowerBounds Mar 12 2011 at 18:29

To sum it all in one sentence, this is the Horner method applied to the computation of the characteristic polynomial of $A$. Your algorithm computes the whole charcateristic polynomial of $A$, in fact, and the determinant is only the last offshoot.

Formally, let $$X^n+\sum_{k=0}^{n-1}a_kX^k$$ be the characteristic polynomial of $A$. Thus, for example, $-a_{n-1}$ is the trace of $A$, and $(-1)^{n}a_0$ is the determinant of $A$. An easy induction on $k$ shows that

$$B_k=A^{k-1}+ \sum_{j=0}^{k-2}a_{n+1-k+j}A^j$$

for all $k$. Finally, the Cayley-Hamilton theorem shows that $AB_n$ is exactly $-a_0I$.

-
 @ Ewan: actually, there's something I still don't understand. How does the above equations explain for the $tr(AB_{k-1})$? Is this via Newton's Identity, or the expansion of $e^A$ ? – LowerBounds Mar 12 2011 at 23:39 This method for computing the characteristic polynomial is sometimes called "Le Verrier method", or "Le Verrier-Faddeev" method. There are some references and explanations in techmath.uibk.ac.at/wagner/psfiles/Faddeev.ps – Emmanuel Briand Mar 13 2011 at 7:52 @ LowerBounds : Yes, one may use Newton's identity (working in the algebraic closure of the ground field if necessary). Emmanuel Briand's reference above provides a different proof, using adjoints. – Ewan Delanoy Mar 13 2011 at 8:04 @Emmanuel. This is the Faddeev variant of the Le Verrier's method. – Denis Serre Mar 13 2011 at 20:33