Монотонная матрица - Monotone matrix

Не путать с монотонная матрица.

Для использования в других целях см. Алгоритм SMAWK и Массив Монжа.

Реальная квадратная матрица ${\displaystyle A}$ является монотонный (в смысле Коллатца), если для всех действительных векторов ${\displaystyle v}$, ${\displaystyle Av\geq 0}$ подразумевает ${\displaystyle v\geq 0}$, куда ${\displaystyle \geq }$ поэлементный порядок на ${\displaystyle \mathbb {R} ^{n}}$.^[1]

Характеристики

Монотонная матрица невырожденна.^[1]

Доказательство: Позволять ${\displaystyle A}$ - монотонная матрица и предположим, что существует ${\displaystyle x\neq 0}$ с ${\displaystyle Ax=0}$. Тогда по монотонности ${\displaystyle x\geq 0}$ и ${\displaystyle -x\geq 0}$, и поэтому ${\displaystyle x=0}$. ${\displaystyle \square }$

Позволять ${\displaystyle A}$ - вещественная квадратная матрица. ${\displaystyle A}$ монотонно тогда и только тогда, когда ${\displaystyle A^{-1}\geq 0}$.^[1]

Доказательство: Предполагать ${\displaystyle A}$ монотонный. Обозначим через ${\displaystyle x}$ то ${\displaystyle i}$-й столбец ${\displaystyle A^{-1}}$. Потом, ${\displaystyle Ax}$ это ${\displaystyle i}$-й стандартный базисный вектор и, следовательно, ${\displaystyle x\geq 0}$ по монотонности. Для обратного направления предположим ${\displaystyle A}$ допускает обратное, такое что ${\displaystyle A^{-1}\geq 0}$. Тогда, если ${\displaystyle Ax\geq 0}$, ${\displaystyle x=A^{-1}Ax\geq A^{-1}0=0}$, и поэтому ${\displaystyle A}$ монотонный. ${\displaystyle \square }$

Примеры

Матрица ${\displaystyle \left({\begin{smallmatrix}1&-2\\0&1\end{smallmatrix}}\right)}$ монотонный, с обратным ${\displaystyle \left({\begin{smallmatrix}1&2\\0&1\end{smallmatrix}}\right)}$Фактически эта матрица представляет собой М-матрица (т.е. монотонный L-матрица ).

Заметим, однако, что не все монотонные матрицы являются M-матрицами. Примером является ${\displaystyle \left({\begin{smallmatrix}-1&3\\2&-4\end{smallmatrix}}\right)}$, обратное ${\displaystyle \left({\begin{smallmatrix}2&3/2\\1&1/2\end{smallmatrix}}\right)}$.

Смотрите также

• М-матрица
• Слабо сцепленная матрица с диагональным преобладанием

Рекомендации

1. Мангасарян, О. Л. (1968). «Характеризации вещественных матриц монотонного вида» (PDF). SIAM Обзор. 10 (4): 439–441. Дои:10.1137/1010095. ISSN  0036-1445.