The study of graphs drawn on surfaces (like a torus or a sphere) involves operations that transform one surface-embedded graph into another while preserving certain structural properties. Two important such operations are "partial duality" and "partial Petrie duality," which modify how a graph sits on a surface by flipping selected edges in specific ways. Researchers have developed polynomials, called partial-twuality polynomials, that track how a numerical property of the graph changes as you apply these operations to different subsets of edges. Earlier work extended this idea from graphs to abstract matrices, but left open the question of whether the operations and their expected algebraic relationships could be rigorously defined at the matrix level.
This paper answers that open question by introducing a "paired-matrix" framework, where a matrix is paired with an identity matrix, all working over a simple two-element number system (binary arithmetic). The authors define two local operations on these paired matrices and prove that they satisfy the key algebraic rules: applying either operation twice returns you to the start, and cycling through a specific sequence of three alternating operations also returns you to the start. These are exactly the relations that the surface-based operations satisfy, meaning the matrix framework faithfully mirrors the geometric situation. Crucially, the partial-twuality polynomials computed in the new paired framework match those computed in the original simpler matrix framework, so no information is lost by the extension.
The authors also derive a recurrence relation, a formula that breaks the computation of one of these polynomials into smaller pieces based on removing individual edges one at a time. This kind of edge-deletion recurrence is a standard and powerful tool in graph theory (similar to how the Tutte polynomial works) because it makes calculations tractable. Using this recurrence, the authors explicitly compute the relevant polynomial for several families of graphs, including bouquets (graphs with one vertex and many loops), simple graphs, and simple signed graphs (graphs where edges carry a positive or negative label). The results confirm that the new framework is both theoretically sound and practically useful for concrete calculations.