A combinatorial proof of the trace Cayley-Hamilton theorem

Basic Information

• Paper ID: 2511.06689
• Title: A combinatorial proof of the trace Cayley-Hamilton theorem
• Author: Sudip Bera (Dhirubhai Ambani University, Gandhinagar, India)
• Classification: math.CO (Combinatorics)
• Publication Date: November 10, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.06689
• MSC2020 Classification: 05C30; 05C50

Abstract

This paper exploits the deep connections between linear algebra and graph theory to provide combinatorial interpretations of classical matrix invariants. For an $n \times n$ matrix $A$ over a commutative ring $K$, one can associate a weighted directed graph $D(A)$, where the algebraic behavior of $A$ is reflected in the combinatorial properties of $D(A)$. In particular, the determinant and characteristic polynomial of $A$ can be elegantly expressed as signed weighted sums over linear subdigraphs of $D(A)$, thereby providing graphical interpretations of fundamental algebraic quantities. Based on this correspondence, the paper establishes a combinatorial proof of the trace Cayley-Hamilton theorem, which provides explicit identities connecting the coefficients of the characteristic polynomial with the traces of matrix powers.

Research Background and Motivation

Research Problem

This paper aims to provide a purely combinatorial proof of the trace Cayley-Hamilton theorem, which establishes identities relating the coefficients of the characteristic polynomial to the traces of matrix powers:

For the characteristic polynomial $p_A(\lambda) = \lambda^n + d_1\lambda^{n-1} + \cdots + d_n$, we have:

• When $r > n$: $\text{Tr}(A^r) + \text{Tr}(A^{r-1})d_1 + \cdots + \text{Tr}(A^{r-n})d_n = 0$
• When $1 \leq r \leq n$: $\text{Tr}(A^r) + \text{Tr}(A^{r-1})d_1 + \cdots + rd_r = 0$

Significance

1. Theoretical Significance: The trace Cayley-Hamilton theorem is an elegant corollary of the classical Cayley-Hamilton theorem, but for arbitrary $r$, it lacks a direct algebraic derivation
2. Combinatorial Perspective: Provides a new understanding through graph-theoretic methods, revealing deep connections between matrix algebra and combinatorial structures
3. Computational Significance: These identities have important applications in matrix computation and symbolic computation

Limitations of Existing Methods

• When $r \geq n$, the result can be obtained by multiplying both sides of the classical Cayley-Hamilton theorem ($p_A(A) = O$) by $A^{r-n}$ and taking the trace
• However, for arbitrary $r$ (particularly the case $r \leq n$), no direct algebraic derivation is known
• Lacks combinatorial interpretation and intuitive understanding

Research Motivation

This paper fills this theoretical gap by providing a unified, purely combinatorial proof method using the framework of weighted directed graphs, exploiting the combinatorial properties of linear subdigraphs and closed paths.

Core Contributions

1. Establishes the first purely combinatorial proof of the trace Cayley-Hamilton theorem, independent of algebraic derivations from the classical Cayley-Hamilton theorem
2. Proposes a key intermediate theorem (Theorem 2.2), establishing a combinatorial identity between the sum of closed path weights and the sum of linear subdigraph weights:
   • $c_r + c_{r-1}\ell_1 + c_{r-2}\ell_2 + \cdots + c_{r-n}\ell_n = 0$ (when $r > n$)
   • $c_r + c_{r-1}\ell_1 + c_{r-2}\ell_2 + \cdots + r\ell_r = 0$ (when $1 \leq r \leq n$)
3. Constructs a clever sign-reversing involution, using pairing to cancel out the proof of the combinatorial identity
4. Provides complete analysis of the $2 \times 2$ matrix case, with detailed computation of all linear subdigraphs and closed paths
5. Establishes clear correspondence between matrix algebraic concepts and graph-theoretic concepts:
   • Characteristic polynomial coefficients ↔ signed weighted sums of linear subdigraphs
   • Traces of matrix powers ↔ sums of closed path weights

