Monday 19 January 2015

linear algebra - Nonsingular M-matrices are nonsingular


Question: What is a good reference for a proof of Proposition 1 below?
It is definitely a known result, appearing e.g. in
Plemmons's M-matrix characterizations,
but I have not managed to follow the chain of references
to an actual proof of it (e.g., if it appears in Ostrowski's papers
cited by Plemmons, then not in this exact form). Has anyone seen it

appear in the literature explicitly and with a self-contained proof?
I give such a proof further below in an answer to this very question,
but I'd prefer to have a published reference I can cite as well.




Definition. Let $\ell$ be a nonnegative integer.



(a) In the following, $\mathbb{R}^\ell$ denotes the
$\mathbb{R}$-vector space of column vectors of size $\ell$.




(b) If $w \in \mathbb{R}^\ell$ is a column vector,
then the notation $w_i$ shall be used for
the $i$-th entry of $w$ (for each $i \in \left\{1,2,\ldots,\ell\right\}$).



(c) For two column vectors $u \in \mathbb{R}^\ell$
and $v \in \mathbb{R}^\ell$, we write $u > v$ if and
only if each $i \in \left\{1,2,\ldots,\ell\right\}$ satisfies
$u_i > v_i$.



(d) If $Q \in \mathbb{R}^{n\times m}$ is any matrix,

then $Q_{i,j}$ shall denote the $\left(i,j\right)$-th entry
of $Q$ for each $i$ and $j$.



(e) A nonsingular $M$-matrix means a matrix
$Q \in \mathbb{R}^{\ell \times \ell}$ satisfying the following
two conditions:




  • The off-diagonal entries of $Q$ are nonpositive.
    In other words, $Q_{i,j} \leq 0$ for $i \neq j$.



  • There exists some $x \in \mathbb{R}^\ell$ such that
    both $x>0$ and $Qx > 0$.





Proposition 1. Let $Q \in \mathbb{R}^{\ell \times \ell}$ be a
nonsingular $M$-matrix. Then,
$Q$ is nonsingular (i.e., we have $\ker Q = 0$).





Proposition 1 is, of course, part of the reason for the
suggestive name "nonsingular $M$-matrix". Nevertheless, it is not
really obvious. I give a proof in an answer to this question, but my real
question is: What is a good reference for Proposition 1 in published
literature that doesn't send its reader on a wild goose chase?
The notion of a nonsingular $M$-matrix is famous for its many equivalent
definitions (R.J. Plemmons, M-matrix characterizations. I
-- nonsingular M-matrices
gives dozens of them), which is at the same time a blessing and a curse,
the latter because it means that a result like Proposition 1 can be
spread across several parts of the literature without ever being stated

explicitly in one of them. My impression so far is that this is what
has happened.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...