Binary Symmetric Matrix Inversion Through Local Complementation

• Autorzy: Brijder, R. , Hoogeboom, H.J.
• Języki publikacji: EN

Abstrakty

EN

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 symmetricmatrices 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.

Słowa kluczowe

EN

Schur complementation; symmetric matrices

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 15-23
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Brijder, R.

autor

Hoogeboom, H.J.

• Hasselt University and Transnational University of Limburg B-3590 Diepenbeek, Belgium,

Bibliografia

• [1] Bouchet, A.: Representability of Δ-matroids, Proc. 6th Hungarian Colloquium of Combinatorics, Colloquia Mathematica Societatis János Bolyai, 52, North-Holland, 1987.
• [2] Brijder, R., Daley, M., Harju, T., Jonoska, N., Petre, I., Rozenberg, G.: Computational Nature of Gene Assembly in Ciliates, in: Handbook of Natural Computing (G. Rozenberg, T. Bäck, J. Kok, Eds.), Springer, 2011.
• [3] Brijder, R., Harju, T., Hoogeboom, H.: Pivots, Determinants, and Perfect Matchings of Graphs, to appear in Theoretical Computer Science, 2012.
• [4] Brijder, R., Hoogeboom, H.: Maximal Pivots on Graphs with an Application to Gene Assembly, Discrete Applied Mathematics, 158(18), 2010, 1977-1985, ISSN 0166-218X.
• [5] Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., Rozenberg, G.: Formal systems for gene assembly in ciliates, Theoretical Computer Science, 292, 2003, 199-219.
• [6] Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., Rozenberg, G.: Computation in Living Cells - Gene Assembly in Ciliates, Springer Verlag, 2004.
• [7] Ehrenfeucht, A., Harju, T., Petre, I., Rozenberg, G.: Characterizing the micronuclear gene patterns in ciliates, Theory of Computing Systems, 35, 2002, 501-519.
• [8] Ehrenfeucht, A., Petre, I., Prescott, D., Rozenberg, G.: String and graph reduction systems for gene assembly in ciliates, Mathematical Structures in Computer Science, 12, 2002, 113-134.
• [9] Geelen, J.: A generalization of Tutte's characterization of totally unimodular matrices, Journal of Combinatorial Theory, Series B, 70, 1997, 101-117.
• [10] Prescott, D., Ehrenfeucht, A., Rozenberg, G.: Molecular operations for DNA processing in hypotrichous ciliates, European Journal of Protistology, 37, 2001, 241-260.
• [11] Tsatsomeros, M.: Principal pivot transforms: properties and applications, Linear Algebra and its Applications, 307(1-3), 2000, 151-165.
• [12] Tucker, A.: A combinatorial equivalence of matrices, Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics, X, American Mathematical Society, 1960.
• [13] Zhang, F.: The Schur Complement and Its Applications, Springer, 2005.