uniolympiads Ελληνικά

Eigenvalues and Cayley–Hamilton

Characteristic and minimal polynomial, the eigenvalues of p(A)p(A), and how a relation such as A3=AA^3 = A tells you almost everything about the matrix.

What to know by heart

For A∈Mn(C)A \in \M_n(\C) with eigenvalues λ1,…,λn\lambda_1, \dots, \lambda_n (with multiplicity):

χA(x)=det⁡(xI−A)=∏i=1n(x−λi),tr⁡A=∑iλi,det⁡A=∏iλi.\chi_A(x) = \det(xI - A) = \prod_{i=1}^n (x - \lambda_i), \qquad \tr A = \sum_i \lambda_i, \qquad \det A = \prod_i \lambda_i .
  • Eigenvalues of a polynomial. For every polynomial pp, the eigenvalues of p(A)p(A) are p(λ1),…,p(λn)p(\lambda_1), \dots, p(\lambda_n), with multiplicity. Proof: triangularise, A=PTP−1A = PTP^{-1}; then p(A)=P p(T) P−1p(A) = P\,p(T)\,P^{-1} and p(T)p(T) is triangular with diagonal p(λi)p(\lambda_i). In particular tr⁡(Ak)=∑iλik\tr(A^k) = \sum_i \lambda_i^k.
  • Cayley–Hamilton. χA(A)=0\chi_A(A) = 0. For 2×22 \times 2: A2−(tr⁡A) A+(det⁡A) I=0A^2 - (\tr A)\,A + (\det A)\, I = 0.
  • Minimal polynomial mAm_A: the monic polynomial of least degree with mA(A)=0m_A(A) = 0. It divides every pp with p(A)=0p(A) = 0 (hence also χA\chi_A) and has the same roots as χA\chi_A, possibly with smaller multiplicities.
  • Diagonalisation. AA is diagonalisable over C\C if and only if mAm_A has simple roots. Consequently: if p(A)=0p(A) = 0 for some pp with simple roots, AA is diagonalisable.
  • ABAB and BABA have the same characteristic polynomial, for square A,BA, B.

When to use it

  • The statement gives a polynomial relation, e.g. A3=AA^3 = A or A2−3A+2I=0A^2 - 3A + 2I = 0. Every eigenvalue is a root of the polynomial: here λ∈{−1,0,1}\lambda \in \{-1, 0, 1\} or λ∈{1,2}\lambda \in \{1, 2\}. Since the roots are simple, AA is diagonalisable. Then tr⁡A\tr A, det⁡A\det A and rank⁡A\rank A count how many times each eigenvalue occurs.
  • Large powers. To find A100A^{100}, divide x100x^{100} by χA\chi_A (or mAm_A): x100=q(x)χA(x)+r(x)x^{100} = q(x)\chi_A(x) + r(x) with deg⁡r<n\deg r < n. Then A100=r(A)A^{100} = r(A). The coefficients of rr come from substituting the eigenvalues for xx.
  • Determinants of the form det⁡(p(A))\det(p(A)) =∏ip(λi)= \prod_i p(\lambda_i). E.g. det⁡(A2+I)=∏i(λi2+1)\det(A^2 + I) = \prod_i (\lambda_i^2 + 1).
  • Inversion. If det⁡A≠0\det A \ne 0, Cayley–Hamilton writes A−1A^{-1} as a polynomial in AA.

Pitfalls

  • The eigenvalues of A+BA + B are not λi+μi\lambda_i + \mu_i when A,BA, B do not commute. With A=(0100)A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} and B=A⊤B = A^\top, both AA and BB have only the eigenvalue 00, but A+BA + B has eigenvalues ±1\pm 1. For commuting matrices, see the sheet on nilpotent and commuting matrices.
  • p(A)=0p(A) = 0 does not mean every root of pp is an eigenvalue. II satisfies A2=AA^2 = A, but 00 is not an eigenvalue of it.
  • Real matrix, complex eigenvalues. (0−110)\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} has no real eigenvalues. Work over C\C and come back to R\R at the end. The non-real eigenvalues of a real matrix come in conjugate pairs.
  • The "proof" χA(A)=det⁡(AI−A)=0\chi_A(A) = \det(AI - A) = 0 is wrong. In det⁡(xI−A)\det(xI - A) the xx is a number; you cannot substitute a matrix before computing the determinant. If you need it in a solution, quote the theorem; don't "prove" it this way.

Further reading

  • Axler, Linear Algebra Done Right, 4th ed., §5A (Invariant Subspaces)
  • Axler, Linear Algebra Done Right, 4th ed., §5D (Diagonalizable Operators)
  • Gelca & Andreescu, Putnam and Beyond, §2.3.6 (Linear Transformations, Eigenvalues, Eigenvectors)
  • Gelca & Andreescu, Putnam and Beyond, §2.3.7 (The Cayley–Hamilton and Perron–Frobenius Theorems)
  • Axler, Linear Algebra Done Right, 4th ed., §5B (The Minimal Polynomial)

Contest problems using these tools

No problems with these tools yet.