Nullity invariance for pivot and the interlace polynomial. (English) Zbl 1226.05152
Summary: We show that the effect of principal pivot transform on the nullity values of the principal submatrices of a given (square) matrix is described by the symmetric difference operator (for sets). We consider its consequences for graphs, and in particular generalize the recursive relation of the interlace polynomial and simplify its proof.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Keywords:
interlace polynomial; principal pivot transform; Schur complement; delta-matroid; local complementation; circle graphReferences:
| [1] | Arratia, R.; Bollobás, B.; Sorkin, G. B., The interlace polynomial: a new graph polynomial, (SODA ’00: Proceedings of the 11th Annual ACM-SIAM Symposium On Discrete Algorithms, Philadelphia, PA, USA (2000), Society for Industrial and Applied Mathematics), 237-245 · Zbl 0955.05066 |
| [2] | Arratia, R.; Bollobás, B.; Sorkin, G. B., The interlace polynomial of a graph, J. Combin. Theory Ser. B, 92, 2, 199-233 (2004) · Zbl 1060.05062 |
| [3] | Arratia, R.; Bollobás, B.; Sorkin, G. B., A two-variable interlace polynomial, Combinatorica, 24, 4, 567-584 (2004) · Zbl 1064.05139 |
| [4] | Bouchet, A., Representability of \(\Delta \)-matroids, (Proceedings of the Sixth Hungarian Colloquium of Combinatorics, Colloquia Mathematica Societatis János Bolyai, vol. 52 (1987), North-Holland), 167-182 · Zbl 0708.05013 |
| [5] | Bouchet, A., Graphic presentations of isotropic systems, J. Combin. Theory Ser. B, 45, 1, 58-76 (1988) · Zbl 0662.05014 |
| [6] | Bouchet, A., Multimatroids III. Tightness and fundamental graphs, European J. Combin., 22, 5, 657-677 (2001) · Zbl 0982.05034 |
| [7] | Bouchet, A.; Duchamp, A., Representability of \(\Delta \)-matroids over \(GF(2)\), Linear Algebra Appl., 146, 67-78 (1991) · Zbl 0738.05027 |
| [8] | R. Brijder, T. Harju, H.J. Hoogeboom, Pivots, determinants, and perfect matchings of graphs, submitted for publication, arXiv:0811.3500; R. Brijder, T. Harju, H.J. Hoogeboom, Pivots, determinants, and perfect matchings of graphs, submitted for publication, arXiv:0811.3500 · Zbl 1251.05132 |
| [9] | Cohn, M.; Lempel, A., Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A, 13, 1, 83-89 (1972) · Zbl 0314.05005 |
| [10] | Cottle, R. W.; Pang, J.-S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press San Diego · Zbl 0757.90078 |
| [11] | Ehrenfeucht, A.; Harju, T.; Petre, I.; Prescott, D. M.; Rozenberg, G., Computation in Living Cells - Gene Assembly in Ciliates (2004), Springer-Verlag · Zbl 1069.68048 |
| [12] | Ehrenfeucht, A.; Petre, I.; Prescott, D. M.; Rozenberg, G., String and graph reduction systems for gene assembly in ciliates, Math. Structures Comput. Sci., 12, 113-134 (2002) · Zbl 1007.68127 |
| [13] | Fiedler, M.; Markham, T. L., Completing a matrix when certain entries of its inverse are specified, Linear Algebra Appl., 74, 225-237 (1986) · Zbl 0592.15002 |
| [14] | Geelen, J. F., A generalization of Tutte’s characterization of totally unimodular matrices, J. Combin. Theory Ser. B, 70, 101-117 (1997) · Zbl 0885.05041 |
| [15] | Glantz, R.; Pelillo, M., Graph polynomials from principal pivoting, Discrete Math., 306, 24, 3253-3266 (2006) · Zbl 1125.05073 |
| [16] | Kotzig, A., Eulerian lines in finite 4-valent graphs and their transformations, (Theory of Graphs, Proceedings of the Colloquium, Tihany, Hungary, 1966 (1968), Academic Press: Academic Press New York), 219-230 · Zbl 0159.54201 |
| [17] | Parsons, T. D., Applications of principal pivoting, (Kuhn, H. W., Proceedings of the Princeton Symposium on Mathematical Programming (1970), Princeton University Press), 567-581 · Zbl 0275.15012 |
| [18] | L. Traldi, Binary nullity, Euler circuits and interlace polynomials, European J. Combin., in press, arXiv:0903.4405; L. Traldi, Binary nullity, Euler circuits and interlace polynomials, European J. Combin., in press, arXiv:0903.4405 · Zbl 1227.05168 |
| [19] | Tsatsomeros, M. J., Principal pivot transforms: properties and applications, Linear Algebra Appl., 307, 1-3, 151-165 (2000) · Zbl 0998.15006 |
| [20] | Tucker, A. W., A combinatorial equivalence of matrices, (Combinatorial Analysis. Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics, vol. X (1960), American Mathematical Society), 129-140 · Zbl 0096.00701 |
| [21] | Van den Nest, M.; Dehaene, J.; De Moor, B., Graphical description of the action of local clifford transformations on graph states, Phys. Rev. A, 69, 2, 022316 (2004) |
| [22] | Zhang, F., The Schur Complement and its Applications (1992), Springer |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
