matrix_cut_norm
def
The cut norm of a real matrix M indexed by finite sets α and β is the maximum over all subsets S ⊆ α and T ⊆ β of the absolute value of the sum of M(i, j) for i ∈ S and j ∈ T.
Statement
def matrix_cut_norm {α β : Type*} [Fintype α] [Fintype β] (M : α → β → ℝ) : ℝ
- Defined in
- arXiv:2611.05048 Section 1; Frieze-Kannan 1999
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Used by 2
- matrix_cut_norm_zeroThe cut norm of the all-zero matrix is zero.
- graph_cut_distThe unnormalized cut distance d_□(G, H) between two simple graphs G and H on the same finite vertex set V is the minimum over all…
Read back from the Lean
For finite types α and β, and a real-valued matrix (or function) M : α → β → ℝ, matrix_cut_norm M is defined as the maximum (supremum over the finite set of all pairs) over all pairs of subsets (S, T) (where S : Finset α and T : Finset β) of the absolute value of the sum ∑ i ∈ S, ∑ j ∈ T, M i j.
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 cut norm of a real matrix indexed by finite types α and β. -/ def matrix_cut_norm {α β : Type*} [Fintype α] [Fintype β] (M : α → β → ℝ) : ℝ := (Finset.univ : Finset (Finset α × Finset β)).sup' Finset.univ_nonempty (fun (S, T) => |∑ i ∈ S, ∑ j ∈ T, M i j|)