Computing the Degree of Determinants via Combinatorial Relaxation
Kazuo Murota · SIAM Journal on Computing · 1995
Let $A(x) = (A_{ij} (x))$ be a square matrix with $A_{ij}$ being a polynomial in x. This paper proposes “combinatorial relaxation-” type algorithms for computing the degree of the determinant $\delta (A) = \deg_{x} \det A(x)$ based on its combinatorial upper bound $\widehat{\delta}(A)$, which is defined in terms of the maximum weight of a perfect matching in an associated graph. The graph is bipartite for a general square matrix A and nonbipartite for a skew-symmetric A. The algorithm transforms A to another matrix $A^{\prime}$, for which $\delta (A) = \delta (A^{\prime}) = \widehat{\delta}(A^{\prime})$ with successive elementary operations. The algorithm is efficient, making full use of the fast algorithms for weighted matchings; it is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. It is shown in passing that for a (skew-)symmetric polynomial matrix $A(x)$ there exists a unimodular matrix $U(x)$ such that $A'(x) = U(x)A(x)U(x)^{\text{T}}$ satisfies $\delta (A) = \delta (A^{\prime}) = \widehat{\delta}(A^{\prime})$.