Diagonal parity and loop toggling for symmetric matrices over ${\mathbb{F}}_2$

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+u{u}^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.

Some typos in the earlier version were fixed