AFTD Auto-Formalizing Theoretical Domains

cycle_weighted_adjacency_matrix_rank_le

theoremverified

For every natural number m, field F, and function t : Fin (2 * m) → F, the rank of cycle_weighted_adjacency_matrix (2 * m) t is at most 2 * m.

Statement

theorem cycle_weighted_adjacency_matrix_rank_le
    {F : Type*} [Field F] (m : ℕ) (t : Fin (2 * m) → F) :
    (cycle_weighted_adjacency_matrix (2 * m) t).rank ≤ 2 * m
Source
arXiv:2610.27080, Eq. (13)
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cycle_weighted_adjacency_matrixFor a type α equipped with AddZeroClass, a natural number n, and a function t : Fin n → α, cycle_weighted_adjacency_matrix n t is the Fin…

Read back from the Lean

For any field F, any natural number m, and any weight function t : Fin (2 * m) → F, the rank of cycle_weighted_adjacency_matrix (2 * m) t is at most 2 * m.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem bounds the rank of the weighted adjacency matrix of the cycle graph C_{2m} by its dimension 2m. This holds directly because the matrix has column index set Fin (2 * m), and the rank of any matrix cannot exceed the cardinality of its column index set.

  1. The rank of the weighted adjacency matrix is at most 2 * m.

    The rank of any matrix is at most the number of its columns (by `Matrix.rank_le_card_width`). Since the column index type is `Fin (2 * m)`, whose cardinality is 2 * m (by `Fintype.card_fin`), chaining the inequality with this cardinality equality gives the bound.

    line 4

    uses Matrix.rank_le_card_width, Fintype.card_fin

        (cycle_weighted_adjacency_matrix (2 * m) t).rank ≤ 2 * m := (Matrix.rank_le_card_width _).trans_eq (Fintype.card_fin _)
Matrix.rank_le_card_width
The rank of a matrix is at most the cardinality of its column index type.
Fintype.card_fin
The cardinality of the standard finite set Fin n is n.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The rank of the weighted adjacency matrix of C_{2m} is at most 2m. -/theorem cycle_weighted_adjacency_matrix_rank_le    {F : Type*} [Field F] (m : ℕ) (t : Fin (2 * m) → F) :    (cycle_weighted_adjacency_matrix (2 * m) t).rank ≤ 2 * m := (Matrix.rank_le_card_width _).trans_eq (Fintype.card_fin _)
See it in the graphDiscuss this resultChallenge it