Неотрицательный ранг (линейная алгебра)

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

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

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

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

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

${\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\},$

где R _j ≥ 0 означает « R _j неотрицательен». (Чтобы получить обычный линейный ранг, отбросьте условие Rj _{неотрицательности} .)

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

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

Заблуждение

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

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

Всегда верно, что Rank(A) ≤ Rank ₊ (A) . Фактически, Rank ₊ (A) = Rank(A) выполняется всякий раз, когда Rank(A) ≤ 2 .

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

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

удовлетворяет Rank(A) = 3 < 4 = Rank ₊ (A) .

Эти два результата (включая приведенный выше пример матрицы 4×4) были впервые предоставлены Томасом в ответе. на вопрос, заданный в 1973 году Берманом и Племмонсом.

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

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

Доказано, что определение того, является ли ${{\text{rank}}_{+}}(A)={\text{rank}}(A)$ является NP-трудным.

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

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

Неотрицательный ранг имеет важные применения в комбинаторной оптимизации : Минимальное число граней расширения многогранника P равно неотрицательному рангу его так называемой слабой матрицы .