AFTD Auto-Formalizing Theoretical Domains

simple_graph_adj_row_add_mem_range

theoremverified

For any two vertices u and v of a finite simple graph, the sum of their adjacency matrix rows lies in the row space (the range of the adjacency matrix linear map) over ℝ.

Statement

theorem simple_graph_adj_row_add_mem_range
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) :
    G.adjMatrix ℝ u + G.adjMatrix ℝ v ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ))
Source
arXiv:2611.08244 Theorem 4.1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, and any two vertices $u, v \in V$, the sum of the $u$-th row and the $v$-th row of the real adjacency matrix of $G$ (as elements of $V \to \mathbb{R}$) belongs to the range (column space) of the linear map on $V \to \mathbb{R}$ represented by the adjacency matrix of $G$.

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

To show that the sum of rows A u + A v of the adjacency matrix belongs to the range of the induced linear map, the proof expresses each row as the matrix-vector product A e_w, where e_w is the standard basis vector at w. Because the adjacency matrix of a simple graph is symmetric, the w-th row equals the w-th column, which is A e_w. By linearity, A u + A v = A(e_u + e_v), which is visibly in the range of the linear map.

  1. The adjacency matrix A of G is symmetric.

    We introduce the notation A for the adjacency matrix G.adjMatrix ℝ. Because G is an undirected simple graph, its adjacency matrix is symmetric, which is given by SimpleGraph.isSymm_adjMatrix.

    lines 6–7

    uses SimpleGraph.isSymm_adjMatrix

      set A : Matrix V V ℝ := G.adjMatrix ℝ
      have hsymm : A.IsSymm := SimpleGraph.isSymm_adjMatrix G
  2. For each vertex w, the row A w equals the matrix-vector product A e_w, where e_w is the standard basis vector at w.

    Multiplying A by the standard basis vector e_w = Pi.single w 1 produces the w-th column of A (Matrix.mulVec_single_one). Since A is symmetric (hsymm), entry (w, i) equals entry (i, w) for all i, so the w-th row equals the w-th column as functions of i.

    lines 8–12

    uses Matrix.mulVec_single_one

      have hrow : ∀ w : V, A w = A.mulVec (Pi.single w 1) := by
        intro w
        rw [Matrix.mulVec_single_one]
        funext i
        exact hsymm.apply i w
  3. The sum of rows A u + A v equals the image of e_u + e_v under the linear map toLin' A.

    Rewriting A u and A v using the row formula hrow expresses their sum as A e_u + A e_v. Matrix-vector multiplication by A is the evaluation of the linear map toLin' A (Matrix.toLin'_apply), and by linearity (LinearMap.map_add), (toLin' A)(e_u) + (toLin' A)(e_v) combines into (toLin' A)(e_u + e_v).

    lines 13–15

    uses Matrix.toLin'_apply, LinearMap.map_add

      rw [hrow u, hrow v]
      rw [← Matrix.toLin'_apply, ← Matrix.toLin'_apply]
      rw [← LinearMap.map_add]
  4. The vector (toLin' A)(e_u + e_v) belongs to the range of toLin' A.

    For any linear map f and vector x, the value f(x) is in the range of f (LinearMap.mem_range_self). Applying this to f = toLin' A and x = e_u + e_v finishes the proof.

    line 16

    uses LinearMap.mem_range_self

      exact LinearMap.mem_range_self _ _
SimpleGraph.isSymm_adjMatrix
The adjacency matrix of a simple graph is symmetric.
Matrix.mulVec_single_one
Multiplying a matrix by the standard basis vector single_j(1) yields its j-th column.
Matrix.toLin'_apply
The linear map toLin' M associated to a matrix M acts on a vector v by matrix-vector multiplication M v.
LinearMap.map_add
A linear map preserves addition: f(x + y) = f(x) + f(y).
LinearMap.mem_range_self
For any linear map f and element x, f(x) belongs to the range of f.

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

/-- The sum of two rows of the adjacency matrix belongs to the range of the adjacency matrix linear map. -/theorem simple_graph_adj_row_add_mem_range    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) :    G.adjMatrix ℝ u + G.adjMatrix ℝ v ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ)) := by  set A : Matrix V V ℝ := G.adjMatrix ℝ  have hsymm : A.IsSymm := SimpleGraph.isSymm_adjMatrix G  have hrow : ∀ w : V, A w = A.mulVec (Pi.single w 1) := by    intro w    rw [Matrix.mulVec_single_one]    funext i    exact hsymm.apply i w  rw [hrow u, hrow v]  rw [← Matrix.toLin'_apply, ← Matrix.toLin'_apply]  rw [← LinearMap.map_add]  exact LinearMap.mem_range_self _ _
See it in the graphDiscuss this resultChallenge it