2
$\begingroup$

The problem:

enter image description here

The attempt at solution:

enter image description here

Am I supposed to just choose random numbers (like I did) just for the sake of proving that there is a solution, or is there a predetermined way of doing this that gives me a better answer (or a range of answers)?

PS: This is for a Introductory Linear algebra class.

  • 1
    Your solution should work for *every* $P$, not just for the one you picked.2011-05-31

2 Answers 2

1

I will assume that you do not know anything about matrices except for the basic definitions. The approach I will take is totally unfeasible for matrices much larger than $3 \times 3$, and is already unpleasant for $3 \times 3$.

From the example that you supplied, the matrix is probably supposed to be column-stochastic. That is, the entries are non-negative, and the entries in any column add up to $1$.

We use more or less what you tried, except that I will let the entry on top left be $a$, and the entry on bottom right be $b$. Then $P$ is the matrix $$ \begin{pmatrix} a & 1-b \\ 1-a & b \end{pmatrix} $$ (We could have let the entry on top right be $b$, and then the entry below would be $1-b$. The calculation would be very similar to the one I will make, but marginally less symmetrical.)

We are looking for a column vector $X$ with non-negative entries such that $PX=X$. We also want the entries not to be both $0$, though the problem did not mention that explicitly. Let the entries of $X$ be $x$ and $y$, with $x$ the top entry and $y$ the bottom one.

Calculate $PX$, with the usual procedure. The top entry of the product is equal to $ax+(1-b)y$, and the bottom entry is $(1-a)x+by$.

We want this vector to be the same as the vector $X$. So the entries must match. We get the equations

$$ax+(1-b)y=x \qquad\text{and}\qquad (1-a)x+by=y$$

With standard "algebra" manipulation, these equations can be rewritten as

$$-(1-a)x + (1-b)y=0 \qquad \text{and}\qquad (1-a)x -(1-b)y=0$$

Note that these two equations say the same thing. The second equation turns out to be the first, with all entries multiplied by $-1$.

So we only need to worry about satisfying the equation $$-(1-a)x +(1-b)y=0$$

If $1-a$ and $1-b$ are both $0$, "any" $x$, $y$ is a solution. If not both $1-a$ and $1-b$ are $0$, there is an obvious solution $x=1-b$ and $y=1-a$, and $x$ and $y$ are not both $0$.

Since $a$ and $b$ are between $0$ and $1$, it follows that $x$ and $y$ are non-negative.

By the way, it is easy to check that if $k$ is any positive number, and if $x$, $y$ is a solution, then $kx$, $ky$ is also a solution. Thus we can, by choosing $k$ appropriately, make $x$, $y$ satisfy some further condition, such as $x+y=1$.

Finally, please remember that the approach I took becomes very unpleasant in larger cases. I wrote out a detailed solution to show that one can solve the problem with very little Linear Algebra background. But in general, you will need the machinery referred to in other solutions.

  • 0
    "If not both 1−a and 1−b are 0, there is an obvious solution x=1−b and y=1−a, and x and y are not both 0. " Could you please explain how you got this? For example, if 1-a is zero, then all you would have left is (1-b)y=02011-06-02
  • 1
    @Virtuoso: If $1-a=0$ then indeed $y=0$. But remember that we are here looking at the case $1-a$, $1-b$, not both $0$. So $1-b \ne 0$. Then if we put $x=1-b$, then $x=1-b$, $y=1-a$, we do get a non-zero solution of the equation, because of the fact that the coefficient of $x$ is $0$.2011-06-02
2

First, show $P$ has $1$ as an eigenvalue. Then let $v$ be a corresponding eigenvector. Show that $(P-I)v=0$. Think about which entries of $P-I$ are positive, which negative, and what that says about the entries of $v$.

  • 0
    Im doing this for a introductory linear algebra class... and I have no clue what you just said.2011-05-31
  • 0
    @Virtuoso, OK, let's take it one step at a time. 1. What's a stochastic matrix? 2. What's meant by eigenvector and eigenvalue? 3. Use the answers to 1. and 2. to show that every stochastic matrix has 1 as an eigenvalue. 4. Show that if $P$ has eigenvalue $1$ with eigenvector $v$ then $(P-I)v=0$, where $I$ is the identity matrix and $0$ is the zero-vector. 5. If $P$ is stochastic, which entries of $P-I$ must be negative? which entries can't be negative? 6. In the light of 5., and $(P-I)v=0$, show that the entries of $v$ can't be of opposite sign. 7. Show that if $v$ works then $kv$ works....2011-05-31
  • 0
    (7., continued) for any real number $k$. 8. What's a state vector? 9. Show that you can choose $k$ to make $kv$ a state vector. You may have to look up some stuff like eigenvector and eigenvalue, but there are plenty of places to do that.2011-05-31