matrix_det_sum_rows
Multilinearity of the determinant in the rows: the determinant of a sum of matrices ∑_{k<m} A_k is the sum, over all functions f : Fin n → Fin m choosing one summand per row, of the determinant of the matrix whose i-th row is the i-th row of A_{f i}.
Statement
theorem matrix_det_sum_rows {n m : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ) : (∑ k : Fin m, A k).det = ∑ f : Fin n → Fin m, (Matrix.of (fun i j => A (f i) i j)).det
- Source
- step towards tournament_arborescence_hadamard_bound
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof establishes row-wise multilinearity of the determinant by expanding the determinant of $\sum_k A_k$ using the row-wise Leibniz formula, expressing each entry as a sum over matrix summands $\sum_k A_k(i, \sigma(i))$. Distributing the product over rows converts the product of sums into a sum over choice functions $f \colon \operatorname{Fin} n \to \operatorname{Fin} m$ that select one matrix summand per row. Finally, exchanging the summation order between permutations and choice functions recognizes the inner sum for each fixed $f$ as the determinant of the matrix whose $i$-th row comes from $A_{f(i)}$.
The determinant of an $n \times n$ matrix $M$ is given by the row-wise Leibniz formula: $\det(M) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i} M_{i, \sigma(i)}$.
Mathlib's standard Leibniz formula `Matrix.det_apply'` expands determinants along columns. Since a matrix and its transpose have the same determinant (`Matrix.det_transpose`), applying `Matrix.det_apply'` to $M^T$ expresses $\det(M) = \det(M^T)$ as $\sum_\sigma \operatorname{sgn}(\sigma) \prod_i M^T_{\sigma(i), i}$, which definitionally simplifies to the row-wise formula.
uses
Matrix.det_transpose,Matrix.det_apply'have hdet : ∀ M : Matrix (Fin n) (Fin n) ℝ, M.det = ∑ σ : Equiv.Perm (Fin n), (Equiv.Perm.sign σ : ℝ) * ∏ i, M i (σ i) := by intro M rw [← Matrix.det_transpose M, Matrix.det_apply'] rfl
The determinant of the sum $\sum_k A_k$ expands to $\sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i} \sum_{k} A_k(i, \sigma(i))$.
We apply the row-expansion formula `hdet` to the matrix sum $\sum_k A_k$. Using `Matrix.sum_apply`, each entry $(\sum_k A_k)_{i, \sigma(i)}$ is rewritten as the sum of the entries $\sum_k A_k(i, \sigma(i))$.
uses
Matrix.sum_applyrw [hdet (∑ k : Fin m, A k)] simp only [Matrix.sum_apply]
The determinant expression is rewritten by expanding the product of sums into a sum over all choice functions $f \colon \operatorname{Fin} n \to \operatorname{Fin} m$.
We rewrite the product of row sums into a double sum $\sum_\sigma \sum_f \operatorname{sgn}(\sigma) \prod_i A_{f(i)}(i, \sigma(i))$ using a `show ... from ?_` assertion. This leaves two goals: finishing the main theorem given this expansion, and subsequently proving the expansion itself.
rw [show (∑ σ : Equiv.Perm (Fin n), (Equiv.Perm.sign σ : ℝ) * ∏ i, ∑ k : Fin m, A k i (σ i)) = ∑ σ : Equiv.Perm (Fin n), ∑ f : Fin n → Fin m, (Equiv.Perm.sign σ : ℝ) * ∏ i, A (f i) i (σ i) from ?_]
Exchanging the summation order expresses the sum as the sum over choice functions $f$ of the determinants of the corresponding row-selected matrices.
Using `Finset.sum_comm`, we exchange the sums over permutations $\sigma$ and choice functions $f$. By `Finset.sum_congr`, it suffices to show that for each fixed $f$, the inner sum over $\sigma$ equals the determinant of the matrix whose $i$-th row is taken from $A_{f(i)}$. Applying the row-expansion formula `hdet` to that matrix and simplifying definitions closes this branch.
uses
Finset.sum_comm,Finset.sum_congr· rw [Finset.sum_comm] apply Finset.sum_congr rfl intro f _ rw [hdet (Matrix.of (fun i j => A (f i) i j))] simp
The product of row sums distributes over choice functions: $\sum_\sigma \operatorname{sgn}(\sigma) \prod_i \sum_k A_k(i, \sigma(i)) = \sum_\sigma \sum_f \operatorname{sgn}(\sigma) \prod_i A_{f(i)}(i, \sigma(i))$.
By `Finset.sum_congr`, it suffices to verify the equality for each permutation $\sigma$. Distributing the product over sums with `Finset.prod_univ_sum` yields a sum over the product space of choices, which `Fintype.piFinset_univ` identifies with the universal set of functions $f \colon \operatorname{Fin} n \to \operatorname{Fin} m$. Finally, `Finset.mul_sum` moves the scalar $\operatorname{sgn}(\sigma)$ inside the sum over $f$.
uses
Finset.sum_congr,Finset.prod_univ_sum,Fintype.piFinset_univ,Finset.mul_sum· apply Finset.sum_congr rfl intro σ _ rw [Finset.prod_univ_sum] rw [Fintype.piFinset_univ] rw [Finset.mul_sum]
Matrix.det_apply'- The Leibniz formula for the determinant expanded along columns: $\det(M) = \sum_{\sigma} \operatorname{sgn}(\sigma) \prod_i M_{\sigma(i), i}$.
Matrix.det_transpose- The determinant of the transpose of a square matrix equals the determinant of the matrix.
Matrix.sum_apply- The $(i, j)$-th entry of a finite sum of matrices is the sum of their $(i, j)$-th entries.
Finset.sum_comm- The order of two finite summations can be exchanged.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element.
Finset.prod_univ_sum- A product of finite sums over a finite index set distributes into a sum of products over choice functions in the Cartesian product of index sets.
Fintype.piFinset_univ- The Cartesian product of universal sets over a finite type is the universal set of all choice functions.
Finset.mul_sum- Left-multiplication distributes over finite summation: $a \sum_i b_i = \sum_i a b_i$.
- In Mathlib, the Leibniz expansion `Matrix.det_apply'` expands along columns; the proof begins by deriving the row-wise Leibniz formula `hdet` by transposing the matrix.
- The proof uses `rw [show ... from ?_]` to rewrite with an intermediate expansion identity, which Lean splits into two branches: completing the main equality (lines 13–17) and proving the expansion identity (lines 18–22).
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.
/-- Row-wise multilinearity: `det` of a sum of matrices expands as a sum over the choice of one summand per row. -/theorem matrix_det_sum_rows {n m : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ) : (∑ k : Fin m, A k).det = ∑ f : Fin n → Fin m, (Matrix.of (fun i j => A (f i) i j)).det := by -- Use the determinant formula expanding along rows (the transpose of `det_apply'`). have hdet : ∀ M : Matrix (Fin n) (Fin n) ℝ, M.det = ∑ σ : Equiv.Perm (Fin n), (Equiv.Perm.sign σ : ℝ) * ∏ i, M i (σ i) := by intro M rw [← Matrix.det_transpose M, Matrix.det_apply'] rfl rw [hdet (∑ k : Fin m, A k)] simp only [Matrix.sum_apply] rw [show (∑ σ : Equiv.Perm (Fin n), (Equiv.Perm.sign σ : ℝ) * ∏ i, ∑ k : Fin m, A k i (σ i)) = ∑ σ : Equiv.Perm (Fin n), ∑ f : Fin n → Fin m, (Equiv.Perm.sign σ : ℝ) * ∏ i, A (f i) i (σ i) from ?_] · rw [Finset.sum_comm] apply Finset.sum_congr rfl intro f _ rw [hdet (Matrix.of (fun i j => A (f i) i j))] simp · apply Finset.sum_congr rfl intro σ _ rw [Finset.prod_univ_sum] rw [Fintype.piFinset_univ] rw [Finset.mul_sum]