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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we address computation of the degree $\mathop{\rm deg Det} A$of Dieudonn\'e determinant $\mathop{\rm Det} A$ of \[ A = \sum_{k=1}^m A_k x_kt^{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 problemgeneralizes noncommutative Edmonds' problem and fundamental combinatorialoptimization problems including the weighted linear matroid intersectionproblem. It was shown that $\mathop{\rm deg Det} A$ is obtained by a discreteconvex optimization on a Euclidean building. We extend this framework byincorporating a cost scaling technique, and show that $\mathop{\rm deg Det} 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 $\mathop{\rm deg Det}$, which says that$\mathop{\rm deg Det} A$ is given by linear optimization over an integralpolytope with respect to objective vector $c = (c_k)$. Based on it, we showthat our algorithm becomes a strongly polynomial one. We apply this result toan algebraic combinatorial optimization problem arising from a symbolic matrixhaving $2 \times 2$-submatrix structure.

A cost-scaling algorithm for computing the degree of determinants