Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-Mcmillan form at infinity and structural indices in Kronecker form

LetA(x)=(A_ij(x)) be a matrix withA_ij(x) being a polynomial or rational function inx. This paper proposes a combinatorial relaxation type algorithm for computing the highest degree_k(A) of a minor ofA(x) of a specified orderk. Such an algorithm can be used to compute the Smith-McMillan form of a rational function matrix at infinity, as well as the structure of the Kronecker form of a matrix pencil. The algorithm is based on a combinatorial upper bound on_k(A), which is defined as the maximum weight of a matching of sizek in a bipartite graph associated withA. The algorithm is efficient, making full use of the fast algorithms for weighted matchings. It is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. The validity relies on the integrality of bipartite matching polytopes.This work is supported in part by the Sumitomo Foundation.