Computing the Maximum Degree of Minors in Skew Polynomial Matrices

Skew polynomials, which have a noncommutative multiplication rule between coefficients and an indeterminate, are the most general polynomial concept that admits the degree function with desirable properties. This talk presents the first algorithms to compute the maximum degree of the Dieudonné determinant of a $k \times k$ submatrix in a matrix $A$ whose entries are skew polynomials over a skew field $F$. Our algorithms make use of the discrete Legendre conjugacy between the sequences of the maximum degrees and the ranks of block matrices over $F$ obtained from coefficient matrices of $A$. Three applications of our algorithms are provided: (i) computing the dimension of the solution spaces of linear differential and difference equations, (ii) determining the Smith--McMillan form of transfer function matrices of linear time-varying systems and (iii) solving the "weighted" version of noncommutative Edmonds' problem with polynomial bit complexity. We also show that the deg-det computation for matrices over sparse polynomials is at least as hard as solving commutative Edmonds' problem.