Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13810

Title: Binary Symmetric Matrix Inversion Through Local Complementation
Authors: Brijder, Robert
Hoogeboom, Hendrik Jan
Issue Date: 2012
Publisher: IOS PRESS
Citation: 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.
URI: http://hdl.handle.net/1942/13810
DOI: 10.3233/FI-2012-664
ISI #: 000304190900003
ISSN: 0169-2968
Category: A1
Type: Journal Contribution
Validation: ecoom, 2013
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A92.38 kBAdobe PDF

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