ИСТИНА

Проект направлен на исследование матричных отношений и инвариантов над полями и полукольцами, их интерпретации в терминах графов, и обратной задачи применения методов и результатов теории графов к решению вопросов теории матриц. Особенность данного исследования состоит в том, что планируется изучение графов матричных отношений, т.е. графов, множеством вершин которых является заданное множество матриц (матричное кольцо, алгебра, полукольцо, полугруппа) и две вершины соединены ребром тогда и только тогда, когда матрицы связаны рассматриваемым отношением. В случае, когда основное поле (полукольцо) коэффициентов бесконечно, соответствующие графы оказываются бесконечными. Целью проекта является разработка технологий применения общих методов теории графов к данным матричным проблемам и графам матричных отношений. Развитую технику планируется применить для решения ряда открытых проблем теории матриц. В частности, для решения проблемы Краутера получения оценки перманента (+1,-1)-матриц через функцию, зависящую от ранга матрицы и доказательства точности полученных оценок, для получения существенных продвижений в доказательстве гипотезы Паза о линейности функции длины на матричной алгебре, в исследовании свойств частичных порядков на матричных и операторных алгебрах.

• Найдены диаметр, обхват, число независимости и некоторые другие числовые параметры графа ортогональности кольца квадратных матриц над произвольным полем и его подграфов, связанных с треугольными, диагональными, нильпотентными и т.д. матрицами. • Изучена связность, найдены диаметр и обхват графов некоторых отношений порядка матриц над полями вещественных и комплексных чисел. • Построены новые серии примеров систем порождающих полной матричной алгебры, принципиально отличающиеся от систем порождающих, предложенных ранее в работах [W.E. Longstaff, Burnside's theorem: irreducible pairs of transformations, Linear Algebra Appl., 382(2004), 247—269], [W.E. Longstaff, Peter Rosenthal, On The Lengths Of Irreducible Pairs Of Complex Matrices, Proceedings Of The American Mathematical Society, 139:11(2011), 3769—3777] и др. Для каждой серии вычислена длина как функция от порядка матриц. Проверено, что значения длин всех указанных систем согласуются с гипотезой Паза [A.Paz, An application of the Cayley—Hamilton theorem to matrix polynomials in several variables, Linear Multilinear Algebra, 15 (1984), 161–170]. • Получено доказательство оптимальности некоторых порождающих систем в групповой алгебре группы перестановок и в алгебре полумагических матриц над различными полями. • Получены существенные продвижения в решении проблемы Краутера о максимальном значении перманента (+1,-1)-матрицы заданного ранга. Проведен обширный компьютерный эксперимент для подтверждения гипотезы Краутера для n=5, 6, 7. Изучены матричные и векторные мажоризации на множествах специального типа и доказана минимальность (относительно слабой векторной мажоризации) векторов ранговой стратификации на множестве подматриц максимального размера для (+1,-1) матриц с -1 по главной диагонали в классе всех (+1,-1) матриц. Получено доказательство гипотезы Краутера для вырожденных матриц порядка n в предположении ее справедливости для всех матриц меньшего порядка. • Получено полное решение проблемы Картрайта и Чан о задании симметрического ранга тропической матрицы в терминах графа недостаточности этой матрицы [D.Cartwright, M.Chan, Tropical rank of symmetric matrices, Combinatorica, 2012]. • Разработаны теоретико-графовые методы получения нижних оценок сложности расширения выпуклых многогранников и улучшены оценки, полученные в работе [S. Fiorini, T. Rothvo, H.R. Tiwary, Discrete & Computational Geometry, 48 (3), 658-668, 2012]. • Развитые методы использованы для получения результатов о сложности вычисления матричных инвариантов, см. проблемы, сформулированные в [P. Butkovic, Strong regularity of matrices – a survey of results, Discrete Mathematics, 48, 1994], описания рангов тропических матриц в терминах рангов их подматриц ограниченного размера [M.Develin, F.Santos, B.Sturmfels, On the rank of a tropical matrix, in Discrete and Computational Geometry, Cambridge Univ. Press, 2005], разложения матриц в сумму элементов тропического грассманниана TropGr(2,n) [Speyer D., Sturmfels B. Tropical mathematics, Mathematics Magazine, 163-173, 2009]. • Построены новые отношения порядка на матричной алгебре, в частности, не G-базированный порядок, расширяющий порядок, порожденный групповой обратной. Исследованы их комбинаторные свойства и охарактеризованы фробениусовы эндоморфизмы.