Tropical patterns of matrices and the Gondran-Minoux rank function

Linear Algebra and its Applications. 2012. Vol. 437. No. 7. P. 1793–1811.

Гутерман А. Э., Шитов Я. Н.

Исследуются свойства функции ранга Гондрана-Мину матриц над R. Вводится понятие шаблона матрицы над R. Показывается, что с точностью до умножения строк на ненулевые элементы, GM-зависимость строк матрицы равносильна GM-зависимости строк шаблона. Показывается, что при фиксированном k задача распознавания свойства  GMr(A)<k решается за полиномиальное по размеру матрицы A ∈| n×m (R) время. Доказываются неравенства trop(A) ≥ √GMr(A), d(A) ≥ √GMr(A), trop(A)  ≥ (d(A)+2)/3, верные для матриц над R. Как следствие мы доказываем, что если тропические ранги матриц ограничены, то ограничены и их ранги Гондрана-Мину, в отличие от ситуации с факторизационным рангом и рангом Капранова.

Ключевые слова: линейная алгебра, tropical algebras, rank functions, matrix spaces, тропические алгебры, ранговые функции, пространства матриц