Computing the degree of determinants via discrete convex optimization on Euclidean buildings

Abstract

In this paper, we consider the computation of the degree of the Dieudonné determinant of a linear symbolic matrix $A=A_0+A_1{x}_1+\cdots +A_m{x}_m$, where each $A_i$ is an $n\times n$ polynomial matrix over $\mathbb{K}[t]$ and $x_1,x_2,\dots ,x_m$ are pairwise "non-commutative" variables. This quantity is regarded as a weighted generalization of the non-commutative rank (nc-rank) of a linear symbolic matrix, and its computation is shown to be a generalization of several basic combinatorial optimization problems, such as weighted bipartite matching and weighted linear matroid intersection problems. Based on the work on nc-rank by Fortin and Rautenauer (2004), and Ivanyos, Qiao, and Subrahmanyam (2018), we develop a framework to compute the degree of the Dieudonné determinant of a linear symbolic matrix. We show that the deg-det computation reduces to a discrete convex optimization problem on the Euclidean building for $\mathrm{SL}(\mathbb{K}(t{)}^n)$. To deal with this optimization problem, we introduce a class of discrete convex functions on the building. This class is a natural generalization of L-convex functions in discrete convex analysis (DCA). We develop a DCA-oriented algorithm (steepest descent algorithm) to compute the degree of determinants. Our algorithm works with matrix computation on $\mathbb{K}$, and uses a subroutine to compute a certificate vector subspace for the nc-rank, where the number of calls of the subroutine is sharply estimated. Our algorithm enhances some classical combinatorial optimization algorithms with new insights, and is also understood as a variant of the combinatorial relaxation algorithm, which was developed earlier by Murota for computing the degree of the (ordinary) determinant.

To appear in SIAM Journal of Applied Geometry and Algebra; v4 corrected small typos