Введение
1 Основные понятия 35
1.1 Полукольца и линейная зависимость 36
1.2 Ранг матрицы 43
1.3 Тропическая линейная алгебра 49
2 Линейная алгебра и структура полуколец 59
2.1 Полумодули и линейные отображения 59
2.2 Факторизация и ранг матрицы 67
2.3 О рангах произведения и суммы матриц 75
3 Полугруппа матриц над полукольцом 89
3.1 Отношения Грина и ранговые функции 89
3. 2 Подгруппы полугруппы матриц 95
3.3 Тождества в полугруппе матриц 98
4 О ранговых функциях булевых матриц 107
4.1 Вычисление ранговых функций 108
4.2 О факторизации булевых матриц 110
4.3 Взаимное поведение ранговых функций 118
5 Ранговые функции тропических матриц 134
5.1 Шаблон тропической матрицы 135
5.2 О ранге Гондрана-Мину матрицы 143
5.3 Приложения метода шаблонов 152
6 Когда миноры порядка г образуют тропический базис? 158
6.1 Предварительные результаты 159
6.2 Миноры порядка 4 матрицы размера 6 х п 165
6.3 Доказательство основного результата 208
Факторизация тропических матриц 211
7.1 Предварительные сведения 211
7.2 Факторизация и ранги подматриц 215
7.3 Распознавание матриц ранга три 224
7.4 Вычислительная сложность факторизации 251
8 Факторизация неотрицательных матриц 269
8.1 Неотрицательный ранг 269
8.2 Факторизация матриц ранга три 272
8.3 Нижние оценки сложности расширенных представлений 281
Заключение