Detailed Methodology

Problem Setup

Input: An $n \times n$ matrix $A = (a_{ij})$ over a commutative ring $K$

Objective: Prove that for all integers $r \geq 1$, the trace Cayley-Hamilton identity holds

Key Idea: Convert algebraic objects (matrices, traces, characteristic polynomials) into combinatorial objects (weighted directed graphs, closed paths, linear subdigraphs), and prove the identity at the combinatorial level

Core Concepts and Definitions

1. Weighted Directed Graph $D(A)$

For a matrix $A = (a_{ij}) \in K^{n \times n}$, construct a weighted directed graph $D(A)$:

• Vertex set: $[n] = \{1, 2, \ldots, n\}$
• Edges: For each ordered pair $(i,j)$, there is a directed edge from $i$ to $j$ with weight $a_{ij}$

2. Linear Subdigraph

• Definition: A collection $\gamma$ of vertex-disjoint directed cycles
• Weight $w(\gamma)$: The product of all edge weights in $\gamma$
• Cycle count $c(\gamma)$: The number of cycles in $\gamma$
• Length $L(\gamma)$: The total number of edges in $\gamma$

Define $L_r$ as the set of all linear subdigraphs of length $r$, and define: $\ell_r = \sum_{\gamma \in L_r} (-1)^{c(\gamma)} w(\gamma)$

Key Lemma (Lemma 1.1): The characteristic polynomial coefficient $d_i = \ell_i$

3. Closed Walk

• Definition: A path sequence $u = x_0, x_1, \ldots, x_k = u$ starting and ending at vertex $u$
• Weight $w(c)$: The product of all edge weights in the path
• Length $L(c)$: The number of edges in the path

Define $c_r$ as the total weight of all closed walks of length $r$.

Key Lemma (Lemma 1.4): $\text{Tr}(A^k) = c_k$

Proof Strategy

Core Theorem (Theorem 2.2)

We need to prove:

1. When $r > n$: $c_r + c_{r-1}\ell_1 + c_{r-2}\ell_2 + \cdots + c_{r-n}\ell_n = 0$
2. When $1 \leq r \leq n$: $c_r + c_{r-1}\ell_1 + c_{r-2}\ell_2 + \cdots + r\ell_r = 0$

Proof Technique: Sign-Reversing Involution

Step 1: Combinatorial Interpretation of Weighted Sums

Consider all ordered pairs $(c, \gamma)$ where:

• $c$ is a closed walk
• $\gamma$ is a linear subdigraph (possibly empty)
• $L(c) + L(\gamma) = r$

Define the weight: $W((c, \gamma)) = (-1)^{c(\gamma)} w(c) w(\gamma)$

Then the left side of the theorem = $\sum_{(c,\gamma)} W((c, \gamma))$

Step 2: Pairing and Cancellation (Case $r > n$)

When $r > n$, either $c$ and $\gamma$ share vertices, or $c$ is not a simple cycle. For each such pair $(c, \gamma)$, construct a sign-reversing involution:

Scenario 1: $c$ encounters vertex $y$ in $\gamma$

• Let $\gamma_y$ be the cycle in $\gamma$ containing $y$
• Construct new pair: $(\tilde{c}, \tilde{\gamma})$, where $\tilde{c}$ incorporates $\gamma_y$ into the closed walk, $\tilde{\gamma} = \gamma \setminus \{\gamma_y\}$
• Key Property: $W((\tilde{c}, \tilde{\gamma})) = -W((c, \gamma))$

Scenario 2: $c$ completes a simple cycle $\acute{c}$ without encountering $\gamma$

• Construct new pair: $(\tilde{\tilde{c}}, \tilde{\tilde{\gamma}})$, where $\tilde{\tilde{c}}$ removes $\acute{c}$ from $c$, $\tilde{\tilde{\gamma}} = \gamma \cup \{\acute{c}\}$
• Key Property: $W((\tilde{\tilde{c}}, \tilde{\tilde{\gamma}})) = -W((c, \gamma))$

