Diagonal parity and loop toggling for symmetric matrices over $\mathbb F_2$

Mohsen Aliabadi

arxiv: 2605.11056 · v2 · pith:UIEA7ZSFnew · submitted 2026-05-11 · 🧮 math.CO

Diagonal parity and loop toggling for symmetric matrices over mathbb F₂

Mohsen Aliabadi This is my paper

Pith reviewed 2026-06-30 22:24 UTC · model grok-4.3

classification 🧮 math.CO

keywords symmetric matrices over F2diagonal equationparity rigidityrank-one diagonal updateodd-dominationloop togglingrooted treesboundary recursion

0 comments

The pith

Every solution x to Mx=diag(M) for symmetric M over F2 satisfies diag(M)^T x ≡ rank(M) mod 2

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

For any symmetric matrix M over the field with two elements the vector diag(M) always lies in the column space of M, making the affine equation Mx=diag(M) solvable. The paper strengthens the mere existence of solutions to a parity rigidity result: the inner product diag(M)^T x is congruent to the rank of M modulo 2 for every solution x. This uniform parity extends earlier odd-domination and parity theorems from closed-neighborhood matrices to arbitrary symmetric matrices that encode partially looped graphs. Additional results supply an exact three-case formula for the change in rank and nullity under the diagonal update M+uu^T that corresponds to toggling a set of loops, together with a finite-state recursion on rooted trees that counts all solutions via affine subspaces of F2^2 and yields eventual quasigeometric nullity formulas under periodic labeling.

Core claim

The central claim is that the solvability of Mx=diag(M) is accompanied by a parity rigidity: diag(M)^T x is the same modulo 2 for all solutions x, and equals rank(M) mod 2. For graph adjacency plus diagonal, this unifies odd-domination and parity theorems under a single statement that holds for any choice of which vertices have loops.

What carries the argument

The parity rigidity condition diag(M)^T x ≡ rank(M) (mod 2) that is independent of the choice of solution to the diagonal system, together with the three-case rank-nullity formula for the rank-one diagonal update M+uu^T.

If this is right

The parity condition extends Sutner's odd-domination theorem and Batal's parity theorem from closed-neighborhood matrices to arbitrary partially looped graph matrices A(G)+D.
Simultaneous loop toggling on the support of any vector u changes rank and nullity according to an exact three-case formula.
The boundary recursion using affine subspaces of F2^2 counts every generalized odd-domination pattern on a rooted tree with arbitrary binary diagonal labels.
For complete rooted trees whose depth labels are eventually periodic the nullity eventually follows a quasigeometric formula.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The uniform parity may permit computing the common value without enumerating all solutions of the linear system.
The tree recursion could be used to obtain closed-form nullity expressions for additional families of labeled trees beyond the complete case.
The three-case update formula supplies an algebraic tool for tracking rank under sequences of diagonal modifications over F2.

Load-bearing premise

That the parity of diag(M)^T x is forced to be independent of which particular solution x is chosen.

What would settle it

A symmetric matrix M over F2 together with two solutions x and y to Mx=diag(M) such that diag(M)^T x and diag(M)^T y differ modulo 2.

read the original abstract

Let $M$ be a symmetric matrix over $\mathbb F_2$, and let $\diag(M)$ be its diagonal vector. It is known that \[ \diag(M)\in \Img(M). \] Thus the affine system $Mx=\diag(M)$ is always solvable. We strengthen this existence statement to a parity rigidity theorem: every solution satisfies \[ \diag(M)^T x\equiv \rank(M)\pmod 2 . \] For graph matrices this gives a common extension of Sutner's odd-domination theorem and Batal's parity theorem from closed-neighborhood matrices $A(G)+I$ to arbitrary partially looped graph matrices $A(G)+D$. We also study how rank and nullity change when loops are toggled. Algebraically, simultaneous loop toggling on the support of a vector $u$ is the diagonal rank-one update $M\mapsto M+uu^T$. We prove an exact three-case rank and nullity formula for this update. Finally, for rooted trees with arbitrary binary diagonal labels, we give a finite-state boundary recursion using affine subspaces of $\mathbb F_2^2$. This recursion counts all generalized odd-domination patterns and implies eventual quasigeometric nullity formulas for complete rooted trees with eventually periodic depth labels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The parity rigidity theorem and the exact three-case rank formula for uu^T updates are the concrete new pieces, with the tree recursion as a practical add-on.

read the letter

The main takeaway is the strengthening of the known fact that diag(M) lies in the image of symmetric M over F2: every solution x to Mx = diag(M) now satisfies the parity condition diag(M)^T x ≡ rank(M) mod 2. The paper also gives a precise three-case formula for rank and nullity after the update M + uu^T, which models simultaneous loop toggling, plus a finite-state recursion on rooted trees with binary diagonal labels that counts generalized odd-domination patterns.

