Xjyuk

Let $A$ be an $ntimes n$ matrix. Then its characteristic polynomial is

$$phi_A(x) = det(xI - A) = x^n - (operatornametr A)x^n-1 + cdots + (-1)^n-1(operatornametr(operatornameadjA))x + (-1)^ndet A,$$

where $operatornameadjA$ denotes the adjugate matrix of $A$.

My question: Why are the coefficients of $phi_A$ those shown above?

I can see why $(-1)^ndet A$ is the constant term, since
$$det(A) = phi_A(0) = (0-mu_1)cdots(0-mu_n) = (-1)^nmu_1cdotsmu_n,$$

where $mu_i$ are the roots ($i=1,dots,n$). I also see why the coefficient of $x^n-1$ is minus the trace, since by Laplace expansion (along the first row):

beginalign*
&det(xI-A)\[10pt]
&= beginvmatrix
x-a_11 & -a_12 & cdots & -a_1n\
-a_21 & x-a_22 & cdots & -a_2n\
vdots & vdots & ddots & vdots\
-a_n1 & -a_n2 & cdots & x-a_nn
endvmatrix\[10pt]
&= (x-a_11)beginvmatrix
x-a_22 & cdots & -a_2n\
vdots & ddots & vdots\
-a_n2 & cdots & x-a_nn
endvmatrix + underbracea_12 beginvmatrix
-a_21 & cdots & -a_2n\
vdots & ddots & vdots\
-a_n1 & cdots & x-a_nn
endvmatrix + cdots_textat most polynomial of degree $n-2$\[10pt]
&=(x-a_11)bigg((x-a_22)beginvmatrix
x-a_33 & cdots & -a_3n\
vdots & ddots & vdots\
-a_n3 & cdots & x-a_nn
endvmatrix
+underbraceunderbracea_23beginvmatrix
-a_32 & cdots & -a_3n\
vdots & ddots & vdots\
-a_n2 & cdots & x-a_nn
endvmatrix+cdots_textat most polynomial of degree $n-3$
bigg) + cdots_textat most polynomial of degree $n-2$\
&kern10ptvdots\[10pt]
&=(x-a_11)(x-a_22)cdots(x-a_nn) + underbracecdots_textat most polynomial of degree $n-2$\[10pt]
&= x^n - (a_11+a_22+cdots + a_nn)x^n-1 + cdots\[10pt]
&= x^n - (operatornametrA)x^n-1 + cdots
endalign*
(Let me know if there is a more elegant way to obtain this).

But what I cannot seem to prove is that the coefficient of $x$ is $ (-1)^n-1operatornametr(operatornameadjA)$. Attempting to work with the Laplace expansion (as I did to obtain the trace above) is leading me nowhere.

This can easily be derived from Corollary 2 in https://math.stackexchange.com/a/3069061/ (applied to $-A$ instead of $A$) by setting $r = 1$, $r = n-1$ or $r = n$. If you follow the reference to my notes, you'll see that I basically make the "expand everything and extract the coefficients of the appropriate powers of $x$" argument that you already did for the $x^n-2$-coefficient and that @J_P sketched for the other coefficients; all I am doing differently is actually formalizing it.

For another proof, see my note The trace Cayley-Hamilton theorem (temporary mirror while the website just linked is offline), specifically:

• Corollary 2.4 (b) for the $x^0$-coefficient being $left(-1right)^n det A$;




• Theorem 5.32 for the $x^1$-coefficient being $left(-1right)^n-1 operatornameTrleft(operatornameadjAright)$;




• Corollary 3.22 for the $x^n-1$-coefficient being $- operatornameTr A$.

Note that my goal in that note (at least the original goal; feature creep has borne all of Section 5 and parts of the preceding sections) is not to find the coefficients of the characteristic polynomial, so I am not taking any sort of beeline. There isn't much to say in favor of my proof other than that it avoids the handwaving that typically appears in the standard (term-by-term expansion) argument.

Suppose first $B$ is an $n times n$ matrix with $det(B) = 1$. Then $textadj(B) = B^-1$, and

$$ phi_B^-1(x) = det(x I - B^-1) = det(x B - I) = (-x)^n det(x^-1 I - B)
= (-x)^n phi_B(1/x)$$

The coefficient of $x^1$ in $phi_B(x)$ is the coefficient of $x^-1$ in $phi_B(1/x)$, i.e. $(-1)^n$ times the coefficient of $x^n-1$ in $(-x)^n phi_B(1/x)$, but you know the coefficient of $x^n-1$ in $phi_B^-1(x)$ is
$texttr(B^-1)$. That is, the coefficient of $x^1$ in $phi_B(x)$ is
$(-1)^n texttr(B^-1) = (-1)^n texttr(textadj; B)$.

