Monotone matrix

Not to be confused with monotonic matrix.

A real square matrix ${\displaystyle A}$ is monotone (in the sense of Collatz) if for all real vectors ${\displaystyle v}$, ${\displaystyle Av\geq 0}$ implies ${\displaystyle v\geq 0}$, where ${\displaystyle \geq }$ is the element-wise order on ${\displaystyle \mathbb {R} ^{n}}$.^[1]

For other uses, see SMAWK algorithm and Monge array.

Properties

A monotone matrix is nonsingular.^[1]

Proof: Let ${\displaystyle A}$ be a monotone matrix and assume there exists ${\displaystyle x\neq 0}$ with ${\displaystyle Ax=0}$. Then, by monotonicity, ${\displaystyle x\geq 0}$ and ${\displaystyle -x\geq 0}$, and hence ${\displaystyle x=0}$. ${\displaystyle \square }$

Let ${\displaystyle A}$ be a real square matrix. ${\displaystyle A}$ is monotone if and only if ${\displaystyle A^{-1}\geq 0}$.^[1]

Proof: Suppose ${\displaystyle A}$ is monotone. Denote by ${\displaystyle x}$ the ${\displaystyle i}$-th column of ${\displaystyle A^{-1}}$. Then, ${\displaystyle Ax}$ is the ${\displaystyle i}$-th standard basis vector, and hence ${\displaystyle x\geq 0}$ by monotonicity. For the reverse direction, suppose ${\displaystyle A}$ admits an inverse such that ${\displaystyle A^{-1}\geq 0}$. Then, if ${\displaystyle Ax\geq 0}$, ${\displaystyle x=A^{-1}Ax\geq A^{-1}0=0}$, and hence ${\displaystyle A}$ is monotone. ${\displaystyle \square }$

Examples

The matrix ${\displaystyle \left({\begin{smallmatrix}1&-2\\0&1\end{smallmatrix}}\right)}$ is monotone, with inverse ${\displaystyle \left({\begin{smallmatrix}1&2\\0&1\end{smallmatrix}}\right)}$. In fact, this matrix is an M-matrix (i.e., a monotone L-matrix).

Note, however, that not all monotone matrices are M-matrices. An example is ${\displaystyle \left({\begin{smallmatrix}-1&3\\2&-4\end{smallmatrix}}\right)}$, whose inverse is ${\displaystyle \left({\begin{smallmatrix}2&3/2\\1&1/2\end{smallmatrix}}\right)}$.

See also

• M-matrix
• Weakly chained diagonally dominant matrix