Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Strongly connected primitive matrix

  1. Nov 24, 2009 #1
    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: Nov 24, 2009
  2. jcsd
  3. Nov 24, 2009 #2
    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[tex]\neq[/tex]j, (Hk)ij must be greater than zero for some k, 1<k<n-1.

    How can I prove THIS?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook