Horn and Johnson in "Matrix Analysis" leave as a exercise this proof:
Let A be a real matrix with characteristic polynomial $p(\lambda)$ where
$$p(\lambda) = \lambda^n + c_{1}\lambda^{n-1} + c_2\lambda^{n-2}+\cdots+c_n.$$
Let $E_k = \sum C_{kk}$ where $C_{kk}$ means a $k$-by-$k$ principal minor of $A$, and the summation is over all $k$-by-$k$ principal minors. Then,
$$p(\lambda) = \lambda^n + E_1\lambda^{n-1}+E_2\lambda^{n-2}+\cdots+E_n.$$
The authors say that this can be proved by mathematical induction, using the Laplace expansion.
I have written out the base case and the induction hypothesis. My assumption is that the induction is on the dimension of the matrix, although now I am not sure at this point as I don't know what to do from here.
Could anyone give me a hint or help as to what I should do next?
Best Answer
Your question amounts to prove that the determinant of the matrix $A-\lambda E$ has the form:
$$ p(\lambda) = (-1)^n\lambda^n+E_1\lambda^{n-1}+E_2\lambda^{n-2}+ \dots +E_{n-1}\lambda + E_n$$
Please notice the $(-1)^n$ sign in front of the first $\lambda$ that is originally missing in your question but which is crucial for the theorem to be proved.
As correctly suggested by Horn and Johnson, the above can be proved by using mathematical induction (on the size of square matrix A) applying the Laplace expansion in the inductive step as follows:
Base case $size(A)=2$ (we omit $n=1$ being trivial)
Consider the determinant of an $2x2$ matrix $\det(A-\lambda E)$ $$ \begin{vmatrix} a-\lambda & b \\ d & e-\lambda \\ \end{vmatrix} $$ If we consider $\det(A-\lambda E)$ as follows $$ \begin{vmatrix} a-\lambda & b+0\\ d+0 & e-\lambda \\ \end{vmatrix} $$ we can see each column of $\det(A-\lambda E)$ as a linear combination of two columns of numbers and, therefore, we can apply the linear property of determinants by "separating out the powers of $\lambda$" (as illustrated in https://math.stackexchange.com/a/144130/557814) by obtaining: $$ \begin{vmatrix} a-\lambda & b \\ c & d-\lambda \end{vmatrix} = \begin{vmatrix} a & b \\ c & d-\lambda \end{vmatrix} + \begin{vmatrix} -\lambda & b \\ 0 & d-\lambda \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix} + %% \begin{vmatrix} a & 0 \\ c & -\lambda \end{vmatrix} + %% \begin{vmatrix} -\lambda & b \\ 0 & d \end{vmatrix} + \begin{vmatrix} -\lambda & 0 \\ 0 & -\lambda \end{vmatrix} = \\ (-1)^2\lambda^2 +E_1\lambda{2-1}+E_2 $$
Inductive step (size(A) $n$ assuming the for matrixes with size $n-1$ the hypothesis is true)
Consider the following determinant: $$ \begin{vmatrix} a_{1,1}-\lambda & a_{1,2} & \dots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2}-\lambda & \dots & a_{2,n-1} & a_{2,n} \\ \vdots & \vdots & \dots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \dots & a_{n-1,n-1}-\lambda & a_{n-1,n} \\ a_{n,1} & a_{n,2} & \dots & a_{n,n-1} & a_{n,n} - \lambda \\ \end{vmatrix} $$ Now, by applying the linear property of determinants (as done the base case) we have: $$ \begin{vmatrix} a_{1,1}-\lambda & a_{1,2} & \dots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2}-\lambda & \dots & a_{2,n-1} & a_{2,n} \\ \vdots & \vdots & \dots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \dots & a_{n-1,n-1}-\lambda & a_{n-1,n} \\ a_{n,1} & a_{n,2} & \dots & a_{n,n-1} & a_{n,n} - \lambda \\ \end{vmatrix} = \\ \begin{vmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{2,n-1} & a_{2,n} \\ \vdots & \vdots & \dots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \dots & a_{n-1,n-1} & a_{n-1,n} \\ a_{n,1} & a_{n,2} & \dots & a_{n,n-1} & a_{n,n}\\ \end{vmatrix} + \begin{vmatrix} a_{1,1}-\lambda & a_{1,2} & \dots & a_{1,n-1} & 0 \\ a_{2,1} & a_{2,2}-\lambda & \dots & a_{2,n-1} & 0 \\ \vdots & \vdots & \dots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \dots & a_{n-1,n-1}-\lambda & 0 \\ a_{n,1} & a_{n,2} & \dots & a_{n,n-1} & - \lambda \\ \end{vmatrix} $$ Now, by applying the Laplace expansion on the last column of the second determinant in the above formula we obtain: $$ \det(A) -\lambda \det(M_{n,n}-\lambda E) $$ where $M_{n,n}$ is the matrix that results by deleting the $n$th row and column from $A$. But the above, by the inductive hypothesis equals to: $$ \det(A) -\lambda[(-1)^{n-1}\lambda^{n-1}+E_1\lambda^{(n-1)-1}+E_2\lambda^{(n-1)-2}+\dots+E_{n-1})] = \\ (-1)^{n}\lambda^n +E_1\lambda^{n-1}+E_2\lambda^{n-2}+\dots+E_{n-1}\lambda+E_n = p(\lambda) $$
QED