7
$\begingroup$

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

$$\phi_A(x) = \det(xI - A) = x^n - (\operatorname{tr} A)x^{n-1} + \cdots + (-1)^{n-1}(\operatorname{tr}(\operatorname{adj}A))x + (-1)^n\det A,$$

where $\operatorname{adj}A$ denotes the adjugate matrix of $A$.

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

I can see why $(-1)^n\det A$ is the constant term, since $$\det(A) = \phi_A(0) = (0-\mu_1)\cdots(0-\mu_n) = (-1)^n\mu_1\cdots\mu_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):

\begin{align*} &\det(xI-A)\\[10pt] &= \begin{vmatrix} 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} \end{vmatrix}\\[10pt] &= (x-a_{11})\begin{vmatrix} x-a_{22} & \cdots & -a_{2n}\\ \vdots & \ddots & \vdots\\ -a_{n2} & \cdots & x-a_{nn} \end{vmatrix} + \underbrace{a_{12} \begin{vmatrix} -a_{21} & \cdots & -a_{2n}\\ \vdots & \ddots & \vdots\\ -a_{n1} & \cdots & x-a_{nn} \end{vmatrix} + \cdots}_{\text{at most polynomial of degree $n-2$}}\\[10pt] &=(x-a_{11})\bigg((x-a_{22})\begin{vmatrix} x-a_{33} & \cdots & -a_{3n}\\ \vdots & \ddots & \vdots\\ -a_{n3} & \cdots & x-a_{nn} \end{vmatrix} +\underbrace{\underbrace{a_{23}\begin{vmatrix} -a_{32} & \cdots & -a_{3n}\\ \vdots & \ddots & \vdots\\ -a_{n2} & \cdots & x-a_{nn} \end{vmatrix}+\cdots}_{\text{at most polynomial of degree $n-3$}} \bigg) + \cdots}_{\text{at most polynomial of degree $n-2$}}\\ &\kern10pt\vdots\\[10pt] &=(x-a_{11})(x-a_{22})\cdots(x-a_{nn}) + \underbrace{\cdots}_{\text{at most polynomial of degree $n-2$}}\\[10pt] &= x^n - (a_{11}+a_{22}+\cdots + a_{nn})x^{n-1} + \cdots\\[10pt] &= x^n - (\operatorname{tr}A)x^{n-1} + \cdots \end{align*} (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-1}\operatorname{tr}(\operatorname{adj}A)$. Attempting to work with the Laplace expansion (as I did to obtain the trace above) is leading me nowhere.

$\endgroup$
  • 1
    $\begingroup$ Leibniz’ expansion seems like it was almost made for proving this. $\endgroup$ – amd Jun 24 at 0:12
4
$\begingroup$

