A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $2\times 2$ submatrices

Abstract

In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) $A=(A_{\alpha \beta }{x}_{\alpha \beta }{t}^{d_{\alpha \beta }})$, where $A_{\alpha \beta }$ is a $2\times 2$ matrix over a field $\mathbf{F}$, $x_{\alpha \beta }$ is an indeterminate, and $d_{\alpha \beta }$ is an integer for $\alpha =1,2,\dots ,\mu$ and $\beta =1,2,\dots ,\nu$, and $t$ is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching problem. The main result of this paper is a combinatorial $O(\mu \nu \min \{\mu ,\nu {\}}^2)$-time algorithm for computing the entire sequence of the maximum degree of minors of a $(2\times 2)$-type generic partitioned polynomial matrix of size $2\mu \times 2\nu$. We also present a minimax theorem, which can be used as a good characterization (NP $\cap$ co-NP characterization) for the computation of the maximum degree of minors of order $k$. Our results generalize the classical primal-dual algorithm (the Hungarian method) and minimax formula (Egerváry's theorem) for the maximum weight bipartite matching problem.

43 pages, 3 figures, the full version of an IPCO 2021 paper