Recognition: no theorem link
Diagonal parity and loop toggling for symmetric matrices over mathbb F₂
Pith reviewed 2026-05-13 01:36 UTC · model grok-4.3
The pith
Symmetric matrices over F₂ always have their diagonal vector in the column space, with solutions obeying a rank parity rule.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every symmetric matrix M over F₂ the vector diag(M) lies in the column space of M. Moreover, if x satisfies Mx = diag(M), then diag(M)ᵀx ≡ rank(M) (mod 2). The paper gives a complete formula for rank(M + uuᵀ) and nullity(M + uuᵀ) in terms of the original rank and the vector u, and constructs a boundary recursion that computes the number of solutions to M(T,ε)x = ε + α e_r on a rooted tree T with prescribed root coordinate.
What carries the argument
The linear system Mx = diag(M) over F₂ together with the invariant diag(M)ᵀx ≡ rank(M) (mod 2) for symmetric M.
If this is right
- Toggling any single loop in a partially looped graph changes the dimension of the associated solution space by a predictable amount given by the rank formula.
- On any rooted tree the number of solutions with a fixed root value is computable by a finite-state recursion whose states depend only on the local diagonal label.
- Complete rooted d-ary trees admit closed-form nullity expressions that depend on depth and the pattern of diagonal entries.
- When diagonal labels on a complete d-ary tree are eventually periodic in depth, the nullity sequence itself becomes eventually periodic.
Where Pith is reading between the lines
- The parity invariant may allow efficient verification of solution existence without enumerating the full null space.
- The tree recursion could be adapted to compute domination parameters on graphs that admit tree decompositions.
- Rank-one diagonal updates provide a controlled way to interpolate between ordinary adjacency matrices and closed-neighborhood matrices.
Load-bearing premise
The matrix M is required to be symmetric over F₂; the diagonal-in-image statement fails without symmetry.
What would settle it
Exhibit a symmetric matrix M over F₂ together with a vector x such that Mx = diag(M) yet diag(M)ᵀx ≢ rank(M) (mod 2), or produce a symmetric M where diag(M) is not in the column space of M.
read the original abstract
Let $G$ be a finite simple graph with adjacency matrix $A(G)$ over $\mathbb F_2$. The closed neighborhood matrix $A(G)+I$ is central in the theory of odd domination. Sutner proved that every graph has an odd dominating set, equivalently $\mathbf 1$ lies in the range of $A(G)+I$, and Batal proved that every such set has cardinality congruent to $\rank(A(G)+I)$ modulo $2$. We extend this parity phenomenon from closed neighborhood matrices to partially looped graph matrices $A(G)+D$, where $D$ is an arbitrary diagonal matrix over $\mathbb F_2$. Equivalently, we work with arbitrary symmetric matrices $M$ over $\mathbb F_2$ and the natural right-hand side $\diag(M)$. We include a self-contained proof, attributed by Filmus to Alon, that $\diag(M)\in\Img(M)$, and we prove that every solution of $Mx=\diag(M)$ satisfies \[ \diag(M)^\top x\equiv \rank(M)\pmod 2. \] We also give a complete rank and nullity formula for rank-one diagonal perturbations $M\mapsto M+uu^\top$, which in the graph setting describes exactly how toggling loops changes the associated solution spaces. Finally, for rooted trees with arbitrary diagonal labels, we develop a finite-state boundary recursion that counts all solutions of $M(T,\varepsilon)x=\varepsilon+\alpha e_r$ with prescribed root value, and we derive explicit nullity formulas for complete rooted $d$-ary trees. For $d\ge2$, we also prove an eventual-periodicity theorem for complete rooted $d$-ary trees with depth-dependent eventually periodic diagonal labels.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper extends parity results for odd dominating sets from closed neighborhood matrices A(G)+I to arbitrary symmetric matrices M over F_2, with right-hand side diag(M). It includes a self-contained proof that diag(M) lies in the image of M, proves that every solution x to Mx=diag(M) satisfies diag(M)^T x ≡ rank(M) mod 2, derives explicit rank and nullity formulas for rank-one diagonal perturbations M ↦ M + uu^T, and develops a finite-state boundary recursion on rooted trees to count solutions of M(T,ε)x = ε + α e_r with prescribed root value, including nullity formulas for complete d-ary trees and an eventual-periodicity theorem for depth-dependent labels.
Significance. If the results hold, the work unifies and generalizes the Sutner/Batal parity phenomena to a broader class of symmetric F_2-matrices, supplying a self-contained proof (attributed to Filmus/Alon) of the image inclusion together with explicit perturbation formulas and a dynamic-programming recursion whose correctness rests only on symmetry. The tree results, including the periodicity theorem for d≥2, furnish concrete computational and theoretical tools for acyclic instances that may apply to domination problems, lights-out puzzles, and linear systems over F_2.
minor comments (2)
- [Abstract / Introduction] The abstract and introduction refer to 'partially looped graph matrices A(G)+D'; a single sentence clarifying how an arbitrary diagonal D corresponds to loop toggling on the underlying graph would aid readers coming from the graph-theoretic literature.
- [Tree recursion] In the tree-recursion section the state space is described via boundary conditions, but an explicit small table listing the possible states and transitions for d=2 would improve immediate readability without lengthening the text.
Simulated Author's Rebuttal
We thank the referee for their positive summary of the manuscript and for recommending acceptance. The referee's description correctly identifies the core extensions from closed-neighborhood matrices to arbitrary symmetric matrices over F_2, the self-contained image proof, the rank-parity relation, the perturbation formulas, and the tree recursion with its periodicity result.
Circularity Check
No significant circularity; derivations are direct and self-contained
full rationale
The central claims rest on explicit linear-algebra identities over F_2 (e.g., x^T M x = diag(M)^T x in char 2) and a self-contained proof of diag(M) in Img(M) attributed to Filmus/Alon rather than prior self-work. Rank-nullity formulas for rank-one updates and the finite-state tree recursion are standard dynamic-programming constructions whose correctness depends only on the given symmetry and does not reduce any quantity to a fitted parameter or self-citation chain. No step equates a derived object to its own definition or renames an input as a prediction.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption M is symmetric over the field F_2
- standard math Standard vector-space properties over F_2
Reference graph
Works this paper leans on
-
[1]
Batal, Parity of an odd dominating set,Commun
A. Batal, Parity of an odd dominating set,Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat.71 (2022), no. 4, 1023–1028. 15
work page 2022
-
[2]
Filmus, Range of symmetric matrices over GF(2), unpublished manuscript, 2010
Y. Filmus, Range of symmetric matrices over GF(2), unpublished manuscript, 2010. Available athttps: //yuvalfilmus.cs.technion.ac.il/Manuscripts/Range.pdf
work page 2010
-
[3]
V. Pless, On Witt’s theorem for nonalternating symmetric bilinear forms over a field of characteristic 2,Proc. Amer. Math. Soc.15(1964), 979–983
work page 1964
-
[4]
Sutner, Linear cellular automata and the Garden-of-Eden,Math
K. Sutner, Linear cellular automata and the Garden-of-Eden,Math. Intelligencer11(1989), no. 2, 49–53
work page 1989
-
[5]
Wagner, Counting all parity realizable trees,J
S. Wagner, Counting all parity realizable trees,J. Combin. Math. Combin. Comput.75(2010), 159–171. 16
work page 2010
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.