simple_graph_adj_row_add_mem_range
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
- simple_graph_nut_graph_diameter_three_has_binary_vectorLet G be a finite simple nut graph on a finite vertex set. If the diameter of G is 3, then there exists a non-zero (0,1)-vector in the row…
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.
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.
uses
SimpleGraph.isSymm_adjMatrixset A : Matrix V V ℝ := G.adjMatrix ℝ have hsymm : A.IsSymm := SimpleGraph.isSymm_adjMatrix G
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.
uses
Matrix.mulVec_single_onehave 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
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).
uses
Matrix.toLin'_apply,LinearMap.map_addrw [hrow u, hrow v] rw [← Matrix.toLin'_apply, ← Matrix.toLin'_apply] rw [← LinearMap.map_add]
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.
uses
LinearMap.mem_range_selfexact 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
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.
/-- 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 _ _