A matrix identity by cycle exchange

A walk that revisits a vertex contains a cycle we can cut out. Could that cut explain a matrix identity? The difficulty is to remember what was removed, assign the right sign, and make the cut reversible. We build the correction terms to solve that matching problem, then recognise the characteristic polynomial in the result.

1. Find what a walk needs beside it

Let A = (a_ij) be an n × n matrix, with n ≥ 1 and entries in a commutative ring with identity. Ordinary real or complex entries are examples. Draw vertices 1, …, n, with an arrow i → j of weight a_ij. Include loops. Following two arrows multiplies their weights; adding all possible intermediate vertices is exactly matrix multiplication. Thus (A^m)_ij is the sum of the weights of all length-m walks from i to j. A walk may repeat vertices. A length-zero walk stays at its starting vertex and has weight 1.

We want a relation between powers of A, with scalar coefficients that work for every matrix entry. In this picture, that means cancelling long walks against corrections to shorter walks. There is a reason to try length n: such a walk visits n + 1 vertices, counting repetitions, so some vertex repeats. The segment between two visits is closed. Cutting it out leaves the same start and finish.

But simply discarding the segment loses its weight. A possible correction must remember the closed segment as well as the shorter walk. This gives a first candidate for our working object: a walk together with a cycle set aside. Its partner has exactly the same edges, so the weights can cancel if the two objects have opposite signs.

Use a small matrix to determine the first signs

Before specifying the general rule, look for a scalar correction to the two-vertex case:

A = [ a  b ]       A² = [ a² + bc   ab + bd ]
    [ c  d ]            [ ca + dc   cb + d² ]

Both off-diagonal entries contain the factor a + d, so subtracting (a + d)A cancels them. Each diagonal entry then becomes bc − ad. The remaining correction is (ad − bc)I:

The coefficient −(a + d) selects one loop with a minus sign. In the constant term, ad selects two separate loops with a plus sign, while −bc selects one two-vertex cycle with a minus sign. Count cycles, rather than edges, to fit both cases. That also matches the proposed exchange: moving one cycle out of a walk must reverse the sign once, whatever its length.

Repair the first candidate

One reserved cycle is not enough. On three vertices, consider the walk 1 → 1 → 3 with the loop at 2 already set aside. Its earliest repeated vertex is 1. Cutting out that loop leaves the walk 1 → 3 with two reserved loops. A class of objects allowing only one reserve would not contain the partner we need.

So allow a collection C of reserved cycles. Try requiring them to be simple and vertex-disjoint: then at a vertex there is at most one reserved cycle to insert. Allow the walk to meet them—such a meeting is precisely where an insertion can occur. We still have to prove that a cut never violates disjointness; this will determine the scanning rule in stage 3.

The resulting candidate is a pair (P, C), where P is a walk and C is a collection of vertex-disjoint directed simple cycles. Count a loop as a one-edge cycle, and do not distinguish rotations of the same directed cycle. Give the pair weight

Keep the total number of edges in the walk and reserve fixed. This is the degree preserved by cutting and inserting. With an empty reserve the sign is positive; each transfer of a cycle reverses it. These choices give us a testable candidate, not yet a proof: we need both a well-defined inverse and cancellation of every term at degree n.

2. Identify the coefficients

A scalar coefficient multiplying a power of A must be independent of the chosen walk and its endpoints. Sum the weights of all reserves of a given size, and pair each reserve with every walk of the complementary length. This explains why the two parts may share vertices: excluding those pairs would make the coefficient depend on the walk.

For a reserve C, let |C| be its number of edges, and let c(C) be its number of cycles. Define

These are precisely the coefficients of the characteristic polynomial:

Here is the identification, directly from the permutation definition of the determinant. Expand each diagonal factor t − a_ii. Let S be the vertices where an entry from −A was chosen. Every vertex outside S contributes t, so the permutation fixes it. On S, the permutation decomposes into disjoint cycles. If |S| = k and there are r cycles, its permutation sign is (−1)^k−r. The k chosen minus signs multiply this by (−1)^k, leaving (−1)^r. This is exactly the reserve rule.

In particular, q₁ = −∑_ia_ii. For three vertices,

q₁ = −(a₁₁ + a₂₂ + a₃₃)
q₂ = a₁₁a₂₂ + a₁₁a₃₃ + a₂₂a₃₃
     − a₁₂a₂₁ − a₁₃a₃₁ − a₂₃a₃₂.

Two separate loops contribute positively. One two-vertex cycle contributes negatively. The coefficient enumerates the corrections our walk can exchange.

3. Exchange the first obstruction

Choosing an arbitrary repeated segment can fail: its interior may meet a reserved cycle, so cutting it would create overlapping reserves. Inserting an arbitrary reserved cycle can fail too if we try to undo it by cutting the first repeated segment: an earlier repetition in the walk would make that cut happen somewhere else. Both failures ask us to use the same ordering for cuts and insertions.

