Finding optimal minors of valuated bimatroids
The author proves the following two theorems: (1) If \(\delta_k\) denotes the highest degree of a minor of order \(k\) of an \(m\times n\) matrix \(A(x)\) with elements \(A_{ij}(x)\) being a rational function in \(x\) with coefficients from a field \(F\) then the function \(\delta_k\) (as a function of \(k\)) is concave. (2) If \((I, J)\) denotes the submatrix of \(A\) with row-set \(I\) and column-set \(J\) and \((I_k, J_k)\) is a maximal minor then there exist \((I_l, J_l)\) maximal \(l\)-minors \((0\leq l\leq r)\), \(l\neq k\) such that the sets \(\{I_j\}\) and \(\{J_j\}\) are nested, respectively. On the basis of these theorems the author gives two algorithms for computing \(\delta_k\).
scientific article; zbMATH DE number 784963