A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with 2 × 2 submatrices
share
In this paper, we consider the problem of computing the degree of the determinant of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = (A_αβ x_αβ t^d_αβ), where A_αβ is a 2 × 2 matrix over a field 𝐅, x_αβ is an indeterminate, and d_αβ is an integer for α, β = 1,2,…, n, and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight perfect bipartite matching problem. The main result of this paper is a combinatorial O(n^4)-time algorithm for the deg-det computation of a (2 × 2)-type generic partitioned polynomial matrix of size 2n × 2n. We also present a min-max theorem between the degree of the determinant and a potential defined on vector spaces. Our results generalize the classical primal-dual algorithm (Hungarian method) and min-max formula (Egerváry's theorem) for maximum weight perfect bipartite matching.
READ FULL TEXT