A combinatorial proof of the trace Cayley-Hamilton theorem
Sudip Bera · 2025
Read A combinatorial proof of the trace Cayley-Hamilton theorem by Sudip Bera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06689.txt.
Introduction
Sudip Bera proves the trace Cayley-Hamilton theorem by counting walks on a graph built from a matrix. Every square matrix over a commutative ring defines a weighted directed graph whose structure mirrors the algebra. Determinants and characteristic polynomials already admit elegant readings as signed sums over the graph's cycle covers.
Building on that link, Bera's combinatorial argument produces explicit trace identities. The coefficients of the characteristic polynomial connect directly to traces of the matrix's successive powers. The proof shows how a cornerstone identity of linear algebra, usually reached through algebraic manipulation, can instead be read off the combinatorics of an associated graph.
Catalog record
| CREATOR | Sudip Bera |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06689
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A combinatorial proof of the trace Cayley-Hamilton theorem Sudip Bera Abstract . The deep interconnection between linear algebra and graph theory allows one to interpret classical matrix invariants through combinatorial structures. To each n × n n\times n matrix A A over a commutative ring 𝕂 \mathbb{K} , one can associate a weighted directed graph 𝒟 ( A ) \mathcal{D}(A) , where the algebraic behavior of A A is reflected in the combinatorial properties of 𝒟 ( A ) \mathcal{D}(A) . In particular, the determinant and characteristic polynomial of A A admit elegant formulations in terms of sign-weighted sums over linear subdigraphs of 𝒟 ( A ) \mathcal{D}(A) , thereby providing a graphical interpretation of fundamental algebraic quantities. Building upon this correspondence, we establish a combinatorial proof of the Trace Cayley–Hamilton theorem . This theorem furnishes explicit trace identities linking the coefficients of the characteristic polynomial of A A with the traces of its successive powers. Precisely, if p A ( λ ) = λ n + d 1 λ n − 1 + ⋯ + d n p_{A}(\lambda)=\lambda^{n}+d_{1}\lambda^{n-1}+\cdots+d_{n} is the characteristic polynomial of A A , then for every integer r ≥ 1 r\geq 1 , the traces of powers of A A satisfy Tr ( A r ) + Tr ( A r − 1 ) d 1 + ⋯ + Tr ( A r − ( n − 1 ) ) d n − 1 + { Tr ( A r − n ) d n = 0 , r > n , r d r = 0 , 1 ≤ r ≤ n . \text{Tr}(A^{r})+\text{Tr}(A^{r-1})d_{1}+\cdots+\text{Tr}(A^{r-(n-1)})d_{n-1}+\begin{cases}\text{Tr}(A^{r-n})d_{n}=0,&r>n,\\[4.0pt] rd_{r}=0,&1\leq r\leq n.\end{cases} Keywords: Combinatorial proof; Digraphs; Trace Cayley-Hamilton theorem MSC2020: 05C30; 05C50 1. Introduction Let \mathbb{K} be a commutative ring, and let A\in\mathbb{K}^{n\times n} be a square matrix of order n . The characteristic polynomial of A is defined by (1) p_{A}(\lambda)=\lambda^{n}+d_{1}\lambda^{n-1}+d_{2}\lambda^{n-2}+\cdots+d_{n-k}\lambda^{k}+\cdots+d_{n}. The classical Cayley-Hamilton theorem states that p_{A}(A)=A^{n}+d_{1}A^{n-1}+d_{2}A^{n-2}+\cdots+d_{n-k}A^{k}+\cdots+d_{n}I_{n}=O, where O denotes the zero matrix. Various combinatorial proofs of such fundamental results are well known in the literature [ 3 , 4 , 5 , 6 ] . A less conventional but equally elegant corollary, referred to as the Trace Cayley-Hamilton theorem , asserts that (2) \operatorname{Tr}(A^{r})+\operatorname{Tr}(A^{r-1})d_{1}+\cdots+\operatorname{Tr}(A^{r-(n-1)})d_{n-1}+\begin{cases}\operatorname{Tr}(A^{r-n})d_{n}=0,&r>n,\\[4.0pt] r\,d_{r}=0,&1\leq r\leq n.\end{cases} When r\geq n , this identity follows immediately from the Cayley–Hamilton theorem by multiplying both sides of p_{A}(A)=O by A^{r-n} and then taking traces. However, for arbitrary r , no direct algebraic derivation is known. In this paper, we present a combinatorial proof of the Trace Cayley–Hamilton theorem using the framework of weighted directed graphs . To every matrix A=(a_{ij})\in\mathbb{K}^{n\times n} , we associate a weighted directed graph \mathcal{D}(A) with vertex set [n]=\{1,2,\ldots,n\} . For each ordered pair (i,j) , there is a directed edge from i to j with weight a_{ij} . We briefly recall a few relevant graph-theoretic notions; see [ 1 ] for further details. A linear subdigraph \gamma of \mathcal{D}(A) is a collection of vertex-disjoint directed cycles. A loop, i.e., a cycle of length one, is regarded as a cycle centered at a single vertex. The weight of \gamma , denoted w(\gamma) , is the product of the weights of all edges belonging to \gamma . The number of cycles in \gamma is denoted by c(\gamma) . For illustration, all linear subdigraphs of the digraph in Figure 1 are displayed in Figures 2 and 3 . The cycle decomposition of permutations yields the following elegant expression for the determinant of A : (3) \det(A)=\sum_{\gamma}(-1)^{n-c(\gamma)}\,w(\gamma), where the sum runs over all linear subdigraphs \gamma of \mathcal{D}(A) that involve all n vertices. The length of a linear subdigraph \gamma , denoted L(\gamma) , is the total number of edges in \gamma . Let L_{r} denote the set of all linear subdigraphs of \mathcal{D}(A) having length r . We then define (4) \ell_{r}\triangleq\sum_{\gamma\in L_{r}}(-1)^{c(\gamma)}\,w(\gamma). Alternatively, the characteristic polynomial of A can also be expressed in terms of the sums of its principal minors as (5) p_{A}(\lambda)=\lambda^{n}-f_{1}\lambda^{n-1}+f_{2}\lambda^{n-2}-\cdots+(-1)^{n-k}f_{n-k}\lambda^{k}+\cdots+(-1)^{n}f_{n}, where f_{i} denotes the sum of all principal minors of order i of A . Comparing Equations ( 1 ) and ( 5 ), we obtain d_{i}=(-1)^{i}f_{i},\qquad\text{for each }i\in[n]. Since f_{i} is the sum of all principal minors of order i , it can equivalently be expressed as a weighted sum over linear subdigraphs of \mathcal{D}(A) : (6) f_{i}=\sum_{\gamma}(-1)^{i-c(\gamma)}\,w(\gamma), where the summation extends over all linear subdigraphs \gamma of \mathcal{D}(A) containing i vertices. Lemma 1.1 . Let p_{A}(\lambda) be the characteristic polynomial of A as in ( 1 ), and let \ell_{i} be defined by ( 4 ). Then, for each i\in[n] , we have d_{i}=\ell_{i}. Proof. We compute: \displaystyle d_{i} \displaystyle=(-1)^{i}f_{i} \displaystyle=(-1)^{i}\sum_{\gamma}(-1)^{i-c(\gamma)}w(\gamma) (by Equation ( 6 )) \displaystyle=\sum_{\gamma}(-1)^{c(\gamma)}w(\gamma) \displaystyle=\ell_{i}, (by Equation ( 4 )). ∎ Remark 1.2 . The preceding discussion provides a clear combinatorial interpretation of the coefficients of the characteristic polynomial of A : each coefficient is a sign-weighted sum of the weights of all linear subdigraphs of the associated digraph \mathcal{D}(A) . A walk c in the directed graph \mathcal{D}(A) from a vertex u to a vertex v is defined as a sequence of vertices u=x_{0},x_{1},\cdots,x_{k-1},x_{k}=v , where each pair (x_{i},x_{i+1}) represents an edge for i=0,1,2,\cdots,k-1 . This walk is termed closed if u is equal to v . The length L(c) of the walk c corresponds to the total number of edges included in it. The weight w(c) of the walk is calculated as the product of the weights of all edges that are part of the walk. It is important to note that in the case of a closed walk, the starting and ending points are inherently defined. We will denote the total weight of all closed walks of length r as c_{r} . For example, some closed walks derived from the graph D(A) in Figure 1 are described in Figures 4 , 5 , 6 , and 7 . Lemma 1.3 . [Theorem 3.1.2, [ 1 ] ] Let A=[a_{ij}] be a matrix of order n. For each positive integer k, the entry a_{ij}^{(k)} of A^{k} in the i th row and j th column equals the sum of the weights of all walks in \mathcal{D}(A) of length k from vertex i to vertex j. Lemma 1.4 . For any k\in\mathbb{N}, the trace of the matrix A^{k} is \text{Tr}(A^{k})=c_{k}. Proof. By Lemma 1.3 , the entry a_{ii}^{(k)} of A^{k} in the i th row and i th column equals the sum of the weights of all closed walks in \mathcal{D}(A) of length k from the vertex i to itself. Therefore, \text{Tr}(A^{k}) is the sum of the weights of all closed walks of length k. That is, \text{Tr}(A^{k})=c_{k}. ∎ Remark 1.5 . According to Lemma 1.4 , a combinatorial interpretation of trace of a matrix is the sum of the weights of closed walks. 2. Trace Cayley-Hamilton theorem In this section, we will articulate and demonstrate the trace Cayley-Hamilton theorem. The theorem, as referenced in [ 2 ] Theorem 2.1 (Trace Cayley-Hamilton theorem) . Let A be a n\times n matrix over the commutative ring \mathbb{K}. Let p_{A}(\lambda) be the characteristic polynomial of A defined as in Equation ( 1 ). Then the trace