Finding optimal minors of valuated bimatroids (Q1895110)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding optimal minors of valuated bimatroids |
scientific article |
Statements
Finding optimal minors of valuated bimatroids (English)
0 references
5 March 1996
0 references
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\).
0 references
valuated bimatroid
0 references
Smith-Mcmillan form
0 references
minor
0 references
rational function
0 references