Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a stochastic matrix. Thus $A$ has nonnegative entries, and the sum of the elements in each row is 1. This implies that the vector $\begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}^T$ is an eigenvector corresponding to the eigenvalue 1. Is it true that there exists a vector $b$ such that

$$(A - I)x \geq b$$

has no solutions in $x$? If so, is there a simple proof?

Motivation: I've been trying to construct an answer to another question using linear programming duality (as the OP implies he is interested in). If my reasoning is correct, this is the only step I need to complete the argument. I feel like this should be an easy question to answer, but I've been working on it for a while with no success.

share|improve this question
    
Wouldn't you have to say how it is you are comparing vectors? What does $v\geq w$ mean in your vector space? Do you mean $||(A−I)x||≥||b||$, under the usual norm of $\mathbb{R}^n$, perhaps? Or that ever entry of $(A-I)x$ is greater than or equal to the corresponding entry of $b$? –  Arturo Magidin Nov 2 '10 at 23:41
1  
I believe inequalities between vectors are meant to be taken componentwise here, i.e. $a \ge b \Leftrightarrow a_i \ge b_i \forall i$. –  Fanfan Nov 2 '10 at 23:52
    
@Arturo: Fanfan is correct. Componentwise comparison for vectors is standard in linear programming. Since that's where I normally work with vectors I tend to forget that there are other ways of interpreting statements like $(A - I)x \geq b$. –  Mike Spivey Nov 3 '10 at 0:08
add comment

1 Answer 1

up vote 5 down vote accepted

Your inequality $(A-I)x \ge b$ has no solutions in $x$ as soon as $b>0$. Indeed, any potential solution would have to satisfy $A x \ge x + b$ and, since rows of $A$ are nonnegative and sum to one, each element of vector $Ax$ is a convex combination of the components of $x$, which must be less than $x_{max}$, the largest component of $x$. On the other hand, at least one element of $x+b$ is greater than $x_{max}$, which proves the impossibility.

By the way, applying Farkas' Lemma to this impossible system shows that the following always admits solutions in y $$y^T (A-I) = 0, y \ge 0 \text{ and } y^T b > 0$$ which expresses the fact that $A$ necessarily admits a nonnegative left eigenvector with eigenvalue $1$ (the last inequality ensures that $y$ is nonzero).

share|improve this answer
    
Thanks, Fanfan. That's exactly what I needed. And, as you probably realize, you've given another answer to the question I was working on: math.stackexchange.com/questions/8556. You can use LP duality as well as Farkas' Lemma to show that same system you give here has a nonzero solution. –  Mike Spivey Nov 3 '10 at 0:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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