AFTD Auto-Formalizing Theoretical Domains

matrix_det_sum_rows

theoremverified

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)}$.

  1. 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.

    lines 4–8

    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
  2. 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))$.

    lines 9–10

    uses Matrix.sum_apply

      rw [hdet (∑ k : Fin m, A k)]
      simp only [Matrix.sum_apply]
  3. 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.

    lines 11–12

      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 ?_]
  4. 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.

    lines 13–17

    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
  5. 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$.

    lines 18–22

    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$.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it