1

I'm studying a proof about PageRank and I have some doubts. The proof states the following:

If $\beta < 1$, and $P$ is a stochastic matrix for column (i.e. $ \lVert P \rVert=1$) then $I-\beta P$ is a $M$-matrix, diagonally-dominant and so its inverse is not negative. Moreover $\lVert (I-\beta P)^{-1} \rVert= \frac1 {1-\beta}$.

I proved that $I−\beta P$ is an $M$−matrix and diagonally-dominant. Does there exist a theorem that states that a matrix of this kind has an inverse that is not negative?. What about the last request? Could someone please help?

hardmath
  • 37,015
Skills
  • 1,433
  • How far did you get trying to verify the claims? It is best to identify a specific difficulty rather than asking someone to do all your thinking for you. – hardmath Jun 10 '17 at 18:47
  • Ok sorry, i edited the question for my doubt. I proved that $I-\beta P$ is a $M-$matrix diagonally-dominant. Could you give me some hint? – Skills Jun 10 '17 at 19:05
  • As the wording of your exercise suggests, knowing the matrix $I-\beta P$ is an $M$-matrix and diagonally dominant does imply the inverse is nonnegative. Diagonally dominant of course implies invertible, and for the proof that the inverse of a nonsingular $M$-matrix is nonnegative, see this previous Question and Accepted Answer. – hardmath Jun 10 '17 at 19:20
  • Ok thanks, very usefull. What about $\lVert( I-\beta P )^{-1}\rVert=\frac1 {1-\beta}$? Do you have any idea? – Skills Jun 10 '17 at 19:25

1 Answers1

1

For the first part note that diagonally dominant matrices are invertible and see the previous Question How to prove that an M-matrix is inverse-non-negative?

Throughout we use the $1$-norm for vectors without explicit annotation:

$$ ||(v_1,v_2,\ldots,v_n)|| = \sum_{i=1}^n |v_i| $$

The final claim you need help with is the $1$-norm of the matrix $||(I-\beta P)^{-1}|| = \frac{1}{1-\beta}$.

Since $||\beta P|| = \beta < 1$, we have a convergent "geometric series" for the inverse of $I-\beta P$:

$$ (I-\beta P)^{-1} = I + \beta P + (\beta P)^2 + (\beta P)^3 + \ldots $$

Now we get by the triangle inequality (taking $1$-norms) that an upper bound on $||(I-\beta P)^{-1}||$ is the fraction $\frac{1}{1-\beta}$:

$$ ||(I-\beta P)^{-1}|| \le \frac{1}{1-\beta} $$

All that remains is to show this upper bound is exact, and for that it suffices to given an example.

In the Question you have written that "$P$ is a stochastic matrix for column". Possibly by this you mean that the matrix $P$ is left stochastic as described in the Wikipedia article Stochastic matrix, i.e. that each column sums to $1$. What this affects is the direction of the multiplication involved in defining the $1$-norm of the matrix $P$. Since you skipped over that part quickly, you are apparently satisfied with the assignment $||P|| = 1$ based on the left multiplication, e.g.

$$ (1,1,1,\ldots,1) P = (1,1,1,\ldots,1) $$

If so, we only need to note that for $(I-\beta P)^{-1}$ we can say the following:

$$ (1,1,1,\ldots,1) (I-\beta P) = (1-\beta) (1,1,1,\ldots,1) $$

It follows that $1$-norm of $(I-\beta P)^{-1}$ being $\frac{1}{1-\beta}$ is attained by the vector $(1,1,1,\ldots,1)$ when the above equation is solved:

$$ (1,1,1,\ldots,1) (I-\beta P)^{-1} = \frac{1}{1-\beta} (1,1,1,\ldots,1) $$

That is, since $(1,1,1,\ldots,1) $ is a left eigenvector of $(I-\beta P)^{-1}$ corresponding to eigenvalue $\frac{1}{1-\beta}$, the $1$-norm is attained here:

$$ || (1,1,1,\ldots,1) (I-\beta P)^{-1} || = \frac{1}{1-\beta} ||(1,1,1,\ldots,1)|| $$

hardmath
  • 37,015
  • Very clearly, thanks! – Skills Jun 10 '17 at 19:44
  • When i see it now, it's not clear last two rows. It's ok last equivalence that you row, but why we can conclude? – Skills Jun 11 '17 at 11:06
  • I "solved" the last equation to show that $\frac{1}{1-\beta}$ is an eigenvalue of $(I-\beta P)^{-1}$ and therefore a lower bound on its $1$-norm. I also added a few clarifications (defn. of $1$-norm, etc.) earlier in my post, if not for your benefit then perhaps for future Readers. – hardmath Jun 11 '17 at 13:31