From normal-matrix factorizations to local complementation sequences

Abstract

We study the Equivalent Local Sequence Problem (ELSP) for simple undirected graphs using Bouchet’s isotropic-system formalism and normal matrices over \(\mathbb F_2\). Although Bouchet’s theory characterizes graph local equivalence in polynomial time, converting normal-matrix certificates into explicit graph transformations remains challenging. We introduce the Normal-Matrix Factorization Problem (NMFP), which asks whether a normal-matrix witness of local equivalence has a graph-compatible factorization into elementary transformations. Whenever such a factorization exists, an explicit local-complementation sequence can be recovered in polynomial time. Thus, the constructive part of ELSP reduces to NMFP, identifying normal-matrix factorization as its main unresolved algebraic difficulty. We apply this framework to undirected Paley graphs. In contrast to the directed case, whose local-complementation dynamics are abelian and admit linear inversion, the undirected case is noncommutative and has a more intricate stabilizer structure. Using normal matrices, we analyze Paley-graph orbits and stabilizers, derive algebraic constraints on stabilizing transformations, and completely verify the first undirected Paley graph \(P_5\). These results establish NMFP as central to constructive local equivalence and reveal connections among isotropic systems, graph transformations, and algebraic stabilizers.