This involution is sign-reversing, so the contributions of all "bad" pairs cancel out.

Step 3: GOOD Pairs and Extra Terms (Case $r \leq n$)

Define the sets:

• BAD pairs $B$: $c \cap \gamma \neq \emptyset$ or $c$ is not a simple cycle
• GOOD pairs $A \setminus B$: $c \cap \gamma = \emptyset$ and $c$ is a simple cycle

BAD pairs cancel via the same involution. For GOOD pairs:

Key Observation: Each GOOD pair $(c, \gamma)$ corresponds to a decomposition of a linear subdigraph $\dot{\gamma} = c \cup \gamma$ on $r$ vertices.

For each linear subdigraph $\dot{\gamma}$ on $r$ vertices, there are exactly $r$ GOOD pairs:

• For each vertex $v_i \in \{v_1, \ldots, v_r\}$
• Let $c_{v_i}$ be the cycle in $\dot{\gamma}$ containing $v_i$
• Construct pair $(c_{v_i}, \gamma_i)$, where $\gamma_i = \dot{\gamma} \setminus \{c_{v_i}\}$

The total contribution of these $r$ GOOD pairs is: $\sum_{i=1}^r W((c_{v_i}, \gamma_i)) = r \cdot (-1)^{c(\dot{\gamma})-1} w(\dot{\gamma})$

The contribution of the $r\ell_r$ term is: $r \cdot (-1)^{c(\dot{\gamma})} w(\dot{\gamma})$

Adding these: $r(-1)^{c(\dot{\gamma})}[(-1)^{-1} + 1]w(\dot{\gamma}) = 0$

Therefore the total sum is 0, completing the proof.

Technical Innovations

1. Elegance of Involution Construction: The two different pairing strategies (incorporating cycles vs. extracting cycles) achieve complete sign reversal
2. Cleverness of GOOD Pair Counting: Exploiting the symmetry that $r$ vertices correspond to $r$ decomposition methods, precisely canceling the extra $r\ell_r$ term
3. Unified Framework: Using a single combinatorial framework to handle both cases ($r \leq n$ and $r > n$)
4. Geometric Intuition: Through graphical displays (Figures 8-9), abstract involution processes become visually intuitive

Experimental Setup

Case Study: Complete Analysis of $2 \times 2$ Matrices

The paper demonstrates the method's effectiveness through a complete $n=2$ case.

Matrix and Graph

$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$

The corresponding weighted directed graph $D(A)$ has 2 vertices $v_1, v_2$ with edge weights:

• Self-loop at $v_1$: weight $a$
• Self-loop at $v_2$: weight $d$
• $v_1 \to v_2$: weight $b$
• $v_2 \to v_1$: weight $c$

Linear Subdigraph Computation

Linear subdigraphs of length 1 (single self-loops):

• Self-loop at $v_1$: weight $a$, sign $(-1)^1 = -1$
• Self-loop at $v_2$: weight $d$, sign $(-1)^1 = -1$
• Therefore: $\ell_1 = -(a+d)$

Linear subdigraphs of length 2:

• Two self-loops: weight $ad$, sign $(-1)^2 = +1$
• One 2-cycle $(v_1 \to v_2 \to v_1)$: weight $bc$, sign $(-1)^1 = -1$
• Therefore: $\ell_2 = ad - bc$

Closed Path Computation

Closed paths of length 1:

• Self-loop at $v_1$: weight $a$
• Self-loop at $v_2$: weight $d$
• Therefore: $c_1 = a + d = \text{tr}(A)$

Closed paths of length 2:

• Self-loop at $v_1$ twice: weight $a^2$
• Self-loop at $v_2$ twice: weight $d^2$
• $v_1 \to v_2 \to v_1$: weight $bc$
• $v_2 \to v_1 \to v_2$: weight $cb$
• Therefore: $c_2 = a^2 + d^2 + 2bc = \text{tr}(A^2)$

