regular_graph_lap_mul_pow_scalar_sub_all_ones_trace
For each d-regular graph G on n vertices and each pair of positive integers i and j, the trace of L(G)^i ((d+1)I_n - J_n)^j equals (d+1)^j ℓ_i(G), where J_n is the all-ones matrix and ℓ_i(G) is the Laplacian trace sequence.
Statement
open scoped Classical in theorem regular_graph_lap_mul_pow_scalar_sub_all_ones_trace {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) (hreg : G.IsRegularOfDegree d) (i j : ℕ+) : Matrix.trace (((G.lapMatrix ℝ) ^ (i : ℕ)) * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ (j : ℕ))) = ((d + 1 : ℝ) ^ (j : ℕ)) * graph_lap_trace_seq G i
- Formalizes
- arXiv:2610.36127 Lemma 34
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_lap_trace_seqFor a graph G on a finite vertex set V, its Laplacian trace sequence (ℓ_i(G))_{i=1}^∞ is the sequence of real numbers tr(L(G)^i) for…
Read back from the Lean
For any finite type $V$, natural number $d$, simple graph $G$ on $V$ such that $G$ is regular of degree $d$, and any positive integers $i$ and $j$:
The trace of the matrix product
$$(L^i) \cdot \left((d + 1) I - J\right)^j$$
equals
$$(d + 1)^j \cdot \operatorname{graph\_lap\_trace\_seq}(G, i),$$
where:
- $L = G.\text{lapMatrix } \mathbb{R}$ is the real Laplacian matrix of $G$,
- $I$ is the identity matrix on $V$,
- $J$ is the all-ones matrix on $V \times V$ (Matrix.of fun _ _ ↦ 1),
- matrix powers and products are taken in $\mathrm{Matrix}(V, V, \mathbb{R})$, and
- $\operatorname{graph\_lap\_trace\_seq}(G, i)$ is the trace of $L^i$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by first showing that any matrix L annihilating the all-ones matrix J satisfies L ((d+1)I - J)^j = (d+1)^j L by induction on j, because L ((d+1)I - J) = (d+1)L - LJ = (d+1)L. Factoring L^i = L^(i-1) L for positive i extends this to L^i ((d+1)I - J)^j = (d+1)^j L^i, from which taking traces yields tr(L^i ((d+1)I - J)^j) = (d+1)^j tr(L^i). Finally, since the row sums of any graph Laplacian are zero, L(G) J = 0 holds, and applying the general trace identity to L(G) gives the desired formula (d+1)^j ℓ_i(G).
For the base case j = 0, L ((d+1)I - J)^0 = (d+1)^0 • L holds. automation
By induction on j. When j = 0, the matrix power ((d+1)I - J)^0 is the identity matrix and (d+1)^0 = 1, so both sides simplify to L.
induction j with | zero => simp
If L * J = 0, then L * ((d+1)I - J)^j = (d+1)^j • L for all j ∈ ℕ.
For the inductive step, we first prove the base algebraic identity L ((d+1)I - J) = (d+1) • L (labeled `hLA`): distributing multiplication over subtraction gives (d+1)L - LJ, and LJ = 0 leaves (d+1)L. Then, writing ((d+1)I - J)^(k+1) as ((d+1)I - J)^k * ((d+1)I - J), we reassociate to isolate L ((d+1)I - J)^k, apply the induction hypothesis to replace it with (d+1)^k • L, pull the scalar out, apply `hLA`, and combine the scalar powers to obtain (d+1)^(k+1) • L.
uses
Matrix.mul_sub,Matrix.mul_smul,Matrix.mul_one,sub_zero,pow_succ,mul_assoc,Matrix.smul_mul,smul_smul| succ k ih => have hLA : L * ((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) = (d + 1 : ℝ) • L := by rw [Matrix.mul_sub, Matrix.mul_smul, Matrix.mul_one, hLJ, sub_zero] rw [pow_succ, ← mul_assoc, ih, Matrix.smul_mul, hLA, smul_smul, pow_succ]For all m, j ∈ ℕ, L^(m+1) * ((d+1)I - J)^j = (d+1)^j • L^(m+1).
We write L^(m+1) as L^m * L using `pow_succ`. Associating L with ((d+1)I - J)^j allows us to apply the lemma `regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1`, which reduces L * ((d+1)I - J)^j to (d+1)^j • L. Factoring the scalar out of the matrix product with `Matrix.mul_smul` and recombining L^m * L = L^(m+1) establishes the result.
uses
pow_succ,mul_assoc,regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1,Matrix.mul_smulrw [pow_succ, mul_assoc, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1 L d hLJ j, Matrix.mul_smul, ← pow_succ]For all positive integers i and j, the trace of L^i ((d+1)I - J)^j equals (d+1)^j tr(L^i).
Since i is a positive integer, it is nonzero, so by `Nat.exists_eq_succ_of_ne_zero` it can be written as m + 1 for some m ∈ ℕ. Substituting this into `regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2` gives L^i ((d+1)I - J)^j = (d+1)^j • L^i. Taking traces on both sides and pulling out the scalar factor (d+1)^j via `Matrix.trace_smul` proves the identity.
uses
Nat.exists_eq_succ_of_ne_zero,regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2,Matrix.trace_smul,smul_eq_mulobtain ⟨m, hm⟩ := Nat.exists_eq_succ_of_ne_zero (show (i : ℕ) ≠ 0 from i.pos.ne') rw [hm, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2 L d hLJ m (j : ℕ), Matrix.trace_smul, smul_eq_mul]
The Laplacian matrix of G satisfies L(G) * J = 0, where J is the all-ones matrix.
By matrix extensionality (`ext a b`), it suffices to check each matrix entry. For any pair of vertices a, b, the (a, b)-th entry of L(G) * J is the row sum ∑_c L(G)_{a, c} * 1. By `SimpleGraph.lapMatrix_mulVec_const_eq_zero`, multiplying the Laplacian by the constant all-ones vector gives the zero vector. Evaluating this vector equation at component a shows that the sum of the entries across row a is 0, so every entry of L(G) * J is zero.
uses
Matrix.mul_apply,Matrix.of_apply,mul_one,Matrix.zero_apply,congrFun,SimpleGraph.lapMatrix_mulVec_const_eq_zero,Matrix.mulVec_apply,Matrix.row_apply,Pi.zero_applyclassical have hLJ : G.lapMatrix ℝ * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0 := by ext a b rw [Matrix.mul_apply] simp only [Matrix.of_apply, mul_one, Matrix.zero_apply] have h := congrFun (SimpleGraph.lapMatrix_mulVec_const_eq_zero (G := G) (R := ℝ)) a simp only [Matrix.mulVec_apply, dotProduct, Matrix.row_apply, Pi.zero_apply, mul_one] at h simpa using h
The trace of L(G)^i ((d+1)I - J)^j equals (d+1)^j ℓ_i(G).
We apply `regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3` with L = L(G) and the established fact that L(G) * J = 0. This evaluates the trace as (d+1)^j tr(L(G)^i), which is by definition (d+1)^j * graph_lap_trace_seq G i.
uses
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3exact regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3 (G.lapMatrix ℝ) d hLJ i j
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_one- Multiplying an element by 1 on the right leaves it unchanged: a * 1 = a.
pow_succ- The (n + 1)-th power of an element in a monoid equals its n-th power multiplied by the element: a^(n + 1) = a^n * a.
sub_zero- Subtracting zero from an element leaves it unchanged: a - 0 = a.
smul_smul- Successive scalar multiplications compose by multiplying the scalars: a₁ • (a₂ • b) = (a₁ * a₂) • b.
smul_eq_mul- Scalar multiplication by an element of the ring agrees with regular multiplication: a • b = a * b.
congrFun- If two functions are equal, their values on any argument are equal: if f = g then f(a) = g(a).
Nat.exists_eq_succ_of_ne_zero- Any nonzero natural number is the successor of some natural number: if n ≠ 0, then n = k + 1 for some k.
Pi.zero_apply- The zero function evaluated at any point gives zero: 0(i) = 0.
Matrix.mul_apply- The (i, k)-th entry of the product of two matrices M and N is the sum ∑ j, M i j * N j k.
Matrix.mul_one- Multiplying a matrix on the right by the identity matrix leaves it unchanged: M * 1 = M.
Matrix.mul_smul- A scalar multiple on the right factor can be factored out of matrix multiplication: M * (a • N) = a • (M * N).
Matrix.mul_sub- Matrix multiplication distributes over subtraction on the right: M * (N - N') = M * N - M * N'.
Matrix.of_apply- The (i, j)-th entry of a matrix defined by a function f is f(i, j).
Matrix.zero_apply- Every entry of the zero matrix is zero: 0 i j = 0.
Matrix.row_apply- The j-th component of the i-th row of matrix A is the matrix entry A i j.
Matrix.mulVec_apply- The i-th component of the matrix-vector product M v is the dot product of the i-th row of M with v.
Matrix.smul_mul- A scalar multiple on the left factor can be factored out of matrix multiplication: (a • M) * N = a • (M * N).
Matrix.trace_smul- The trace of a scalar multiple of a matrix is the scalar multiple of the trace: tr(r • A) = r • tr(A).
SimpleGraph.lapMatrix_mulVec_const_eq_zero- Multiplying the Laplacian matrix of a graph by the constant all-ones vector yields the zero vector (every row sum of the Laplacian is zero).
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1- If L * J = 0 for the all-ones matrix J, then L * ((d + 1)I - J)^j = (d + 1)^j • L for all natural numbers j.
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2- If L * J = 0 for the all-ones matrix J, then L^(m + 1) * ((d + 1)I - J)^j = (d + 1)^j • L^(m + 1) for all natural numbers m and j.
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3- If L * J = 0 for the all-ones matrix J, then tr(L^i ((d + 1)I - J)^j) = (d + 1)^j tr(L^i) for all positive integers i and j.
- Although the theorem assumes that G is d-regular via `hreg : G.IsRegularOfDegree d`, the regularity hypothesis is not actually needed: the identity holds for any finite graph and any scalar d, as the argument only relies on the Laplacian row sums being zero.
- At the final step, the expression `(L(G)^i).trace` matches the definition `graph_lap_trace_seq G i` definitionally, so `exact` closes the goal directly without an explicit unfolding step.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- If `L * J = 0` (`J` the all-ones matrix), then `L * ((d+1)I - J)^j = (d+1)^j • L`. -/lemma regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1 {V : Type*} [Fintype V] [DecidableEq V] (L : Matrix V V ℝ) (d : ℕ) (hLJ : L * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0) (j : ℕ) : L * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ j) = ((d + 1 : ℝ) ^ j) • L := by induction j with | zero => simp | succ k ih => have hLA : L * ((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) = (d + 1 : ℝ) • L := by rw [Matrix.mul_sub, Matrix.mul_smul, Matrix.mul_one, hLJ, sub_zero] rw [pow_succ, ← mul_assoc, ih, Matrix.smul_mul, hLA, smul_smul, pow_succ]/-- Hence `L^(m+1) * ((d+1)I - J)^j = (d+1)^j • L^(m+1)`. -/lemma regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2 {V : Type*} [Fintype V] [DecidableEq V] (L : Matrix V V ℝ) (d : ℕ) (hLJ : L * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0) (m j : ℕ) : L ^ (m + 1) * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ j) = ((d + 1 : ℝ) ^ j) • L ^ (m + 1) := by rw [pow_succ, mul_assoc, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1 L d hLJ j, Matrix.mul_smul, ← pow_succ]/-- Taking traces: `tr (L^i ((d+1)I - J)^j) = (d+1)^j tr (L^i)` for positive `i`, `j`. -/lemma regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3 {V : Type*} [Fintype V] [DecidableEq V] (L : Matrix V V ℝ) (d : ℕ) (hLJ : L * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0) (i j : ℕ+) : (L ^ (i : ℕ) * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ (j : ℕ))).trace = ((d + 1 : ℝ) ^ (j : ℕ)) * (L ^ (i : ℕ)).trace := by obtain ⟨m, hm⟩ := Nat.exists_eq_succ_of_ne_zero (show (i : ℕ) ≠ 0 from i.pos.ne') rw [hm, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2 L d hLJ m (j : ℕ), Matrix.trace_smul, smul_eq_mul]open scoped Classical in/-- For any d-regular graph G and positive integers i and j, the trace of L(G)^i ((d+1)I - J)^j equals (d+1)^j tr(L(G)^i). -/theorem regular_graph_lap_mul_pow_scalar_sub_all_ones_trace {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) (hreg : G.IsRegularOfDegree d) (i j : ℕ+) : Matrix.trace (((G.lapMatrix ℝ) ^ (i : ℕ)) * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ (j : ℕ))) = ((d + 1 : ℝ) ^ (j : ℕ)) * graph_lap_trace_seq G i := by classical have hLJ : G.lapMatrix ℝ * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0 := by ext a b rw [Matrix.mul_apply] simp only [Matrix.of_apply, mul_one, Matrix.zero_apply] have h := congrFun (SimpleGraph.lapMatrix_mulVec_const_eq_zero (G := G) (R := ℝ)) a simp only [Matrix.mulVec_apply, dotProduct, Matrix.row_apply, Pi.zero_apply, mul_one] at h simpa using h exact regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3 (G.lapMatrix ℝ) d hLJ i j