Matrices with indeterminates
Contents
Problems in this category
Introduction
A crucial problem concerning applications of linear algebra in combinatorial optimization is the following: find a polynomial-time algorithm for deciding whether a square polynomial matrix is singular.
In the context of combinatorial optimization, the first matrix with indeterminates was introduced by Tutte. He defined the Tutte matrix of a graph, and showed that it is nonsingular if and only if the graph has a perfect matching. In bipartite graphs, one can consider the Edmonds matrix instead of the Tutte matrix.
The problem is in co-RP, since it is a special case of polynomial identity testing. A simple randomized algorithm is the following (see [1] and [2]). Let S be a finite subset of numbers of size at least 2d, where d is an upper bound on the degree of the determinant (which is a polynomial). Replace each variable by a uniform random element of S, and evaluate the determinant of the resulting (constant) matrix. If this determinant is zero, then the Schwartz-Zippel lemma guarantees that the determinant of the polynomial matrix is zero as well with probability at least 1/2.
From the algorithmic perspective, the advantage of such an algorithm is that it can be used in designing efficient parallel algorithms for maximum matching and generalizations[3].
Tutte matrix and extensions
The following example demonstrates the possible impact of polynomial matrices in supplying combinatorial optimization with new ideas. Cunningham and Geelen[4] studied the rank of the submatrices of the Tutte matrix. This led them to the formulation of the even factor problem and its solution via a random algorithm. Later, Gy. Pap and Szegő[5] gave a min-max formula on the maximum cardinality of an even factor. In a subsequent paper, Gy. Pap[6] also developed a purely combinatorial algorithm for finding an optimal solution.
A similar development would be desirable concerning exact matchings:
|
Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly k red edges. |
In this case, there exists an algorithm based on random evaluation of a matrix with indeterminates. However, neither a min-max formula, nor a deterministic algorithm is known so far.
Iwata and Geelen[7] studied the rank of T+K where T is the Tutte matrix of a graph, and K is a skew symmetric constant matrix. This modest generalization already turns out to be equivalent to the so called linear delta-matroid parity problem.
One might be interested not only in deciding whether a polynomial matrix is nonsingular, but also in (deterministically) finding an evaluation with nonzero determinant, if it exists (the Schwartz-Zippel lemma shows that there are indeed only a few evaluations with zero determinant for a nonsingular matrix). For the Tutte-matrix, Geelen[8] gave a deterministic polynomial-time algorithm.
Linear polynomials
An important special case is when all entries in the matrix are linear polynomials. This can be formulated equivalently as follows[1] [9]. Let A be a linear subspace of [math]n \times n[/math] real matrices. Determine the maximum rank of a matrix in A; in particular, determine whether A contains a nonsingular matrix.
This problem can be solved[9] if A is generated by rank 1 matrices or by rank 2 skew-symmetric matrices (in both cases, we assume that a set of such generators is given). The first case deduces from the matroid intersection theorem, while the second can be solved using linear matroid matching.
Rigidity
Polynomial matrices play an important role in the field of rigidity. Indeed, the notion of generic rigidity in d dimensions is defined by the rank of the rigidity matrix, which is a polynomial matrix. Two-dimensional generic rigidity is a well-understood property admitting a graph theoretic description, however the characterization of generic rigidity in three dimensions is a major open question in the field.
Dual critical graphs
An interesting question related to ear decompositions is the characterization of dual-critical graphs:
|
A graph G=(V,E) is called dual-critical if it can be constructed from a single node by adding new nodes one by one so that the currently added node is connected by an odd number of edges with already existing nodes. Design an algorithm to decide if a graph is dual-critical. |
Again, a random algorithm is known based on a random evaluation of a matrix with indeterminates.
References
- ↑ 1.0 1.1 J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards B 71 (1967), pp. 241–245. PDF
- ↑ L. Lovász, On determinants, matchings and random algorithms, Fund. Comput. Theory 79 (1979), pp. 565–574. PDF
- ↑ Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7(1): 105-113 (1987) DOI link author link
- ↑ W. Cunningham, J. Geelen, The optimal path matching problem, Combinatorica 17, pp 315-337 (1997). DOI link
- ↑ Gy. Pap, L. Szegő, On the maximum even factor in weakly symmetric graphs, Journal of Combinatorial Theory Ser. B, 91/2 (2004) 201-213, DOI link author link
- ↑ Gy. Pap, A Combinatorial Algorithm to Find a Maximum Even Factor, Lecture Notes in Computer Science, LNCS 3509, Springer Verlag (2005), 66-80. DOI link
- ↑ J. Geelen, S. Iwata, Matroid matching via mixed skew-symmetric matrices, Combinatorica 25, pp 187-215 (2005) DOI link author link
- ↑ J. Geelen, An algebraic matching algorithm, Combinatorica 20, pp 61-70 (2000) DOI link author link
- ↑ 9.0 9.1 L. Lovász, Singular spaces of matrices and their application in combinatorics, Bol. Soc. Braz. Mat. 20 (1989), 87-99. DOI link PDF
