AFTD Auto-Formalizing Theoretical Domains

matrix_block_det_card_sum_le_width

theoremverified

Let K be a field, L a matrix with rows indexed by a finite type ι and columns by a finite type κ, and R a matrix with rows indexed by κ and columns by ι. Let A_1, ..., A_t be finite subsets of ι such that the product L*R vanishes at (a, b) whenever a lies in A_i and b in A_j with i ≠ j, and such that each principal submatrix of L*R on A_i has nonzero determinant. Then the sizes of the A_i sum to at most the cardinality of κ.

Statement

theorem matrix_block_det_card_sum_le_width {K : Type*} [Field K] {ι κ : Type*} [Fintype ι]
    [DecidableEq ι] [Fintype κ] {t : ℕ} (L : Matrix ι κ K) (R : Matrix κ ι K)
    (𝒜 : Fin t → Finset ι)
    (hzero : ∀ i j, i ≠ j → ∀ a ∈ 𝒜 i, ∀ b ∈ 𝒜 j, (L * R) a b = 0)
    (hdet : ∀ i, ((L * R).submatrix (fun x : 𝒜 i => (x : ι)) (fun x : 𝒜 i => (x : ι))).det ≠ 0) :
    ∑ i, (𝒜 i).card ≤ Fintype.card κ
Source
arXiv:2611.12199, proof of Theorem 1.7 (block-diagonal rank count)
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • op_1370_upper_bound_of_matrixLet n be a natural number. Suppose there are a field K, a matrix L with rows indexed by the subsets of Fin n and 2^(n-1) columns, and a…

The proof, explained

