В линейной алгебре , то неотрицательное ранг из неотрицательной матрицы это понятие аналогично обычному линейному ранга реальной матрицы, но добавив требование , чтобы определенные коэффициенты и записи векторов / матриц должны быть неотрицательными.
Например, линейный ранг матрицы - это наименьшее количество векторов, так что каждый столбец матрицы может быть записан как линейная комбинация этих векторов. Для неотрицательного ранга требуется, чтобы векторы имели неотрицательные элементы, а также чтобы коэффициенты в линейных комбинациях были неотрицательными.
Формальное определение
Есть несколько эквивалентных определений, каждое из которых немного изменяет определение линейного ранга . Помимо приведенного выше определения, существует следующее: неотрицательный ранг неотрицательной m × n -матрицы A равен наименьшему числу q , так что существуют неотрицательная m × q -матрица B и неотрицательная q × n -матрица C такой, что A = BC (обычное матричное произведение). Чтобы получить линейный ранг, отбросьте условие неотрицательности B и C.
Далее, неотрицательный ранг - это наименьшее количество неотрицательных матриц ранга один, на которые матрица может быть разложена аддитивно:
где R j ≥ 0 означает « R j неотрицательно». [1] (Чтобы получить обычный линейный ранг, отбросьте условие неотрицательности R j .)
Учитывая неотрицательный матрица A неотрицательного рангаиз А удовлетворяет
Заблуждение
Ранг матрицы A - это наибольшее количество столбцов, которые являются линейно независимыми, т. Е. Ни один из выбранных столбцов не может быть записан как линейная комбинация других выбранных столбцов. Неверно, что добавление неотрицательности к этой характеристике дает неотрицательный ранг: неотрицательный ранг обычно меньше или равен наибольшему количеству столбцов, так что ни один выбранный столбец не может быть записан как неотрицательная линейная комбинация других выбранных столбцов.
Связь с линейным рангом
Всегда верно, что rank (A) ≤ rank + (A) . Фактически, rank + (A) = rank (A) выполняется всякий раз, когда rank (A) ≤ 2 [2].
В случае ранга (A) ≥ 3 , однако, ранг (А) <ранг + (А) возможно. Например, матрица
удовлетворяет rank (A) = 3 <4 = rank + (A) [2].
Вычисление неотрицательного ранга
Неотрицательный ранг матрицы можно определить алгоритмически. [2]
Доказано, что определение того, NP-сложно. [3]
Очевидные вопросы, касающиеся сложности вычисления неотрицательного ранга, до сих пор остаются без ответа. Например, сложность определения неотрицательного ранга матриц фиксированного ранга k неизвестна при k> 2 .
Дополнительные факты
Неотрицательный ранг имеет важные приложения в оптимизации комбинаторной : [4] Минимальное количество граней в качестве расширения многогранника P равно неотрицательного ранг так называемой слабина матрицы . [5]
Рекомендации
- ^ Авраам Берман и Роберт Дж. Племмонс . Неотрицательные матрицы в математических науках , SIAM
- ^ Дж. Коэн и У. Ротблюм. «Неотрицательные ранги, разложения и факторизации неотрицательных матриц». Линейная алгебра и ее приложения , 190: 149–168, 1993.
- ^ Стивен Вавасис, О сложности факторизации неотрицательной матрицы, SIAM Journal on Optimization 20 (3) 1364-1377, 2009.
- ^ Михалис Яннакакис. Выражение задач комбинаторной оптимизации линейными программами. J. Comput. Syst. Наук, 43 (3): 441–466, 1991.
- ^ См. Это сообщение в блоге. Архивировано 7 октября 2014 г. на Wayback Machine.