AFTD Auto-Formalizing Theoretical Domains

perm_edit_cost_eq_graph_edit_cost

theoremverified

For any permutation $\pi$ of $\{0, \dots, n-1\}$ and matrices $A, B$, the permutation edit cost $\mathcal{C}_{\mathsf{ed}}(\pi)$ equals the fractional edit cost $\mathcal{C}_{\mathsf{ed}}(P_\pi)$ evaluated on the permutation matrix $P_\pi$.

Statement

theorem perm_edit_cost_eq_graph_edit_cost {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (π : Equiv.Perm (Fin n)) :
    perm_edit_cost A B π = graph_edit_cost A B (π.permMatrix ℝ)
Source
arXiv:2611.05048 Section 3, line 325
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • perm_edit_costThe edit cost $\mathcal{C}_{\mathsf{ed}}(\pi)$ of a permutation $\pi$ between two $n \times n$ matrices $A$ and $B$ is the sum over all…
Used by 1

Read back from the Lean

For every natural number $n$, for all $n \times n$ real matrices $A$ and $B$, and for every permutation $\pi$ of $\mathrm{Fin}(n)$, the permutation edit cost $\mathrm{perm\_edit\_cost}(A, B, \pi)$ equals the graph edit cost $\mathrm{graph\_edit\_cost}(A, B, \pi.\mathrm{permMatrix}(\mathbb{R}))$, where $\pi.\mathrm{permMatrix}(\mathbb{R})$ is the permutation matrix of $\pi$ over $\mathbb{R}$.

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 permutation edit cost equals the fractional edit cost evaluated on the permutation matrix $P_\pi$, we unfold both definitions and reduce to showing that their summands match for arbitrary indices $v, v'$. We then characterize the entries of $P_\pi$ as Kronecker delta indicators, $(P_\pi)_{i, j} = [j = \pi(i)]$. Finally, the double sum over $w$ and $w'$ collapses to the unique non-zero term where $w = \pi(v)$ and $w' = \pi(v')$, which evaluates exactly to $|A_{v, v'} - B_{\pi(v), \pi(v')}|$.

  1. The theorem reduces to showing equality of the summands for arbitrary fixed indices $v, v' \in \{0, \dots, n-1\}$.

    Unfolding the definitions of `perm_edit_cost` and `graph_edit_cost`, both sides are double sums over $v, v'$. By applying sum congruence (`Finset.sum_congr`) to both summations, it suffices to fix $v$ and $v'$ and prove that their corresponding inner expressions are equal.

    lines 4–8

    uses perm_edit_cost, graph_edit_cost, Finset.sum_congr

      simp only [perm_edit_cost, graph_edit_cost]
      apply Finset.sum_congr rfl
      intro v _
      apply Finset.sum_congr rfl
      intro v' _
  2. The permutation matrix entries in the double sum are replaced by Kronecker delta indicators: $(P_\pi)_{v, w} = [w = \pi(v)]$ and $(P_\pi)_{v', w'} = [w' = \pi(v')]$.

    We first prove an auxiliary statement `h1` asserting that $(P_\pi)_{i, j}$ equals $1$ when $j = \pi(i)$ and $0$ otherwise, by unfolding the definitions of `Equiv.Perm.permMatrix` and `PEquiv.toMatrix`. Rewriting with `h1` replaces the matrix entries in the right-hand sum with these indicator conditions.

    lines 9–12

    uses Equiv.Perm.permMatrix, Equiv.toPEquiv, PEquiv.toMatrix, Matrix.of_apply, eq_comm

      have h1 : ∀ (i j : Fin n), (π.permMatrix ℝ) i j = if j = π i then 1 else 0 := by
        intro i j
        simp [Equiv.Perm.permMatrix, Equiv.toPEquiv, PEquiv.toMatrix, Matrix.of_apply, eq_comm]
      simp only [h1]
  3. The double sum over $w$ and $w'$ collapses to the single non-zero term $(w, w') = (\pi(v), \pi(v'))$, which equals $|A_{v, v'} - B_{\pi(v), \pi(v')}|$.

    Using `Finset.sum_eq_single`, the outer sum over $w$ collapses to $w = \pi(v)$ because whenever $w \neq \pi(v)$ the indicator $[w = \pi(v)]$ is $0$ by `if_neg`. Similarly, the inner sum over $w'$ collapses to $w' = \pi(v')$ because terms with $w' \neq \pi(v')$ vanish. At $(w, w') = (\pi(v), \pi(v'))$, both indicator factors equal $1$, leaving $|A_{v, v'} - B_{\pi(v), \pi(v')}|$, which matches the left-hand side. The side conditions requiring the indices to lie in `Finset.univ` hold by `Finset.mem_univ`.

    lines 13–23

    uses Finset.sum_eq_single, if_neg, Finset.mem_univ

      rw [Finset.sum_eq_single (π v)]
      · rw [Finset.sum_eq_single (π v')]
        · simp
        · intro w' _ hw'
          simp [if_neg hw']
        · intro h
          exact absurd (Finset.mem_univ _) h
      · intro w _ hw
        simp [if_neg hw]
      · intro h
        exact absurd (Finset.mem_univ _) h
perm_edit_cost
the permutation edit cost $\sum_{v} \sum_{v'} |A_{v, v'} - B_{\pi(v), \pi(v')}|$
graph_edit_cost
the fractional edit cost $\sum_{v} \sum_{v'} \sum_{w} \sum_{w'} |A_{v, v'} - B_{w, w'}| Q_{v, w} Q_{v', w'}$
Finset.sum_congr
if two finite sums have the same index set and their summands agree everywhere on it, the sums are equal
Equiv.Perm.permMatrix
the permutation matrix $P_\pi$ associated with a permutation $\pi$, defined via its partial equivalence representation
Equiv.toPEquiv
embeds an equivalence into a partial equivalence
PEquiv.toMatrix
the matrix associated with a partial equivalence $f$, with $(i, j)$-entry equal to $1$ if $j \in f(i)$ and $0$ otherwise
Matrix.of_apply
evaluating a matrix defined by a function at indices $(i, j)$ yields the function value at $(i, j)$
eq_comm
equality is symmetric: $a = b \iff b = a$
Finset.sum_eq_single
a finite sum reduces to a single term if every other term vanishes and the chosen index is in the domain
if_neg
an if-then-else expression evaluates to its false branch when the condition is false
Finset.mem_univ
every element of a finite type belongs to the universal set `Finset.univ`

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 permutation edit cost equals the fractional edit cost on the permutation matrix. -/theorem perm_edit_cost_eq_graph_edit_cost {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (π : Equiv.Perm (Fin n)) :    perm_edit_cost A B π = graph_edit_cost A B (π.permMatrix ℝ) := by  simp only [perm_edit_cost, graph_edit_cost]  apply Finset.sum_congr rfl  intro v _  apply Finset.sum_congr rfl  intro v' _  have h1 : ∀ (i j : Fin n), (π.permMatrix ℝ) i j = if j = π i then 1 else 0 := by    intro i j    simp [Equiv.Perm.permMatrix, Equiv.toPEquiv, PEquiv.toMatrix, Matrix.of_apply, eq_comm]  simp only [h1]  rw [Finset.sum_eq_single (π v)]  · rw [Finset.sum_eq_single (π v')]    · simp    · intro w' _ hw'      simp [if_neg hw']    · intro h      exact absurd (Finset.mem_univ _) h  · intro w _ hw    simp [if_neg hw]  · intro h    exact absurd (Finset.mem_univ _) h
See it in the graphDiscuss this resultChallenge it