Linear Algebra II: Spectra, Cayley–Hamilton & Finite Fields

A $3\times3$ matrix with eigenvalues $1, 2, 3$ has $\det(A^2 + I) = 2\cdot5\cdot10 = 100$ — no entries needed. Trace and determinant are the first two symmetric functions of the spectrum; Newton's identities convert power sums $\mathrm{tr}(A^k)$ into the characteristic polynomial and back. If $\mathrm{tr}(A^k) = 0$ for $k = 1..n$, then all eigenvalues vanish and $A$ is nilpotent — a classic Putnam lemma.

Consequences: $A^n$ is a combination of $I, A, \ldots, A^{n-1}$, so powers reduce; $A^{-1}$ is a polynomial in $A$ when $\det A \ne 0$; and a matrix with $A^2 = A$ (idempotent) or $A^2 = I$ (involution) or $A^k = 0$ (nilpotent) has eigenvalues confined to the roots of the corresponding polynomial — $\{0,1\}$, $\{\pm1\}$, $\{0\}$. Rank of an idempotent equals its trace. These one-liners decide many "show that" problems.

$|GL_2(\mathbb F_2)| = 3\cdot2 = 6$ ($\cong S_3$); $|GL_2(\mathbb F_3)| = 8\cdot6 = 48$; $|SL_n| = |GL_n|/(q - 1)$. The number of $k$-dimensional subspaces of $\mathbb F_q^n$ is the Gaussian binomial $\binom nk_q$. Over $\mathbb F_2$, "how many symmetric / nilpotent / invertible matrices" problems all reduce to this counting-by-columns template.

$\mathrm{tr} = 1$, $\det = -1$: $A^2 = A + I$. Then $A^3 = A^2 + A = 2A + I$, $A^4 = 2A^2 + A = 3A + 2I$, $A^5 = 3A^2 + 2A = 5A + 3I$. The coefficients are Fibonacci numbers — because $A$ is the Fibonacci matrix.

