Strongly connected primitive matrix

In summary, a nxn primitive, irreducible matrix H is defined as having a positive kth power, where k is some positive integer. The matrix is also strongly connected, meaning that it is possible to reach every node from every other node in a finite number of steps. However, it is not guaranteed that (H n -1)ij will always be positive, as it may not be possible to reach certain nodes in exactly n-1 steps. It is possible for some k, 1<k<n-1, and the diagonal entries of Hn-1 may not be positive. However, the matrix I + H + H2 +... + Hn-1 will have all positive entries, showing that the digraph is
  • #1
Doom of Doom
86
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
  • #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?

thanks
 

FAQ: Strongly connected primitive matrix

What is a strongly connected primitive matrix?

A strongly connected primitive matrix is a square matrix where every element is either 0 or 1, and there exists a path from every element to every other element. This means that every element is connected to every other element through a series of non-zero elements.

What is the significance of a strongly connected primitive matrix?

Strongly connected primitive matrices have several important applications in fields such as graph theory, linear algebra, and computer science. They are often used to model and analyze networks, transportation systems, and other complex systems.

How is a strongly connected primitive matrix different from a regular primitive matrix?

A strongly connected primitive matrix is a square matrix where every element is either 0 or 1 and there exists a path from every element to every other element. A regular primitive matrix is also a square matrix where every element is either 0 or 1, but it may not necessarily have a path from every element to every other element.

What is the relationship between strongly connected primitive matrices and eigenvalues?

Strongly connected primitive matrices have a special property where their largest eigenvalue is equal to their spectral radius. This property is useful in analyzing the stability and behavior of certain systems that can be represented by strongly connected primitive matrices.

How are strongly connected primitive matrices used in computer algorithms?

Strongly connected primitive matrices are often used in algorithms that involve graph traversal and finding paths between nodes. They can also be used in algorithms that involve finding the shortest path or the minimum spanning tree in a graph.

Back
Top