Scan from the start. Keep going only while the vertices seen so far are distinct and outside the reserve. This prefix is exactly the part we know is safe to leave alone. At its first obstruction, either the walk meets a reserved cycle or it returns to a vertex already in the prefix. There is now a specific cycle to exchange.

More precisely, include the starting vertex in the scan and stop at the first of these events:

1. The current vertex belongs to a reserved cycle. Remove that cycle from C and insert one traversal of it into P, starting and ending at the current vertex.
2. The current vertex has already occurred in the walk. The segment since its previous occurrence is a directed cycle. Cut that segment out of P and put it into C.

Before the first event, the scanned vertices are all distinct and avoid the reserve. Consequently, the cycle removed from the walk is simple and disjoint from every reserved cycle. Conversely, a cycle inserted from the reserve contains none of the earlier scanned vertices. The first event in the new pair is therefore its return to the insertion vertex, and the reverse operation cuts out exactly what was inserted.

If we cut a cycle out at an earlier vertex, that vertex becomes the first contact with the enlarged reserve, so the reverse operation inserts exactly the same cycle. Neither operation changes the start or finish of the walk. Both keep the edge multiset, including repeated edges, and change the number of reserved cycles by one. Apply the rule twice and the original pair returns, with opposite weights in between.

The two events cannot tie at the first obstruction. If the repeated vertex were in the reserve, its earlier occurrence would already have stopped the scan. The first-event requirement is what makes the exchange an involution; choosing an arbitrary cycle would not provide this inverse.

Parentheses list directed cycles; a bare vertex denotes a length-zero walk. The last row shows why scanning begins at the starting vertex. Its right-hand pair has no walk edge, but vertex 1 already belongs to a reserved loop, which can be inserted.

For three vertices, the diagonal term 1 → 2 → 3 → 1 with an empty reserve pairs with the length-zero walk at 1 and the reserved cycle (1 2 3). Their weights are +a₁₂a₂₃a₃₁ and −the same product. Among the terms contributing to (A³ + q₁A² + q₂A + q₃I)₁₃, we also have:

The last two rows have the same monomial but different records. Keeping the walk and reserve separate explains the multiplicities that collecting like terms would conceal.

4. See why the number of vertices is the bound

Fix a start i and finish j. Consider all pairs with exactly n edges in total. If the reserve has k edges, its signed weight sum is q_k, while the walk has n − k edges. Adding their weights therefore gives exactly the (i,j) entry of

The exchange must be possible for every pair. Otherwise the walk would have distinct vertices, all outside the reserve. Write its length as ℓ. It would occupy ℓ + 1 vertices, and the reserve would occupy another k. That would require ℓ + k + 1 = n + 1 distinct vertices in an n-vertex graph.

Every term consequently has a different partner with the same edge product and opposite sign. Their total is zero, entry by entry. Since the coefficients were identified in the previous stage, this proves det(tI − A) evaluated as a scalar-coefficient polynomial at A is zero: the Cayley–Hamilton theorem.

The proof works over every commutative ring with identity. It uses finite sums, products, and additive inverses. Entries need not be invertible, and zero divisors cause no problem. Commutativity is used when a cycle moves within an edge product. In characteristic two, the paired weights still sum to zero: a quantity and its additive inverse cancel even when they are equal.

5. Read more than the vanishing

The exchange works with any total number m of edges. Its only survivors are pairs whose walk has distinct vertices and avoids all reserved cycles. Such a pair uses m + 1 distinct vertices, so it can survive only when m ≤ n − 1. This gives the same recurrence for every later length:

There is also a finite description of what remains at shorter lengths. Attach a marker z to each edge, and let B_ij(z) be the signed sum of the surviving pairs from i to j. The same cancellation, coefficient by coefficient, proves

This is an identity of formal power series: each coefficient comes from a finite set of pairs, so no analytic convergence is involved. The numerator is the signed sum of simple walks with disjoint reserved cycles. One local exchange explains the polynomial identity, its degree bound, and the recurrence for all later walk sums.

A useful route to this construction is to ask what a cut loses, enlarge the object to retain it, and then restrict the move until it can undo itself. The small example suggested the signs; closure under the move required a collection of cycles; the unchanged prefix supplied the inverse. Identifying the resulting coefficients was a separate step. This suggests a question to try on other expansions: what would an elementary move need to remember so that it could be undone?

Howard Straubing published A combinatorial proof of the Cayley–Hamilton theorem in 1983. Doron Zeilberger presents the walk–cycle exchange in §3, pp. 66–67, of A Combinatorial Approach to Matrix Algebra (1985), explicitly crediting Straubing. The route above reconstructs reasons for the choices in that proof; it is not an account of the authors’ historical discovery process.

Continue with a determinant that counts trees, where incidence minors select precisely the spanning trees, or a quantity that moves on its own, where the correction is a weighted difference instead of a reserve of cycles.