trace_pow_eq_walk
Provedcombinatoricslinear-algebramatrixtrace
For a square matrix over a commutative ring and any , the trace of equals the sum over all closed walks of length of the product of edge weights along the walk:
Here a closed walk of length is a function from the cyclic index set to the vertex set , and the successor index is taken modulo (so the walk returns to its start). This is the standard combinatorial expansion of trace moments as a sum over closed walks, the entry point of the moment method (Buchholz, Operator Khintchine inequality in non-commutative probability, Math. Ann. 319 (2001) 1–16, §2).
Preamble
import Mathlib open Matrix open scoped BigOperators
Formal statement
theorem trace_pow_eq_walk {iota : Type*} [Fintype iota] [DecidableEq iota]
{R : Type*} [CommRing R] (M : Matrix iota iota R) (n : Nat) :
Matrix.trace (M ^ (n + 1)) =
∑ v : Fin (n + 1) → iota,
∏ k : Fin (n + 1),
M (v k) (v ⟨(k.1 + 1) % (n + 1), Nat.mod_lt _ (Nat.succ_pos n)⟩) := by sorrySource
Buchholz, Operator Khintchine inequality in non-commutative probability, Math. Ann. 319 (2001) 1-16, section 2; CR2009 (arXiv:0805.4471) section 6.1 Lemma 6.1