Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
Hiroshi Hirai · SIAM Journal on Applied Algebra and Geometry · 2019
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,\ldots,x_m$ are pairwise “noncommutative” variables. This quantity is regarded as a weighted generalization of the noncommutative 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 Reutenauer [ Sém. Lothar. Combin., 52 (2004), B52f] and Ivanyos, Qiao, and Subrahmanyam [ Comput. Complex., 27 (2018), pp. 561--593], 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 ${\rm 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 it 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.