is_doubly_stochastic
def
A real matrix Q on a finite set V is doubly stochastic if all entries are nonnegative and all row and column sums equal 1.
Statement
def is_doubly_stochastic {V : Type*} [Fintype V] (Q : V → V → ℝ) : Prop
- Defined in
- arXiv:2611.05048 Section 2; Birkhoff 1946
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Used by 2
- 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 finite type V, a function (or matrix) Q : V → V → ℝ is defined to be doubly stochastic (is_doubly_stochastic Q) if and only if:
1. For all i, j : V, 0 ≤ Q i j (every entry is non-negative),
2. For all i : V, the sum over all j : V of Q i j equals 1 (each row sum is 1), and
3. For all j : V, the sum over all i : V of Q i j equals 1 (each column sum is 1).
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
/-- A matrix Q is doubly stochastic if its entries are nonnegative and every row and column sums to 1. -/ def is_doubly_stochastic {V : Type*} [Fintype V] (Q : V → V → ℝ) : Prop := (∀ i j, 0 ≤ Q i j) ∧ (∀ i, ∑ j, Q i j = 1) ∧ (∀ j, ∑ i, Q i j = 1)