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. A $2\times2$ picture: $A = \begin{pmatrix}2&1\\1&2\end{pmatrix}$ has eigenvectors $(1, 1)$ and $(1, -1)$ with eigenvalues $3$ and $1$, so $\det(A^2 + I) = (3^2 + 1)(1^2 + 1) = 20$ — and directly, $A^2 + I = \begin{pmatrix}6&4\\4&6\end{pmatrix}$ has determinant $36 - 16 = 20$.

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.

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. A second route, worth knowing as a technique: for diagonalizable $A = PDP^{-1}$, $p_A(A) = P\,p_A(D)P^{-1}$ and $p_A(D)$ is diagonal with entries $p_A(\lambda_i) = 0$; diagonalizable matrices are dense (perturb the eigenvalues apart) and $A \mapsto p_A(A)$ is continuous in the entries, so the identity extends to every complex matrix. Prove an algebraic identity on a dense set, then pass to the limit.

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".

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$.

Step 1 — write $Q = \mathbf x^{\mathsf T}A\mathbf x$ with the symmetric $A = \begin{pmatrix}5&2\\2&2\end{pmatrix}$ (the cross term is split evenly).

Step 2 — eigenvalues: $\mathrm{tr}A = 7$, $\det A = 6$, so $\lambda^2 - 7\lambda + 6 = 0$ and $\lambda = 6, 1$, with unit eigenvectors $\mathbf v_1 = \tfrac{1}{\sqrt5}(2, 1)$ and $\mathbf v_2 = \tfrac{1}{\sqrt5}(1, -2)$, orthogonal as the spectral theorem promises.

Step 3 — write a unit vector as $\mathbf x = c_1\mathbf v_1 + c_2\mathbf v_2$ with $c_1^2 + c_2^2 = 1$. Then $Q = 6c_1^2 + c_2^2 = 1 + 5c_1^2$, which ranges over $[1, 6]$.

Step 4 — maximum $6$ at $\pm\tfrac{1}{\sqrt5}(2, 1)$, minimum $1$ at $\pm\tfrac{1}{\sqrt5}(1, -2)$. Check: $Q(2, 1) = 20 + 8 + 2 = 30 = 6\cdot5$ ✓.

How to find it. Any extremum of a quadratic form on a sphere is an eigenvalue problem (the Rayleigh quotient); Lagrange's condition $\nabla Q = \lambda\nabla(x^2 + y^2)$ is literally $A\mathbf x = \lambda\mathbf x$.