Strongly connected primitive matrix

  • Thread starter Thread starter Doom of Doom
  • Start date Start date
  • Tags Tags
    Matrix Primitive
Doom of Doom
Messages
85
Reaction score
0
If H is a nxn primitive, irreducible matrix, is it always true that Hn-1 > 0? That is, every entry in Hn-1 is positive.

From my class notes, the definition of H primitive is that there exists some k>0 such that Hk > 0. And a matrix is irreducible if its digraph is strongly connected (that is, it is possible to reach every node from every other node in a finite number of steps).

I am interpreting H as a matrix of a strongly connected digraph. Since it is strongly connected, it should be possible to reach any other node after n-1 steps, and thus (H n -1)ij should be positive since there is a positive probability that it will get to node j from node i in n-1 steps.

Is there a good way to prove that every element of Hn-1 must be positive?
 
Last edited:
Physics news on Phys.org
Ok, I thought about it a little more. Hn-1 might not necessarily be positive, since it might not be possible to go from i to j in exactly n-1 steps, but it would be possible for some k, 1<k<n-1. Also, the diagonal entries of Hn-1 would not necessarily be positive (if for some node you have to hit every other node before coming back to the original node

Thus, I + H + H2 +... + Hn-1 should have all positive entries.

i.e., if the digraph is strongly positive, it should be possible to get from every node to every other node in at most n-1 steps. Thus, for all i,j, with i\neqj, (Hk)ij must be greater than zero for some k, 1<k<n-1.

How can I prove THIS?

thanks
 
Back
Top