Duality with a stochastic matrix If I have a stochastic matrix $X$- the sum of each row is equal to $1$ and all elements are non-negative.
Given this property, how can I show that:
$x'X=x'$ ,  $x\geq 0$ 
Has a non-zero solution?
I'm assuming this has something to do with proving a feasible dual, but not may be wrong..

Here's the linear programming approach (with considerable help from another user, Fanfan).  Consider the LP
$$\min 0^T y$$
subject to
$$(X - I)y \geq 1,$$
where $0$ and $1$ are, respectively, vectors containing all 0's and all 1's.
By Fanfan's answer to my question this LP is infeasible.  Thus its dual,
$$\max 1^T x$$
subject to
$$x^T (X-I) = 0^T,$$
$$x \geq 0,$$
is either infeasible or unbounded.  But $x = 0$ is a solution, and so this dual problem is feasible.  Thus it must be unbounded.  But that means there must be a nonzero solution $x_1$ in its feasible region.  Thus we have $x_1^T X = x_1^T$ with $x_1 \geq 0$, $x_1 \neq 0$.
(Fanfan's answer to my question also includes another answer to your question - one that uses Farkas's Lemma rather than LP duality.  It ends up being quite similar to my answer here, as, of course, Farkas's Lemma and LP duality are basically equivalent.)
