Binary Symmetric Matrix Inversion Through Local Complementation

Issue title: Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju

Article type: Research Article

Authors: Brijder, Robert | Hoogeboom, Hendrik Jan

Affiliations: Hasselt University and Transnational University of Limburg, B-3590 Diepenbeek, Belgium, robert.brijder@uhasselt.be | Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands, hoogeboom@liacs.nl

Note: [] Address for correspondence: Hasselt University and Transnational University of Limburg, Belgium

Abstract: We consider the Schur complement operation for symmetric matrices over GF(2), which we identify with graphs through the adjacency matrix representation. It is known that Schur complementation for such a matrix (i.e., for a graph) can be decomposed into a sequence of two types of elementary Schur complement operations: (1) local complementation on a looped vertex followed by deletion of that vertex and (2) edge complementation on an edge without looped vertices followed by deletion of that edge. We characterize the symmetric matrices over GF(2) that can be transformed into the empty matrix using only operations of (1). As a consequence, we find that these matrices can be inverted using local complementation. The result is applied to the theory of gene assembly in ciliates.

DOI: 10.3233/FI-2012-664

Journal: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 15-23, 2012