Closed paths of length 3 (8 total):

• Self-loops three times: $a^3, d^3$
• Self-loop plus 2-cycle combinations: $3abc + 3dbc$
• Therefore: $c_3 = a^3 + d^3 + 3bc(a+d)$

Identity Verification

Case $r=1$: $c_1 + \ell_1 = (a+d) + (-(a+d)) = 0 \checkmark$

Case $r=2$: $c_2 + c_1\ell_1 + 2\ell_2 = (a^2 + d^2 + 2bc) + (a+d)(-(a+d)) + 2(ad-bc) = 0 \checkmark$

Case $r=3 > n=2$: $c_3 + c_2\ell_1 + c_1\ell_2 = [a^3 + d^3 + 3bc(a+d)] + [a^2+d^2+2bc][-(a+d)] + [a+d][ad-bc] = 0 \checkmark$

Detailed verification of the expansion process is provided in Example 2.1.

Experimental Results

Main Results

The paper's main result is a purely combinatorial proof of Theorem 2.1 (the trace Cayley-Hamilton theorem), completed through the following logical chain:

1. Lemma 1.1: Establishes $d_i = \ell_i$ (characteristic polynomial coefficients = linear subdigraph weight sums)
2. Lemma 1.4: Establishes $\text{Tr}(A^k) = c_k$ (traces of matrix powers = closed path weight sums)
3. Theorem 2.2: Proves the combinatorial identity (relationship between closed paths and linear subdigraphs)
4. Theorem 2.1: Follows directly from the above three results

Successful Case Analysis Verification

Through complete case analysis of $2 \times 2$ matrices:

• All 8 closed paths of length 3 are completely enumerated and computed
• All linear subdigraphs (lengths 1 and 2) are completely analyzed
• All three identities ($r=1, 2, 3$) are successfully verified
• Demonstrates the operability and correctness of the method

Effectiveness of Graphical Presentation

The paper clearly presents through 9 figures (Figures 1-9):

• Construction of weighted directed graphs (Figure 1)
• Enumeration of linear subdigraphs (Figures 2-3)
• Classification of closed paths (Figures 4-7)
• Visualization of involution process (Figure 8)
• Counting of GOOD pairs (Figure 9)

These figures make abstract combinatorial arguments intuitively understandable.

Importance of Theoretical Contributions

1. Fills Theoretical Gap: Provides the first direct proof of the trace Cayley-Hamilton theorem for the case $r \leq n$
2. Methodological Innovation: Novel application of sign-reversing involution technique in matrix theory
3. Unification: Single framework handling all cases ($r \leq n$ and $r > n$)

Related Work

Combinatorial Matrix Theory

This paper builds on the foundation of Brualdi and Cvetkovic's monograph 1, which systematically presents combinatorial methods in matrix theory, including:

• Correspondence between weighted directed graphs and matrices
• Combinatorial interpretation of determinants (Equation 3)
• Relationship between matrix powers and paths (Lemma 1.3)

Combinatorial Proofs of Classical Theorems

Related combinatorial proof work includes:

1. Straubing (1983) 4: Combinatorial proof of the Cayley-Hamilton theorem
2. Zeilberger (1984, 1985) 5, 6:
   • Combinatorial proof of Newton's identities
   • Combinatorial methods in matrix algebra
3. Mukherjee & Bera (2019) 3: Combinatorial proofs of Newton-Girard and Chapman-Costas-Santos identities

Trace Cayley-Hamilton Theorem

This paper directly responds to a question posed by Grinberg (2019) 2, which noted:

• The trace Cayley-Hamilton theorem can be derived from the classical theorem when $r \geq n$
• However, for arbitrary $r$ (particularly $r \leq n$), direct algebraic or combinatorial proofs are lacking

Unique Contributions of This Paper

Compared to related work, this paper:

