Finding optimal minors of valuated bimatroids
type: Item
instance of: scholarly article
title: Finding optimal minors of valuated bimatroids
zbMATH Open document ID: 0833.05017
DOI: 10.1016/0893-9659(95)00043-P
author: Kazuo Murota
published in: Applied Mathematics Letters
publication date: 1996-03-05T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 26C15
zbMATH DE Number: 784963
zbMATH Keywords: valuated bimatroid
zbMATH Keywords: Smith-Mcmillan form
zbMATH Keywords: minor
zbMATH Keywords: rational function
reviewed by: Ákos G. Horváth
MaRDI profile type: Publication
cites work: Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form
cites work: Valuated matroids: A new look at the greedy algorithm
cites work: Valuated matroids
cites work: Bimatroids and invariants
cites work: Matroids and linking systems
cites work: Rational matrix structure
cites work: Q3254327
cites work: Q3803596
cites work: Computing the Degree of Determinants via Combinatorial Relaxation
full work available at URL: 0893-9659(95)00043-p
OpenAlex ID: W2130529283
description: scientific article; zbMATH DE number 784963