This unifies Sutner's odd-domination theorem and Batal's parity result for closed-neighborhood matrices into a statement that works for arbitrary symmetric matrices and partially looped graphs. The rank formula is stated as exact rather than asymptotic, and the recursion uses affine subspaces of F2^2 to stay finite-state, which directly yields the quasigeometric nullity claims for eventually periodic complete trees.

The stress-test checks confirm the parity holds on small cases and follows from the orthogonal complement property once the constant value is pinned to rank mod 2. No counterexamples appear, and the claims do not reduce to prior theorems in a circular way.

Soft spots are limited. The three-case split for the update needs to handle all kernel and image interactions cleanly, but the abstract presents it as exact so the manuscript presumably verifies the cases. The recursion is described as boundary-type, which should be straightforward to implement and check.

This is for people working on combinatorial linear algebra over F2 or graph algorithms involving domination and rank. A reader who needs explicit rank formulas or computable counts on labeled trees will find usable statements here.

It deserves a serious referee because the algebraic claims are specific, the extensions are concrete, and the computational tool is reproducible in principle.

Referee Report

0 major / 4 minor

Summary. The paper proves a parity rigidity theorem for symmetric matrices M over F_2: the system Mx = diag(M) is always solvable, and every solution x satisfies diag(M)^T x ≡ rank(M) (mod 2). It derives an exact three-case formula for the rank and nullity of the update M + uu^T, extends odd-domination results to arbitrary looped graphs, and gives a finite-state boundary recursion on rooted trees that counts generalized odd-domination patterns and yields quasigeometric nullity formulas for periodic labels.

Significance. The parity result supplies a uniform algebraic strengthening of Sutner's and Batal's theorems. The three-case update formula is exact and directly applicable to iterative rank computations. The tree recursion is a concrete algorithmic tool that produces falsifiable predictions for nullity growth on complete rooted trees. These contributions are load-bearing for the central claims and are supported by the algebraic arguments and small-case verifications supplied in the manuscript.

minor comments (4)

§2.1: the statement that diag(M) ∈ Im(M) is invoked as known; a one-sentence reminder of the standard argument (M symmetric implies diag(M) ⊥ ker(M)) would improve self-containedness without lengthening the text.
Figure 1 (tree recursion diagram): the affine subspaces of F_2^2 are drawn but the transition labels are not explicitly matched to the four possible binary diagonal pairs; adding a small table of the eight possible transitions would clarify the finite-state machine.
Notation: the manuscript alternates between Img(M) and Im(M); standardize to one throughout, including in the abstract.
Bibliography: the citations to Sutner (odd-domination) and Batal (parity theorem) appear only in the abstract; ensure both are listed with full bibliographic data in the references section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation begins from the standard fact that diag(M) lies in Im(M) for symmetric M over F2, which is invoked as known rather than derived internally. The constancy of the linear functional diag(M)^T x on the affine solution space follows immediately from the orthogonal-complement relation Im(M) = ker(M)^⊥ (a basic property of symmetric bilinear forms over F2) and does not rely on any result proved later in the paper. The additional claim that this constant equals rank(M) mod 2 is an independent algebraic identity whose verification on small matrices and extension to graph matrices is presented as new content, without reduction to self-citations, fitted parameters, or prior results by the same author. No self-definitional steps, renamed known results, or load-bearing self-citations appear in the stated claims or abstract.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard vector-space axioms of F2 and the definition of symmetric matrices; no free parameters, ad-hoc constants, or new postulated entities are introduced in the abstract.

axioms (1)

standard math Standard properties of the finite field F2 and symmetric bilinear forms over it
Invoked implicitly for the image-membership fact and the parity identity

pith-pipeline@v0.9.1-grok · 5756 in / 1311 out tokens · 21072 ms · 2026-06-30T22:24:07.237522+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 1 canonical work pages · 1 internal anchor

[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

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

2010
[3]

Symmetric Matrices over F_2 and the Lights Out Problem

I. Minevich, Symmetric matrices overF 2 and the Lights Out problem, arXiv:1206.2973

work page internal anchor Pith review Pith/arXiv arXiv
[4]

Pless, On Witt’s theorem for nonalternating symmetric bilinear forms over a field of characteristic 2,Proc

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

1964
[5]

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. Department of Mathematics, Clayton State University, Morrow, GA 30260, USA Email address:maliabadi@clayton.edu Email address:mohsenmath88@gmail.com

1989

[1] [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

2022

[2] [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

2010

[3] [3]

Symmetric Matrices over F_2 and the Lights Out Problem

I. Minevich, Symmetric matrices overF 2 and the Lights Out problem, arXiv:1206.2973

work page internal anchor Pith review Pith/arXiv arXiv

[4] [4]

Pless, On Witt’s theorem for nonalternating symmetric bilinear forms over a field of characteristic 2,Proc

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

1964

[5] [5]

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. Department of Mathematics, Clayton State University, Morrow, GA 30260, USA Email address:maliabadi@clayton.edu Email address:mohsenmath88@gmail.com

1989