AFTD Auto-Formalizing Theoretical Domains

graph_edit_cost_nonneg

theoremverified

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.

  1. 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.

    lines 5–7

    uses Finset.sum_nonneg

      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' _ => ?_))))
  2. 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.

    line 8

    uses mul_nonneg, abs_nonneg

      exact 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

/-- 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')
See it in the graphDiscuss this resultChallenge it