# Computation of characteristic polynomial fails for me

For a matrix $A\in\mathbb{K}^{n\times n}$ where $\mathbb{K}\in\{\mathbb{R},\mathbb{C}\}$ the characteristic polynomial is defined as

$$\chi_A(\lambda) := \text{det}(A-\lambda I_n) = \sum_{k=0}^n c_k \lambda^k$$

with the recursive definition of the coefficients

$$c_n = (-1)^n,\;\;\;\;c_{n-1}=(-1)^{n-1}\text{tr}A,\;\;\;\;c_0 = \text{det}A$$

and the trace of the matrix $A$

$$\text{tr}A := \sum_{k=1}^n a_{kk}$$

But when i try to compute the polynomial my "hand-computed" solution is not the same as the one Mathematica provides.

$$A:=\begin{bmatrix}a&0&0\\0&b&0\\0&0&c\end{bmatrix}$$

leads for me to the polynomial

$$\chi_A^{Hand}(\lambda) = -\lambda^3+\lambda^2 (a+b+c)-\lambda (a+b+c) +abc$$

but calling

CharacteristicPolynomial[{{a, 0, 0}, {0, b, 0}, {0, 0, c}}, \[Lambda]]


in Mathematica leads to the result

$$\chi_A^{Mathematica}(\lambda)=a b c-a b \lambda -a c \lambda -b c \lambda +a \lambda ^2+b \lambda ^2+c \lambda ^2-\lambda ^3$$

Can anyone explain me, what i am doing wrong?

-
The answer is that you do not develop correctly the polynomial $(a-\lambda)(b-\lambda)(c-\lambda)$. The correct expression is the one given by Mathematica. – Did Jul 16 '11 at 14:24

Mathematica agrees with your answer. The degree is $n=3$. Your formulas say $c_3=(-1)^3=-1$, and $c_2 = (-1)^2 tr(A) = a+b+c$ and $c_0 = det(A) = a b c$, but the $c_1$ is not determined by your statement, so there is no contradiction. You wrongly concluded that $c_1 = -c_2$.

-
Understood. I don't know why i haven't seen this before! But is there any other algorithm or any other solution to make this one "really" recursive? This is just what was given to us in a lecture. – Christian Ivicevic Jul 16 '11 at 14:29
Yes, there is. I have seen in the book of Carl Meyer. That book also said it is not practical for inexact matrices because of numerical instabilities. Also you may find the Cayley-Hamilton wiki-page useful – Sasha Jul 16 '11 at 14:35
"it is not practical for inexact matrices because of numerical instabilities" - the usual example (due to Jim Wilkinson) is the diagonal matrix with diagonal elements $1,2,\dots,20$; the eigenvalues are easy to compute, but woe betide thee who expands it to its eigenpolynomial... – J. M. Jul 16 '11 at 15:07

Your "recursive" definition isn't really recursive. It only describes three of the coefficients. You get the same value for those as Mathematica does. The coefficient of $\lambda^1 = \lambda^{n-2}$ isn't described by your formulas, and I don't understand how you computed it.

-
@Christian: That was exactly the point I was trying to explain to Yuval: that you get your solution by computing $c_{1}$ and $c_{2}$ using the formula for $c_{n-1}$. Aren't you given an $n \times n$-matrix and you have to prove the formulas for $c_{k}$ the three values $k = 0$, $k = n-1$ and $k=n$? – t.b. Jul 16 '11 at 14:35
@Theo Buehler: I am not given any specific matrix. The exercise is to prove the correctness of the relations... might it be true that $c_{n-1}$ can be computed this way and the other parts like $c_1$ not? Therefore i could proove the correctness of this without havong a look at $c_1$ if e.g. i let $n=3$. – Christian Ivicevic Jul 16 '11 at 14:39
@Christian: Yes, that was my point. You're given $n$ and you can ignore $c_1, c_2, \ldots, c_{n-2}$. In general, the coefficients in the characteristic polynomial are given by the elementary symmetric polynomials in the eigenvalues (up to a sign): $c_{k} = (-1)^k e_{k}(\lambda_1,\lambda_2,\ldots,\lambda_n)$. – t.b. Jul 16 '11 at 14:48
@Theo Buehler: Thanks for the help - und danke sehr ;) – Christian Ivicevic Jul 16 '11 at 14:49
@Christian: my pleasure - gern geschehen. Yuval: sorry about the pings. – t.b. Jul 16 '11 at 14:51