§7, p. 23 — the coefficient matrix of the system (RS)–(CS) is totally unimodular
ProvedProConChoice.Rational.rs_cs_matrix_tuLet and be finite index sets. Consider the linear system in the unknowns , , consisting of the row equations for (RS) and the column equations for (CS). Its coefficient matrix has one row for each , with a in the columns , , and one row for each , with a in the columns , , and zeros elsewhere. This matrix is totally unimodular:
In Section 7, indexes the prefixes ordering and the alternatives of ; total unimodularity together with Lemma 4 makes the weights of the next step integral.
Formalization Note The matrix is indexed by rows I ⊕ J and columns I × J. The paper's description of the rows by integer indices on p. 23 does not match its own column ordering; the matrix stated here is the coefficient matrix of (RS)–(CS) that the text describes in words.
import Mathlib
namespace ProConChoice.Rational
/-- Section 7 (p. 23): the coefficient matrix of the system (RS)–(CS) is totally unimodular. Its
columns are the variables `λᵢⱼ`, `(i, j) ∈ I × J`; the row of `i ∈ I` (RS) has a `1` exactly in the
columns `(i, j)`, `j ∈ J`, and the row of `j ∈ J` (CS) has a `1` exactly in the columns `(i, j)`,
`i ∈ I`. -/
theorem rs_cs_matrix_tu {I J : Type*} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J] :
(Matrix.of (fun (r : I ⊕ J) (c : I × J) =>
Sum.elim (fun i => if c.1 = i then (1 : ℝ) else 0)
(fun j => if c.2 = j then (1 : ℝ) else 0) r)).IsTotallyUnimodular := by sorry
end ProConChoice.Rational
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.