Computing valuations of the Dieudonné determinants. (May 2023)

• Record Type: Journal Article
• Authors: Oki, Taihei
• Is Part Of: Journal of symbolic computation. Volume 116(2023)
• Page Start: 284
• Page End: 323
• Publication Date: 2023-05
• Subjects: Valuation skew fields -- Dieudonné determinants -- Skew polynomials -- Differential equations -- Edmonds' problem -- Combinatorial relaxation; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.10.010
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: This paper addresses the problem of computing valuations of the Dieudonné determinants of matrices over discrete valuation skew fields (DVSFs). Under a reasonable computational model, we propose two algorithms for a class of DVSFs, called split. Our algorithms are extensions of the combinatorial relaxation of Murota (1995) and the matrix expansion by Moriyama and Murota (2013), both of which are based on combinatorial optimization. While our algorithms require an upper bound on the output, we give an estimation of the bound for skew polynomial matrices and show that the estimation is valid only for skew polynomial matrices. We consider two applications of this problem. The first one is the noncommutative weighted Edmonds' problem (nc-WEP), which is to compute the degree of the Dieudonné determinants of matrices having noncommutative symbols. We show that the presented algorithms reduce the nc-WEP to the unweighted problem in polynomial time. In particular, we show that the nc-WEP over the rational field is solvable in time polynomial in the input bit-length. We also present an application to analyses of degrees of freedom of linear time-varying systems by establishing formulas on the solution spaces of linear differential/difference equations.