b5_quotient_trace_sq
tr(M^2) = Σ (n_i - 1)^2 + 2 (n_0 n_1 + n_2 n_3 + n_1 n_3 + n_4 (n_0 + n_1 + n_2 + n_3)) for the quotient matrix of B_5.
Statement
theorem b5_quotient_trace_sq (n : Fin 5 → ℕ) :
(b5_quotient_matrix n ^ 2).trace =
∑ i, ((n i : ℝ) - 1) ^ 2 + 2 * ((n 0 : ℝ) * n 1 + n 2 * n 3 + n 1 * n 3 + n 4 * (n 0 + n 1 + n 2 + n 3))- Source
- arXiv:2610.21388 (Stronger spectral bound for clique number), Theorem 2.6 with s = 2 (odd case t = 5); serves b5_clique_bound_iff
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- b5_quotient_matrixM_ii = n_i - 1, M_ij = a_ij n_j (a = adjacency of G_5); the eigenvalues of M are those of B_5 other than -1 (Theorem 2.3 of…
- g5_adjG_5 on vertices r_1, r_2, w_1, w_2, r_3 (indices 0..4): edges r_1 r_2, w_1 w_2, r_2 w_2, and r_3 adjacent to all.
- Used by 1
- b5_clique_bound_iffFor B_5(n_0..n_4) with all n_i ≥ 1, the strong spectral clique bound sqrt(Σ_{λ ≠ -1} λ^2) ≤ n(1 - 1/ω) (with Σ_{λ≠-1} λ^2 = tr(M^2) for…
The proof, explained
The identity expresses the trace of the squared quotient matrix for B₅ in terms of the vertex weights n_i. The proof proceeds by direct finite computation: it unfolds the trace of M² into an explicit double sum over the 5 vertices, expands the finite sums with Fin.sum_univ_five, and checks that the resulting polynomial in n_0, ..., n_4 matches the right-hand side using ring arithmetic.
The trace tr(M²) is rewritten as the double sum ∑ x, ∑ x₁, M x x₁ * M x₁ x with explicit entry definitions.
By unfolding the definitions of trace (`Matrix.trace`, `Matrix.diag_apply`), matrix square (`pow_two`, `Matrix.mul_apply`), and the matrix entries (`b5_quotient_matrix`, `g5_adj`), the trace of the squared quotient matrix becomes the sum over all index pairs (x, x₁) of the product M(x, x₁) * M(x₁, x).
uses
Matrix.trace,Matrix.diag_apply,pow_two,Matrix.mul_apply,b5_quotient_matrix,g5_adjsimp only [Matrix.trace, Matrix.diag_apply, pow_two, Matrix.mul_apply, b5_quotient_matrix, g5_adj]The sums over Fin 5 are unrolled and the adjacency conditions evaluated for all pairs of indices.
Rewriting with `Fin.sum_univ_five` expands both the outer and inner sums over the 5 vertices into explicit sums of 5 terms. The simplifier also decides the equality and adjacency relations for each concrete pair in {0, 1, 2, 3, 4}, reducing the expression to an explicit polynomial in n 0, n 1, n 2, n 3, n 4.
uses
Fin.sum_univ_fivesimp [Fin.sum_univ_five]The expanded polynomial matches the right-hand side.
Both sides of the equation are now concrete polynomials in the real variables n 0, ..., n 4. The `ring` tactic verifies that expanding all products and collecting like terms yields identical polynomials on both sides.
ring
Matrix.trace- The trace of a square matrix is the sum of its diagonal entries, ∑ i, A i i.
Matrix.diag_apply- The i-th entry of the diagonal vector of a matrix A is the entry A i i.
pow_two- Squaring an element in a monoid equals multiplying it by itself: a ^ 2 = a * a.
Matrix.mul_apply- The (i, k)-th entry of a matrix product M * N is the sum ∑ j, M i j * N j k.
b5_quotient_matrix- The definition of the 5 × 5 quotient matrix for B₅, whose (i, j)-th entry is n i - 1 when i = j, n j when i and j are adjacent in G₅, and 0 otherwise.
g5_adj- The adjacency relation for the 5-vertex graph G₅, in which vertex 4 is adjacent to vertices 0, 1, 2, 3, and the remaining edges form the path 0-1-3-2.
Fin.sum_univ_five- A sum over all five elements of Fin 5 expands to f 0 + f 1 + f 2 + f 3 + f 4.
- The proof is purely computational: rather than using graph-theoretic properties of symmetric quotient matrices, Lean expands all 25 index pairs directly and simplifies the resulting polynomial identity using ring normalization.
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.
theorem b5_quotient_trace_sq (n : Fin 5 → ℕ) : (b5_quotient_matrix n ^ 2).trace = ∑ i, ((n i : ℝ) - 1) ^ 2 + 2 * ((n 0 : ℝ) * n 1 + n 2 * n 3 + n 1 * n 3 + n 4 * (n 0 + n 1 + n 2 + n 3)) := by simp only [Matrix.trace, Matrix.diag_apply, pow_two, Matrix.mul_apply, b5_quotient_matrix, g5_adj] simp [Fin.sum_univ_five] ring