# 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 |

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 |

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