perm_edit_cost_eq_graph_edit_cost
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
- graph_edit_cost_permutation_decomposition_le_two_mulLet $Q$ be an $n \times n$ doubly stochastic matrix with a convex decomposition $Q = \sum_{i \in \iota} w_i P_{\pi_i}$, where $w_i \ge 0$,…
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')}|$.
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.
uses
perm_edit_cost,graph_edit_cost,Finset.sum_congrsimp only [perm_edit_cost, graph_edit_cost] apply Finset.sum_congr rfl intro v _ apply Finset.sum_congr rfl intro v' _
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.
uses
Equiv.Perm.permMatrix,Equiv.toPEquiv,PEquiv.toMatrix,Matrix.of_apply,eq_commhave 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]
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`.
uses
Finset.sum_eq_single,if_neg,Finset.mem_univrw [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`
- The lemma `Finset.sum_eq_single` formally requires checking that the designated index belongs to the index set `Finset.univ`; in ordinary mathematics, this is immediate since the sum runs over the entire finite type `Fin n`.
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 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