graph_edit_cost_nonneg
For any $n \times n$ real matrices $A$ and $B$ and any matrix $Q$ with non-negative entries, the edit cost $\mathcal{C}_{\mathsf{ed}}(Q)$ is non-negative.
Statement
theorem graph_edit_cost_nonneg {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (Q : Matrix (Fin n) (Fin n) ℝ)
(hQ : ∀ i j, 0 ≤ Q i j) :
0 ≤ graph_edit_cost A B Q- Source
- arXiv:2611.05048 Section 2
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_edit_costThe edit cost $\mathcal{C}_{\mathsf{ed}}(Q)$ of a fractional alignment matrix $Q$ between two $n \times n$ matrices $A$ and $B$ is the sum…
Read back from the Lean
For any natural number $n$ and any $n \times n$ real matrices $A$, $B$, and $Q$, if every entry of $Q$ is non-negative (i.e., $0 \le Q i j$ for all $i, j \in \text{Fin } n$), then graph_edit_cost A B Q is non-negative ($0 \le \text{graph\_edit\_cost A B Q}$).
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 definition of graph edit cost expands into a quadruple sum of terms of the form $|A_{v, v'} - B_{w, w'}| Q_{v, w} Q_{v', w'}$. Because a sum of non-negative terms is non-negative, the proof reduces to checking each term individually. Each term is a product of an absolute value and two entries of $Q$, all of which are non-negative.
It suffices to show that each term $|A_{v, v'} - B_{w, w'}| \cdot Q_{v, w} \cdot Q_{v', w'}$ in the sum is non-negative.
Unfolding the definition of `graph_edit_cost` expresses the edit cost as a quadruple sum over indices $v, v', w, w'$. Applying `Finset.sum_nonneg` across all four summations reduces the non-negativity of the total sum to the non-negativity of an arbitrary individual term.
uses
Finset.sum_nonnegunfold graph_edit_cost refine Finset.sum_nonneg (fun v _ => Finset.sum_nonneg (fun v' _ => Finset.sum_nonneg (fun w _ => Finset.sum_nonneg (fun w' _ => ?_))))
Each term $|A_{v, v'} - B_{w, w'}| \cdot Q_{v, w} \cdot Q_{v', w'}$ is non-negative.
The absolute difference $|A_{v, v'} - B_{w, w'}|$ is non-negative by `abs_nonneg`, and the matrix entries $Q_{v, w}$ and $Q_{v', w'}$ are non-negative by the assumption `hQ`. Applying `mul_nonneg` twice shows that the product of these three non-negative terms is non-negative.
uses
mul_nonneg,abs_nonnegexact mul_nonneg (mul_nonneg (abs_nonneg _) (hQ v w)) (hQ v' w')
Finset.sum_nonneg- If every term in a finite sum is non-negative, the sum is non-negative.
mul_nonneg- The product of two non-negative numbers is non-negative.
abs_nonneg- The absolute value of a real number is non-negative.
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.
/-- The edit cost of a fractional alignment with non-negative entries is non-negative. -/theorem graph_edit_cost_nonneg {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (Q : Matrix (Fin n) (Fin n) ℝ) (hQ : ∀ i j, 0 ≤ Q i j) : 0 ≤ graph_edit_cost A B Q := by unfold graph_edit_cost refine Finset.sum_nonneg (fun v _ => Finset.sum_nonneg (fun v' _ => Finset.sum_nonneg (fun w _ => Finset.sum_nonneg (fun w' _ => ?_)))) exact mul_nonneg (mul_nonneg (abs_nonneg _) (hQ v w)) (hQ v' w')