Now let $A = t B$, where $t ne 0$. Then $phi_A(x) = det(x I - t B) = t^n det((x/t)I - A) = t^n phi_B(x/t)$. The coefficient of $x^1$ in $phi_A(x)$ is then
$t^n-1$ times the coefficient of $x^1$ in $phi_B(x)$. But also
$textadj; A = t^n-1 textadj; B$. So we again obtain that the coefficient of
$x^1$ in $phi_A(x)$ is $(-1)^n texttr(textadj; A)$.

Every nonsingular matrix
$A = det(A)^1/n B$ where $det(B) = 1$, so the formula for the coefficient holds for every nonsingular matrix. (Note that in the case where $det(A)$ is negative and $n$ is even, we must use complex numbers here, but that's not a problem)

Now the coefficient of $x^1$ in $phi_A(x)$ and $(-1)^n texttr(textadj; A)$ are both polynomials in the coefficients of $A$.

Thus the equation must hold for all $n times n$ matrices, not just the nonsingular ones.

I define $phi_A(x)=det(A-lambda I)$. You get the coefficient at $lambda^n-k$ in the following way: pick $k$ diagonal entries $a_i_1i_1,...,a_i_ki_k$. These define a $ktimes k$ minor of $A$ that you get by removing every row and column that does not contain one of the chosen diagonal elements. Calculate the determinant of this minor and sum over all $nchoose k$ selections of the $k$ diagonal entries. Up to sign (which is just alternating) that is your $lambda^n-k$ coefficient.

I have to say that I don't know a precise formal proof (EDIT: go to the bottom of the answer, I've now added an attempt at formalizing what follows), I like to view this in a more algorithmic fashion. Here's how I convince myself:
$$
beginvmatrix
a_11-lambda & a_12 & ... & a_1n \
a_21 & a_22-lambda & ... & a_2n \
... & ... & ... & ... \
a_n1 & a_n2 & ...& a_nn-lambda
endvmatrix=\
=beginvmatrix
a_11 & a_12 & ... & a_1n \
a_21 & a_22-lambda & ... & a_2n \
... & ... & ... & ... \
a_n1 & a_n2 & ...& a_nn-lambda
endvmatrix-lambdabeginvmatrix
a_22-lambda & ... & a_2n \
... & ... & ... \
a_n2 & ...& a_nn-lambda
endvmatrix
$$
Now you see the problem has split into two parts. Deal with each one seperately: in the first one, move on to the next column and again split the determinant up as
$$
beginvmatrix
a_11 & a_12 & ... & a_1n \
a_21 & a_22-lambda & ... & a_2n \
... & ... & ... & ... \
a_n1 & a_n2 & ...& a_nn-lambda
endvmatrix=beginvmatrix
a_11 & a_12 & ... & a_1n \
a_21 & a_22 & ... & a_2n \
... & ... & ... & ... \
a_n1 & a_n2 & ...& a_nn-lambda
endvmatrix-lambdabeginvmatrix
a_11 & ... & a_2n \
... & ... & ... \
a_n2 & ...& a_nn-lambda
endvmatrix
$$
Do the same for the second one. As you keep doing this, a huge number of determinants will crop up ($2^n$ in total - which is just the sum of the binomial coefficients $nchoose k$, already suggestive). You can view this as a decision tree: at each step, you say whether you want to keep the $i$-th column or not. After you pick, you won't touch the previous columns again. So doing this will give you square determinants with certain columns missing. If you pick some columns (equivalently, some diagonal elements) to remove, say "NO" to every decision where you remove one of the desired columns and "YES" otherwise. This defines a path down the binary tree which terminantes when no more $lambda$'s are left. Since every selection of $k$ diagonal elements corresponds to exactly one path down the binary tree with $n-k$ "YES"'s, you will get $(-1)^n-klambda^n-k$ in front of each such determinant and so when you sum it all up, you get precisely the sum of of all diagonal-centered $ktimes k$ determinants.

In particular, you get the linear term by removing only $1$ column and row and summing over all possibilities. Since these are determinants of the principal minors which feature in the definition of the adjugate matrix, what you calculate is just the sum of the diagonal elements of the adjugate - that is, its trace.

If you don't believe all this mumbo-jumbo (which is perfectly reasonable), I strongly encourage you to try a $4times 4$ case since that is only $16$ determinants in total, or, if you have a lot of paper, the $5times 5$ case. That might help you get a "feel" for the pattern.