1. Provides the first purely combinatorial proof: Independent of the classical Cayley-Hamilton theorem
2. Handles complete cases: Unified proof for both $r \leq n$ and $r > n$
3. Technical Innovation: Introduces new sign-reversing involution construction
4. Enhanced Visualization: Detailed graphical presentation improves comprehensibility

Conclusions and Discussion

Main Conclusions

1. Establishes the first purely combinatorial proof of the trace Cayley-Hamilton theorem, proving that the trace identity holds for all $r \geq 1$
2. Reveals deep algebraic-combinatorial correspondence:
   • Algebraic properties of matrices ↔ combinatorial properties of directed graphs
   • Characteristic polynomial coefficients ↔ linear subdigraphs
   • Traces of matrix powers ↔ closed paths
3. Provides new proof techniques: Systematic application of sign-reversing involutions in matrix identity proofs

Limitations

1. Theoretical Nature: This paper is a pure mathematical proof, not addressing computational efficiency or numerical stability
2. Scope of Applicability:
   • Method applies to matrices over commutative rings
   • Non-commutative cases and other algebraic structures not discussed
3. Complexity:
   • For large matrices, the number of linear subdigraphs and closed paths grows exponentially
   • No computational optimization strategies provided
4. Generalizability:
   • Whether the method can be generalized to other matrix identities remains unexplored
   • Relationship with other combinatorial proof techniques not deeply discussed
5. Limited Case Coverage: Only complete $n=2$ case provided; larger-scale examples might be more convincing

Future Directions

While not explicitly proposed in the paper, possible research directions include:

1. Generalization to Other Identities: Apply the method to combinatorial proofs of other matrix identities
2. Computational Algorithms: Develop efficient graph-theoretic algorithms for computing characteristic polynomials and matrix functions
3. Non-commutative Cases: Explore generalization of the method to non-commutative rings or quantum groups
4. Higher-Order Identities: Study identities involving higher-order traces
5. Random Matrix Theory: Apply combinatorial methods to expected trace computations in random matrices

In-Depth Evaluation

Strengths

1. Mathematical Rigor

• Complete Proof: Clear logical chain from basic definitions to final theorem
• Sufficient Detail: Key steps (such as involution construction) are thoroughly explained
• No Circular Reasoning: Does not depend on the theorem being proved

2. Methodological Innovation

• Clever Application of Sign-Reversing Involution: Elegant design of two pairing strategies (incorporating/extracting cycles)
• GOOD Pair Counting: Precise cancellation of extra terms using symmetry ($r$ vertices correspond to $r$ decompositions)
• Unified Framework: Single technique handles different cases ($r \leq n$ vs $r > n$)

3. Comprehensibility

• Graphical Presentation: 9 carefully designed figures make abstract concepts concrete
• Complete Case: Thorough analysis of $2 \times 2$ matrices demonstrates method operability
• Clear Structure: Progression from simple to complex, specific to general, well-organized

4. Theoretical Contribution

• Fills Gap: Solves the open problem posed by Grinberg (2019)
• Deepens Understanding: Reveals new connections between matrix algebra and graph theory
• Methodological Value: Provides a paradigm for combinatorial proofs of other matrix identities

5. Writing Quality

• Clear Expression: Precise definitions, consistent notation
• Logical Organization: Complete structure from introduction through case study to proof and conclusion
• Adequate References: Appropriate citations of related work

Weaknesses

1. Case Coverage

• Only $n=2$ Complete Case: Examples with $n=3$ or larger would be more convincing
• Lack of Concrete Involution Examples: While Figure 8 provides schematic diagrams, specific numerical examples are missing

2. Intuitive Explanation

• Combinatorial Meaning of Involution: Why this particular involution works lacks deeper intuitive explanation
• Geometric or Topological Perspective: Whether deeper geometric or topological interpretations exist is unexplored

3. Computational Complexity

• No Complexity Analysis: Exponential complexity of enumerating all linear subdigraphs and closed paths not analyzed
• No Algorithm Implementation: Lacks algorithmic description or pseudocode for practical computation

