User:IssaRice/Linear algebra/Trace of matrix equals sum of eigenvalues

This is chapter 4 exercise 1.11 in Linear Algebra Done Wrong (p. 105).

Theorem. Let $A$ be a matrix. Then $\operatorname {trace} A=\lambda _{1}+\cdots +\lambda _{n}$ , where $\lambda _{1},\ldots ,\lambda _{n}$ are the eigenvalues of $A$ (counting multiplicities).

Proof. We already know that $\det(A-\lambda I)=(\lambda _{1}-\lambda )\cdots (\lambda _{n}-\lambda )$ . Multiplying out the right hand side, the $\lambda ^{n-1}$ term is $\lambda _{1}(-\lambda )^{n-1}+\lambda _{2}(-\lambda )^{n-1}+\cdots +\lambda _{n}(-\lambda )^{n-1}=(\lambda _{1}+\cdots +\lambda _{n})(-1)^{n-1}\lambda ^{n-1}$ .

Now consider equation 4.2 from the book (p. 89):

$\det A=\sum _{\sigma \in \mathrm {Perm} (n)}a_{\sigma (1),1}a_{\sigma (2),2}\cdots a_{\sigma (n),n}\mathrm {sign} (\sigma )$

The matrix $A-\lambda I$ has the form:

${\begin{pmatrix}a_{1,1}-\lambda &&*\\&\ddots &\\{*}&&a_{n,n}-\lambda \end{pmatrix}}$

Taking the identity permutation we get the term $(a_{1,1}-\lambda )\cdots (a_{n,n}-\lambda )$ . All the rest of the permutations correspond to terms that can take at most $n-2$ of the elements along the diagonal, so will result in a term (when multiplied out) that will have degree at most $n-2$ (why $n-2$ rather than $n-1$ ? because if we pick row k in column j!=k (i.e. not a diagonal element), then we can't take row k in any of the other columns including in column k, since a permutation can take at most one element from each row. So once we pick one element that's not on the diagonal, we must have at least two that aren't on the diagonal).

So we can write $\det(A-\lambda I)=(a_{1,1}-\lambda )\cdots (a_{n,n}-\lambda )+q(\lambda )$ , where $q(\lambda )$ has degree at most $n-2$ .

Now if we look at the $\lambda ^{n-1}$ term in $(a_{1,1}-\lambda )\cdots (a_{n,n}-\lambda )+q(\lambda )$ we get $(a_{1,1}+\cdots +a_{n,n})(-1)^{n-1}\lambda ^{n-1}$ . This means that $\lambda _{1}+\cdots +\lambda _{n}=a_{1,1}+\cdots +a_{n,n}=\operatorname {trace} A$ as required.

See also