Suppose first $B$ is an $n \times n$ matrix with $\det(B) = 1$. Then $\text{adj}(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 $\text{tr}(B^{-1})$. That is, the coefficient of $x^1$ in $\phi_B(x)$ is $(-1)^n \text{tr}(B^{-1}) = (-1)^n \text{tr}(\text{adj}\; 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 $\text{adj}\; A = t^{n-1} \text{adj}\; B$. So we again obtain that the coefficient of $x^1$ in $\phi_A(x)$ is $(-1)^n \text{tr}(\text{adj}\; 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 \text{tr}(\text{adj}\; 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.

$\endgroup$
3
$\begingroup$

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(-1\right)^n \det A$;

  • Theorem 5.32 for the $x^1$-coefficient being $\left(-1\right)^{n-1} \operatorname{Tr}\left(\operatorname{adj}A\right)$;

  • Corollary 3.22 for the $x^{n-1}$-coefficient being $- \operatorname{Tr} 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.

$\endgroup$
  • $\begingroup$ I've always wanted to see this done more rigorously, I'll have to sit down and peruse your other post carefully. Apparently this can also be done with exterior powers but I don't know the first thing about them, do you have any references for that subject? $\endgroup$ – J_P Jun 23 at 22:36
  • $\begingroup$ I also tried my own hand at formalizing the argument which I added to my answer. I'd be very grateful if you found the time to just quickly scan it and tell me if it seems okay. $\endgroup$ – J_P Jun 23 at 23:40
  • 1
    $\begingroup$ @J_P: Ironically, it is the "This can be rigorously demonstrated by observing" part that I don't understand about your proof, but it is otherwise a nice outline of a rigorous proof without too much pain (and the part I don't understand can be done by induction). Good job! $\endgroup$ – darij grinberg Jun 24 at 5:06
  • 1
    $\begingroup$ Thank you for checking! Yes, that part also bugged me but I think it can indeed be rather easily filled in by doing induction more explicitly, though I think I've had enough of this problem for a while... Thanks again. $\endgroup$ – J_P Jun 24 at 11:16
1
$\begingroup$

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 $k\times 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 $n\choose 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: $$ \begin{vmatrix} a_{11}-\lambda & a_{12} & ... & a_{1n} \\ a_{21} & a_{22}-\lambda & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ...& a_{nn}-\lambda \end{vmatrix}=\\ =\begin{vmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22}-\lambda & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ...& a_{nn}-\lambda \end{vmatrix}-\lambda\begin{vmatrix} a_{22}-\lambda & ... & a_{2n} \\ ... & ... & ... \\ a_{n2} & ...& a_{nn}-\lambda \end{vmatrix} $$ 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 $$ \begin{vmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22}-\lambda & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ...& a_{nn}-\lambda \end{vmatrix}=\begin{vmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22} & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ...& a_{nn}-\lambda \end{vmatrix}-\lambda\begin{vmatrix} a_{11} & ... & a_{2n} \\ ... & ... & ... \\ a_{n2} & ...& a_{nn}-\lambda \end{vmatrix} $$ 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 $n\choose 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-k}\lambda^{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 $k\times 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 $4\times 4$ case since that is only $16$ determinants in total, or, if you have a lot of paper, the $5\times 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_i\in\{0,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)=\begin{vmatrix} a_{11}-\lambda & a_{12} & a_{13} \\ a_{21} & a_{22}-\lambda & a_{23} \\ a_{31} & a_{32} & a_{33}-\lambda \end{vmatrix}\quad D(2,1,1)=\begin{vmatrix} a_{11}-\lambda & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{vmatrix}\\ D(2,1,0)=\begin{vmatrix} a_{11}-\lambda & a_{12}\\ a_{21} & a_{22} \end{vmatrix} $$ 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 $\bf{b}$ for the vector of $b_i$ and let $\Vert {\bf b}\Vert$ be the number of $1$'s in $\bf{b}$. If we proceed by induction, we can say that $$D(0,2_1,...,2_{n-1})=\sum_{\dim{\bf b}=n-1\\\quad \,2\not\in{\bf b}}D(0,{\bf b})(-\lambda)^{n-1-\Vert{\bf b}\Vert}$$ 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_{\dim{\bf b}=n-1\\\quad \,2\not\in{\bf b}}D(1,{\bf b})(-\lambda)^{n-1-\Vert{\bf b}\Vert}$$ 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(1\text{ 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_{\dim{\bf b}=n-1\\\quad \,2\not\in{\bf b}}\left(D(1,{\bf b})(-\lambda)^{n-1-\Vert{\bf b}\Vert}+D(0,{\bf b})(-\lambda)^{n-\Vert{\bf b}\Vert}\right)=\sum_{\dim{\bf b}=n\\\,\,\,\,\, 2\not\in{\bf b}}D({\bf b})(-\lambda)^{n-\Vert{\bf b}\Vert} $$ 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\}$. \begin{align} &\det(A-\lambda I)=\sum_{\sigma\in\mathrm{Sym}(n)}\mathrm{sgn}(\sigma)\prod_{i=1}^n(a_{i\sigma(i)}-\lambda\delta_{i\sigma(i)})=\\ &=\sum_{\sigma\in\mathrm{Sym}(n)}\mathrm{sgn}(\sigma)\sum_{A\subset N}\prod_{i\in A}a_{i\sigma(i)}\prod_{j\in N-A}(-\lambda)\delta_{j\sigma(j)}=\\ &=\sum_{A\subset N}(-\lambda)^{n-\Vert A\Vert}\sum_{\sigma\in\mathrm{Sym}(n)}\mathrm{sgn}(\sigma)\prod_{i\in A}a_{i\sigma(i)}\prod_{j\in N-A}\delta_{j\sigma(j)} \end{align} In the last expression we have that $\prod_{j\in N-A}\delta_{j\sigma(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 $\mathrm{Sym}(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_{A\subset N}(-\lambda)^{n-\Vert A\Vert}\sum_{\sigma\in\mathrm{Sym}(A)}\mathrm{sgn}(\sigma)\prod_{i\in A}a_{i\sigma(i)} $$ But the sums over $\sigma\in\mathrm{Sym}(A)$ are now just determinants of the principal minors and we are done.

$\endgroup$
  • $\begingroup$ I believe that the Leibniz formula for determinants can be used to prove this. $\endgroup$ – amd Jun 23 at 23:07
  • $\begingroup$ Possibly, but I dread the thought of using that formula, I just find it really unwieldy. $\endgroup$ – J_P Jun 23 at 23:37
  • $\begingroup$ It’s awful for computations, but great for proofs. In particular, your construction is equivalent to picking out the terms that involve exactly $n-k$ $\lambda$’s. $\endgroup$ – amd Jun 24 at 0:09
  • $\begingroup$ Wow, you're right! I think I managed to do it. Well, I'm not absolutely certain about my combinatorics (have to think about permutations a bit at one step) but I think it works. I'll also add this approach to my answer unless you were thinking of posting it yourself in which case tell me and I'll delete my edit. $\endgroup$ – J_P Jun 24 at 0:33
  • $\begingroup$ You need to be a bit careful about contributions from terms with more $\lambda$’s, but they might cancel nicely. Anyway, that formula is where I’d start looking for a proof. $\endgroup$ – amd Jun 24 at 0:36
0
$\begingroup$

The above answers are excellent and are a bit more general than what I had in mind, but if you only wanted the coefficient of $x$ in $\phi_A(x)$, here is a reasonably straightforward way to get it: this coefficient is just $\phi_A'(0)$, so if we write $A(x)=xI-A$, we are looking for the derivative of the composite function $\det(A(x))$. For any square matrix $M$, $\det(M)=\det(\{M_{i,j}\}_{i,j=1}^n)$ is some polynomial function of the entries, and by the cofactor expansion, we can expand along any row $i$ to find that $$\det(M)=\sum_{j=1}^n M_{i,j}C_{i,j},$$ where $C_{i,j}$ is the $(i,j)$ cofactor of $M$. Note that this is not a function of $M_{i,j}$. In particular, for any indices $i,k$, the product rule gives $$\frac{\partial \det(M)}{\partial M_{i,k}}=\sum_{j=1}^n\frac{\partial M_{i,j}}{\partial M_{i,k}}C_{i,j}+M_{i,j}\frac{\partial C_{i,j}}{M_{i,k}}.$$ But unless $j=k$, the term $\partial M_{i,j}/\partial M_{i,k}=0$ (and is $1$ when $j=k$) and similarly $\partial C_{i,j}/\partial M_{i,k}=0$ as $C_{i,j}$ is obtained by taking a determinant that excludes the $i$th row. Therefore, $$\frac{\partial \det(M)}{\partial M_{i,k}}=C_{i,k}.$$

In our case, the chain rule gives $$ \phi_A'(0)=\sum_{i,j=1}^n \frac{\partial \det(A(0))}{\partial A_{i,j}}\frac{\partial A_{i,j}}{\partial x}(0)=\sum_{i=1}^n C_{i,i},$$ where $C_{i,i}$ is the $(i,i)$-cofactor of $A(0)=-A$. All the off-diagonal terms are zero as $\partial A_{i,j}/\partial x=1$ if $i=j$ and is zero otherwise as only diagonal entries are affected by adding $xI$. This is exactly $(-1)^{n-1}\text{tr}(\text{adj}(A))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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