### Bocher’s formula

A colleague of mine mentioned to me today the Bocher’s formula for computing the coefficients of the characteristic polynomial of a matrix. It seems that this formula does not appear too often in textbooks or literature. I’ll just write down the formula and the idea of a simple proof here.

Let the characteristic polynomial of a matrix $A$ be

$\displaystyle{p(\lambda)=\lambda^n+a_1\lambda^{n-1}+\cdots+a_n.}$

Then the coefficients can be computed by
$a_1=-tr(A),$
$a_2=-\frac{1}{2}\left(a_1tr(A)+tr(A^2)\right),$
$a_3=-\frac{1}{3}\left(a_2tr(A)+a_1tr(A^2)+tr(A^3)\right),$
$\vdots$
$a_n=-\frac{1}{n}\left(a_{n-1}tr(A)+\cdots+a_1tr(A^{n-1})+tr(A^n)\right).$

To prove the formula, note that the coefficient $a_j$ is the summation of all possible products of j eigenvalues, i.e.,

$\displaystyle{a_j=(-1)^j\sum_{\{t_1\cdots t_j\}\in C_n^j}\lambda_{t_1}\cdots\lambda_{t_j},}$

where $C_n^j$ denotes the j-combination of numbers from 1 to n, and the trace of $A^i$ is the sum of the $j$th power of the eigenvalues, i.e.,

$\displaystyle{tr(A^i)=\sum_{t=1}^n\lambda_t^i.}$

$\displaystyle{\left(\sum_{\{t_1\cdots t_j\}\in C_n^j}\lambda_{t_1}\cdots\lambda_{t_j}\right)\left(\sum_{t_{j+1}=1}^n\lambda_{t_{j+1}}^i\right)=\sum_{\{t_1\cdots t_{j+1}\}\in C_n^{j+1}}\lambda_{t_1}\cdots\lambda_{t_j}\lambda_{t_{j+1}}^i+\sum_{\{t_1\cdots t_j\}\in C_n^j}\lambda_{t_1}\cdots\lambda_{t_{j-1}}\lambda_{t_j}^{i+1}.}$

The above indicates that the first part of $(-1)^ja_jtr(A^i)$ cancels the second part of $(-1)^{j-1}a_{j-1}tr(A^{i+1})$, whereas the second part of $(-1)^ja_jtr(A^i)$ cancels the first part of $(-1)^{j+1}a_{j+1}tr(A^{i-1}).$ The rest of proof becomes obvious now.