Applications of Positive Matrices
We have now accumulated enough material to pause for a while to discuss its consequences in concrete situations. We have revised linear algebra facts from a functional analytic perspective and obtained a construction to get functions of matrices in a coor
- PDF / 222,198 Bytes
- 12 Pages / 439.371 x 666.142 pts Page_size
- 64 Downloads / 186 Views
Applications of Positive Matrices We have now accumulated enough material to pause for a while to discuss its consequences in concrete situations. We have revised linear algebra facts from a functional analytic perspective and obtained a construction to get functions of matrices in a coordinate-free manner, without the use of the Jordan normal form. This was useful when we considered positive matrices, and enabled us to see important and deep spectral consequences of positivity. The applications of the developed theory are numerous and we have selected just a few representing our taste: graph matrices, the Google matrix, and agestructured population models.
6.1 Motivating Examples Revisited We start by revisiting our motivating examples from Section 1.1.
Graphs Let G = (V, E) be a directed graph with n vertices V = {v1 , . . . , vn } and a set of directed edges E. The graph G is called strongly connected if for every vi ∈ V and every vj ∈ V there is walk in G from vi to vj . This property of the graph can be read from its adjacency matrix. Proposition 6.1. A graph G is strongly connected if and only if its adjacency matrix is irreducible. Proof. Let A = (aij ) be the adjacency matrix of G. By Lemma 5.10, A is reducible iff we can partition the sets of vertices V = V1 ∪ V2 into two disjoint subsets such that after relabeling the vertices we obtain a block-triangular form for A, A11 A12 , (6.1) A= 0 A22 © Springer International Publishing AG 2017 A. Bátkai et al., Positive Operator Semigroups, Operator Theory: Advances and Applications 257, DOI 10.1007/978-3-319-42813-0_6
69
70
Chapter 6. Applications of Positive Matrices
where the block Ak for each k, ∈ {1, 2} corresponds to connections from the set of vertices Vk to the set V . Note that A21 = 0 is equivalent to the fact that there are no direct edges from a vertex in V2 to a vertex in V1 . Let vi ∈ V2 and vj ∈ V1 and assume there exists a walk in G from vi to vj . Then aii1 ai1 i2 · · · ais j = 0 for some i1 , . . . , is ∈ {1, . . . , n}. Observe that in this product there must be a nonzero entry with “mixed” indices, i.e., aik i = 0 with vik ∈ V2 and vi ∈ V1 , which contradicts (6.1). So, if G is strongly connected, A must be irreducible. For the converse assume that G is not strongly connected. Hence there exist vertices vi , vj ∈ V such that there is no walk starting in vi and ending in vj . Let V1 be the set of all initial vertices of walks which end in vj , and let V2 = V \V1 . The sets V1 and V2 are disjoint and nonempty. According to the partition V = V1 ∪ V2 the adjacency matrix has block-triangular form given in (6.1), so A is reducible. As a corollary we obtain a combinatorial characterization of positive irreducible matrices. Note that every positive matrix can be seen as the adjacency matrix of a graph. Corollary 6.2. A positive n × n matrix A, n ≥ 2, is irreducible if and only if for every i, j ∈ {1, . . . , n} there exists an s ∈ N such that (As )ij > 0. We will illustrate another property of the adjacency matrix A in terms of the
Data Loading...
