Неотрицательный ранг (линейная алгебра) - Nonnegative rank (linear algebra)

В линейная алгебра, то неотрицательный ранг из неотрицательная матрица - концепция, аналогичная обычной линейной ранг действительной матрицы, но добавляя требование, чтобы некоторые коэффициенты и элементы векторов / матриц были неотрицательными.

Например, линейный ранг матрицы - это наименьшее количество векторов, так что каждый столбец матрицы может быть записан как линейная комбинация этих векторов. Для неотрицательного ранга требуется, чтобы векторы имели неотрицательные элементы, а также чтобы коэффициенты в линейных комбинациях были неотрицательными.

Формальное определение

Существует несколько эквивалентных определений, изменяющих определение линейного ранг немного. Помимо приведенного выше определения, существует следующее: неотрицательный ранг неотрицательного м × п-матрица А равно наименьшему числу q такой существует неотрицательный м × д-матрица B и неотрицательный q × n-матрица C такой, что A = BC (обычное матричное произведение). Чтобы получить линейный ранг, отбросьте условие, что B и C должно быть неотрицательным.

Далее, неотрицательный ранг - это наименьшее количество неотрицательных матриц ранга один, на которые матрица может быть разложена аддитивно:

${\displaystyle {\mbox{rank}}_{+}(A)=\min\{q\mid \sum _{j=1}^{q}R_{j}=A,\;{\mbox{rank}}\,R_{1}=\dots ={\mbox{rank}}\,R_{q}=1,\;R_{1},\dots ,R_{q}\geq 0\},}$

где р_j ≥ 0 означает "р_j неотрицательно ".^[1] (Чтобы получить обычный линейный ранг, отбросьте условие, что р_j должны быть неотрицательными.)

Учитывая неотрицательный ${\displaystyle m\times n}$ матрица А неотрицательный ранг ${\displaystyle rank_{+}(A)}$ из А удовлетворяет

${\displaystyle {\mbox{rank}}\,(A)\leq {\mbox{rank}}_{+}(A)\leq \min(m,n),}$ где ${\displaystyle {\mbox{rank}}\,(A)}$ обозначает обычный линейный ранг из А.

Заблуждение

Ранг матрицы А - это наибольшее количество столбцов, которые являются линейно независимыми, т.е. ни один из выбранных столбцов не может быть записан как линейная комбинация других выбранных столбцов. Неверно, что добавление неотрицательности к этой характеристике дает неотрицательный ранг: неотрицательный ранг обычно меньше или равен наибольшему количеству столбцов, так что ни один выбранный столбец не может быть записан как неотрицательная линейная комбинация других выбранных столбцов.

Связь с линейным рангом

Это всегда правда, что ранг (A) ≤ ранг₊(А). по факту ранг₊(A) = ранг (A) держится всякий раз, когда ранг (A) ≤ 2 [2].

В этом случае ранг (A) ≥ 3, Однако, ранг (А) <ранг₊(А) возможно. Например, матрица

${\displaystyle \mathbf {A} ={\begin{bmatrix}1&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&1\end{bmatrix}},}$

удовлетворяет ранг (A) = 3 <4 = ранг₊(А) [2].

Вычисление неотрицательного ранга

Неотрицательный ранг матрицы можно определить алгоритмически.^[2]

Было доказано, что определение того, ${\displaystyle {{rank}_{+}}(A)=rank(A)}$ NP-сложно.^[3]

Очевидные вопросы, касающиеся сложности вычисления неотрицательного ранга, до сих пор остаются без ответа. Например, сложность определения неотрицательного ранга матриц фиксированного ранга k неизвестно для k> 2.

Дополнительные факты

Неотрицательный ранг имеет важные приложения в Комбинаторная оптимизация:^[4] Минимальное количество грани из продолжение многогранника п равен неотрицательному рангу так называемого матрица провисания.^[5]

использованная литература

1. Авраам Берман и Роберт Дж. Племмонс. Неотрицательные матрицы в математических науках, СИАМ
2. Дж. Коэн и У. Ротблюм. «Неотрицательные ранги, разложения и факторизации неотрицательных матриц». Линейная алгебра и ее приложения, 190:149–168, 1993.
3. Стивен Вавасис, О сложности факторизации неотрицательной матрицы, SIAM Journal on Optimization 20 (3) 1364-1377, 2009.
4. Михалис Яннакакис. Выражение задач комбинаторной оптимизации линейными программами. J. Comput. Syst. Sci., 43 (3): 441–466, 1991.
5. Посмотри это Сообщение блога В архиве 2014-10-07 на Wayback Machine