no. 14 · Friday 13 November 2026
Diagonal parity and loop toggling for symmetric matrices over $\mathbb F_2$
Abstract
For a symmetric matrix $M$ over $\mathbb F_2$, it is known that its diagonal vector belongs to its column space. We prove the parity refinement that every solution of $Mx=\operatorname{diag}(M)$ satisfies $\operatorname{diag}(M)^Tx\equiv\operatorname{rank}(M)\pmod 2$. This extends the parity theorem for odd dominating sets to graph matrices with arbitrary binary diagonal labels. A self-contained rank-one update formula gives the changes caused by a single loop toggle and yields $\operatorname{nul} A(\overline G)=\operatorname{nul}(A(G)+I)+[\operatorname{rank}(A(G)+I)\text{ is odd}]$. For rooted trees, we augment Filmus's three classes of realizable boundary data with an explicit multiplicity recursion. The resulting formula computes the nullity of $A(T)+D_\varepsilon$ in a single traversal and gives a nonsingularity criterion. For complete rooted trees with eventually periodic labels indexed by height above the leaves, we obtain eventual periodicity of the boundary states and nullity formulas affine in powers of the branching degree on each eventual residue class. Constant labels give explicit closed forms.
- comments
- Some typos in the earlier version were fixed! The main theorems have been strengthened
- fields
- Combinatorics