Let the distinct nonzero eigenvalues be $\lambda_1, \ldots, \lambda_m$ with multiplicities $c_1, \ldots, c_m \ge 1$. The hypotheses say $\sum_i c_i\lambda_i^k = 0$ for $k = 1, \ldots, m$ (we only need $m \le n$ of them): a homogeneous linear system in the unknowns $c_i$ whose coefficient matrix $[\lambda_i^k]$ is a Vandermonde matrix in distinct nonzero nodes times $\operatorname{diag}(\lambda_i)$ — invertible. So all $c_i = 0$, contradicting $c_i \ge 1$ unless $m = 0$. $\blacksquare$ Significance: traces of powers determine the spectrum (Newton's identities in matrix clothing); the converse — a nilpotent matrix has all power-traces zero — is immediate from triangularization.

Let $p_A(t) = \det(tI - A) = t^n + c_{n-1}t^{n-1} + \cdots + c_0$ and let $B(t) = \operatorname{adj}(tI - A)$, a matrix whose entries are polynomials in $t$ of degree $\le n - 1$; write $B(t) = \sum_{k=0}^{n-1}B_kt^k$ with constant matrices $B_k$. The adjugate identity $(tI - A)B(t) = p_A(t)I$ holds for every scalar $t$, so comparing coefficients of $t^k$ on both sides gives $B_{k-1} - AB_k = c_kI$ (with $B_{-1} = B_n = 0$). Multiply the $k$th equation by $A^k$ on the left and add over $k$: the left side telescopes to $0$, the right side is $\sum c_kA^k = p_A(A)$. $\blacksquare$ (The one-line "substitute $t = A$ into $\det(tI - A)$" is NOT a proof — $t$ is a scalar there.) Significance: $A^n$ is a combination of $I, A, \ldots, A^{n-1}$, so powers, inverses, and $e^{A}$ all live in an $n$-dimensional space; that is what makes "compute $A^{100}$" tractable.

Real eigenvalues: if $A\mathbf x = \lambda\mathbf x$ with $\mathbf x \ne 0$ complex, then $\bar{\mathbf x}^{\mathsf T}A\mathbf x = \lambda|\mathbf x|^2$, and taking the conjugate transpose of the same scalar (using $A^{\mathsf T} = A$ real) gives $\bar\lambda|\mathbf x|^2$; hence $\lambda = \bar\lambda$. Orthogonality: for eigenvectors with $\lambda \ne \mu$, $\lambda\,\mathbf y^{\mathsf T}\mathbf x = \mathbf y^{\mathsf T}A\mathbf x = (A\mathbf y)^{\mathsf T}\mathbf x = \mu\,\mathbf y^{\mathsf T}\mathbf x$, so $\mathbf y^{\mathsf T}\mathbf x = 0$. Full basis: take a unit eigenvector $\mathbf q_1$ (it exists since the characteristic polynomial has a real root); $A$ maps the orthogonal complement $\mathbf q_1^\perp$ to itself (if $\mathbf x \perp \mathbf q_1$ then $\mathbf q_1^{\mathsf T}A\mathbf x = (A\mathbf q_1)^{\mathsf T}\mathbf x = \lambda_1\mathbf q_1^{\mathsf T}\mathbf x = 0$), and restricted there it is again symmetric; induct on the dimension. $\blacksquare$ Significance: $\mathbf x^{\mathsf T}A\mathbf x = \sum\lambda_ic_i^2$ in the eigenbasis, which is the Rayleigh-quotient principle and the reason every quadratic-form extremum on the Putnam is "largest or smallest eigenvalue".

If $A = PDP^{-1}$ with $D$ diagonal, then $p_A(A) = P\,p_A(D)P^{-1}$, and $p_A(D)$ is diagonal with entries $p_A(\lambda_i) = 0$. So $p_A(A) = 0$. Diagonalizable matrices are dense in all matrices (perturb the eigenvalues to be distinct), and $A \mapsto p_A(A)$ is continuous (a polynomial in the entries), so the identity persists for every matrix. $\blacksquare$ Significance: the density argument is itself a Putnam technique — prove an algebraic identity on a dense set, then pass to the limit.

Let the distinct nonzero eigenvalues be $\mu_1, \ldots, \mu_m$ with multiplicities $c_j \ge 1$. The hypotheses say $\sum_jc_j\mu_j^k = 0$ for $k = 1..n$, in particular for $k = 1..m$. The matrix of this linear system in the unknowns $c_j$ is $[\mu_j^k]$, a Vandermonde times $\mathrm{diag}(\mu_j)$, invertible for distinct nonzero $\mu_j$. So all $c_j = 0$ — contradiction unless $m = 0$: every eigenvalue is $0$, and $A$ is nilpotent. $\blacksquare$ Vandermonde reappears as the engine of a spectral argument — the two linear algebra topics are one subject.

Step 1 — $A$ satisfies $x^3 - x = x(x-1)(x+1)$, which has distinct roots, so $A$ is diagonalizable with eigenvalues in $\{-1, 0, 1\}$.

Step 2 — in the eigenbasis, $A^2$ is diagonal with entries $\lambda_i^2 \in \{0, 1\}$: it is $1$ exactly for the nonzero eigenvalues.

Step 3 — so $\mathrm{tr}(A^2)$ counts nonzero eigenvalues, which (diagonalizable!) equals the rank. $\blacksquare$ The whole proof is: a polynomial with distinct roots forces diagonalizability, and then everything is a count.

Step 1 — columns one at a time: the first is any nonzero vector ($2^3 - 1 = 7$), the second avoids the $2$ vectors in the span of the first ($8 - 2 = 6$), the third avoids the $4$ in the span of the first two ($8 - 4 = 4$).

Step 2 — $7\cdot6\cdot4 = 168$ (this group is $GL_3(\mathbb F_2)$, the second-smallest nonabelian simple group).

Step 3 — fraction: $\tfrac{168}{512} \approx 0.33$; as $n \to \infty$ the fraction of invertible matrices over $\mathbb F_2$ tends to $\prod_{k\ge1}(1 - 2^{-k}) \approx 0.289$. A random binary matrix is singular with probability about $0.71$.