Cayley–Hamilton theorem
The Cayley–Hamilton theorem is a fundamental result in linear algebra stating that every square matrix over a commutative ring satisfies its own characteristic equation, meaning that if p(\lambda) = \det(\lambda I - A) is the characteristic polynomial of an n \times n matrix A, then p(A) = 0.[1] This monic polynomial of degree n annihilates the matrix, providing a polynomial relation A^n + c_{n-1} A^{n-1} + \cdots + c_0 I = 0, where the c_i are the coefficients of p(\lambda) and I is the identity matrix.[1] The theorem applies to matrices with entries in fields like the real or complex numbers, as well as more general commutative rings, and serves as a cornerstone for understanding matrix polynomials and spectral properties.[2] Named after mathematicians Arthur Cayley and William Rowan Hamilton, the theorem was independently discovered and proved in the mid-19th century. Hamilton contributed insights through his work on linear operators over quaternions in the 1860s, establishing a general form of the result for such structures.[3] Cayley formalized the theorem for matrices in his seminal publications, including a 1858 memoir on matrix theory where he verified it for small dimensions and postulated its general validity.[4] The full proof for arbitrary dimensions was later provided by Georg Frobenius in 1878, solidifying its place in abstract algebra.[5] The Cayley–Hamilton theorem has wide-ranging applications in matrix computations and theoretical mathematics. It enables efficient calculation of high powers of matrices by reducing them to linear combinations of lower powers via the annihilating polynomial, which is essential for numerical algorithms and simulations.[5] In control theory and dynamical systems, it facilitates the analysis of linear time-invariant systems by expressing state transitions using the characteristic equation.[6] Additionally, the theorem underpins methods for computing matrix inverses through the adjugate matrix and characteristic polynomial, as well as evaluating matrix exponentials and functions like the resolvent.[5] These properties extend to advanced topics, including extensions for non-commutative rings and generalizations in operator theory on infinite-dimensional spaces.[7]Statement and Background
Theorem statement
The Cayley–Hamilton theorem asserts that for any n \times n matrix A with entries in a commutative ring R with identity, the matrix A satisfies its own characteristic equation.[8] The characteristic polynomial of A is defined as p(\lambda) = \det(\lambda I_n - A), where I_n denotes the n \times n identity matrix, and this is a monic polynomial of degree n in \lambda with coefficients in R.[1] Explicitly, p(\lambda) = \sum_{k=0}^n c_k \lambda^k with c_n = 1, and the theorem states that p(A) = \sum_{k=0}^n c_k A^k = 0, where A^0 = I_n and powers of A are defined via matrix multiplication.[8] This result implies that the minimal polynomial of A, which is the monic polynomial of least degree annihilating A, divides the characteristic polynomial p(\lambda).[9]Historical development
The Cayley–Hamilton theorem originated in the mid-19th century amid the emerging theory of matrices and quaternions. Arthur Cayley introduced the core result in his seminal 1858 memoir, where he proved the theorem for square matrices over the real numbers, specifically stating it for dimensions up to 3×3 and providing a detailed proof for the 2×2 case.[10] This work laid the foundation by linking matrices to their characteristic equations, though Cayley's proof relied on explicit computations limited to small dimensions. William Rowan Hamilton's contributions, in his 1853 Lectures on Quaternions and subsequent work, involved linear operators on quaternion spaces and influenced early matrix concepts, with independent discoveries of analogous results for quaternion linear functions that paralleled Cayley's findings.[3][11] Although Hamilton's quaternion-based explorations predated some of Cayley's matrix applications, Cayley's 1858 publication preceded Hamilton's fuller exposition in 1864, sparking debates on priority; the theorem's dual naming honors both for their intertwined advancements in non-commutative algebra and linear transformations.[12] Ferdinand Frobenius advanced the theorem significantly in 1878 by providing the first general proof for matrices of arbitrary finite dimension over arbitrary fields, extending Cayley's ideas through the introduction of the minimal polynomial and bilinear forms.[1] This generalization addressed limitations in earlier versions restricted to reals or small sizes. In the 20th century, the theorem evolved from classical matrix theory to a fully abstract form applicable to endomorphisms over commutative rings, as formalized in modern algebra texts integrating ring theory and module structures.[13]Foundational Concepts
Characteristic polynomial
The characteristic polynomial of an n \times n matrix A over a field is defined asp_A(\lambda) = \det(\lambda I_n - A),
where I_n is the n \times n identity matrix and \lambda is a scalar variable.[14] This yields a monic polynomial of degree n, with leading coefficient 1.[14] Over an algebraically closed field, the roots of p_A(\lambda) = 0 are precisely the eigenvalues of A, counting algebraic multiplicities, and the coefficients of p_A(\lambda) (up to sign) are the elementary symmetric functions of these eigenvalues.[15] In particular, the coefficient of \lambda^{n-1} is -\operatorname{tr}(A), where \operatorname{tr}(A) denotes the trace of A (the sum of its diagonal entries), and the constant term is (-1)^n \det(A).[14] The characteristic polynomial is invariant under similarity transformations: if B = P^{-1} A P for some invertible matrix P, then p_B(\lambda) = p_A(\lambda).[16] To compute p_A(\lambda), one typically expands the determinant using the cofactor method along a row or column, which is straightforward for small n (e.g., n = 2 or $3) but grows computationally intensive for larger n.[14] For triangular matrices, the characteristic polynomial simplifies to the product \prod_{i=1}^n (\lambda - a_{ii}), where a_{ii} are the diagonal entries.[14] This construction extends to matrices over commutative rings with identity: p_A(\lambda) = \det(\lambda I_n - A) remains a monic polynomial of degree n in the polynomial ring over the base ring, without requiring the existence of eigenvalues.[17] The Cayley–Hamilton theorem asserts that substituting A for \lambda yields the zero matrix.[16]
Adjugate matrix
The adjugate matrix, also known as the classical adjoint, of an n \times n matrix B is defined as the transpose of its cofactor matrix. The cofactor matrix C has entries C_{ij} given by (-1)^{i+j} times the determinant of the submatrix of B obtained by removing the i-th row and j-th column. Thus, the (i,j)-entry of the adjugate \operatorname{adj}(B) is C_{ji}.[18] A fundamental property of the adjugate is the classical adjugate formula, which states that B \cdot \operatorname{adj}(B) = \operatorname{adj}(B) \cdot B = \det(B) I_n, where I_n is the n \times n identity matrix. This relation holds for any square matrix B over a commutative ring and is derived from the Laplace expansion of the determinant along rows and columns.[18] Consider the specific case where B = \lambda I_n - A for an n \times n matrix A and scalar \lambda. The entries of \operatorname{adj}(\lambda I_n - A) are polynomials in \lambda of degree at most n-1. This follows from the structure of the cofactor expansions, where each cofactor determinant is a polynomial of degree n-1 in the entries of \lambda I_n - A.[19] The characteristic polynomial of A, defined as p_A(\lambda) = \det(\lambda I_n - A), takes the form \lambda^n - (\operatorname{tr} A) \lambda^{n-1} + \cdots + (-1)^n \det(A), where \operatorname{tr} A is the trace of A, the sum of its diagonal entries. This monic polynomial arises directly from expanding \det(\lambda I_n - A) using properties of determinants, with the coefficient of \lambda^{n-1} being the negative trace.[20] For computation, consider a $2 \times 2 matrix B = \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix}. The adjugate is \operatorname{adj}(B) = \begin{pmatrix} b_{22} & -b_{12} \\ -b_{21} & b_{11} \end{pmatrix}, obtained by transposing the cofactor matrix whose entries are the signed $1 \times 1 minors. Verifying the formula, B \cdot \operatorname{adj}(B) = \begin{pmatrix} b_{11} b_{22} - b_{12} b_{21} & 0 \\ 0 & b_{11} b_{22} - b_{12} b_{21} \end{pmatrix} = \det(B) I_2.[18]Illustrative Examples
$1 \times 1 matrices
The Cayley–Hamilton theorem holds in its simplest form for $1 \times 1 matrices, which are scalar matrices over a field. Consider a $1 \times 1 matrix A = , where a is an element of the field. The characteristic polynomial of A is given by p(\lambda) = \det(\lambda I - A) = \lambda - a.[21] Substituting the matrix A into this polynomial yields p(A) = A - aI = - a{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} = [a - a] = {{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}}, the zero matrix, verifying the theorem directly.[21] This trivial verification illustrates that every scalar a satisfies the equation a - a = 0, which aligns with the theorem's assertion that a matrix satisfies its own characteristic equation. In this context, the $1 \times 1 case links the theorem to the basic properties of field elements, where the matrix structure reduces to scalar arithmetic.[21]2 × 2 matrices
Consider a general $2 \times 2 matrix A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}. The characteristic polynomial of A is given by p(\lambda) = \det(A - \lambda I) = \lambda^2 - (a + d)\lambda + (ad - bc), where a + d is the trace of A and ad - bc is the determinant of A.[2] By the Cayley–Hamilton theorem, substituting A into its characteristic polynomial yields the zero matrix: p(A) = A^2 - (\operatorname{tr} A) A + (\det A) I_2 = 0.[2] To verify explicitly, first compute A^2 = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} a^2 + bc & ab + bd \\ ac + dc & bc + d^2 \end{pmatrix} = \begin{pmatrix} a^2 + bc & b(a + d) \\ c(a + d) & d^2 + bc \end{pmatrix}. Then, p(A) = \begin{pmatrix} a^2 + bc & b(a + d) \\ c(a + d) & d^2 + bc \end{pmatrix} - (a + d) \begin{pmatrix} a & b \\ c & d \end{pmatrix} + (ad - bc) \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}. The (1,1) entry is a^2 + bc - (a + d)a + (ad - bc) = a^2 + bc - a^2 - ad + ad - bc = 0. The (1,2) entry is b(a + d) - (a + d)b = 0. Similarly, the (2,1) and (2,2) entries simplify to zero, confirming p(A) is the zero matrix.[2] For a numerical illustration, take A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}. The trace is $1 + 4 = 5 and the determinant is $1 \cdot 4 - 2 \cdot 3 = -2, so p(\lambda) = \lambda^2 - 5\lambda - 2. Now, A^2 = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = \begin{pmatrix} 7 & 10 \\ 15 & 22 \end{pmatrix}. Then, p(A) = \begin{pmatrix} 7 & 10 \\ 15 & 22 \end{pmatrix} - 5 \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} - 2 \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 7 & 10 \\ 15 & 22 \end{pmatrix} - \begin{pmatrix} 5 & 10 \\ 15 & 20 \end{pmatrix} - \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, verifying the theorem holds.[2]Proof Techniques
Direct algebraic proof
The direct algebraic proof of the Cayley–Hamilton theorem employs the adjugate matrix to establish a polynomial identity that, upon formal evaluation at the matrix itself, yields the desired result. Let A be an n \times n matrix over a commutative ring R with identity. The characteristic polynomial is defined as p(\lambda) = \det(\lambda I - A), a monic polynomial of degree n with coefficients in R. By the property of the adjugate matrix, the following identity holds for any scalar \lambda \in R: (\lambda I - A) \operatorname{adj}(\lambda I - A) = p(\lambda) I. The adjugate \operatorname{adj}(\lambda I - A) is itself a matrix whose entries are polynomials in \lambda of degree at most n-1, so it can be expressed as the matrix polynomial \operatorname{adj}(\lambda I - A) = \sum_{k=0}^{n-1} B_k \lambda^k, where each B_k is an n \times n matrix over R. Substituting this expansion into the identity gives a polynomial equation in \lambda that holds identically: (\lambda I - A) \sum_{k=0}^{n-1} B_k \lambda^k = p(\lambda) I. This equation can be viewed in the ring of matrix polynomials over R, where the indeterminate \lambda acts as a central scalar multiple of the identity (i.e., \lambda M = M \lambda for any matrix M).[22] To evaluate at the matrix A, apply the natural evaluation homomorphism from this polynomial ring to the ring of n \times n matrices over R, which sends \lambda to A and preserves multiplication and addition. Under this homomorphism, the left side becomes (A I - A) \sum_{k=0}^{n-1} B_k A^k = 0 \cdot \operatorname{adj}(0) = O, where O is the zero matrix, since A I - A = O. The right side evaluates to p(A) I. Thus, p(A) I = O, which implies p(A) = O, as multiplication by the identity matrix is injective.[22] The formal substitution is valid because the evaluation homomorphism respects the structure of the polynomial ring: the central nature of \lambda I ensures that terms like \lambda I \cdot \sum B_k \lambda^k map to A \sum B_k A^k, without issues from non-commutativity of matrix multiplication, as the indeterminate commutes with all matrix coefficients in the polynomial expressions. This proof assumes R is commutative to ensure the characteristic polynomial has coefficients in R and the determinant is well-defined; it extends directly to fields (where R is a field) and more generally to integral domains, with the result holding in the matrix ring over R.[8]Proof using polynomial coefficients
One approach to proving the Cayley–Hamilton theorem utilizes the structure of the polynomial ring over the base ring and the adjugate matrix to establish the identity formally before substituting the matrix argument. Let R be a commutative ring with identity, and let A be an n \times n matrix with entries in R. The characteristic polynomial is defined as p(\lambda) = \det(\lambda I - A) \in R[\lambda].[8] Consider the matrices over the polynomial ring R[\lambda]. The matrix \lambda I - A has entries in R[\lambda], and its adjugate \operatorname{adj}(\lambda I - A) is an n \times n matrix whose entries are polynomials in \lambda of degree at most n-1 with coefficients in R. By the fundamental property of the adjugate and determinant, the matrix equation (\lambda I - A) \operatorname{adj}(\lambda I - A) = p(\lambda) I holds in \operatorname{Mat}_n(R[\lambda]), where I is the n \times n identity matrix over R[\lambda].[8] To express this identity in terms of coefficients, write \operatorname{adj}(\lambda I - A) = \sum_{k=0}^{n-1} \lambda^k B_k, where each B_k \in \operatorname{Mat}_n(R). Each B_k is constructed from the entries of A via the cofactor expansion, making B_k a polynomial expression in A with scalar coefficients from R. Consequently, each B_k commutes with A, as both are elements in the commutative subring of \operatorname{Mat}_n(R) generated by A. Substituting into the left side of the identity yields (\lambda I - A) \sum_{k=0}^{n-1} \lambda^k B_k = \sum_{k=0}^{n-1} \lambda^{k+1} B_k - \sum_{k=0}^{n-1} \lambda^k A B_k = \sum_{k=0}^{n-1} \lambda^{k+1} B_k - \sum_{k=0}^{n-1} \lambda^k B_k A, and the commutativity A B_k = B_k A ensures the expansion aligns with the scalar multiple p(\lambda) I on the right side, confirming the coefficient-wise equality in R[\lambda].[8] Now evaluate the identity at \lambda = A via the natural ring homomorphism \phi: R[\lambda] \to \operatorname{Mat}_n(R) defined by \phi(\lambda) = A and fixing elements of R (extended componentwise to matrices). This homomorphism is well-defined because polynomials in \lambda map to polynomials in A, and matrix multiplication is preserved. Applying \phi to the left side gives \phi(\lambda I - A) \cdot \phi(\operatorname{adj}(\lambda I - A)) = (A I - A) \operatorname{adj}(A I - A) = 0 \cdot \operatorname{adj}(0) = 0, while the right side becomes p(A) I. Thus, p(A) I = 0, implying p(A) = 0 since I is invertible. The commutativity of the coefficients ensures the substitution is valid without non-commutativity issues.[8]Proof via endomorphisms
The Cayley–Hamilton theorem can be formulated intrinsically for linear endomorphisms on finite-dimensional vector spaces, without reference to a specific matrix representation. Let V be a finite-dimensional vector space over a field K, with \dim_K V = n < \infty, and let T: V \to V be a linear endomorphism. The characteristic polynomial of T is defined as p_T(\lambda) = \det(\lambda I_V - T) \in K[\lambda], where the determinant is computed with respect to any basis of V, as it is independent of the choice. The theorem asserts that p_T(T) = 0, meaning the endomorphism induced by evaluating the polynomial at T is the zero map on V.[23] One approach to proving this relies on the relationship between the minimal and characteristic polynomials. The minimal polynomial m_T(\lambda) of T is the monic polynomial of least degree such that m_T(T) = 0, and it divides any polynomial that annihilates T. To show that p_T(\lambda) annihilates T, note that the coefficients of p_T(\lambda) are determined by the traces of powers of T via Newton–Girard identities, which relate the elementary symmetric functions (coefficients of the characteristic polynomial) to the power sums \operatorname{tr}(T^k) for k = 1, \dots, n. Specifically, these identities imply that p_T(T) satisfies the same linear recurrence as the powers of T up to degree n-1, ensuring annihilation since the space of endomorphisms generated by powers of T has dimension at most n.[24] An alternative proof proceeds by considering the case where T is diagonalizable and then extending to the general case. If T is diagonalizable, there exists a basis of V consisting of eigenvectors with eigenvalues \lambda_1, \dots, \lambda_n \in K, so p_T(\lambda) = \prod_{i=1}^n (\lambda - \lambda_i). In this basis, T acts diagonally, and substituting into the polynomial yields zero on each eigenspace, hence p_T(T) = 0. For the general case, every endomorphism T is similar to its Jordan canonical form, consisting of Jordan blocks J_k(\lambda) where each block satisfies (J_k(\lambda) - \lambda I)^k = 0; since the characteristic polynomial of a block is (\lambda - \mu)^k for eigenvalue \mu, evaluation at the block gives zero, and thus p_T(T) = 0 overall.[25] A more abstract proof uses the exterior algebra to define the characteristic polynomial intrinsically. The top exterior power \bigwedge^n V is a one-dimensional K-vector space, and T induces an endomorphism \bigwedge^n T: \bigwedge^n V \to \bigwedge^n V whose scalar action is multiplication by p_T(1) or related determinants. Extending to the polynomial ring K[\lambda] \otimes_K V, the operator \lambda I - T acts, and the adjugate derived from multilinear properties satisfies \operatorname{adj}(\lambda I - T) \cdot (\lambda I - T) = p_T(\lambda) I; evaluating at \lambda = T in the appropriate quotient module yields annihilation.[26]Abstract algebraic proofs
In the abstract algebraic framework, the Cayley–Hamilton theorem extends to endomorphisms of finitely generated modules over a commutative ring R with identity. Let M be a finitely generated R-module and \varphi: M \to M an R-linear endomorphism. The theorem states that there exists a monic polynomial P \in R of degree at most the minimal number of generators of M such that P(\varphi) = 0, the zero endomorphism on M.[27] When M is free of rank n, say M = R^n, and \varphi is given by left multiplication by an n \times n matrix A with entries in R, this polynomial is precisely the characteristic polynomial \chi_A(x) = \det(xI_n - A).[28] The characteristic polynomial arises naturally from the theory of determinantal ideals or Fitting ideals in commutative algebra. Consider M as an R-module where x acts via \varphi. Choose a presentation R^n \to M \to 0, where the map is represented by the matrix xI_n - A. The determinantal ideals of this presentation matrix are the ideals generated by its minors; in particular, the ideal generated by the n \times n minor, which is \det(xI_n - A), is the principal ideal (\chi_A(x)) in R. More generally, the Fitting ideals of M as an R-module are defined from such presentations: for a presentation with r generators, the k-th Fitting ideal \mathrm{Fit}_k(M) is the ideal generated by all (r - k) \times (r - k) minors of the presentation matrix, independent of the choice of presentation.[29] In this setup, \mathrm{Fit}_0(M) is generated by \chi_A(x). A key property is that the zeroth Fitting ideal annihilates the module: \mathrm{Fit}_0(M) \subseteq \mathrm{Ann}_{R}(M), so every element of \mathrm{Fit}_0(M) acts as zero on M. Thus, \chi_A(x) annihilates M, implying \chi_A(\varphi) = 0 as an endomorphism, which is the Cayley–Hamilton theorem.[30] This formulation interprets the Cayley–Hamilton theorem as the statement that the subring R[\varphi] \subseteq \mathrm{End}_R(M) annihilates M via the characteristic polynomial. To establish the Fitting ideal annihilation over arbitrary commutative rings, one employs localization. Localize the ring R at a prime ideal \mathfrak{p} \in \mathrm{Spec}(R), yielding the local ring R_\mathfrak{p} and localized module M_\mathfrak{p}. Over R_\mathfrak{p}, the endomorphism \varphi extends, and M_\mathfrak{p} is free (or projective) of rank n if M is free. The theorem holds over the residue field k(\mathfrak{p}) = R_\mathfrak{p}/\mathfrak{p} R_\mathfrak{p} by the classical case for vector spaces. Since the characteristic polynomial is monic, its annihilation on M_\mathfrak{p} implies it annihilates M globally, as the result localizes faithfully and the monic condition ensures no denominator issues upon descent.[31] This localization argument reduces the general case to fields and globalizes via the properties of monic polynomials.[28] The theorem generalizes briefly to projective modules, where the characteristic polynomial is defined similarly via a locally free presentation, though the proof requires additional care with locally free sheaves or resolutions. Early abstract treatments, such as those building on Frobenius's work, laid groundwork for these module-theoretic views over rings.[27]Combinatorial proof
The combinatorial proof of the Cayley–Hamilton theorem utilizes the Leibniz formula for the determinant to expand the characteristic polynomial and interprets the substitution into the matrix via a weighted directed graph, demonstrating cancellation through a sign-reversing involution.[32] Consider an n \times n matrix A = (a_{ij}) over a commutative ring. The characteristic polynomial is p(\lambda) = \det(\lambda I - A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n \left( \lambda \delta_{i,\sigma(i)} - a_{i,\sigma(i)} \right), where S_n is the symmetric group on n elements, \operatorname{sgn}(\sigma) is the sign of the permutation \sigma, and \delta_{i,j} is the Kronecker delta.[32] Each product \prod_{i=1}^n \left( \lambda \delta_{i,\sigma(i)} - a_{i,\sigma(i)} \right) expands via the binomial theorem into a sum of $2^n terms, but many vanish: for any i with \sigma(i) \neq i, the factor \lambda \delta_{i,\sigma(i)} = 0, so the \lambda choice yields zero, leaving only the -a_{i,\sigma(i)} option; for fixed points i = \sigma(i), both choices are possible. Thus, the powers of \lambda arise from the number of fixed points where the \lambda term is selected, and the coefficients involve signed products over the non-fixed points, grouped by the number of such fixed points.[32] To evaluate p(A), interpret A as the weighted adjacency matrix of the complete directed graph G on vertex set = \{1, \dots, n\}, with edge weight a_{ij} from i to j (and loops a_{ii} at vertices). The expansion of p(\lambda) translates to a generating function where powers of \lambda correspond to isolated vertices (treated as trivial fixed points). Substituting A for \lambda yields an expression for the entries of p(A) as signed sums over combinatorial objects covering the graph: for the (i,j)-entry [p(A)]_{ij}, sum over all pairs (P, C) where P is a directed path from i to j (possibly trivial if i=j) using distinct edges, and C is a set of vertex-disjoint directed cycles covering the remaining vertices (using the remaining edges), such that P \cup C uses exactly n edges in total. The weight of such a pair is \operatorname{sgn}(P \cup C) \prod w(e), where w(e) is the weight of edge e, but equivalently \ (-1)^{|C|} \prod w(e) , since the sign from cycles dominates via parity. This arises from multilinearity in the Leibniz expansion, where paths encode matrix powers and cycles encode the signed contributions from permutation cycles.[32][33] The terms cancel completely via a weight-preserving, sign-reversing involution \iota on the set of such pairs (P, C). If P contains a directed cycle (a subpath that loops back to an earlier vertex), \iota detaches this cycle, adding it to C (increasing |C| by 1 and reversing the sign); if P has no cycles but some cycle in C shares an endpoint with P (or can be inserted), \iota merges it into P (decreasing |C| by 1 and reversing the sign). Pairs fixed by \iota—those with no detachable cycles in P and no mergeable cycles in C—must have P as a simple path and C consisting of cycles disjoint from P's endpoints in a way that prevents merging, but such configurations have zero weight because they require impossible edge usages or empty products over non-existent edges. Thus, all non-fixed terms pair into equal-weight opposites that sum to zero, so [p(A)]_{ij} = 0 for all i,j, proving p(A) = 0. The powers of \lambda in the original expansion ensure the covering uses exactly n edges, matching the degree-n polynomial structure.[32] For n=2, label vertices 1 and 2; consider [p(A)]_{11} without loss of generality (others follow similarly). The relevant pairs (P, C) with two edges total are:- Trivial path at 1 (P = \emptyset), C = \{(2 \to 2)\}: weight (-1)^1 a_{22} = -a_{22}.
- Loop path P = (1 \to 1), C = \emptyset: weight (+1) a_{11}.
- Path P = (1 \to 2 \to 1), C = \emptyset: weight (+1) a_{12} a_{21}.
- Trivial path at 1, C = \emptyset and an isolated 2, but this uses fewer than 2 edges, so invalid (zero contribution).