English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper, we consider the computation of the degree of the Dieudonn\'edeterminant 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 "non-commutative" variables. This quantity isregarded as a weighted generalization of the non-commutative rank (nc-rank) ofa linear symbolic matrix, and its computation is shown to be a generalizationof several basic combinatorial optimization problems, such as weightedbipartite matching and weighted linear matroid intersection problems. Based onthe work on nc-rank by Fortin and Rautenauer (2004), and Ivanyos, Qiao, andSubrahmanyam (2018), we develop a framework to compute the degree of theDieudonn\'e determinant of a linear symbolic matrix. We show that the deg-detcomputation reduces to a discrete convex optimization problem on the Euclideanbuilding for ${\rm SL}(\mathbb{K}(t)^n)$. To deal with this optimizationproblem, we introduce a class of discrete convex functions on the building.This class is a natural generalization of L-convex functions in discrete convexanalysis (DCA). We develop a DCA-oriented algorithm (steepest descentalgorithm) to compute the degree of determinants. Our algorithm works withmatrix computation on $\mathbb{K}$, and uses a subroutine to compute acertificate vector subspace for the nc-rank, where the number of calls of thesubroutine is sharply estimated. Our algorithm enhances some classicalcombinatorial optimization algorithms with new insights, and is also understoodas a variant of the combinatorial relaxation algorithm, which was developedearlier by Murota for computing the degree of the (ordinary) determinant.

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