A cost-scaling algorithm for computing the degree of determinants

Abstract

In this paper, we address computation of the degree $\mathrm{degDet}A$ of Dieudonné determinant $\mathrm{Det}A$ of \[ A = \sum_{k=1}^m A_k x_k t^{c_k}, \] where $A_k$ are $n\times n$ matrices over a field $\mathbb{K}$, $x_k$ are noncommutative variables, $t$ is a variable commuting with $x_k$, $c_k$ are integers, and the degree is considered for $t$. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that $\mathrm{degDet}A$ is obtained by a discrete convex optimization on a Euclidean building. We extend this framework by incorporating a cost scaling technique, and show that $\mathrm{degDet}A$ can be computed in time polynomial of $n,m,{\log }_{2}C$, where $C:={\max }_k|c_k|$. We give a polyhedral interpretation of $\mathrm{degDet}$, which says that $\mathrm{degDet}A$ is given by linear optimization over an integral polytope with respect to objective vector $c=(c_k)$. Based on it, we show that our algorithm becomes a strongly polynomial one. We apply this result to an algebraic combinatorial optimization problem arising from a symbolic matrix having $2\times 2$-submatrix structure.

new results (section 4) are added in version 2