circulant_laplacian_is_standardized
For n ≥ 2 and coefficients t_m ∈ [0, 1] for m = 1, ..., n-1, the matrix (1/n) ∑_{m=1}^{n-1} t_m (I - Q^m), where Q is the cyclic permutation matrix, is a standardized Laplacian matrix of order n.
Statement
theorem circulant_laplacian_is_standardized (n : ℕ) (hn : 2 ≤ n) (t : ℕ → ℝ) (ht : ∀ m ∈ Finset.Ico 1 n, 0 ≤ t m ∧ t m ≤ 1) : is_standardized_laplacian n ((1 / (n : ℝ)) • ∑ m ∈ Finset.Ico 1 n, (t m) • ((1 : Matrix (Fin n) (Fin n) ℝ) - (Matrix.of fun (i j : Fin n) => if j.val = (i.val + m) % n then 1 else 0)))
- Source
- arXiv:2610.14100 proof of Corollary 2
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_standardized_laplacianA standardized Laplacian matrix of order n is a real n x n matrix with zero row sums and off-diagonal entries in [-1/n, 0].
- Used by 1
- zonotope_polygon_subset_standardized_laplacian_spectraFor any integer n ≥ 2, the zonotope polygon S_n, defined as the set of linear combinations ∑_{m=1}^{n-1} t_m g_m with t_m ∈ [0, 1] and g_m…
Read back from the Lean
For any natural number $n$ such that $2 \le n$, and any function $t : \mathbb{N} \to \mathbb{R}$ such that $0 \le t(m) \le 1$ for all $m \in \{1, \dots, n-1\}$, the matrix
$$ L = \frac{1}{n} \sum_{m=1}^{n-1} t(m) (I_n - P_m) $$
satisfies is_standardized_laplacian n L, where $I_n$ is the $n \times n$ identity matrix over $\mathbb{R}$ and $P_m$ is the $n \times n$ matrix whose $(i, j)$-th entry is $1$ if $j \equiv i + m \pmod n$ and $0$ otherwise (with indices $i, j \in \{0, \dots, n-1\}$).
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
To show that the matrix M = (1/n) ∑_{m=1}^{n-1} t_m (I - Q^m) is a standardized Laplacian matrix, the proof verifies zero row sums and off-diagonal bounds in [-1/n, 0]. For row sums, swapping the order of summation reveals that each component matrix I - Q^m has row sum 1 - 1 = 0, so the total row sum vanishes. For off-diagonal entries (i ≠ j), the identity term vanishes and the entry simplifies to -(1/n) S, where S is a convex-like sum of shift indicators. Because 0 ≤ t_m ≤ 1 and at most one shift m connects index i to j modulo n, the sum satisfies 0 ≤ S ≤ 1, which immediately implies the required bounds -1/n ≤ M_{ij} ≤ 0.
The sum of the identity indicator over Fin n is 1.
For a fixed index i, the sum ∑_j [i = j] evaluates the indicator of i over the finite universe of indices, which equals 1 by Finset.sum_ite_eq.
uses
Finset.sum_ite_eqlemma circulant_laplacian_is_standardized_indicator_one (n : ℕ) (i : Fin n) : (∑ j : Fin n, (if i = j then (1:ℝ) else 0)) = 1 := by rw [Finset.sum_ite_eq]; simp
For any remainder r < n, the sum over j in Fin n of the indicator [j.val = r] is 1.
Because r < n, the element ⟨r, hr⟩ is the unique element of Fin n with value r, as shown using Fin.ext_iff. Rewriting with this equality and summing the indicator over the universe yields 1 via Finset.sum_ite_eq'.
uses
Fin.ext_iff,Finset.sum_ite_eq'lemma circulant_laplacian_is_standardized_indicator_mod (n r : ℕ) (hr : r < n) : (∑ j : Fin n, (if j.val = r then (1:ℝ) else 0)) = 1 := by have h : ∀ j : Fin n, (if j.val = r then (1:ℝ) else 0) = (if j = ⟨r, hr⟩ then 1 else 0) := by intro j; simp [Fin.ext_iff] simp only [h] rw [Finset.sum_ite_eq']; simp
For any indices i, j in Fin n, at most one shift m in {1, ..., n-1} satisfies j ≡ i + m (mod n), so the sum of indicators over m in [1, n) is at most 1.
Using Finset.sum_boole, the sum of indicators equals the cardinality of the subset of shifts m in [1, n) satisfying j.val = (i.val + m) % n. By Finset.card_le_one, it suffices to show that any two such shifts a and b are equal. Cancelling i.val via Nat.ModEq.add_left_cancel' gives a ≡ b [MOD n], and since both a < n and b < n, Nat.ModEq.eq_of_lt_of_lt implies a = b. Hence the subset has cardinality at most 1.
uses
Finset.sum_boole,Finset.card_le_one,Finset.mem_filter,Finset.mem_Ico,Nat.ModEq,Nat.ModEq.add_left_cancel',Nat.ModEq.eq_of_lt_of_ltlemma circulant_laplacian_is_standardized_indicator_le_one (n : ℕ) (i j : Fin n) : (∑ m ∈ Finset.Ico 1 n, (if j.val = (i.val + m) % n then (1:ℝ) else 0)) ≤ 1 := by rw [Finset.sum_boole] have hcard : ((Finset.Ico 1 n).filter (fun m => j.val = (i.val + m) % n)).card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb simp only [Finset.mem_filter, Finset.mem_Ico] at ha hb obtain ⟨⟨ha1, ha2⟩, hpa⟩ := ha obtain ⟨⟨hb1, hb2⟩, hpb⟩ := hb have hmod : (i.val + a) ≡ (i.val + b) [MOD n] := by unfold Nat.ModEq; rw [← hpa, ← hpb] exact Nat.ModEq.eq_of_lt_of_lt (Nat.ModEq.add_left_cancel' i.val hmod) ha2 hb2 exact_mod_cast hcard
The definition of a standardized Laplacian reduces to verifying zero row sums and off-diagonal bounds [-1/n, 0] for the entries M_{ij} = (1/n) ∑_{m=1}^{n-1} t_m (I_{ij} - (Q^m)_{ij}).
We define M as the given matrix and unfold is_standardized_laplacian. We establish the entry-wise formula hM for M i j by distributing matrix scalar multiplication, addition, and subtraction over entries using Matrix.smul_apply, Matrix.sum_apply, Matrix.sub_apply, and smul_eq_mul. Splitting the conjunction produces two subgoals: zero row sums and bounds on off-diagonal entries.
uses
is_standardized_laplacian,Matrix.smul_apply,Matrix.sum_apply,Matrix.sub_apply,smul_eq_multheorem circulant_laplacian_is_standardized (n : ℕ) (hn : 2 ≤ n) (t : ℕ → ℝ) (ht : ∀ m ∈ Finset.Ico 1 n, 0 ≤ t m ∧ t m ≤ 1) : is_standardized_laplacian n ((1 / (n : ℝ)) • ∑ m ∈ Finset.Ico 1 n, (t m) • ((1 : Matrix (Fin n) (Fin n) ℝ) - (Matrix.of fun (i j : Fin n) => if j.val = (i.val + m) % n then 1 else 0))) := by let M : Matrix (Fin n) (Fin n) ℝ := (1 / (n : ℝ)) • ∑ m ∈ Finset.Ico 1 n, (t m) • ((1 : Matrix (Fin n) (Fin n) ℝ) - (Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ))) change is_standardized_laplacian n M unfold is_standardized_laplacian have hM : ∀ (i j : Fin n), M i j = (1/(n:ℝ)) * ∑ m ∈ Finset.Ico 1 n, t m * (((1 : Matrix (Fin n) (Fin n) ℝ) i j) - ((Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ)) i j)) := by intro i j simp only [M, Matrix.smul_apply, Matrix.sum_apply, Matrix.sub_apply, smul_eq_mul] constructor
Every row of M sums to zero: ∑_j M_{ij} = 0 for all i.
Factoring out 1/n, we evaluate the double sum ∑_j ∑_{m=1}^{n-1} t_m (I_{ij} - (Q^m)_{ij}). Exchanging the order of summation with Finset.sum_comm, each term for fixed m factors as t_m ∑_j (I_{ij} - (Q^m)_{ij}). The inner sum splits into ∑_j I_{ij} - ∑_j (Q^m)_{ij}, which equals 1 - 1 = 0 by circulant_laplacian_is_standardized_indicator_one and circulant_laplacian_is_standardized_indicator_mod (valid since (i.val + m) % n < n by Nat.mod_lt). Therefore every summand is zero, so the total row sum is zero.
uses
Finset.mul_sum,Finset.sum_comm,Finset.sum_eq_zero,Finset.sum_sub_distrib,Matrix.one_apply,Matrix.of_apply,circulant_laplacian_is_standardized_indicator_one,circulant_laplacian_is_standardized_indicator_mod,Nat.mod_lt,mul_zero· intro i simp only [hM] rw [← Finset.mul_sum] have hzero : (∑ j : Fin n, ∑ m ∈ Finset.Ico 1 n, t m * ((1 : Matrix (Fin n) (Fin n) ℝ) i j - Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ) i j)) = 0 := by rw [Finset.sum_comm] apply Finset.sum_eq_zero intro m hm rw [← Finset.mul_sum] have hrow : (∑ j : Fin n, ((1 : Matrix (Fin n) (Fin n) ℝ) i j - Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ) i j)) = 0 := by rw [Finset.sum_sub_distrib] simp only [Matrix.one_apply, Matrix.of_apply] rw [circulant_laplacian_is_standardized_indicator_one n i, circulant_laplacian_is_standardized_indicator_mod n ((i.val + m) % n) (Nat.mod_lt _ (by omega))] ring rw [hrow, mul_zero] rw [hzero, mul_zero]
For i ≠ j, the diagonal identity term vanishes and M_{ij} = -(1/n) S, where S = ∑_{m=1}^{n-1} t_m [j.val = (i.val + m) % n].
Because i ≠ j, the identity entry I_{ij} is 0 by if_neg. The sum over m in the entry formula simplifies to ∑_m t_m (0 - (Q^m)_{ij}) = -S using Finset.sum_neg_distrib and Finset.sum_congr, where S = ∑_{m=1}^{n-1} t_m [j.val = (i.val + m) % n]. Thus M_{ij} = (1/n) * (-S).
uses
Matrix.one_apply,Matrix.of_apply,if_neg,Finset.sum_neg_distrib,Finset.sum_congr· intro i j hij simp only [hM] simp only [Matrix.one_apply, Matrix.of_apply, if_neg hij] set S := ∑ m ∈ Finset.Ico 1 n, t m * (if j.val = (i.val + m) % n then (1:ℝ) else 0) with hS have hsum : (∑ m ∈ Finset.Ico 1 n, t m * (0 - (if j.val = (i.val + m) % n then (1:ℝ) else 0))) = -S := by rw [hS, ← Finset.sum_neg_distrib] apply Finset.sum_congr rfl intro m hm ring rw [hsum]
The off-diagonal sum S satisfies 0 ≤ S ≤ 1.
Each coefficient t_m is non-negative and each indicator is non-negative, so S ≥ 0 by Finset.sum_nonneg and mul_nonneg. For the upper bound, since t_m ≤ 1, each term is bounded above by 1 times the indicator via mul_le_mul_of_nonneg_right and Finset.sum_le_sum. The resulting sum of indicators is bounded by 1 using circulant_laplacian_is_standardized_indicator_le_one, showing S ≤ 1.
uses
Finset.sum_nonneg,mul_nonneg,Finset.sum_le_sum,mul_le_mul_of_nonneg_right,Finset.sum_congr,circulant_laplacian_is_standardized_indicator_le_onehave hS_nonneg : 0 ≤ S := by rw [hS] apply Finset.sum_nonneg intro m hm have h1 := (ht m hm).1 have hind : (0:ℝ) ≤ (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by split <;> norm_num exact mul_nonneg h1 hind have hS_le : S ≤ 1 := by rw [hS] calc ∑ m ∈ Finset.Ico 1 n, t m * (if j.val = (i.val + m) % n then (1:ℝ) else 0) ≤ ∑ m ∈ Finset.Ico 1 n, 1 * (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by apply Finset.sum_le_sum intro m hm have ht1 := (ht m hm).2 have hind : (0:ℝ) ≤ (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by split <;> norm_num exact mul_le_mul_of_nonneg_right ht1 hind _ = ∑ m ∈ Finset.Ico 1 n, (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by apply Finset.sum_congr rfl; intro m hm; ring _ ≤ 1 := circulant_laplacian_is_standardized_indicator_le_one n i j
Each off-diagonal entry satisfies -1/n ≤ M_{ij} ≤ 0, completing the proof.
Since n ≥ 2, we have 1/n > 0. The lower bound -1/n ≤ (1/n)(-S) is equivalent to (1/n) S ≤ 1/n by neg_le_neg_iff, which follows from S ≤ 1 by multiplying by 1/n using mul_le_mul_of_nonneg_left and le_of_lt. The upper bound (1/n)(-S) ≤ 0 is equivalent to 0 ≤ (1/n) S by neg_nonpos, which holds by mul_nonneg since 1/n > 0 and S ≥ 0.
uses
neg_le_neg_iff,mul_le_mul_of_nonneg_left,le_of_lt,neg_nonpos,mul_nonneghave hn0 : (0:ℝ) < n := by exact_mod_cast (by omega : 0 < n) have h1n : (0:ℝ) < 1/(n:ℝ) := by positivity constructor · rw [show (1:ℝ)/↑n * -S = -((1:ℝ)/↑n * S) by ring, show (-1:ℝ)/↑n = -((1:ℝ)/↑n) by ring] rw [neg_le_neg_iff] simpa using mul_le_mul_of_nonneg_left hS_le (le_of_lt h1n) · rw [show (1:ℝ)/↑n * -S = -((1:ℝ)/↑n * S) by ring] rw [neg_nonpos] exact mul_nonneg (le_of_lt h1n) hS_nonneg
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.sum_boole- The sum of an indicator condition over a finite set equals the cardinality of the subset of elements satisfying the condition.
Finset.card_le_one- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.sum_ite_eq- The sum of a Kronecker delta over a finite set s evaluates to the value at that element if it belongs to s, and 0 otherwise.
Finset.sum_ite_eq'- The sum of a Kronecker delta over a finite set s evaluates to the value at that element if it belongs to s, and 0 otherwise.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_Ico- An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Nat.ModEq- Modular equivalence a ≡ b [MOD n] means a % n = b % n.
Nat.ModEq.add_left_cancel'- A constant added to both sides of a modular congruence can be cancelled: c + a ≡ c + b [MOD n] implies a ≡ b [MOD n].
Nat.ModEq.eq_of_lt_of_lt- If two natural numbers are congruent modulo m and both are strictly less than m, they are equal.
is_standardized_laplacian- A matrix is a standardized Laplacian if all its row sums are zero and every off-diagonal entry lies in [-1/n, 0].
Matrix.smul_apply- The (i, j)-th entry of a scalar multiple of a matrix is the scalar times the (i, j)-th entry of the matrix.
Matrix.sum_apply- The (i, j)-th entry of a sum of matrices is the sum of their (i, j)-th entries.
Matrix.sub_apply- The (i, j)-th entry of the difference of two matrices is the difference of their (i, j)-th entries.
smul_eq_mul- Scalar multiplication of real numbers is ordinary multiplication.
Finset.mul_sum- Multiplication distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
Finset.sum_comm- The order of summation in a finite double sum can be swapped.
Finset.sum_eq_zero- If every term in a finite sum is zero, the sum is zero.
Finset.sum_sub_distrib- A finite sum of differences equals the difference of the finite sums.
Matrix.one_apply- The (i, j)-th entry of the identity matrix is 1 if i = j and 0 otherwise.
Matrix.of_apply- The (i, j)-th entry of the matrix defined by a function f is f i j.
circulant_laplacian_is_standardized_indicator_one- Summing the indicator of equality with a fixed element over all j in Fin n yields 1.
circulant_laplacian_is_standardized_indicator_mod- For any remainder r < n, summing the indicator that j.val = r over all j in Fin n yields 1.
Nat.mod_lt- For any positive modulus y, the remainder x % y is strictly less than y.
mul_zero- Multiplying any number by zero gives zero.
if_neg- An if-then-else expression reduces to its 'else' branch when the condition is false.
Finset.sum_neg_distrib- The sum of negated terms equals the negation of the sum.
Finset.sum_congr- Two sums are equal if their index sets are equal and their summands agree on every element.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
mul_nonneg- The product of two non-negative real numbers is non-negative.
Finset.sum_le_sum- If each term of one finite sum is bounded by the corresponding term of another, the same bound holds for the sums.
mul_le_mul_of_nonneg_right- Multiplying an inequality on the right by a non-negative number preserves the inequality.
circulant_laplacian_is_standardized_indicator_le_one- For any i, j in Fin n, at most one shift m in {1, ..., n-1} satisfies j ≡ i + m (mod n), so the sum of indicators is at most 1.
neg_le_neg_iff- -a ≤ -b is equivalent to b ≤ a.
mul_le_mul_of_nonneg_left- Multiplying an inequality on the left by a non-negative number preserves the inequality.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
neg_nonpos- -a ≤ 0 is equivalent to 0 ≤ a.
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.
lemma circulant_laplacian_is_standardized_indicator_one (n : ℕ) (i : Fin n) : (∑ j : Fin n, (if i = j then (1:ℝ) else 0)) = 1 := by rw [Finset.sum_ite_eq]; simplemma circulant_laplacian_is_standardized_indicator_mod (n r : ℕ) (hr : r < n) : (∑ j : Fin n, (if j.val = r then (1:ℝ) else 0)) = 1 := by have h : ∀ j : Fin n, (if j.val = r then (1:ℝ) else 0) = (if j = ⟨r, hr⟩ then 1 else 0) := by intro j; simp [Fin.ext_iff] simp only [h] rw [Finset.sum_ite_eq']; simplemma circulant_laplacian_is_standardized_indicator_le_one (n : ℕ) (i j : Fin n) : (∑ m ∈ Finset.Ico 1 n, (if j.val = (i.val + m) % n then (1:ℝ) else 0)) ≤ 1 := by rw [Finset.sum_boole] have hcard : ((Finset.Ico 1 n).filter (fun m => j.val = (i.val + m) % n)).card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb simp only [Finset.mem_filter, Finset.mem_Ico] at ha hb obtain ⟨⟨ha1, ha2⟩, hpa⟩ := ha obtain ⟨⟨hb1, hb2⟩, hpb⟩ := hb have hmod : (i.val + a) ≡ (i.val + b) [MOD n] := by unfold Nat.ModEq; rw [← hpa, ← hpb] exact Nat.ModEq.eq_of_lt_of_lt (Nat.ModEq.add_left_cancel' i.val hmod) ha2 hb2 exact_mod_cast hcard/-- The circulant Laplacian matrix formed from cyclic permutation matrices is a standardized Laplacian matrix. -/theorem circulant_laplacian_is_standardized (n : ℕ) (hn : 2 ≤ n) (t : ℕ → ℝ) (ht : ∀ m ∈ Finset.Ico 1 n, 0 ≤ t m ∧ t m ≤ 1) : is_standardized_laplacian n ((1 / (n : ℝ)) • ∑ m ∈ Finset.Ico 1 n, (t m) • ((1 : Matrix (Fin n) (Fin n) ℝ) - (Matrix.of fun (i j : Fin n) => if j.val = (i.val + m) % n then 1 else 0))) := by let M : Matrix (Fin n) (Fin n) ℝ := (1 / (n : ℝ)) • ∑ m ∈ Finset.Ico 1 n, (t m) • ((1 : Matrix (Fin n) (Fin n) ℝ) - (Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ))) change is_standardized_laplacian n M unfold is_standardized_laplacian have hM : ∀ (i j : Fin n), M i j = (1/(n:ℝ)) * ∑ m ∈ Finset.Ico 1 n, t m * (((1 : Matrix (Fin n) (Fin n) ℝ) i j) - ((Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ)) i j)) := by intro i j simp only [M, Matrix.smul_apply, Matrix.sum_apply, Matrix.sub_apply, smul_eq_mul] constructor · intro i simp only [hM] rw [← Finset.mul_sum] have hzero : (∑ j : Fin n, ∑ m ∈ Finset.Ico 1 n, t m * ((1 : Matrix (Fin n) (Fin n) ℝ) i j - Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ) i j)) = 0 := by rw [Finset.sum_comm] apply Finset.sum_eq_zero intro m hm rw [← Finset.mul_sum] have hrow : (∑ j : Fin n, ((1 : Matrix (Fin n) (Fin n) ℝ) i j - Matrix.of (fun (i j : Fin n) => (if j.val = (i.val + m) % n then (1:ℝ) else 0) : Fin n → Fin n → ℝ) i j)) = 0 := by rw [Finset.sum_sub_distrib] simp only [Matrix.one_apply, Matrix.of_apply] rw [circulant_laplacian_is_standardized_indicator_one n i, circulant_laplacian_is_standardized_indicator_mod n ((i.val + m) % n) (Nat.mod_lt _ (by omega))] ring rw [hrow, mul_zero] rw [hzero, mul_zero] · intro i j hij simp only [hM] simp only [Matrix.one_apply, Matrix.of_apply, if_neg hij] set S := ∑ m ∈ Finset.Ico 1 n, t m * (if j.val = (i.val + m) % n then (1:ℝ) else 0) with hS have hsum : (∑ m ∈ Finset.Ico 1 n, t m * (0 - (if j.val = (i.val + m) % n then (1:ℝ) else 0))) = -S := by rw [hS, ← Finset.sum_neg_distrib] apply Finset.sum_congr rfl intro m hm ring rw [hsum] have hS_nonneg : 0 ≤ S := by rw [hS] apply Finset.sum_nonneg intro m hm have h1 := (ht m hm).1 have hind : (0:ℝ) ≤ (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by split <;> norm_num exact mul_nonneg h1 hind have hS_le : S ≤ 1 := by rw [hS] calc ∑ m ∈ Finset.Ico 1 n, t m * (if j.val = (i.val + m) % n then (1:ℝ) else 0) ≤ ∑ m ∈ Finset.Ico 1 n, 1 * (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by apply Finset.sum_le_sum intro m hm have ht1 := (ht m hm).2 have hind : (0:ℝ) ≤ (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by split <;> norm_num exact mul_le_mul_of_nonneg_right ht1 hind _ = ∑ m ∈ Finset.Ico 1 n, (if j.val = (i.val + m) % n then (1:ℝ) else 0) := by apply Finset.sum_congr rfl; intro m hm; ring _ ≤ 1 := circulant_laplacian_is_standardized_indicator_le_one n i j have hn0 : (0:ℝ) < n := by exact_mod_cast (by omega : 0 < n) have h1n : (0:ℝ) < 1/(n:ℝ) := by positivity constructor · rw [show (1:ℝ)/↑n * -S = -((1:ℝ)/↑n * S) by ring, show (-1:ℝ)/↑n = -((1:ℝ)/↑n) by ring] rw [neg_le_neg_iff] simpa using mul_le_mul_of_nonneg_left hS_le (le_of_lt h1n) · rw [show (1:ℝ)/↑n * -S = -((1:ℝ)/↑n * S) by ring] rw [neg_nonpos] exact mul_nonneg (le_of_lt h1n) hS_nonneg