2
$\begingroup$

I have this theorem.

So if A is a nonnegative matrix, then the following conditions are equivalent.

  1. $(I-A)^{-1}$ exists and is non-negative
  2. There is a non-negative vector $\vec{x}$ so that $(I-A)\vec{x}$ is positive (that is, all entries of $(I-A)\vec{x}$ are positive)

I have proved that 1 implies 2, but I am getting stuck on 2 implies 1.

Here's what I have for 1 implies 2. First we will start with 1 $\rightarrow$ 2. So we assume the first condition to be true, meaning that $(I-A)^{-1}$ exists and is non-negative. By definition $\vec{x}$ can be solved for using the equation $\vec{x} = (I-A)^{-1}\vec{b}$. Additionally, it is known that $\vec{b}$ cannot contain negative values as the external demand can only be positive. Using these two pieces of information, it can be seen that $\vec{x}$ must be positive, as only positive numbers are being used in its calculation. Now, the equation can be modified to solve for $\vec{b}$, giving $(I-A)\vec{x}=\vec{b}$ since we know that $\vec{x}$ and $\vec{b}$ are non-negative we can conclude that there is some non-negative vector $\vec{x}$ such that all the values of $(I-A)\vec{x}$ are positive.

Any help on 2 implies 1 would be greatly appreciated.

$\endgroup$
8
  • $\begingroup$ An observation: with diagonal similarity, the case where $x$ is positive can be further reduced to the case where $x = (1,\dots,1)$. $\endgroup$ Commented May 20, 2020 at 19:06
  • $\begingroup$ Note also that because of the Perron Frobenius theorem and because of the infinite series $$ (I - A)^{-1} = I + A + A^2 + \cdots, $$ it would suffices to show that $A$ has maximal positive eigenvalue less than $1$. $\endgroup$ Commented May 20, 2020 at 19:10
  • 1
    $\begingroup$ In your proof, how did you conclude that $x = (I - A)^{-1}b$ is positive as opposed to merely non-negative? And what do you mean by "external demand"? $\endgroup$ Commented May 20, 2020 at 22:11
  • 1
    $\begingroup$ Here is a correct proof for $1 \implies 2$: take $b = (1,\dots,1)$ and $x = (I - A)^{-1}b$. $b$ is positive, and because $(I - A)^{-1}$ is non-negative, $x = (I - A)^{-1}b$ must be non-negative. Also, we indeed have $(I - A)x = b$. $\endgroup$ Commented May 20, 2020 at 22:31
  • 1
    $\begingroup$ All we need to do to make my proof work is pick a $b$ with positive (as opposed to non-negative) entries. $b = (1,\dots,1)$ is one such vector. $\endgroup$ Commented May 21, 2020 at 0:53

1 Answer 1

1
$\begingroup$

A proof of $1 \implies 2$:

Let $e = (1,\dots,1)^T$. First, we show that there is necessarily a positive vector $x'$ for which $(I - A)x'$ is positive. In particular, we note that $\lim_{t \to 0^+}(I - A)(x + te)$ is positive. It follows that there exists a $t > 0$ for which $x' = x + te$ is such that $(I - A)x'$ is positive, and for this $t$, $x'$ is clearly positive.

Let $D = \operatorname{diag}(x')$. We have $$ 0 < D^{-1}(I - A)x' = D^{-1}(I - A)D(D^{-1}x') = (I - D^{-1}AD)(D^{-1}x') = (I - B)e $$ where $B = D^{-1}AD$. We see that $B$ is a matrix for which $(I - B)e$ is positive. That is, we have $$ 0 < (I - B)e \implies Be < e. $$ Thus, $B$ is a matrix for which all row-sums are at strictly less than $1$. We note that $$ \rho(B) = \lambda_{\max}(B) \leq \|B\|_\infty = \max_{i=1,\dots,n} \sum_{j=1}^n |b_{ij}| < 1. $$ Here, $\rho$ denotes the spectral radius and $\|\cdot\|_\infty$ denotes the induced $\infty$-norm. Because $\rho(B) < 1$, it follows that the "Neumann series" $(I - B)^{-1} = \sum_{i=0}^\infty B^i$ converges. We then see that because $B$ is non-negative, this sum and hence $(I - B)^{-1}$ must be non-negative.

We can conclude that $(I - A)^{-1} = D(I - B)^{-1}D^{-1}$ is also non-negative, which was what we wanted.

$\endgroup$
2
  • $\begingroup$ It's Neumann series, not von Neumann series. It is named after Carl Neumann rather than John von Neumann. $\endgroup$
    – user1551
    Commented May 21, 2020 at 5:45
  • 1
    $\begingroup$ @user1551 thanks for the correction. I also recently learned that Friedrich Schur and Issai Schur are distinct (unrelated, I think) people; math needs more surnames $\endgroup$ Commented May 21, 2020 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .