Let $A \in \mathbb{R}^{n \times n}$ be a non-negative matrix, i.e. $A_{i,j} \geq 0$ $\forall (i,j)$.
Let $x \in \mathbb{R}^n \setminus \{0\}$ be a non-negative vector, i.e. $x_i \geq 0$ $\forall i$.
Assume $A x > x$ (componentwise), that is $(Ax)_i > x_i$ $\forall i$.
Prove that the following componentwise inequality holds: $$A \left( A x - x\right) > Ax - x.$$
Comment. This is what I tried out. The assumption is equivalent to $(A-I)x > 0$, while the thesis is equivalent to $(A-I)^2 x > 0$. Notice that $A-I$ is Metzler. Now, by contradiction, let $x \neq 0$ such that $(A-I)^2 = 0$, i.e., $x$ belongs to the null space of $(A-I)^2$. Does this imply that $x$ also belongs to the null space of $A - I$?
$\endgroup$ 52 Answers
$\begingroup$Here is a counterexample: $$A=\begin{pmatrix}0.86 & 0.88 \\ 0.92 & 0.17\end{pmatrix}, \qquad x = \begin{pmatrix} 69 \\11 \end{pmatrix}$$ Indeed, $$y:=Ax-x = \begin{pmatrix} 69.02 \\ 65.35 \end{pmatrix} -\begin{pmatrix} 69 \\11 \end{pmatrix} = \begin{pmatrix} 0.02 \\ 54.35 \end{pmatrix} >0$$ but $$Ay = \begin{pmatrix} 47.8452 \\ 9.2579 \end{pmatrix} \not> y$$
The following code (Scilab) finds such examples in spades.
for i=1:100 A=rand(2,2,"uniform") for j=1:100 x=rand(2,1,"uniform") y=A*x-x if min(y)>0 & min(A*y-y)<0 disp(A*y-y,x,A) end end
endHere are all the counterexamples with dimension $n = 2$ and entries in $\{0,1,2\}$.
[[0, 1], [0, 2]] [0, 1]
[[0, 1], [0, 2]] [0, 2]
[[0, 1], [1, 1]] [1, 2]
[[0, 1], [1, 2]] [0, 1]
[[0, 1], [1, 2]] [0, 2]
[[0, 1], [2, 2]] [0, 1]
[[0, 1], [2, 2]] [0, 2]
[[0, 2], [0, 2]] [0, 1]
[[0, 2], [0, 2]] [0, 2]
[[0, 2], [1, 1]] [1, 2]
[[0, 2], [1, 2]] [0, 1]
[[0, 2], [1, 2]] [0, 2]
[[0, 2], [2, 2]] [0, 1]
[[0, 2], [2, 2]] [0, 2]
[[1, 1], [1, 0]] [2, 1]
[[1, 1], [2, 0]] [2, 1]
[[2, 0], [1, 0]] [1, 0]
[[2, 0], [1, 0]] [2, 0]
[[2, 0], [2, 0]] [1, 0]
[[2, 0], [2, 0]] [2, 0]
[[2, 1], [1, 0]] [1, 0]
[[2, 1], [1, 0]] [2, 0]
[[2, 1], [2, 0]] [1, 0]
[[2, 1], [2, 0]] [2, 0]
[[2, 2], [1, 0]] [1, 0]
[[2, 2], [1, 0]] [2, 0]
[[2, 2], [2, 0]] [1, 0]
[[2, 2], [2, 0]] [2, 0]
Total found: 28Python code:
def find_counterexamples(lower, upper) : # Matrix A: # a b # c d # Vector x: x, y count = 0 for a in range(lower, upper) : for b in range(lower, upper) : for c in range(lower, upper) : for d in range(lower, upper) : for x in range(lower, upper) : for y in range(lower, upper) : if is_valid_counterexample(a,b,c,d,x,y) : print [[a,b],[c,d]], [x,y] count += 1 print "Total found: " print count print "\n"
def is_valid_counterexample(a,b,c,d,x,y) : x2 = (a - 1) * x + b * y y2 = c * x + (d - 1) * y x3 = (a - 1) * x2 + b * y2 y3 = c * x2 + (d - 1) * y2 if x2 <= 0 or y2 <= 0 : return False elif x3 > 0 and y3 > 0 : return False else : return True
lower = 0
upper = 1 + int(raw_input("upper: "))
find_counterexamples(lower, upper)
