Please use this identifier to cite or link to this item:
Title: Binary Symmetric Matrix Inversion Through Local Complementation
Authors: BRIJDER, Robert 
Hoogeboom, Hendrik Jan
Issue Date: 2012
Publisher: IOS PRESS
Source: FUNDAMENTA INFORMATICAE, 116 (1-4), p. 15-23
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.
Notes: [Brijder, Robert] Hasselt Univ, B-3590 Diepenbeek, Belgium. [Brijder, Robert] Transnatl Univ Limburg, B-3590 Diepenbeek, Belgium. [Hoogeboom, Hendrik Jan] Leiden Univ, Leiden Inst Adv Comp Sci, NL-2300 RA Leiden, Netherlands.
Keywords: Computer Science, Software Engineering; Mathematics, Applied
Document URI:
ISSN: 0169-2968
e-ISSN: 1875-8681
DOI: 10.3233/FI-2012-664
ISI #: 000304190900003
Category: A1
Type: Journal Contribution
Validations: ecoom 2013
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
th-brijder-hoogeboom.pdf92.38 kBAdobe PDFView/Open
Show full item record


checked on Sep 3, 2020


checked on May 21, 2022

Page view(s)

checked on May 25, 2022


checked on May 25, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.