[proofplan] We expand the characteristic polynomial in two ways — as a product of linear factors and as a determinant — then compare coefficients. [/proofplan] [step:Characteristic Polynomial Factorisation | Factor over eigenvalues] By the Leibniz formula, $\det(A - tI) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n (A - tI)_{i,\sigma(i)}$. Each entry $(A-tI)_{i,\sigma(i)}$ is either $a_{ii} - t$ (degree $1$) when $\sigma(i) = i$, or $a_{i,\sigma(i)}$ (degree $0$) when $\sigma(i) \neq i$. So $\chi_A(t) = \det(A - tI)$ is a polynomial in $t$ of degree at most $n$. The identity permutation contributes the product $(a_{11} - t)\cdots(a_{nn} - t)$, which has degree $n$ with leading term $(-t)^n = (-1)^n t^n$. Every other permutation has at least two non-fixed points, so it contributes a degree at most $n - 2$. Therefore $\chi_A$ has degree exactly $n$ with leading coefficient $(-1)^n$. Since $\lambda_1, \ldots, \lambda_n$ are its roots (counted with algebraic multiplicity), \begin{align*} \chi_A(t) = (-1)^n(t - \lambda_1)(t - \lambda_2)\cdots(t - \lambda_n). \end{align*} [guided] We begin by establishing that $\chi_A(t) = \det(A - tI)$ is a polynomial in $t$. By the Leibniz formula, \begin{align*} \det(A - tI) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n (A - tI)_{i,\sigma(i)}. \end{align*} Each factor $(A - tI)_{i,\sigma(i)}$ is either the diagonal entry $a_{ii} - t$ (a degree-$1$ polynomial in $t$) when $\sigma(i) = i$, or the off-diagonal entry $a_{i,\sigma(i)}$ (a constant, degree $0$) when $\sigma(i) \neq i$. Each product $\prod_{i=1}^n (A - tI)_{i,\sigma(i)}$ is therefore a polynomial in $t$, and their sum is a polynomial in $t$ of degree at most $n$. To pin down the leading coefficient, observe that the identity permutation $\sigma = \text{id}$ contributes the diagonal product \begin{align*} (a_{11} - t)(a_{22} - t)\cdots(a_{nn} - t), \end{align*} which has degree $n$ with leading term $(-t)^n = (-1)^n t^n$. Can any other permutation also contribute a degree-$n$ term? No: if $\sigma \neq \text{id}$, then $\sigma$ has at least two non-fixed points $i, j$ with $\sigma(i) \neq i$ and $\sigma(j) \neq j$. The corresponding factors $a_{i,\sigma(i)}$ and $a_{j,\sigma(j)}$ are constants, so the product has degree at most $n - 2$. Therefore $\chi_A$ has degree exactly $n$ with leading coefficient $(-1)^n$. Since $\lambda_1, \ldots, \lambda_n$ are the roots of $\chi_A$ (counted with algebraic multiplicity) and a degree-$n$ polynomial with known leading coefficient is determined by its roots, \begin{align*} \chi_A(t) = (-1)^n(t - \lambda_1)(t - \lambda_2)\cdots(t - \lambda_n). \end{align*} [/guided] [/step] [step:Determinant Identity | Evaluate at $t = 0$] Evaluating at $t = 0$: $\chi_A(0) = \det(A)$ on the left, and on the right \begin{align*} (-1)^n(0 - \lambda_1)\cdots(0 - \lambda_n) = (-1)^n(-1)^n\lambda_1\cdots\lambda_n = \lambda_1\cdots\lambda_n. \end{align*} [guided] To recover the determinant, evaluate the characteristic polynomial at $t = 0$. On the left-hand side, \begin{align*} \chi_A(0) = \det(A - 0 \cdot I) = \det(A). \end{align*} On the right-hand side, substituting $t = 0$ into the factored form gives \begin{align*} (-1)^n(0 - \lambda_1)(0 - \lambda_2)\cdots(0 - \lambda_n) = (-1)^n(-\lambda_1)(-\lambda_2)\cdots(-\lambda_n). \end{align*} Each factor $(-\lambda_k)$ contributes one sign of $(-1)$, yielding $n$ additional factors of $(-1)$: \begin{align*} (-1)^n \cdot (-1)^n \cdot \lambda_1\lambda_2\cdots\lambda_n = (-1)^{2n}\lambda_1\cdots\lambda_n = \lambda_1\cdots\lambda_n. \end{align*} The determinant is therefore the product of all eigenvalues. [/guided] [/step] [step:Trace Identity | Compare coefficients of $t^{n-1}$] **Right-hand side.** In $(t - \lambda_1)\cdots(t - \lambda_n)$, the $t^{n-1}$ term arises by choosing $-\lambda_k$ from one factor and $t$ from the remaining $n-1$, giving coefficient $-(\lambda_1 + \cdots + \lambda_n)$. With the leading $(-1)^n$, the coefficient of $t^{n-1}$ on the right is \begin{align*} (-1)^n \cdot (-(\lambda_1 + \cdots + \lambda_n)) = (-1)^{n+1}(\lambda_1 + \cdots + \lambda_n). \end{align*} **Left-hand side.** In $\det(A - tI) = \sum_{\sigma \in S_n} \text{sgn}(\sigma)\prod_{i=1}^n (A - tI)_{i,\sigma(i)}$, a term has degree $n - 1$ in $t$ only if exactly $n - 1$ indices satisfy $\sigma(i) = i$ (contributing $a_{ii} - t$) and the remaining index contributes an off-diagonal entry (degree $0$ in $t$). But if $n - 1$ indices are fixed, the last must be fixed too, so only $\sigma = \text{id}$ contributes. The diagonal product gives \begin{align*} \text{coefficient of } t^{n-1} \text{ in } (a_{11} - t)\cdots(a_{nn} - t) = (-1)^{n-1}(a_{11} + \cdots + a_{nn}) = (-1)^{n-1}\operatorname{tr}(A). \end{align*} **Comparison.** Equating: \begin{align*} (-1)^{n-1}\operatorname{tr}(A) &= (-1)^{n+1}(\lambda_1 + \cdots + \lambda_n). \end{align*} Since $(-1)^{n+1} = (-1)^{n-1}\cdot(-1)^2 = (-1)^{n-1}$, dividing by $(-1)^{n-1}$ gives $\operatorname{tr}(A) = \lambda_1 + \cdots + \lambda_n$. [guided] For the trace, we compare the coefficient of $t^{n-1}$ on both sides of the identity \begin{align*} \det(A - tI) = (-1)^n(t - \lambda_1)(t - \lambda_2)\cdots(t - \lambda_n). \end{align*} **Right-hand side.** Expanding the product $(t - \lambda_1)\cdots(t - \lambda_n)$, each factor contributes either $t$ or $-\lambda_k$. To obtain $t^{n-1}$, we must choose $-\lambda_k$ from exactly one factor and $t$ from the remaining $n - 1$ factors. Summing over all $n$ choices: \begin{align*} \text{coefficient of } t^{n-1} \text{ in } (t - \lambda_1)\cdots(t - \lambda_n) = -(\lambda_1 + \lambda_2 + \cdots + \lambda_n). \end{align*} Including the leading $(-1)^n$, the coefficient of $t^{n-1}$ on the right is $(-1)^n \cdot (-(\lambda_1 + \cdots + \lambda_n)) = (-1)^{n+1}(\lambda_1 + \cdots + \lambda_n)$. **Left-hand side.** In the Leibniz expansion $\det(A - tI) = \sum_{\sigma \in S_n} \text{sgn}(\sigma)\prod_{i=1}^n (A - tI)_{i,\sigma(i)}$, we ask: which permutations $\sigma$ produce a term of degree $n - 1$ in $t$? A factor $(A - tI)_{i,\sigma(i)}$ contributes degree $1$ in $t$ only when $\sigma(i) = i$ (the diagonal entry $a_{ii} - t$). Off-diagonal entries $a_{i,\sigma(i)}$ have degree $0$. So to get total degree $n - 1$, we need exactly $n - 1$ indices with $\sigma(i) = i$. But if a permutation fixes $n - 1$ elements, it must fix the last one too — so $\sigma = \text{id}$ is the only permutation contributing degree $n - 1$. The identity permutation gives the diagonal product \begin{align*} (a_{11} - t)(a_{22} - t)\cdots(a_{nn} - t). \end{align*} Expanding this product, the coefficient of $t^{n-1}$ arises by choosing $(-t)$ from $n - 1$ factors and the constant $a_{ii}$ from one factor: \begin{align*} (-1)^{n-1}(a_{11} + a_{22} + \cdots + a_{nn}) = (-1)^{n-1}\operatorname{tr}(A). \end{align*} **Comparison.** Setting the two expressions equal: \begin{align*} (-1)^{n-1}\operatorname{tr}(A) = (-1)^{n+1}(\lambda_1 + \cdots + \lambda_n). \end{align*} Since $(-1)^{n+1} = (-1)^{n-1} \cdot (-1)^2 = (-1)^{n-1}$, we may divide both sides by $(-1)^{n-1}$ to obtain \begin{align*} \operatorname{tr}(A) = \lambda_1 + \lambda_2 + \cdots + \lambda_n. \end{align*} [/guided] [/step]