perm_edit_cost
def
The 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 $v, v' \in \{0, \dots, n-1\}$ of $|A(v, v') - B(\pi(v), \pi(v'))|$.
Statement
def perm_edit_cost {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (π : Equiv.Perm (Fin n)) : ℝ- Defined in
- arXiv:2611.05048 Section 3, line 325
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Used by 3
- perm_edit_cost_eq_graph_edit_costFor any permutation $\pi$ of $\{0, \dots, n-1\}$ and matrices $A, B$, the permutation edit cost $\mathcal{C}_{\mathsf{ed}}(\pi)$ equals…
- simple_graph_edit_cost_permutation_decomposition_le_two_mulFor any simple graphs $G$ and $H$ on $n$ vertices and any doubly stochastic matrix $Q$ with a convex decomposition into permutation…
- 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 a natural number n, two n × n real matrices A and B (represented as functions Fin n → Fin n → ℝ), and a permutation π of Fin n, perm_edit_cost A B π is defined as the real number equal to the double sum over all v, v' : Fin n of |A v v' - B (π v) (π v')|.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The edit cost of a permutation π between two matrices A and B. -/ def perm_edit_cost {n : ℕ} (A B : Matrix (Fin n) (Fin n) ℝ) (π : Equiv.Perm (Fin n)) : ℝ := ∑ v : Fin n, ∑ v' : Fin n, |A v v' - B (π v) (π v')|