Oki, Taihei
On Solving (Non)commutative Weighted Edmonds' Problem
Abstract
In this paper, we consider computing the degree of the Dieudonné determinant of a polynomial matrix A = A_l + A_{l1} s + ⋯ + A₀ s^l, where each A_d is a linear symbolic matrix, i.e., entries of A_d are affine functions in symbols x₁, …, x_m over a field K. This problem is a natural "weighted analog" of Edmonds' problem, which is to compute the rank of a linear symbolic matrix. Regarding x₁, …, x_m as commutative or noncommutative, two different versions of weighted and unweighted Edmonds' problems can be considered. Deterministic polynomialtime algorithms are unknown for commutative Edmonds' problem and have been proposed recently for noncommutative Edmonds' problem.
The main contribution of this paper is to establish a deterministic polynomialtime reduction from (non)commutative weighted Edmonds' problem to unweighed Edmonds' problem. Our reduction makes use of the discrete Legendre conjugacy between the integer sequences of the maximum degree of minors of A and the rank of linear symbolic matrices obtained from the coefficient matrices of A. Combined with algorithms for noncommutative Edmonds' problem, our reduction yields the first deterministic polynomialtime algorithm for noncommutative weighted Edmonds' problem with polynomial bitlength bounds. We also give a reduction of the degree computation of quasideterminants and its application to the degree computation of noncommutative rational functions.
BibTeX  Entry
@InProceedings{oki:LIPIcs:2020:12496,
author = {Taihei Oki},
title = {{On Solving (Non)commutative Weighted Edmonds' Problem}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {89:189:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12496},
URN = {urn:nbn:de:0030drops124963},
doi = {10.4230/LIPIcs.ICALP.2020.89},
annote = {Keywords: skew fields, Edmonds' problem, Dieudonn{\'e} determinant, degree computation, Smith  McMillan form, matrix expansion, discrete Legendre conjugacy}
}
29.06.2020
Keywords: 

skew fields, Edmonds' problem, Dieudonné determinant, degree computation, Smith  McMillan form, matrix expansion, discrete Legendre conjugacy 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 