The proof applies a rank-counting argument to the restriction of the matrix product L * R to the disjoint union of the sets 𝒜 i. Because off-diagonal blocks vanish and each principal diagonal block has nonzero determinant, this restriction is a block-diagonal matrix N with invertible blocks, hence N is invertible and has full rank ∑ i, |𝒜 i|. On the other hand, N factors through the intermediate type κ via the corresponding submatrices of L and R, so its rank cannot exceed |κ|. Combining the two bounds yields ∑ i, |𝒜 i| ≤ |κ|.

  1. Define N as the restriction of L * R to the disjoint union Σ i, 𝒜 i.

    We assume classical logic and define a square matrix N indexed by pairs (i, a) where i ∈ {0, ..., t - 1} and a ∈ 𝒜 i, with entries N (i, a) (j, b) = (L * R) a b.

    lines 8–9

      classical
      set N : Matrix (Σ i, 𝒜 i) (Σ i, 𝒜 i) K := fun x y => (L * R) x.2 y.2 with hN
  2. N is a block-diagonal matrix whose i-th diagonal block is the principal submatrix of L * R restricted to 𝒜 i.

    We verify equality entrywise for pairs (i, a) and (j, b). If i = j, the entry is on the i-th diagonal block and matches by definition of the block-diagonal matrix (Matrix.blockDiagonal'_apply_eq). If i ≠ j, the entry is off-diagonal, which vanishes by the hypothesis hzero that L * R is zero between distinct blocks, matching the off-diagonal zeros of the block-diagonal matrix (Matrix.blockDiagonal'_apply_ne).

    lines 10–17

    uses Matrix.blockDiagonal'_apply_eq, Matrix.blockDiagonal'_apply_ne

      have hblk : N = Matrix.blockDiagonal'
          (fun i => (L * R).submatrix (fun x : 𝒜 i => (x : ι)) (fun x : 𝒜 i => (x : ι))) := by
        ext ⟨i, a⟩ ⟨j, b⟩
        by_cases h : i = j
        · subst h
          simp [hN, Matrix.blockDiagonal'_apply_eq]
        · rw [Matrix.blockDiagonal'_apply_ne _ _ _ h]
          exact hzero i j h a a.2 b b.2
  3. The determinant of N is a unit in K, so N is invertible.

    To show det N is a unit, it suffices to construct a right inverse for N (Matrix.isUnit_det_of_right_inverse). We take the block-diagonal matrix whose diagonal blocks are the inverses of the individual diagonal blocks of N. Multiplying these block-diagonal matrices acts blockwise (Matrix.blockDiagonal'_mul). Since each diagonal block has nonzero determinant by hypothesis hdet, its determinant is a unit in the field K (isUnit_iff_ne_zero.mpr), so each block multiplied by its nonsingular inverse is the identity matrix (Matrix.mul_nonsing_inv). The block diagonal of identity blocks is the overall identity matrix (Matrix.blockDiagonal'_one).

    lines 18–24

    uses Matrix.isUnit_det_of_right_inverse, Matrix.blockDiagonal'_mul, Matrix.blockDiagonal'_one, Matrix.mul_nonsing_inv, isUnit_iff_ne_zero.mpr

      have hunitN : IsUnit N.det := by
        refine Matrix.isUnit_det_of_right_inverse (B := Matrix.blockDiagonal' (fun i =>
          ((L * R).submatrix (fun x : 𝒜 i => (x : ι)) (fun x : 𝒜 i => (x : ι)))⁻¹)) ?_
        rw [hblk, ← Matrix.blockDiagonal'_mul, ← Matrix.blockDiagonal'_one]
        congr 1
        funext i
        exact Matrix.mul_nonsing_inv _ (isUnit_iff_ne_zero.mpr (hdet i))
  4. N factors through κ as the product of a submatrix of L and a submatrix of R.

    Entrywise, the product of the submatrix of L (rows indexed by Σ i, 𝒜 i and columns by κ) and the submatrix of R (rows indexed by κ and columns by Σ i, 𝒜 i) evaluates at ((i, a), (j, b)) to the sum over k ∈ κ of L a k * R k b (Matrix.mul_apply), which is precisely (L * R) a b = N (i, a) (j, b).

    lines 25–28

    uses Matrix.mul_apply

      have hfac : N = Matrix.of (fun (x : Σ i, 𝒜 i) k => L x.2 k) *
          Matrix.of (fun k (y : Σ i, 𝒜 i) => R k y.2) := by
        ext x y
        simp [hN, Matrix.mul_apply]
  5. The rank of N equals the total dimension of the disjoint union, ∑ i, |𝒜 i|.

    Since det N is a unit, N is an invertible matrix (Matrix.isUnit_iff_isUnit_det). Over any commutative ring satisfying the strong rank condition, such as a field, an invertible matrix has full rank equal to its dimension (Matrix.rank_of_isUnit).

    lines 29–30

    uses Matrix.rank_of_isUnit, Matrix.isUnit_iff_isUnit_det

      have hrank : N.rank = Fintype.card (Σ i, 𝒜 i) :=
        Matrix.rank_of_isUnit N ((Matrix.isUnit_iff_isUnit_det N).mpr hunitN)
  6. The rank of N is at most |κ|.

    Using the factorization N = L' * R', the rank of a matrix product is bounded by the rank of the first factor (Matrix.rank_mul_le_left), which in turn is bounded by its number of columns, |κ| (Matrix.rank_le_card_width).

    lines 31–33

    uses Matrix.rank_mul_le_left, Matrix.rank_le_card_width

      have hle : N.rank ≤ Fintype.card κ := by
        rw [hfac]
        exact (Matrix.rank_mul_le_left _ _).trans (Matrix.rank_le_card_width _)
  7. The sum of the sizes of the sets 𝒜 i is at most |κ|.

    Substituting the rank of N into the rank bound and rewriting the cardinality of the disjoint union Σ i, 𝒜 i as the sum of cardinalities ∑ i, |𝒜 i| (Fintype.card_sigma) yields the final inequality ∑ i, |𝒜 i| ≤ |κ|.

    lines 34–35

    uses Fintype.card_sigma

      rw [hrank, Fintype.card_sigma] at hle
      simpa using hle
Matrix.blockDiagonal'_apply_eq
The diagonal block entries of a block-diagonal matrix agree with the entries of the corresponding block matrix.
Matrix.blockDiagonal'_apply_ne
The off-diagonal block entries of a block-diagonal matrix (where the block indices differ) are zero.
Matrix.isUnit_det_of_right_inverse
A square matrix that has a right inverse has an invertible (unit) determinant.
Matrix.blockDiagonal'_mul
Multiplication of block-diagonal matrices with matching block structures is performed blockwise.
Matrix.blockDiagonal'_one
A block-diagonal matrix whose diagonal blocks are identity matrices is the overall identity matrix.
Matrix.mul_nonsing_inv
A square matrix whose determinant is a unit, multiplied on the right by its nonsingular inverse, equals the identity matrix.
isUnit_iff_ne_zero.mpr
In a field, any nonzero element is a unit (invertible).
Matrix.mul_apply
The (i, k)-th entry of a matrix product M * N is the sum over j of M i j * N j k.
Matrix.rank_of_isUnit
An invertible square matrix has full rank equal to its dimension.
Matrix.isUnit_iff_isUnit_det
A square matrix is invertible if and only if its determinant is a unit.
Matrix.rank_mul_le_left
The rank of a matrix product A * B is at most the rank of A.
Matrix.rank_le_card_width
The rank of a matrix is at most its number of columns (width).
Fintype.card_sigma
The cardinality of a disjoint union (sigma type) of finite types is the sum of the cardinalities of the individual types.

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

/-- Rank counting: nonsingular principal blocks of a block-diagonal restriction of a product L*R through κ have total size at most |κ|. -/theorem matrix_block_det_card_sum_le_width {K : Type*} [Field K] {ι κ : Type*} [Fintype ι]    [DecidableEq ι] [Fintype κ] {t : ℕ} (L : Matrix ι κ K) (R : Matrix κ ι K)    (𝒜 : Fin t → Finset ι)    (hzero : ∀ i j, i ≠ j → ∀ a ∈ 𝒜 i, ∀ b ∈ 𝒜 j, (L * R) a b = 0)    (hdet : ∀ i, ((L * R).submatrix (fun x : 𝒜 i => (x : ι)) (fun x : 𝒜 i => (x : ι))).det ≠ 0) :    ∑ i, (𝒜 i).card ≤ Fintype.card κ := by  classical  set N : Matrix (Σ i, 𝒜 i) (Σ i, 𝒜 i) K := fun x y => (L * R) x.2 y.2 with hN  have hblk : N = Matrix.blockDiagonal'      (fun i => (L * R).submatrix (fun x : 𝒜 i => (x : ι)) (fun x : 𝒜 i => (x : ι))) := by    ext ⟨i, a⟩ ⟨j, b⟩    by_cases h : i = j    · subst h      simp [hN, Matrix.blockDiagonal'_apply_eq]    · rw [Matrix.blockDiagonal'_apply_ne _ _ _ h]      exact hzero i j h a a.2 b b.2  have hunitN : IsUnit N.det := by    refine Matrix.isUnit_det_of_right_inverse (B := Matrix.blockDiagonal' (fun i =>      ((L * R).submatrix (fun x : 𝒜 i => (x : ι)) (fun x : 𝒜 i => (x : ι)))⁻¹)) ?_    rw [hblk, ← Matrix.blockDiagonal'_mul, ← Matrix.blockDiagonal'_one]    congr 1    funext i    exact Matrix.mul_nonsing_inv _ (isUnit_iff_ne_zero.mpr (hdet i))  have hfac : N = Matrix.of (fun (x : Σ i, 𝒜 i) k => L x.2 k) *      Matrix.of (fun k (y : Σ i, 𝒜 i) => R k y.2) := by    ext x y    simp [hN, Matrix.mul_apply]  have hrank : N.rank = Fintype.card (Σ i, 𝒜 i) :=    Matrix.rank_of_isUnit N ((Matrix.isUnit_iff_isUnit_det N).mpr hunitN)  have hle : N.rank ≤ Fintype.card κ := by    rw [hfac]    exact (Matrix.rank_mul_le_left _ _).trans (Matrix.rank_le_card_width _)  rw [hrank, Fintype.card_sigma] at hle  simpa using hle
See it in the graphDiscuss this resultChallenge it