4. Generalization Discussion

• Method Limitations: Which types of matrix identities can be proved using similar methods?
• Necessary Conditions: Under what conditions can sign-reversing involutions be successfully constructed?
• Comparison with Other Techniques: Relationship with generating functions and other methods not discussed

5. Practical Value

• Computational Applications: Advantages or disadvantages of combinatorial methods in practical matrix computation not discussed
• Numerical Stability: From a computational perspective, does this method have practical applications?

Impact Assessment

Contribution to the Field

1. Combinatorial Matrix Theory: Adds important new results and techniques to the field
2. Symbolic Computation: May inspire new symbolic matrix computation algorithms
3. Educational Value: Provides new perspective for teaching matrix theory

Potential Impact

• Short-term: Will attract interest from combinatorists and matrix theorists
• Medium-term: May inspire combinatorial proof research for other matrix identities
• Long-term: Likely to become standard content in combinatorial matrix theory textbooks

Practical Value

• Theory-Focused: Primarily theoretical contribution, limited practical computational applications
• High Educational Value: Excellent for teaching, demonstrating connections between algebra and combinatorics
• Strong Inspirational Value: Provides methodological reference for related problems

Reproducibility

• Fully Reproducible: Clear logical proof, explicit steps
• Highly Verifiable: $2 \times 2$ case can be verified by hand
• Extensible: Method applicable to arbitrary matrix sizes (though computational cost increases)

Applicable Scenarios

Theoretical Research

1. Combinatorial Matrix Theory: Study combinatorial interpretations of matrix invariants
2. Algebraic Combinatorics: Explore correspondences between algebraic and combinatorial structures
3. Graph Theory: Study properties of weighted directed graphs

Teaching Applications

1. Advanced Linear Algebra Courses: Present combinatorial perspective on matrix theory
2. Combinatorics Courses: Use as case study of graph theory applications
3. Graduate Seminars: Learn combinatorial proof techniques through this example

Potential Extensions

1. Symbolic Computation Software: Develop graph-theoretic matrix computation modules
2. Other Identities: Apply similar methods to prove related theorems
3. Generalization Research: Explore method applications in broader algebraic structures

Overall Assessment

This is a high-quality pure mathematics paper with main strengths:

• ✅ Solves a clearly defined open problem
• ✅ Innovative and rigorous method
• ✅ Complete and comprehensible proof
• ✅ Clear writing with excellent figures

Main weaknesses:

• ⚠️ Limited case coverage (only $n=2$)
• ⚠️ Lacks deeper intuitive explanation
• ⚠️ Insufficient discussion of practical value
• ⚠️ Generalizability not fully explored

Recommendation Index: ⭐⭐⭐⭐ (4/5)

Recommended for researchers and students interested in combinatorial matrix theory and algebraic combinatorics. For pure mathematicians, this is an elegant theoretical contribution; for applied researchers, it offers primarily inspirational value.

References

Key references cited in this paper:

1. Brualdi & Cvetkovic (2009): A combinatorial approach to matrix theory and its application - Authoritative monograph on combinatorial matrix theory
2. Grinberg (2019): The trace Cayley-Hamilton theorem - Posed the problem addressed in this paper
3. Mukherjee & Bera (2019): Combinatorial proofs of the Newton–Girard and Chapman–Costas-Santos identities - Related prior work by the author
4. Straubing (1983): A combinatorial proof of the Cayley-Hamilton theorem - Combinatorial proof of classical Cayley-Hamilton theorem
5. Zeilberger (1984, 1985): Series on combinatorial methods in matrix algebra - Pioneering combinatorial proof techniques

Reading Recommendations:

• Suitable for graduate-level mathematics students and above
• Requires background in linear algebra and graph theory
• Recommended to carefully study the $n=2$ case first (Example 2.1)
• Focus on understanding the sign-reversing involution construction (proof of Theorem 2.2)
• Consider verifying the $n=3$ case independently to deepen understanding