Let $M = (m_{ij})\in \mathbb R^{n\times n}$ be a square real matrix, such that $m_{ij}\leq 0$ for all $i\neq j$. We say that a matrix is monotone when $M$ is invertible and $M^{-1}$ has all its coefficients positive. We call "leading principal minors" the $\det (m_{ij})_{1\leq i,j\leq k}$ for $1\leq k \leq n$.

The problem:

Show that $M$ is monotone $\iff$ all the leading principal minors of $M$ are $>0$.

What I've done so far:

I'm really stuck with this one. Tried lots of things but nothing seems to work yet.

  • $\begingroup$ Yes, you are right. I fixed it. However, I didn't find anything on the internet to show this equivalence simply (without showing a lot of other equivalence). Do you have any idea? $\endgroup$
    – MiKiDe
    May 18 '20 at 17:27

These are actually two equivalent characterisations of nonsingular $M$-matrices. In standard terminologies for nonnegative matrices, it can be stated as follows: let $M\in\mathbb R^{n\times n}$ be a nonsingular $Z$-matrix. Then $M$ is inverse-positive if and only if all leading principal minors of $M$ are positive.

A proof of $50$ equivalent characterisations of nonsingular $M$-matrices can be found in theorem 2.3, chapter 6 of Nonnegative Matrices in the Mathematical Sciences written by Berman and Plemmons. The equivalence of the two particular characterisations in your question can be proved as follows.

Suppose $M$ is inverse-positive. Let $\alpha=\max_im_{ii}$. Then $P=\alpha I-M\ge0$. Let $x\ge0$ be a Perron vector for $P$. Then $(\alpha-\rho(P))M^{-1}x=x\ge0$. Since $M^{-1}x$ is also nonnegative, we must have $\alpha>\rho(P)$. Now denote by $P_k$ the leading principal $k\times k$ submatrix of $P$ and define $M_k$ analogously. Since $P\ge0$, by using Gelfand's formula with the induced $\infty$-norm, we have $\rho(P_k)\le\rho(P)$. It follows that $\alpha-\rho(P_k)\ge\alpha-\rho(P)>0$. Consequently, all eigenvalues of $M_k=\alpha I_k-P_k$ lie on the open right half plane. Therefore $\det(M_k)>0$ for each $k$, i.e. $M$ has positive leading principal minors.

Conversely, suppose $M$ has positive leading principal minors. By mathematical induction on $n$, one can show that $M$ has an LU-decomposition $M=LU$ such that all diagonal elements of $L$ are equal to $1$ and $L,U$ are inverse-positive. More specifically, in the inductive step, we have \begin{aligned} \pmatrix{L_0U_0&x\\ y^T&a} &=\pmatrix{L_0&0\\ y^TU_0^{-1}&1}\pmatrix{U_0&L_0^{-1}x\\ 0&b} \quad(b=a-y^TU_0^{-1}L_0^{-1}x),\\ \pmatrix{L_0&0\\ y^TU_0^{-1}&1}^{-1}&=\pmatrix{L_0^{-1}&0\\ -y^TU_0^{-1}L_0^{-1}&1},\\ \pmatrix{U_0&L_0^{-1}x\\ 0&b}^{-1}&=\pmatrix{U_0^{-1}&-b^{-1}U_0^{-1}L_0^{-1}x\\ 0&b^{-1}}. \end{aligned} It follows that $M^{-1}=U^{-1}L^{-1}$ is nonnegative, i.e. $M$ is inverse-positive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.