I also think this exact argument could be made more rigorous if you threw in some arguments like "at the $i$-th step, determinants of a certain size will appear at a certain power of $lambda$" and try doing this by induction, but I never actually went through with this so it's just a hunch at this point.

So I tried my hand at formalizing this a bit and here's my attempt. Let $D(b_1,b_2,...,b_n)$ denote the various determinants that will appear, where $b_iin0,1,2$. $b_i=0$ means that you remove the $i$-th row and column entirely, $b_i=1$ means that you only remove the $lambda$ at $a_ii$ and $b_i=2$ means "leave the $i$-th diagonal element and its row and column as is". For example:
$$
D(2,2,2)=beginvmatrix
a_11-lambda & a_12 & a_13 \
a_21 & a_22-lambda & a_23 \
a_31 & a_32 & a_33-lambda
endvmatrixquad
D(2,1,1)=beginvmatrix
a_11-lambda & a_12 & a_13 \
a_21 & a_22 & a_23 \
a_31 & a_32 & a_33
endvmatrix\
D(2,1,0)=beginvmatrix
a_11-lambda & a_12\
a_21 & a_22
endvmatrix
$$
We have the reduction formula: $$D(b_1,...,2,...,b_n)=D(b_1,...,1,...,b_n)-lambda D(b_1,...,0,...,b_n)$$
We start with $D(2_1,2_2,...,2_n)$. Write $bfb$ for the vector of $b_i$ and let $Vert bVert$ be the number of $1$'s in $bfb$. If we proceed by induction, we can say that
$$D(0,2_1,...,2_n-1)=sum_dimbf b=n-1\quad ,2notinbf bD(0,bf b)(-lambda)^n-1-Vertbf bVert$$
Since the $0$ at the front plays no role and the reduction formula is the same regardless of what the first $b_i$ is, we must have that also:
$$D(1,2_1,...,2_n-1)=sum_dimbf b=n-1\quad ,2notinbf bD(1,bf b)(-lambda)^n-1-Vertbf bVert$$
This can be rigorously demonstrated by observing that if we apply the reduction formula to $D(0,bf b)$ on some index, we get the same as if we would for $D(1text or 2,bf b)$ but for the first index. By applying reduction inductively on the indices, we eliminate all $2$'s but since at each step the formula is the same except that we change the first index, after all's said and done, we're left with identical formulas but for the first index.

Anyway, we have:
$$
D(2_1,2_2,...,2_n)=D(1,2,...,2)-lambda D(0,2,...,2)=\
=sum_dimbf b=n-1\quad ,2notinbf bleft(D(1,bf b)(-lambda)^n-1-Vertbf bVert+D(0,bf b)(-lambda)^n-Vertbf bVertright)=sum_dimbf b=n\,,,,, 2notinbf bD(bf b)(-lambda)^n-Vertbf bVert
$$
This establishes the inductive step and completes the proof.

Due to the helpful suggestion of @amd in the comments, here's an approach with Leibniz's formula. Here, $N=1,...,n$.
beginalign
&det(A-lambda I)=sum_sigmainmathrmSym(n)mathrmsgn(sigma)prod_i=1^n(a_isigma(i)-lambdadelta_isigma(i))=\
&=sum_sigmainmathrmSym(n)mathrmsgn(sigma)sum_Asubset Nprod_iin Aa_isigma(i)prod_jin N-A(-lambda)delta_jsigma(j)=\
&=sum_Asubset N(-lambda)^n-Vert AVertsum_sigmainmathrmSym(n)mathrmsgn(sigma)prod_iin Aa_isigma(i)prod_jin N-Adelta_jsigma(j)
endalign
In the last expression we have that $prod_jin N-Adelta_jsigma(j)$ which is $0$ unless $N-A$ contains only fixed points of $sigma$ - in other words, we need only sum over $sigma$ whose fixed points are a superset of $N-A$. But these new permutations form a group which is essentially just $mathrmSym(A)$, the permutations of $A$. The sign of a permutation of length $m$ is $(-1)^k$ where $k=m-text(number of disjoint cycles that make up $sigma$)$ - when we drop the stationary points from $sigma$, $m$ decreases but the number of disjoint cycles decreases by the exact same amount since stationary points correspond to trivial cycles. Hence the sign remains the same and we have:
$$
det(A-lambda I)=sum_Asubset N(-lambda)^n-Vert AVertsum_sigmainmathrmSym(A)mathrmsgn(sigma)prod_iin Aa_isigma(i)
$$
But the sums over $sigmainmathrmSym(A)$ are now just determinants of the principal minors and we are done.