Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
3  
I have a feeling that this might belong better on math.stackexchange.com –  Yemon Choi Mar 12 '11 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 '11 at 11:32
    
@Gerry: good call. Change accepted. –  LowerBounds Mar 12 '11 at 14:41
    
Shouldn't there be an $I$ in your recurrence relation? –  Thierry Zell Mar 12 '11 at 17:28
    
@ Thierry: I don't see where I'm missing an $I$, can you make the edit? –  LowerBounds Mar 12 '11 at 18:29
show 2 more comments

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

share|improve this answer
    
@ 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 '11 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 '11 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 '11 at 8:04
    
@Emmanuel. This is the Faddeev variant of the Le Verrier's method. –  Denis Serre Mar 13 '11 at 20:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.