Recurrence Equations for Matrix Determinant

Question

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!

Answer 1

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$.