東北大学機関リポジトリTOUR

全文

(1)Interdisciplinary Information Sciences Vol. 26, No. 1 (2020) 1–39 #Graduate School of Information Sciences, Tohoku University ISSN 1340-9050 print/1347-6157 online DOI 10.4036/iis.2020.A.01. Walks: A Beginner’s Guide to Graphs and Matrices Yuki IRIE Research Alliance Center for Mathematical Sciences, Tohoku University, Sendai 980-8579, Japan We provide an introduction to graph theory and linear algebra. The present article consists of two parts. In the first part, we review the transfer-matrix method. It is known that many enumeration problems can be reduced to counting walks in a graph. After recalling the basics of linear algebra, we count walks in a graph by using eigenvalues. In the second part, we introduce PageRank by using a random walk model. PageRank is a method to estimate the importance of web pages and is one of the most successful algorithms. This article is based on the author’s lectures at Tohoku University in 2018 and 2020. KEYWORDS: Graphs, Walks, Eigenvalues, Transfer-Matrix Method, PageRank. 1. Introduction A relation in the real world can be modeled by using a graph consisting of vertices and edges. For example, in Fig. 1(a), vertices represent people and an edge connects two people if they know each other. In certain cases, directed graphs are more suitable than undirected graphs. In Fig. 1(b), species are represented by vertices and predator-prey relationships by directed edges. Figure 1(c) shows the structure of this article.. Fig. 1. Graphs. Received March 31, 2020; Accepted July 2, 2020; J-STAGE Advance published August 25, 2020 Corresponding author. E-mail: [email protected].

(2) 2. IRIE. We now give a formal definition of graphs. We first define undirected graphs. An undirected graph is defined as a pair ðV; EÞ such that V is a set and E is a set of two-element subsets of V. The set V is called the vertex set of and E is called the edge set of . Example 1.1. Let be the undirected graph with vertex set f1; 2; 3; 4; 5g and edge set ff1; 2g; f2; 3g; f1; 3g; f2; 4gg: The graph can be drawn as shown in Fig. 2.. Fig. 2. An undirected graph with five vertices and four edges.. Example 1.2. Let be the undirected graph with vertex set f1; 2; 3; 4; 5g and edge set ff1; 2g; f2; 3g; f3; 4g; f4; 5g; f1; 5gg: The graph can be drawn as shown in Fig. 3.. Fig. 3. An undirected graph with five vertices and five edges.. There are many ways to draw a graph. For example, we can also draw as shown in Fig. 4.. Fig. 4. Another way to draw .. Next, we define directed graphs. A directed graph (or digraph) is defined as a pair ðV; EÞ such that V is a set and E is a subset of V V. The set V is called the vertex set of and E is called the edge set of . Throughout this article, we assume that the vertex set of a digraph is f1; 2; . . . ; ng unless otherwise noted, where n is a positive integer. Example 1.3. Let be the digraph with vertex set f1; 2; 3; 4g and edge set fð1; 1Þ; ð1; 2Þ; ð1; 3Þ; ð2; 3Þ; ð3; 2Þ; ð1; 4Þg. Note that ð2; 3Þ 6¼ ð3; 2Þ. The digraph can be drawn as shown in Fig. 5. An edge that connects a vertex to itself is called a loop. For example, has a loop ð1; 1Þ.. Fig. 5. A digraph with four vertices and six edges..

(3) Walks: A Beginner’s Guide to Graphs and Matrices. 3. Remark 1.4. In our definition, an undirected graph is not allowed to have a loop. A loop in an undirected graph can be considered as a multiset fv; vg. Thus to allow loops, we can define an undirected graph with loops as a pair ðV; EÞ such that V is a set and E is a set of two-element multisets. Example 1.5. Let us consider the digraph shown in Fig. 6. In this digraph, each vertex represents a web page and each edge represents a link. For example, page 4 contains a link to page 1, so there is an edge from page 4 to page 1; however page 1 does not contain a link, so there is no edge from page 1 to page 4. Our question is as follows. Which page is the most important? If there were a few web pages, for example, 100 or 1000 pages, then we could evaluate them by hand. There are, however, a huge number of web pages in the world, so it is impossible to rank them by hand. We want to find a good solution.. Fig. 6. A web graph.. One of the most successful algorithms is PageRank invented by Page and Brin [9]. It is a method to estimate the importance of a page. The key ingredients of PageRank are random walks and eigenvalues. In Sect. 2, we review walks and eigenvalues. We then introduce PageRank by using a random walk model in Sect. 3. Exercise 1.6. Find ten examples of (undirected or directed) graphs in the real world.. 2. Counting Walks In this section, we count walks by using eigenvalues. It is known that many enumeration problems can be reduced to counting walks in a graph. This technique is called the transfer-matrix method (see, for example, [32] for details). 2.1. Walks. A walk from v0 to vl in a digraph is a sequence of vertices ðv0 ; v1 ; . . . ; vl Þ such that ðv0 ; v1 Þ;. ðv1 ; v2 Þ;. ...;. ðvl1 ; vl Þ. are edges of . The number l is called the length of this walk. Example 2.1. Let be the digraph with vertex set f1; 2; 3g and edge set fð1; 2Þ; ð1; 3Þ; ð2; 1Þ; ð3; 1Þg.. Fig. 7. A digraph with three vertices and four edges.. Then . (1) is a walk from 1 to 1 of length 0. . ð1; 2Þ is a walk from 1 to 2 of length 1. . ð1; 1Þ is not a walk since ð1; 1Þ is not an edge. . ð1; 2; 1Þ is a walk from 1 to 1 of length 2. . ð1; 2; 3Þ is not a walk since ð2; 3Þ is not an edge. . ð1; 2; 1; 2; 1; 3Þ is a walk from 1 to 3 of length 5. In this digraph, there are the following six walks of length 2: ð1; 2; 1Þ; ð1; 3; 1Þ; ð2; 1; 2Þ; ð2; 1; 3Þ; ð3; 1; 2Þ; ð3; 1; 3Þ:.

(4) 4. IRIE. Exercise 2.2. Let be the digraph with vertex set f1; 2; 3g and edge set fð1; 2Þ; ð1; 3Þ; ð2; 1Þ; ð2; 3Þ; ð3; 1Þ; ð3; 2Þg: Count walks from 1 to 1 in of length 2, 3, 4, and 5, respectively.. Fig. 8. A digraph with three vertices and six edges.. Remark 2.3. Exercise 2.2 can be immediately interpreted as a word counting problem as follows. Let Wm be the set of m-letter words over fa; b; cg. For example, W1 ¼ fa; b; cg; W2 ¼ faa; ab; ac; ba; bb; bc; ca; cb; ccg; W3 ¼ faaa; aab; aac; . . . ; cccg: m. It is easy to see that the size of Wm is 3 . We count the number of words w 2 Wm satisfies the following two conditions. (w1) The first and the last letters of w are a. (w2) w does not contain aa, bb, cc. For example, abcbca satisfies (w1) and (w2), but acbccba does not satisfy (2) since it contains cc. We can see that this problem is equivalent to counting walks from 1 to 1 of length m 1 in the digraph of Exercise 2.2. 2.2. Adjacency matrices. We have counted walks from 1 to 1 of length 5 in Exercise 2.2. Let us consider the following problem. Problem 2.4. Count the number of walks from 1 to 1 of length 100 in the digraph shown in Fig. 8. It seems impossible to count such walks because it may be complicated to even count them of length 5. However, we can count them by using the adjacency matrix of the digraph . Our goal is to solve Problem 2.4. An n m matrix A is an array of numbers with n rows and m columns. The number in the ith row and the jth column of A is called the ði; jÞ entry of A. Let Aij denote the ði; jÞ entry of A. An n n matrix is called a square matrix. Example 2.5. The following is a 2 2 square matrix: 1 A¼ 2. 3 4. :. The ð1; 2Þ entry of A is 3. The identity matrix In of size n is the n n square matrix such that 1 if i ¼ j, ðIn Þij ¼ 0 if i 6¼ j. For example, I1 ¼ 1 ;. I2 ¼. 1 0. 0 ; 1. 2. 1 0 6 I3 ¼ 4 0 1 0 0. 3. 0 7 0 5; 1. 2. 3. 1. 0 0. 0. 60 6 I4 ¼ 6 40. 1 0 0 1. 07 7 7: 05. 0. 0 0. 1. We will write I instead of In when no confusion can arise. Matrices can be used to study graphs. For a digraph with n vertices, its adjacency matrix A is the n n square matrix whose ði; jÞ entry is defined by 1 if ði; jÞ is an edge of , Aij ¼ 0 if ði; jÞ is not an edge of . Example 2.6. Let be the digraph with vertex set f1; 2; 3g and edge set fð1; 2Þ; ð1; 3Þ; ð3; 1Þg..

(5) Walks: A Beginner’s Guide to Graphs and Matrices. 5. Fig. 9. A digraph with three vertices and three edges.. Then its adjacency matrix A is. 2. 0 1 6 40 0 1 0. 3 1 7 0 5: 0. For example, the ð1; 2Þ entry of A is 1 since ð1; 2Þ is an edge of . 2.3. Matrix multiplication. We can count walks by using matrix multiplication. Let us recall this operation. An n 1 matrix is called a column vector of order n. Let A be a 2 2 matrix. We can consider that A is a function that maps a column vector v of order 2 to the following column vector Av: A11 A12 v1 A11 v1 þ A12 v2 Av ¼ ¼ ; A21 A22 v2 A21 v1 þ A22 v2 where vi is the ði; 1Þ entry of v. Example 2.7. Let. A¼. Then. Av ¼. 1. 0. 0 1. . v1 v2. 1. 0. 0. 1. . ¼. v1 v2. . and. B¼. and. Bv ¼. . 0 1 1. . . 0 0. 1. 1. 0. : . v1 v2. . ¼. v2 v1. :. We can illustrate A and B by using the two-dimensional Euclidean space. The matrix A corresponds to the reflection in the horizontal axis and B corresponds to the rotation through angle 90 (see Fig. 10). To define matrix multiplication, let us consider the composition C of A and B, that is C maps a column vector v to AðBvÞ.. Fig. 10. A, B, and the composition AB.. We can represent the composition C as a matrix as follows: 1 0 0 1 v1 Cv ¼ AðBvÞ ¼ 0 1 1 0 v2 1 0 v2 ¼ v1 0 1 v2 ¼ v1 0 1 v1 : ¼ 1 0 v2.

(6) 6. IRIE. Thus the composition C is corresponding to the matrix 0. 1. :. 0. 1. In general, if A and B are 2 2 matrices, then we can consider the composition C of A and B. We can calculate Cv as follows: A11 A12 B11 B12 v1 Cv ¼ AðBvÞ ¼ A21 A22 B21 B22 v2 A11 A12 B11 v1 þ B12 v2 ¼ A21 A22 B21 v1 þ B22 v2 A11 ðB11 v1 þ B12 v2 Þ þ A12 ðB21 v1 þ B22 v2 Þ ¼ A21 ðB11 v1 þ B12 v2 Þ þ A22 ðB21 v1 þ B22 v2 Þ ðA11 B11 þ A12 B21 Þv1 þ ðA11 B12 þ A12 B22 Þv2 ¼ ðA21 B11 þ A22 B21 Þv1 þ ðA21 B12 þ A22 B22 Þv2 A11 B11 þ A12 B21 A11 B12 þ A12 B22 v1 : ¼ A21 B11 þ A22 B21 A21 B12 þ A22 B22 v2 From this, the composition C corresponds to the matrix A11 B11 þ A12 B21. A11 B12 þ A12 B22. A21 B11 þ A22 B21. A21 B12 þ A22 B22. :. This matrix is called the product of A and B and is denoted by AB. Note that the first column of AB equals Ab1 , where b1 is the first column of B, since A11 A12 B11 A11 B11 þ A12 B21 ¼ ¼ Ab1 : A21 B11 þ A22 B21 A21 A22 B21 Similarly, the second column of AB equals Ab2 , where b2 is the second column of B, since A11 A12 B12 A11 B12 þ A12 B22 ¼ ¼ Ab2 : A21 B12 þ A22 B22 A21 A22 B22 Thus we will write. AB ¼ Ab1. Ab2 :. More generally, let A and B be two n n matrices. Then the matrix product AB is defined to be an n n matrix C such that Cv ¼ AðBvÞ for all column vectors v of order n. Remark 2.8. Although we can define the matrix product AB for an n m matrix A and an m k matrix B, we only discuss the case when n ¼ m ¼ k for simplicity. Exercise 2.9. Let A and B be two n n matrices. Show that AB ¼ Ab1 Ab2 Abn ; where bi is the ith column of B. In particular, the ði; jÞ entry of AB is equal to n X. Aik Bkj :. k¼1. Example 2.10. The identity matrices play a role in matrix multiplication similar to the role of 1 in multiplication. For example, if A is a 2 2 square matrix, then AI2 ¼ I2 A. Indeed, A11 A12 1 0 1 0 A11 A12 A11 A12 A11 A12 AI2 ¼ ¼ ¼ A and I2 A ¼ ¼ ¼ A: 0 1 A21 A22 A21 A22 0 1 A21 A22 A21 A22 In general, if A is an n n square matrix, then AIn ¼ In A ¼ A: Example 2.11. Let A and B be the same as in Example 2.7, that is,.

(7) Walks: A Beginner’s Guide to Graphs and Matrices. A¼. 7. . 1. 0. 0. 1. and. B¼. 0 1 1. :. 0. Then AB ¼. 1. 0. 0. 1. . 0. 1. 1. 0. . ¼. 0. 1. 1. 0. . and BA ¼. 0. 1. 1. 0. . 1. 0. 0. 1. . ¼. 0. 1. 1. 0. :. Thus AB 6¼ BA.. Fig. 11. AB and BA.. As we have seen in Example 2.11, matrix multiplication is not commutative, that is, AB may be different from BA. However, matrix multiplication is associative, that is, if A, B, and C are n n matrices, then AðBCÞ ¼ ðABÞC:. ð2:1Þ. Indeed, the ði; jÞ entries of AðBCÞ and ðABÞC are equal to n X n X. Aik1 Bk1 k2 Ck2 j :. k1 ¼1 k2 ¼1. Thus we will write ABC ¼ AðBCÞ ¼ ðABÞC: We also see that A commutes with A2 , that is, AA2 ¼ A2 A. For a nonnegative integer l, we define the lth power Al of A by Al ¼ A A; |fflfflffl{zfflfflffl} l. 0. where A ¼ I. Example 2.12. Let. 2. 1. 6 A ¼ 40 2 Let us calculate A3 . We see that. Therefore. 2. 32. 2. 2 1. 7 0 5: 0 3. 2. 3. 1. 0. 2. 1. 0. 2. 5. 2. 2. 6 A2 ¼ 4 0 2. 2 1. 76 0 54 0 0 2. 2 1. 7 6 05 ¼ 40 0 2. 4 2. 7 0 5: 4. 5 6 3 2 A ¼ A A ¼ 40. 2 4. 32 2 1 76 0 54 0. 2. 2. 4. Recall that A3 ¼ AA2 . Indeed,. 3. 0. 2. 2. 3 2 0 2 9 7 6 2 05 ¼ 4 0 1 0 10. 6 8. 3 10 7 0 5:. 8. 4.

(8) 8. IRIE. 2. 32. 3. 2. 3. 1. 0. 2. 5. 2. 2. 9. 6. 10. 6 AA2 ¼ 4 0 2. 2 1. 76 0 54 0 0 2. 4 2. 7 6 05 ¼ 4 0 4 10. 8 8. 7 0 5 ¼ A3 : 4. Exercise 2.13. Let be the digraph of Exercise 2.2. (1) Calculate the adjacency matrix of . (2) Calculate A2 , A3 , A4 , and A5 . (3) Compare your answer with that of Exercise 2.2. 2.4. Counting walks using adjacency matrices. The key to solve Problem 2.4 is the following result. Theorem 2.14. Let be a digraph with adjacency matrix A. Then the number of walks from i to j of length l in is equal to the ði; jÞ entry of Al . We present an example to illustrate Theorem 2.14. Let us consider the digraph with vertex set f1; 2; 3g and edge set fð1; 2Þ; ð1; 3Þ; ð2; 1Þ; ð2; 3Þ; ð3; 1Þ; ð3; 2Þg. Its adjacency matrix A is 2 3 0 1 1 6 7 4 1 0 1 5: 1 1 0 Theorem 2.14 asserts that the ð1; 1Þ entry of Al is equal to the number of walks from 1 to 1 of length l. Indeed, the ð1; 1Þ entry of A2 is equal to 2 since ðA2 Þ11 ¼. 3 X. A1k Ak1. k¼1. ¼ A11 A11 þ A12 A21 þ A13 A31 ¼ 0 0 þ 1 1 þ 1 1 ¼ 2; and the number of walks from 1 to 1 of length 2 is 2. Why are they equal? This is because A1k Ak1 ¼ 1 () A1k ¼ Ak1 ¼ 1 () ð1; kÞ and ðk; 1Þ are edges () ð1; k; 1Þ is a walk: Indeed, (1) A11 A11 is equal to 0 and ð1; 1; 1Þ is not a walk. (2) A12 A21 is equal to 1 and ð1; 2; 1Þ is a walk. (3) A13 A31 is equal to 1 and ð1; 3; 1Þ is a walk. Thus the ð1; 1Þ entry of A2 is equal to two and there are two walks from 1 to 1 of length 2. In general, we can see that the number of walks from i to j of length 2 is equal to 3 X. Aik Akj ;. k¼1. that is, the ði; jÞ entry of A2 . Exercise 2.15. Complete the proof of Theorem 2.14. Hint We can prove it by induction or using the fact that the ði; jÞ entry of Al is equal to n X n n X X Aik1 Ak1 k2 Akl2 kl1 Akl1 j : k1 ¼1 k2 ¼1. 2.5. kl1 ¼1. Diagonalization. From Theorem 2.14, we can solve Problem 2.4 by computing ðA100 Þ11 . To this end, we introduce diagonalization. A square matrix A is said to be diagonal if its ði; jÞ entry is 0 whenever i 6¼ j. For example, if 2 3 2 3 1 0 0 4 0 0 2 0 6 7 6 7 A¼ ; B ¼ 4 0 3 0 5; C ¼ 4 0 1 0 5; 0 5 0 0 2 2 0 3.

(9) Walks: A Beginner’s Guide to Graphs and Matrices. 9. then A and B are diagonal matrices, but C is not since C31 ¼ 2. diagonal matrix. Indeed, we can see that 2 # 1 0 l " l 2 0 2 0 6 ¼ and 4 0 3 0 5 0 5l 0 0. Note that it is easy to calculate the lth power of a 3l 2 ð1Þl 0 6 7 05 ¼ 4 0. 0. 0. 3l. 7 0 5:. 2. 0. 2l. 0. 3. Using eigenvalues and eigenvectors, we can reduce the calculation of A100 to the calculation of the 100th power of a diagonal matrix as follows. For simplicity, let A be a 2 2 square matrix. Assume that there are two vectors u1 and u2 and two numbers 1 and 2 such that Au1 ¼ 1 u1 Let U ¼ ½u1. u2 . Then. AU ¼ Au1. and. Au2 ¼ 2 u2 :. Au2 ¼ 1 u1. ð2:2Þ. 2 u2 :. On the other hand, let . 0 : 2. 1 ¼ 0 Then 1 U ¼ U 0. U. . 0 2. ¼ 1 u1. 2 u2 :. Therefore AU ¼ U:. ð2:3Þ. Here, assume that U is invertible, that is, there is the inverse matrix U 1 such that UU 1 ¼ U 1 U ¼ I. By multiplying (2.3) from the right by U 1 , we see that ðAUÞU 1 ¼ AðUU 1 Þ ¼ AI ¼ A and ðUÞU 1 ¼ UU 1 : This implies that A ¼ UU 1 . Hence A100 ¼ ðUU 1 Þ100 ¼ ðUU 1 ÞðUU 1 Þ ðUU 1 ÞðUU 1 Þ |fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl} 100. ¼ UðU. 1. UÞðU. 1. UÞ ðU 1 UÞðU 1 UÞU 1. ¼ U100 U 1 : Since. " . 100. ¼. 1100. 0. 0. 2100. # ;. we can calculate A100 by using A100 ¼ U100 U 1 . Example 2.16. Let . 6 ; 5. 2 A¼ 9. 2 u1 ¼ ; 3. . 1 and u2 ¼ : 1. We see that Au1 ¼. 2. 6. 2. 9. 5. 3. ¼. 22 33. ¼ 11. 2 3. ¼ 11u1. and . 2 6 Au2 ¼ 9 5. . 1 4 1 ¼ ¼ 4 ¼ 4u2 : 1 4 1.

(10) 10. IRIE. Therefore, u1 and u2 satisfy (2.2). Let. 2 u2 ¼ 3. U ¼ u1. . 1. and. 1. ¼. 11. 0. 0. 4. :. We see that AU ¼. 2 9. 6 5. . 2 3. 1 22 ¼ 1 33. 4 ¼ Au1 4. Au2. . and U ¼. 2. . 1. 3 1. . 11. 0. 0. 4. ¼. Therefore AU ¼ U. Moreover, U is invertible. Indeed, 2 1 1 1 5 ¼ 3 1 3 2 0. 22. 4. 33. 4. :. 0 : 5. Therefore the inverse U 1 of U is 1 1 5 3. 1 2. :. Hence A ¼ UU 1 : It follows that l. l. A ¼ U U. 1. # 1 1 1 ¼ 5 3 2 3 1 0 ð4Þl " # 2 11l ð4Þl 1 1 1 ¼ 5 3 2 3 11l ð4Þl " # l l 1 2 11 þ 3 ð4Þ 2 11l 2 ð4Þl ¼ : 5 3 11l 3 ð4Þl 3 11l þ 2 ð4Þl . 2. 1. ". 11l. 0. For example, 2 1 2 11 þ 3 ð4Þ 2 11 2 ð4Þ 1 10 30 ¼ ¼ 5 3 11 3 ð4Þ 3 11 þ 2 ð4Þ 5 45 25 9 and 1 5. ". 2 112 þ 3 ð4Þ2. 2 112 2 ð4Þ2. 3 112 3 ð4Þ2. 3 112 þ 2 ð4Þ2. #. 1 290 ¼ 5 315. 210 395. 6. . 5 . ¼A. ¼ A2 :. From the above example, we can see that u1 and u2 are significant. They are called eigenvectors of A. If we can obtain them, then we can calculate A100 . How can we find them? 2.6. Eigenvectors and eigenvalues. Let A be a square matrix and let be a complex number. If Au ¼ u. ð2:4Þ. for some non-zero column vector u (that is, at least one entry of u is not zero), then is called an eigenvalue of A and u is called an eigenvector of A with eigenvalue . Example 2.17. Let A, u1 , and u2 be the same as in Example 2.16. Since Au1 ¼ 11u1. and. Au2 ¼ 4u2 ;. it follows that u1 and u2 are eigenvectors of A with eigenvalues 11 and 4, respectively. We can find eigenvalues and eigenvectors by using determinants. Let A be an n n square matrix. If n ¼ 1, then define.

(11) Walks: A Beginner’s Guide to Graphs and Matrices. 11. detðAÞ ¼ A11 :. ð2:5Þ. If n > 1, then define n X. detðAÞ ¼. ð1Þiþ1 A1i detðAð1iÞ Þ;. ð2:6Þ. i¼1. where Að1iÞ is the ðn 1Þ ðn 1Þ square matrix obtained from A by removing the first row and the ith column. The number detðAÞ is called the determinant of A. The determinant detðAÞ is also denoted by jAj or. A11 A12 A1n. A21 A22 A2n. . ... : .. ... . .. . .. .. An1 An2 Ann. Example 2.18. If A is a 1 1 matrix, then detðAÞ ¼ A11 . Note that detð½2Þ ¼ j2j ¼ 2. Example 2.19. If A is a 2 2 matrix, then. For example, if A¼. 5. 3. 2. 4. ;. then. 5 detðAÞ ¼. 2. 3. ¼ 5 4 3 ð2Þ ¼ 26: 4. Example 2.20. If A is a 3 3 matrix, then. Let A be an n n square matrix. Then eigenvalues of A are the solutions of the following equation: detðA xIÞ ¼ 0: Example 2.21. Let A be the matrix of Example 2.16. We see that 2 6 x 0 detðA xIÞ ¼ det 9 5 0 x. 2 x 6. ¼. 9 5 x. ¼ ð2 xÞð5 xÞ 54 ¼ x2 7x 44 ¼ ðx 11Þðx þ 4Þ:.

(12) 12. IRIE. Therefore the eigenvalues of A are 11 and 4. Let u be an eigenvector of A with eigenvalue 4. Then 2 6 u1 2u1 þ 6u2 4u1 Au ¼ ¼ ¼ : 9 5 u2 9u1 þ 5u2 4u2 Therefore u1 and u2 satisfy the following system of linear equations: 6u1 þ 6u2 ¼ 0 9u1 þ 9u2 ¼ 0: By solving this, we find a solution u1 ¼ 1 and u2 ¼ 1. Thus 1 1 is an eigenvector of A with eigenvalue 4. In general, . c c. . is an eigenvector of A with eigenvalue 4 for c 6¼ 0. Exercise 2.22. Let A be the matrix of Example 2.21. Find an eigenvector of A with eigenvalue 11. Remark 2.23. We can determine whether a square matrix is invertible by using its determinant. A square matrix A is invertible if and only if detðAÞ 6¼ 0. Moreover, if A is invertible, then 2 3 detðAð21Þ Þ ð1Þnþ1 detðAðn1Þ Þ detðAð11Þ Þ 6 7 detðAð12Þ Þ detðAð22Þ Þ ð1Þnþ2 detðAðn2Þ Þ 7 1 1 6 6 7 1 iþ j ½ð1Þ detðAð jiÞ Þi; j ¼ A ¼ 6 7; .. .. .. .. 7 detðAÞ detðAÞ 6 . . . . 4 5 ð1Þnþ1 detðAð1nÞ Þ ð1Þnþ2 detðAð2nÞ Þ. detðAðnnÞ Þ. . where Að jiÞ is the ðn 1Þ ðn 1Þ square matrix obtained from A by removing the jth row and the ith column. For example, if A is a 2 2 square matrix with detðAÞ 6¼ 0, then A22 A12 1 A1 ¼ : A11 A22 A12 A21 A21 A11 For example, . 1. 1 2. 3 7. . 1 3. . 7 ¼ 2. 3 1. . and. 1 3. 1 2. 1. 1 2 1 1 2 ¼ ¼ 5 3 1 5 3. 1 : 1. Indeed, 2 7 2.7. . 7. 3. 2. 1. . ¼. 1. 0. 0. 1. . and. 1 2 3 2 5 3 1. 1. 1. . 1. ¼. 1. 0. 0. 1. :. Counting walks by using eigenvalues. Let be the digraph of Exercise 2.2. We can now count the number of walks from 1 to 1 of length 100 in . Recall that the adjacency matrix A of is 2 3 0 1 1 6 7 4 1 0 1 5: 1 1 0 We first calculate the eigenvalues of A. Since. x 1 1. detðA xIÞ ¼ 1 x 1. 1 1 x. x 1. 1. . ¼ x. 1 x. 1. 1. 1 þ x. 1. ¼ xðx2 1Þ ðx 1Þ þ ð1 þ xÞ. x. 1.

(13) Walks: A Beginner’s Guide to Graphs and Matrices. 13. ¼ x3 þ 3x þ 2 ¼ ðx 2Þðx þ 1Þ2 ; it follows that the eigenvalues of A are 2 and 1. Next, we calculate eigenvectors. Let u be an eigenvector of A with eigenvalue 2. Then 32 3 2 3 2 3 2 u1 u2 þ u3 2u1 0 1 1 76 7 6 7 6 7 6 Au ¼ 4 1 0 1 54 u2 5 ¼ 4 u1 þ u3 5 ¼ 4 2u2 5: 1. 1. 0. u3. u1 þ u2. 2u3. By solving this, we can find a solution u1 ¼ u2 ¼ u3 ¼ 1. Thus 2 3 1 6 7 415 1 is an eigenvector of A with eigenvalue 2. Indeed,. 2 3 2 3 1 2 6 7 6 7 A4 1 5 ¼ 4 2 5: 1 2. Next, let u be an eigenvector of A with eigenvalue 1. Then 32 3 2 2 3 2 3 u1 u2 þ u3 u1 0 1 1 76 7 6 6 7 6 7 Au ¼ 4 1 0 1 54 u2 5 ¼ 4 u1 þ u3 5 ¼ 4 u2 5: 1. 1. 0. u3. u1 þ u2. By solving this, we find that u1 þ u2 þ u3 ¼ 0. Therefore, for 2 3 1 6 7 4 1 5 and 0 are eigenvectors of A with eigenvalue 1. Let 2 3 1 1 0 6 7 U ¼ 4 1 1 1 5 1 0 1. example, 2 3 0 6 7 4 1 5 1 2. and. Then U is invertible because detðUÞ 6¼ 0. Moreover, 2 3 0 2 1 1 0 1 6 7 B1 6 4 1 1 1 5 @ 4 2 3 1 0 1 1. u3. 2. 6 ¼ 40 0. 0. 0. 1 0. 7 0 5: 1. 31 2 1 1 1 7C 6 1 1 5A ¼ 4 0 1. 0. 2. 3. 3 0 0 7 1 0 5: 0 1. Therefore 2. Al ¼ Ul U 1. 1 6 ¼ 41 1 2. 1 1 0 l. 32 l 2 0 76 1 54 0 1 0 l. ð1Þ 2 16 l ¼ 4 2 ð1Þl 3 2l 0 2 l 2 þ 2ð1Þl 16 l ¼ 4 2 ð1Þl 3 2l ð1Þl. 0. 0. 30 2. 1 1 7B 1 6 l ð1Þ 0 5@ 4 2 1 3 1 1 0 ð1Þl 32 3 0 1 1 1 l 76 2 1 1 7 ð1Þ 54 5 l 1 1 2 ð1Þ 3 l l 2 ð1Þ 2l ð1Þl 7 2l þ 2ð1Þl 2l ð1Þl 5: 2l ð1Þl. 2l þ 2ð1Þl. For example, the number of walks from 1 to 1 of length 5 is 10 since 25 þ 2ð1Þ5 ¼ 10; 3. 31 1 7C 1 5A 2.

(14) 14. IRIE. and that of length 100 is 2100 þ 2 : 3 Recall that the number of words with length m satisfying (w1) and (w2) defined in Remark 2.3 is equal to the number of walks from 1 to 1 of length m 1. As this example shows, some problems can be reduced to counting walks. We could then solve it by using eigenvalues as we have seen. This technique is called the transfer-matrix method [32]. Remark 2.24. We can avoid computing U 1 in the above calculation by using the trace of A as follows. For an n n square matrix A, define the trace trðAÞ of A by n X. trðAÞ ¼. Aii :. i¼1. For example, tr. 4 2. ¼ 4 þ 3 ¼ 7:. 1 3. We can show that trðABÞ ¼ trðBAÞ:. ð2:7Þ. Indeed, trðABÞ ¼. n X. ðABÞii ¼. i¼1. n X n X. Aik Bki ¼. i¼1 k¼1. n X n X. Bki Aik ¼. k¼1 i¼1. n X. ðBAÞkk ¼ trðBAÞ:. k¼1. Let be the digraph of Exercise 2.2 and let A be its adjacency matrix. We now calculate ðAl Þ11 without computing U . Note that 1. trðAl Þ ¼ ðAl Þ11 þ ðAl Þ22 þ ðAl Þ33 : By the symmetry of , we see that ðAl Þ11 ¼ ðAl Þ22 ¼ ðAl Þ33 : Therefore ðAl Þ11 ¼. trðAl Þ : 3. ð2:8Þ. On the other hand, since Al ¼ Ul U 1 , it follows from (2.7) that trðAl Þ ¼ trððUl ÞU 1 Þ ¼ trðU 1 ðUl ÞÞ ¼ trðl Þ: Recall that 2. 2l. 6 l ¼ 4 0 0. 0. 0. 3. ð1Þl. 0. 7 5:. 0. ð1Þl. Therefore trðAl Þ ¼ trðl Þ ¼ 2l þ 2ð1Þl : By combining (2.8) and (2.9), we see that ðAl Þ11 ¼. 2l þ 2ð1Þl : 3. Exercise 2.25. Let be the digraph with vertex set f1; 2g and edge set fð1; 1Þ; ð1; 2Þ; ð2; 1Þg: Count walks from 1 to 1 of length l in .. Fig. 12. A digraph with two vertices and three edges.. ð2:9Þ.

(15) Walks: A Beginner’s Guide to Graphs and Matrices. 15. Exercise 2.26. Let Wm be the set of m-letter words over fa; b; c; dg. Count the number of words w 2 Wm satisfies the following two conditions. (w1) The first and the last letters of w are a. (w2) w does not contain aa, bb, cc, dd. 2.A One-dimensional Ising model In this section, we have reviewed the basics of the transfer-matrix method. By using this method, we solved some enumeration problems. We can apply the transfer-matrix method also to other kinds of problems. Indeed, this method is successfully used in statistical mechanics and has a wide range of applications. As a typical example, we consider the one-dimensional Ising model of spins in this appendix. See [4] for details. The reader can skip this appendix without loss of continuity. Let ðu0 ; u1 ; . . . ; ul Þ be a sequence over f1g. This sequence represents a state of N spins. The energy of ðu0 ; . . . ; ul Þ is defined by l l X X Eðu0 ; . . . ; ul Þ ¼ J ui uiþ1 H ui ; ð2:10Þ i¼0. i¼0. where ulþ1 ¼ u0 , and J and H are constants. For example, Eð1; 1; 1Þ ¼ Jð1 1 þ 1 ð1Þ þ ð1Þ 1Þ Hð1 þ 1 1Þ ¼ J H: The first term (2.10) represents the interaction between pairs of spins. We define the partition function by X ZðÞ ¼ expðEðu0 ; . . . ; ul ÞÞ: ðu0 ;...;ul Þ2f1glþ1. For example, if l ¼ 1, then X ZðÞ ¼. expðEðu0 ; u1 ÞÞ. ðu0 ;u1 Þ2f1g2. ¼ expðEð1; 1ÞÞ þ expðEð1; 1ÞÞ þ expðEð1; 1ÞÞ þ expðEð1; 1ÞÞ: Surprisingly, we can calculate ZðÞ by the matrix-transfer method as follows. Note that Eðu0 ; . . . ; ul Þ ¼ . l X. Jui uiþ1 þ H. i¼0. ui þ uiþ1 2. ¼ u0 ;u1 þ þ ul ;ulþ1 ; where ui ;uiþ1 ¼ Jui uiþ1 H ui þu2 iþ1 . It follows that X ZðÞ ¼ expðEðu0 ; . . . ; ul ÞÞ ðu0 ;...;ul Þ2f1glþ1. X. ¼. . u0 2f1g. X. ¼. expððu0 ;u1 þ þ ul ;ulþ1 ÞÞ. ul 2f1g. . u0 2f1g. X X. expðu0 ;u1 Þ expðul ;ulþ1 Þ:. ul 2f1g. Let A¼. expð1;1 Þ. expð1;1 Þ. . expð1;1 Þ expð1;1 Þ. ¼. expððJ þ HÞÞ. expðJÞ. expðJÞ. expððJ HÞÞ. :. We index the rows and the columns of A by f1g, that is, A11 ¼ expððJ þ HÞÞ;. A1;1 ¼ A1;1 ¼ expðJÞ;. A1;1 ¼ expððJ HÞÞ:. Note that the matrix A can be considered as the adjacency matrix of the weighted digraph shown in Fig. 13.. Fig. 13. A weighted digraph with two vertices.. Then expðu0 ;u1 Þ expðul ;ulþ1 Þ corresponds to the walk ðu0 ; u1 ; . . . ; ul ; ulþ1 Þ in . Recall that ulþ1 ¼ u0 . This implies that.

(16) 16. IRIE. ðAlþ1 Þu0 u0 ¼. X. . u1 2f1g. ¼. X. X. Au0 u1 Au1 u2 Aul u0. ul 2f1g. . u1 2f1g. X. ð2:11Þ expðu0 ;u1 Þ expðul ;ulþ1 Þ:. ul 2f1g. For example,. X. ðA2 Þ11 ¼. A1;u1 Au1 ;1. u1 2f1g. ¼ A11 A11 þ A1;1 A1;1 ¼ expð2ðJ þ HÞÞ þ expð2JÞ: By (2.11),. X. trðAlþ1 Þ ¼ ðAlþ1 Þ11 þ ðAlþ1 Þ1;1 ¼. X. u0 2f1g u1 2f1g. . X. expðu0 ;u1 Þ expðul ;ulþ1 Þ. ul 2f1g. ¼ ZðÞ: Because the eigenvalues of A are. qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ¼ expðJÞ coshðHÞ ðsinhðHÞÞ2 þ expð4JÞ ;. we conclude that ZðÞ ¼ þlþ1 þ lþ1 : In this way, we can calculate the function ZðÞ by the transfer-matrix method.. 3. PageRank We introduce PageRank by using a random walk model. We can search for what we want to know on the internet. For example, if we search ‘‘Tohoku University,’’ then there are about 16,100,000 pages in Google’s estimate. The first item of the search results must be the official web page of Tohoku University. In other words, the official one is estimated as the most important page. How can we estimate the importance of web pages? There are a lot of algorithms to estimate the importance (or centrality) of web pages. One of the successful algorithms is PageRank, which is a measure to estimate the importance of pages. In this section, we define five rank functions ra , rb , rc , rd , and re . The last function re is PageRank. Remark 3.1. According to Google’s page [34], Google uses multiple algorithms to evaluate web pages and the key idea of PageRank seems to still be used as of 2020. Remark 3.2. PageRank has been applied to various fields. Bergstrom [5] used PageRank to rank academic journals. Morrison [25] gave a method of evaluating microarray experiments by using PageRank. Jiang [21] used PageRank to analyze the relation between a road network and human movement. See [16, 23] for more examples. Hereafter, we consider that a vertex represents a web page and an edge represents a link. For notational reasons, which will be explained in Sect. 3.3, we will use transposed adjacency matrices. For an n m matrix A, let A> denote the m n matrix whose ði; jÞ entry is Aji . The matrix A> is called the transpose of A. For example, 2 3> 2 3 2 3 2 3 4 2 0 1 2 > 6 7 6 7 6 7 1 2 5 ¼ 4 3 1 2 5 and 2 0 1 ¼ 4 0 5: 4 0 1 2. 0. 4. 2. 0. 1. Let be a digraph. The transposed adjacency matrix T of is the transpose of the adjacency matrix of , that is, 1 if ð j; iÞ is an edge of , Tij ¼ 0 if ð j; iÞ is not an edge of . Example 3.3. Let be the digraph with vertex set f1; 2; 3g and edge set fð1; 3Þ; ð2; 1Þ; ð3; 1Þ; ð3; 2Þg. Then its transposed adjacency matrix is 3 2 0 1 1 7 6 4 0 0 1 5: 1 0 0.

(17) Walks: A Beginner’s Guide to Graphs and Matrices. 17. Fig. 14. A digraph with three vertices and four edges.. Exercise 3.4. Let be the digraph with vertex set f1; 2; 3; 4g and edge set fð1; 4Þ; ð2; 1Þ; ð3; 1Þ; ð3; 2Þ; ð3; 4Þ; ð4; 1Þ; ð4; 3Þg: Calculate the transposed adjacency matrix of .. Fig. 15. A digraph with four vertices and seven edges.. 3.1. Step A: In-degree rank. If page 1 is important, then it may have a lot of backlinks. In other words, many pages have links to page 1. For example, in Fig. 16, page 1 may be more important than page 2 since the former has more backlinks than the latter.. Fig. 16. Page 1 has 12 backlinks and page 2 has 2 backlinks.. We now define our first rank function. Let be a digraph with n vertices and transposed adjacency matrix T. For a vertex i of , define ra ðiÞ to be the number of backlinks of i, that is, ra ðiÞ ¼. n X. Tij :. ð3:1Þ. j¼1. In other words, ra ðiÞ is the sum of the entries in the ith row of T. The number ra ðiÞ is called the in-degree of i. Example 3.5. Let be the digraph of Example 3.3. We see that ra ð1Þ ¼ 2 since pages 2 and 3 have links to page 1 (see Fig. 17). Table 1 shows ra ðiÞ for i 2 f1; 2; 3g.. Fig. 17. The in-degree of 1 is two. Table 1. In-degrees. i. 1. 2. 3. ra ðiÞ. 2. 1. 1.

(18) 18. IRIE. From this, we estimate the importance of the three pages as follows: page 1 is the most important, and pages 2 and 3 are the second. Exercise 3.6. Let be the digraph of Exercise 3.4. Estimate the importance of the four pages by using ra . 3.2. Step B: Weighted in-degree rank. Suppose that some tourist attractions in Sendai are recommended on pages 1 and 2. Page 1 lists ten places and page 2 lists one hundred places. If pages 1 and 2 are equally reliable, we will consider that the recommendation of page 1 should be more worth than that of page 2. Based on this idea, we assign a weight to each edge by using out-degrees.. Fig. 18. Page 1 lists ten places and page 2 lists one hundred places.. We first define out-degrees and weights. Let be a digraph with n vertices and transposed adjacency matrix T. For a vertex i of , the out-degree di of i is defined to be the number of edges from i, that is, di ¼. n X. Tki :. k¼1. If ði; jÞ is an edge of , then we assign weight 1=di to this edge. Let H denote the n n square matrix whose ði; jÞ entry is Tij : di The matrix H is called the hyperlink matrix of . Example 3.7. Let be the digraph of Example 3.5. Since page 1 has one link, the out-degree d1 of page 1 is one, so the edge ð1; 3Þ is weighted by 1. Similarly, the edge ð2; 1Þ is weighted by 1. Since page 3 has two links, the out-degree d3 of page 3 is two, so the edges ð3; 1Þ and ð3; 2Þ are weighted by 12 . Figure 19 shows the weights and the hyperlink matrix of .. Fig. 19. Weighs and hyperlink matrix.. We now define the second rank function. For a vertex i of a digraph , we define rb ðiÞ as the weighted in-degree of i, that is, rb ðiÞ ¼. n X Tij j¼1. di. :. In other words, rb ðiÞ is the sum of the entries in the ith row of the hyperlink matrix of . Example 3.8. Let be the digraph of Example 3.7. By the definition of rb , we see that 1 3 ¼ ; 2 2 1 1 rb ð2Þ ¼ 0 þ 0 þ ¼ ; 2 2 rb ð3Þ ¼ 1 þ 0 þ 0 ¼ 1: rb ð1Þ ¼ 0 þ 1 þ. ð3:2Þ.

(19) Walks: A Beginner’s Guide to Graphs and Matrices. 19. Therefore we estimate the importance of the three pages as follows: page 1 is the most important, page 3 is the second, and page 2 is the third. Exercise 3.9. Let be the digraph of Exercise 3.6. Estimate the importance of the four pages by using rb . 3.3. Step C: Eigenvector rank. Suppose again that some tourist attractions are recommended on pages 1 and 2. This time, suppose that both pages list ten places, but page 1 is much more reliable than page 2. Thus we consider that the recommendation of page 1 should be more worth than that of page 2. How can we achieve this? Let be a digraph with n vertices and transposed adjacency matrix T. For a vertex i of , we will define rc ðiÞ by X Tij rc ðiÞ ¼ rc ð jÞ: ð3:3Þ d j¼1 j For example, suppose that . rc ð1Þ ¼ 500, d1 ¼ 10, page 1 has a link to page 3, . rc ð2Þ ¼ 3, d2 ¼ 10, page 2 has a link to page 4. Then page 1 gives 50 scores to page 3, and page 2 gives 0.3 scores to page 4 as expected. Although this definition looks strange because rc is defined by using rc , it works well as we will see in Example 3.10.. Fig. 20. Idea of rc .. Example 3.10. Let be the digraph of Example 3.7. By the definition of rc , we find that 1 1 rc ð3Þ ¼ rc ð2Þ þ rc ð3Þ; 2 2 1 1 rc ð2Þ ¼ 0 rc ð1Þ þ 0 rc ð2Þ þ rc ð3Þ ¼ rc ð3Þ; 2 2 rc ð3Þ ¼ rc ð1Þ þ 0 rc ð2Þ þ 0 rc ð3Þ ¼ rc ð1Þ:. rc ð1Þ ¼ 0 rc ð1Þ þ. rc ð2Þ þ. ð3:4Þ ð3:5Þ ð3:6Þ. Fig. 21. rb and rc .. This can be seen as a system of linear equations of rc ð1Þ, rc ð2Þ, and rc ð3Þ. Let us solve it. Since rc ð2Þ ¼ 12 rc ð3Þ and rc ð3Þ ¼ rc ð1Þ, it follows that 2 3 2 3 rc ð1Þ 2 6 7 6 7 4 rc ð2Þ 5 ¼ c4 1 5: rc ð3Þ. 2. If c ¼ 0, then rc ðiÞ ¼ 0 for i 2 f1; 2; 3g, and hence c should be non-zero for our purpose. By using rc , we estimate the importance of the three pages as follows: pages 1 and 3 are the most important, and page 2 is the second. Here, we can rewrite (3.4)–(3.6) as follows: 32 2 3 2 3 0 1 12 rc ð1Þ rc ð1Þ 76 6 7 6 7 4 rc ð2Þ 5 ¼ 4 0 0 12 54 rc ð2Þ 5: rc ð3Þ rc ð3Þ 1 0 0.

(20) 20. IRIE. In other words, rc ¼ Hrc ; >. where rc ¼ ½rc ð1Þ rc ð2Þ rc ð3Þ . Surprisingly, rc therefore is an eigenvector of H with eigenvalue 1. This is the reason why we prefer transposed adjacency matrices to adjacency matrices. (We have to consider left eigenvectors if we use adjacency matrices. Since this article is for beginners, the author avoided using left eigenvectors to prevent confusion.) Pn From the above P observation, we define rc as an eigenvector of H with eigenvalue 1 such that i¼1 rc ðiÞ ¼ 1. Here, the condition rc ðiÞ ¼ 1 is for normalization. Unfortunately, there is a problem with this definition because T may not have such an eigenvector. Exercise 3.11. Let be the digraph of Exercise 3.9. Estimate the importance of the four pages by using rc . Exercise 3.12. Let be the digraph with vertex set f1; 2; 3g and edge set fð1; 3Þ; ð3; 1Þ; ð3; 2Þg. Estimate the importance of the three pages by using rc .. Fig. 22. A digraph with three vertices and three edges.. 3.4. Random walks. A vertex said to be dangling or sink if its out-degree is 0. For example, if is the digraph of Exercise 3.12, then the out-degree d2 of vertex 2 is 0, so this vertex is dangling. It a digraph has no dangling vertices, then its hyperlink matrix has an eigenvector with eigenvalue 1 (see Remark 3.18); however, if it has a dangling vertex, then its hyperlink matrix may not have such an eigenvector as we have seen in Exercise 3.12. To solve the above problem, Brin and Page adjusted the hyperlink matrix by using a random walk model. In this model, we randomly click a link to get another page. Suppose that page i has a link to page j. If we are on page i, then we move to page j in the next step with probability d1i . Example 3.13. Let be the digraph with vertex set f1; 2; 3; 4g and edge set fð1; 2Þ; ð1; 3Þ; ð1; 4Þg. If we are now on page 1 in this digraph, then the probability that we next move to page 2 is 13 .. Fig. 23. A random walk on .. Example 3.14. Let be the digraph of Example 3.7. We are now on page 1. In the first step, we move to page 3. In the second step, we either move to page 1 with probability 12 or move to page 2 with probability 12 .. Fig. 24. A random walk on ..

(21) Walks: A Beginner’s Guide to Graphs and Matrices. 21. Let pt ðiÞ be the probability of being on page i at step t and 2 3 pt ð1Þ 6 7 pt ¼ 4 pt ð2Þ 5: pt ð3Þ Then 2 3 1 6 7 p0 ¼ 4 0 5;. 213. 2 3 0 6 7 p1 ¼ 4 0 5;. 0. 2 1 2. 6 7 p2 ¼ 4 5;. 1. We see that. 213. 213. 6 7 p3 ¼ 4 0 5;. 6 7 p4 ¼ 4 14 5:. 2. 1 2. 0. 3 2 0 pt ð1Þ 6 7 6 4 pt ð2Þ 5 ¼ 4 0 2. pt ð3Þ. 1. 0. 1 2 1 2. 0. 0. 1. 4. 1 2. 32. 3 pt1 ð1Þ 76 7 54 pt1 ð2Þ 5: pt1 ð3Þ. Thus pt ¼ H pt1 ¼ H t p0 : For example,. 2 p15 ¼ H 15 p0 ¼. Since. 51. 3. 2. 0:3984375. 3. 2. 0:4. 3. 1 6 7 6 7 6 7 4 26 5 ¼ 4 0:203125 5 4 0:2 5: 128 51 0:3984375 0:4 2 3 2 3 2 0:4 16 7 6 7 rc ¼ 4 1 5 ¼ 4 0:2 5; 5 2 0:4. we can observe that the limit of pt as t approaches 1 may be equal to rc (see Remark 3.15). From this observation, we will define PageRank by adjusting our random work model in the next two sections. Remark 3.15. Let us illustrate the reason why the limit of pt is equal to rc . The hyperlink matrix H has the following three eigenvalues: 1 i 1 þ i ; ; 2 2 where i is the imaginary unit. The corresponding eigenvectors are as follows: 2 3 2 3 2 3 2 1 1 6 7 6 7 6 7 u1 ¼ 4 1 5; u2 ¼ 4 i 5; u3 ¼ 4 i 5: 2 1 þ i 1 i 1;. We can express p0 as a linear combination of u1 ; u2 ; u3 . Indeed, p0 ¼. 1 3i 3þi u1 þ u2 þ u3 : 5 10 10. Therefore pt ¼ H t p0 1 3i 3þi u1 þ u2 þ u3 ¼ Ht 5 10 10 t 1 3 i 1 i 3 þ i 1 þ i t u2 þ u3 : ¼ u1 þ 5 10 2 10 2 Since the absolute values of that is, rc . 3.5. 1i 2. and. 1þi 2. are less than 1, we see that the limit of pt as t approaches 1 is equal to 15 u1 ,. Step D: First adjustment. If we reach a dangling vertex, then we get stuck. For example, in the left digraph in Fig. 25, if we are on page 4, we cannot walk anymore. To keep going, we may enter an address into the URL bar. In other words, we jump to a random.

(22) 22. IRIE. page. This is called teleportation. By adding teleportation, we obtain the right graph in Fig. 25. For example, if we are on page 4, then we will move to page i with probability 14 for i 2 f1; 2; 3; 4g.. Fig. 25. The right digraph is obtained from the left one by adding teleportation.. We now define the fourth rank function. Let be a digraph with hyperlink matrix H. Let S be the matrix obtained from H by replacing the 0 columns with 1n 1, where 0 and 1 are the column vectors whose all entries are 0 and 1, respectively. For example, if is the left graph in Fig. 25, then 2 3 0 12 0 0 6 7 60 0 0 07 6 7; H¼6 7 4 0 12 0 0 5 1 0 1 0 so the fourth column is 0. Hence 2. 0. 6 60 S¼6 60 4 1. 1 2. 0. 0 0 1 2. 0. 0 1. 1 4 1 4 1 4 1 4. 3 7 7 7: 7 5. The matrix S will be called P the stochastic matrix of in this article. We define rd to be an eigenvector of S with eigenvalue 1 satisfying ni¼1 rd ðiÞ ¼ 1. Exercise 3.16. Let be the digraph of Exercise 3.12. Estimate the importance of the three pages by using rd . Exercise 3.17. Let be the digraph with vertex set f1; 2; 3; 4g and edge set fð1; 2Þ; ð2; 1Þ; ð3; 4Þ; ð4; 3Þg. Estimate the importance of the four pages by using rd . Remark 3.18. Although the hyperlink matrix H may not have an eigenvector with eigenvalue 1 as we have seen in Exercise 3.12, the matrix S always has such an eigenvector. Moreover, we can show that the first eigenvalue of S is 1, that is, if 1 ; 2 ; . . . ; n are the eigenvalues of S with j1 j j2 j jn j, then 1 ¼ 1. We first show that 1 is an eigenvalue of S. By the definition of S, we see that the sum of the entries in the ith column of S is 1, that is, n X. Ski ¼ 1:. k¼1. Therefore the all-one vector 1 is an eigenvector of the matrix S> with eigenvalue 1, since 32 3 2 Pn 3 2 3 2 1 1 S11 Sn1 k¼1 Sk1 7 7 6 7 6 7 6 6 .. 76 .. 7 ¼ 6 .. . .. 7 ¼ 6 .. 7: S> 1 ¼ 6 5 4.5 4 .. . 54 . 5 4 . . Pn 1 S1n Snn 1 k¼1 Skn This implies that detðS> IÞ ¼ 0: Since detðS IÞ ¼ detððS IÞ> Þ ¼ detðS> IÞ; it follows that 1 is also an eigenvalue of S. Next, we show that 1 is the first eigenvalue of S. Suppose that S has an eigenvector u with eigenvalue . Then.

(23) Walks: A Beginner’s Guide to Graphs and Matrices. ui ¼. n X. 23. Sij uj. for every i 2 f1; 2; . . . ; ng:. ð3:7Þ. j¼1. We choose i so that jui j ¼ maxfju1 j; ju2 j; . . . ; jun jg: Note that jui j > 0 since u is an eigenvector. By (3.7), we see that. n n. X. X. Sij uj jS u j jui j ¼. j¼1 ij j. j¼1 ¼. n X. Sij jui j ¼ jui j:. j¼1. Therefore jj 1. 3.6. Step E: PageRank. As we have seen in Exercise 3.17, rd may not be uniquely determined. We make the second adjustment. Even when we are on a non-dangling page, we may enter an address into the URL bar. Fix a real number with 0 < < 1. On a non-dangling page, we either click a link with probability or teleport to a random page with probability 1 . Example 3.19. Let be the digraph of Exercise 3.17. Set ¼ 45 . Suppose that we are on page 1. We either click a link and move to page 2 with probability 45 or teleport to a random page with probability 15 . Thus we move to page 2 4 1 1 1 with probability 17 20 (¼ 5 þ 5 4 ) or move to page i with probability 20 for i 2 f1; 3; 4g.. Fig. 26. We either click a link or teleport to a random page.. For a digraph with n vertices, define 1 G ¼ S þ ð1 Þ J; n where S is the stochastic matrix of and J is the all-one matrix, that is, Jij ¼ 1 for 1 i; j n. Then the ð j; iÞ entry of G is equal to the probability of moving to page i from page j. The matrix G is called P the Google matrix (with parameter ) of . We define re to be an eigenvector of G with eigenvalue 1 satisfying re ðiÞ ¼ 1. The vector re is called the PageRank of . 3.17. Set ¼ 45 . Then 21 1 1 13 2 1 3 0 20 4 4 4 4 6 1 1 1 1 7 6 17 6 6 7 07 1 7 4 4 4 4 6 20 7þ 61 1 1 17 7¼6 1 15 5 6 4 4 4 4 4 5 4 20 1 1 1 1 1 1 0. Example 3.20. Let be the digraph of Exercise 2 0 1 0 4 1 1 46 61 0 0 G¼ Sþ J ¼ 6 5 5 4 5 40 0 0 0 0. 4. 17 20 ,. Note that the probability moving page 1 to page 2 is which is We now calculate re . Let re ¼ ½x y z w> . By definition, 2 2 3 1 17 1 x 6 6y7 1 6 17 1 1 6 7 6 6 7¼ 4 z 5 20 4 1 1 1 w Hence. 1. 1. 17. 4. 4. 4. 20. 17 20 1 20 1 20 1 20. 1 20 1 20 1 20 17 20. 1 20 1 20 17 20 1 20. equal to the ð2; 1Þ entry of G. 32 3 1 x 7 6 1 76 y 7 7 76 7: 17 54 z 5 1 w. 3 7 7 7: 7 5.

(24) 24. IRIE. 19x þ 17y þ z þ w ¼ 0;. ð3:8Þ. 17x þ 19y þ z þ w ¼ 0; x þ y 19z þ 17w ¼ 0;. ð3:9Þ ð3:10Þ. x þ y þ 17z þ 19w ¼ 0:. ð3:11Þ. By adding (3.8) and (3.9), 2x 2y þ 2z þ 2w ¼ 0: Hence x þ y ¼ z þ w:. ð3:12Þ. It follows from (3.8), (3.10), and (3.12) that 18x þ 18y ¼ 0. and. 18z þ 18w ¼ 0:. Therefore x ¼ y ¼ z ¼ w. Since x þ y þ z þ w ¼ 1, we see that 2 3 1 6 1 617 7 re ¼ 6 7: 4 415 1 Note that re is uniquely determined. In this section, we have considered the question of how we can estimate the importance of pages. As an answer to this question, we introduced PageRank re . In Steps A and B, we defined ra and rb by using degrees. We then provided rc by using eigenvalues in Step C, and found that rc sometimes does not exists. To solve this problem, by using the random walk model, we defined rd and re in Steps D and E. Although rd may not be uniquely determined, PageRank re is uniquely determined (see Remark 3.23). Exercise 3.21. Let be the digraph with vertex set f1; 2; 3g and edge set fð1; 2Þ; ð1; 3Þ; ð3; 1Þ; ð3; 2Þg. Set ¼ 23 . Estimate the importance of the three pages by using re .. Fig. 27. A digraph with three vertices and four edges.. Exercise 3.22. Let be the digraph of Example 1.5. Set ¼ 45 . Estimate the importance of the twelve pages by using re (we may need to use a computer program). Remark 3.23. By using the Perron–Frobenius theorem [13–15, 28], we can show that re is positive and uniquely determined (see, for example, [22, 24] for details). A matrix is said to be positive if all entries are positive. For example, " # 1 12 3 2. 3. 1. 0. 4. 3. is positive and . . is not positive since the ð1; 2Þ entry is not positive. The Perron–Frobenius theorem asserts that if a square matrix A is positive then the following statements hold. (1) The first eigenvalue 1 of A is positive and simple, that is, if u and u0 are eigenvectors of A with eigenvalue 1 , then u ¼ cu0 for some c 6¼ 0. (2) There is a positive eigenvector with eigenvalue 1 . As we have seen in Remark 3.18, the first eigenvalue of the matrix G is 1. Since G is positive, it follows from the Perron–Frobenius theorem that re is positive and uniquely determined..

(25) Walks: A Beginner’s Guide to Graphs and Matrices. 25. A Solutions A.1. Section 1. Exercise 1.6 We give some examples of graphs. See [3, 8, 10, 19, 33] for other examples. (1) Transportation The graph in Fig. A·1 shows the Tohoku University campus bus stops [35].. Fig. A1. Tohoku University campus bus stops.. (2) Dressing The digraph in Fig. A·2 shows the order of dressing in the morning. For example, we have to wear socks before wearing shoes.. Fig. A2. Dressing in the morning.. (3) Matching In the graph in Fig. A·3, vertices represent men and women, and there is an edge between a man and a woman if they prefer each other. We want to make as many couples as possible. Let be an undirected graph without loops. A matching of is a set of edges such that no two of them share common vertices. A matching is said to be perfect if it contains all vertices. For example, Fig. A·4 shows a perfect matching.. Fig. A3. Three women and three men.. Fig. A4. A perfect matching.. (4) Scheduling Suppose that there are five meetings. The members of each meeting are shown in Table A·1. Each meeting uses an hour. We want to schedule them to avoid conflicts. For example, Meetings 1 and 2 cannot be scheduled for the same time slot because Alice has to attend both of them. If all members will gather at 1 pm, what time can they finish the five meetings in the shortest? We can model this problem by using the following graph..

(26) 26. IRIE Table A1. Members of the five meetings. Meeting 1. Meeting 2. Meeting 3. Meeting 4. Meeting 5. Alice Bob. Alice Carol Dave. Carol Eikichi Goro. Dave Fumiko Goro. Bob Eikichi Fumiko. Fig. A5. A graph whose vertices represent the five meetings.. In this graph, fi; jg is an edge if and only if there is a person who has to attend Meetings i and j. For example, f1; 2g is an edge since Alice is a member of both Meetings 1 and 2. Our scheduling problem is equivalent to coloring the vertices of the graph so that two vertices i and j are assigned two different colors whenever fi; jg is an edge. For example, we can color this graph by using three colors as shown in Fig. A·6.. Fig. A6. Vertices 1 and 4 are colored by black, 2 and 5 by gray, and 3 by white.. From this, we can schedule the meetings as follows: 1 pm Meeting 1 2 pm Meeting 2 3 pm Meeting 3. Meeting 4 Meeting 5. (5) Rigidity Consider a grid framework consists of rods and rotatable joints. Rods cannot stretch and compress. For example, the framework in Fig. A·7(a) is flexible. In contrast, the framework in Fig. A·7(b) is rigid because it cannot be deformed without changing the lengths of rods.. Fig. A7. Rigidity.. Let us consider the following two frameworks in Fig. A·8.. Fig. A8. Rigid or flexible?.

(27) Walks: A Beginner’s Guide to Graphs and Matrices. 27. The left framework is rigid and the right one is flexible. Indeed, the right framework can be deformed without changing the lengths of any rods as shown in Fig. A·9.. Fig. A9. We can deform the right framework.. How can we determine whether a framework is rigid or flexible? We can solve this problem by using graphs. For an n m grid framework, we consider the graph with vertex set fr1 ; . . . ; rn ; c1 ; . . . ; cm g and edge set ffri ; cj g : there is a rod in the ith row and the jth columng: For example, the corresponding graphs of the two frameworks in Fig. A·8 are as shown in Fig. A·10.. Fig. A10. Corresponding graphs.. We see that the left graph in Fig. A·10 is connected, that is, there is a walk from i to j for every pair of vertices i and j. Here, a walk is a sequence ðv0 ; v1 ; . . . ; vl Þ of vertices such that ðv0 ; v1 Þ; ðv1 ; v2 Þ; . . . ; ðvl1 ; vl Þ are edges. See Sect. 2 for details. In contrast, the right graph is not connected. It is known that a grid framework is rigid if and only if the corresponding graph is connected (see, for example, [2, 7, 19]). For example, the framework in Fig. A·11 is flexible.. Fig. A11. A flexible framework.. See [17] for details of rigidity. (6) Gray codes In the binary numeral system, a number is expressed by using 0 and 1. For example, 5 ¼ 22 þ 1 ¼ 1012 and 11 ¼ 23 þ 2 þ 1 ¼ 10112 . The subscript 2 indicates the base. Let us consider 3 ¼ 0112 and 4 ¼ 1002 . The two numbers 3 and 4 are near but their representations differ in three positions. In some cases, this is not convenient. For example, in some devices like rotary encoders, there is a risk of reading bits before the bit change is completed. Let us consider the transition from 0112 (¼ 3) to 1002 (¼ 4). Because bits do not change simultaneously, 0112 changes to 1002 via, for example, 0012 and 1012 as follows: 0112 ! 0012 ! 1012 ! 1002 . Thus there is a possibility to produce 0012 or 1012 accidentally. We can solve this problem by using Gray codes [18]. In the following number system, two successive numbers differ only in one position. 0 1 2 3 4 5 6 7 000 001 101 100 110 111 011 010 This is called a Gray code. In general, an n-bit Gray code is a (cyclic) ordering of n-bit strings such that two successive strings differ only in one position. See [12, 29] for details of Gray codes..

(28) 28. IRIE. Gray codes correspond to a special type of walks, called Hamiltonian cycle. Let be the graph shown in Fig. A·12. Then our Gray code corresponds to the following walk: ð000; 001; 101; 100; 110; 111; 011; 010Þ: A walk is called a Hamiltonian cycle if it satisfies the following two conditions: (1) It visits every vertex exactly once. (2) vl ¼ v0 .. Fig. A12. A Gray code corresponds to a Hamiltonian cycle.. (7) Games We can represent certain games by using digraphs. Let us consider the following game called Treblecross or 007. This game is a Tic-Tac-Toe game played by two players with a strip of squares. Two players alternately write the symbol X in a square. The player who creates a line of three crosses wins. Figure A·13 shows an example of Treblecross. Although this game is simple, it is not completely solved. We now represent Treblecross as a digraph. Consider the digraph whose vertex set is the set of positions in this game and there is an edge from a position P to a position Q if moving from P to Q is legal. Figure A·15 shows the digraph of Treblecross with four squares. In this way, many games can be represented by using digraphs. This allows us to analyze them in a unified manner. We will describe how to analyze a class of games, including Treblecross, called impartial games.. Fig. A13. An example of Treblecross.. A (short) impartial game is defined as a digraph such that the maximum length of a walk from each vertex is finite. For example, Treblecross is an impartial game; however, the digraph with vertex set f1; 2g with edge set fð1; 2Þ; ð2; 1Þg is not since the walk ð1; 2; 1; 2; . . .Þ has infinite length. Let be an impartial game. We will consider the vertices of as the positions and the edges as the legal moves (see Remark A.1). If P and Q are positions in , then Q is called an option or out-neighbor of P if ðP; QÞ is an edge in . We can show that every impartial game has a terminal position, that is, a position without options. For example, Treblecross with four squares has the three terminal positions shown in Fig. A·14.. Fig. A14. Terminal positions.. Remark A.1. We can consider as the following two-player game. Before the game, we pick an initial position and put a token on it. Two players alternately move the token to an option of the position where the token is currently placed. The winner is the player who moves the token to a terminal position. For example, in Treblecross, the initial position is the position where every square is empty, and moving to an option corresponds to writing the symbol X in a square. We can analyze impartial games in a unified manner by using Sprague–Grundy functions. For a vertex P of an impartial game , define the Sprague–Grundy value sgðPÞ of P by.

(29) Walks: A Beginner’s Guide to Graphs and Matrices. 29. sgðPÞ ¼ mexfsgðQÞ : Q is an option of Pg; where mex M ¼ minfm 2 N : m 62 Mg and N is the set of nonnegative integers. Recall that an impartial game has a terminal position. By definition, if P is terminal, then sgðPÞ ¼ mex ; ¼ 0: Sprague [31] and Grundy [20] independently proved that we can force a win by moving to an option with Sprague– Grundy value 0. In fact, they obtained a much stronger theorem, which states that every position in an impartial game can be characterized by its Sprague–Grundy value in some sense. See, for example, [1, 6, 11, 30] for details. Let us calculate the Sprague–Grundy function of Treblecross with four squares. First, we introduce a notation for positions in Treblecross. We represent positions in Treblecross as strings over f0; 1g. For example, the initial position is represented as 0000 and the position only marked the third square is 0010. We now calculate the Sprague–Grundy function of Treblecross. Since 1110, 0111, and 1111 are terminal, their Sprague–Grundy values are 0. Therefore sgð1101Þ ¼ sgð1011Þ ¼ mexfsgð1111Þg ¼ mexf0g ¼ 1: We also see that sgð1100Þ ¼ mexfsgð1110Þ; sgð1101Þg ¼ mexf0; 1g ¼ 2 and sgð1010Þ ¼ mexfsgð1110Þ; sgð1011Þg ¼ mexf0; 1g ¼ 2: By symmetry, sgð0011Þ ¼ sgð0101Þ ¼ 2. In this way, we can calculate the Sprague–Grundy values of the other positions (see Fig. A·15). The Sprague–Grundy theorem asserts that the first player can force a win by moving to 0100 or 0010 since their Sprague–Grundy values are 0. Let us consider the reason why we can force a win by moving to an option with Sprague–Grundy value 0. See Fig. A·16. Suppose that the Sprague–Grundy value of the current position P is greater than 0. Then P has an option Q with sgðQÞ ¼ 0, so we move to Q. Since Q has no option with Sprague–Grundy value 0, the opponent cannot move anymore or has to move an option R with sgðRÞ > 0. If he cannot move, then we win. If he moves R, then we again can move to an option S of R with sgðSÞ ¼ 0. In this way, we can keep moving to an option with Sprague–Grundy value 0. Because the Sprague–Grundy value of a terminal position is 0, we can force a win in this way. We have seen that games can be analyzed by using their Sprague–Grundy functions. Finding an explicit formula for the Sprague–Grundy function of a game is challenging. For example, the Sprague–Grundy function of Treblecross is not determined, which is one of the most famous open problems in combinatorial game theory [27].. Fig. A15. The digraph of Treblecross with four squares.. Fig. A16. We can force a win by moving to an option with Sprague–Grundy value 0..

(30) 30. IRIE. A.2. Section 2. Exercise 2.2 (1) (2) (3) (4). 2 walks of length 2: ð1; 2; 1Þ, ð1; 3; 1Þ. 2 walks of length 3: ð1; 2; 3; 1Þ, ð1; 3; 2; 1Þ. 6 walks of length 4: ð1; 2; 1; 2; 1Þ, ð1; 2; 1; 3; 1Þ, ð1; 2; 3; 2; 1Þ, ð1; 3; 1; 2; 1Þ, ð1; 3; 1; 3; 1Þ, ð1; 3; 2; 3; 1Þ. 10 walks of length 5: ð1; 2; 1; 2; 3; 1Þ, ð1; 2; 1; 3; 2; 1Þ, ð1; 2; 3; 1; 2; 1Þ, ð1; 2; 3; 1; 3; 1Þ, ð1; 2; 3; 2; 3; 1Þ, ð1; 3; 1; 2; 3; 1Þ, ð1; 3; 1; 3; 2; 1Þ, ð1; 3; 2; 1; 2; 1Þ, ð1; 3; 2; 1; 3; 1Þ, ð1; 3; 2; 3; 2; 1Þ. We can easily count walks from 1 to 1 of length 5 by using a digraph as follows. There are two choices for v1 . We first count the case when v1 is vertex 2. See the digraph in Fig. A·17. There are two choices for v2 , vertex 1 or vertex 3. In this way, there are four choices for v3 and there are eight choices for v4 . Note that there is no edge from vertex 1 to itself. Thus ð1; 2; 1; 2; 1; 1Þ is not a walk, but ð1; 2; 1; 2; 1; 3; 1Þ is a walk. We then find five walks with v1 ¼ 2. By symmetry, we can see that there are five walks from 1 to 1 with v2 ¼ 3. Therefore there are ten walks from 1 to 1 of length 5 in .. Fig. A17. Ten walks from 1 to 1 of length 5.. Exercise 2.9 Let C ¼ AB. By definition, Cv ¼ AðBvÞ for every column vector v of order n. Hence 2 3 2 32 3 C11 C11 C12 C1n 1 6 C21 7 6 C21 C22 C2n 76 0 7 6 7 6 76 7 6 7 6 76 7 .. 76 .. 7 .. .. 6 .. 7 ¼ 6 .. 4 . 5 4 . . 54 . 5 . . Cn1. Cn1 Cn2 Cnn 0 302 A11 A12 A1n B11 6 A21 A22 A2n 7B6 B21 6 7B6 7B6 ¼6 .. 7B6 .. .. .. 6 .. 4 . . 5@4 . . . 2. Bn1 Bn2 Ann 32 3 B11 A1n 6 A21 A22 A2n 76 B21 7 6 76 7 76 7 ¼6 .. 76 .. 7 .. .. 6 .. 4 . 5 4 . . . . 5 An1 An2 Ann Bn1 2 3 A11 B11 þ A12 B21 þ A1n Bn1 6 7 ¼ 4 A21 B11 þ A22 B21 þ A2n Bn1 5: 2. An1 A11. B12 B22 .. .. An2 A12. 32 31 1 B1n 6 0 7C B2n 7 76 7C 76 7C .. 76 .. 7C .. . 54 . 5A . Bnn. 0. An1 B11 þ An2 B21 þ Ann Bn1 Hence the first column of C is equal to Ab1 . Similarly, we can show that its ith column is equal to Abi . Exercise 2.13 The adjacency matrix A is.

(31) Walks: A Beginner’s Guide to Graphs and Matrices. 31. 2. 0 1. 6 41 0 1 1 Therefore. 2. 2. 6 A2 ¼ 4 1 1. 1 1. 3. 7 2 1 5; 1 2. 2. 2 3. 6 A3 ¼ 4 3 2 3 3. 3. 1. 3. 7 1 5: 0. 3. 2. 7 3 5; 2. 3. 6. 5. 5. 6 A4 ¼ 4 5 5. 6. 7 5 5;. 5. 6. 2. 3. 10. 11. 11. 6 A5 ¼ 4 11 11. 10. 7 11 5:. 11. 10. l. From this, we see that the ð1; 1Þ entry of A is equal to the number of walks from 1 to 1 of length l for l 2 f1; 2; 3; 4; 5g. Exercise 2.15 Note that the ði; jÞ entry of Al is n X n X k1 ¼1 k2 ¼1. . n X. Aik1 Ak1 k2 Akl2 kl1 Akl1 j :. kl ¼1. We see that Aik1 Ak1 k2 Akl2 kl1 Akl1 j ¼ 1 () Aik1 ¼ Ak1 k2 ¼ Akl2 kl1 ¼ Akl1 j ¼ 1 () ði; k1 Þ; ðk1 ; k2 Þ; . . . ; ðkl2 ; kl1 Þ; and ðkl1 ; jÞ are edges () ði; k1 ; k2 ; . . . ; kl1 ; jÞ is a walk: Therefore the ði; jÞ entry of Al is equal to the number of walks from i to j of length l. Exercise 2.22 Let u be an eigenvector of A with eigenvalue 11. Then 2 6 u1 2u1 þ 6u2 11u1 Au ¼ ¼ ¼ : 9 5 u2 9u1 þ 5u2 11u2 Therefore u1 and u2 satisfy the following system of linear equations: 9u1 þ 6u2 ¼ 0 99u1 6u2 ¼ 0: By solving this, we see that . 2c 3c. . is an eigenvector of A with eigenvalue 11 for c 6¼ 0. Indeed, 2 6 2 22 ¼ : 9 5 3 33 Exercise 2.25 Let A be the adjacency matrix of . Then A¼. 1. 1. 1. 0. :. We first calculate the eigenvalues of A. Since detðA xIÞ ¼ ð1 xÞx 1 ¼ x2 x 1; pffiffiffi it follows that the eigenvalues of A are ð1 5Þ=2. Let pffiffiffi pffiffiffi 1þ 5 1 5 and ¼ : ¼ 2 2 Note that 2 ¼ þ 1 and 2 ¼ þ 1 since and are solutions of x2 x 1 ¼ 0. Next, we calculate eigenvectors. Let u be an eigenvector of A with eigenvalue . Then u1 1 1 u1 ¼ : u2 1 0 u2.

(32) 32. IRIE. This implies that . ð1 Þu1 þ u2 ¼ 0 u1 u2 ¼ 0:. From this, let u1 ¼. : 1. Then u1 is an eigenvector of A with eigenvalue . Indeed, since 2 ¼ þ 1, we see that 1 1 þ1 ¼ ¼ : 1 0 1 1 Similarly, let u2 ¼. : 1. Then u2 is an eigenvector of A with eigenvalue . Let U ¼ u1 u2 ¼ 1 1. and. ¼. . 0. 0. . :. Then U and. 1. AU ¼ Au1. Hence l. l. A ¼ U U. 1. 1 1 ¼ 1 Au2 ¼ u1. . . u2 ¼ U:. # " l 0 1 1 ¼ 1 1 1 0 l " # l1 l 1 ¼ 1 1 l l1 " # l l lþ1 lþ1 1 ¼ : l l l1 l1. Therefore the number of walks from 1 to 1 of length l is equal to 1 ðlþ1 lþ1 Þ: For example, . l¼0: . l¼1: . l¼2: . l¼3: . l¼4: . l¼5:. 1 ð Þ ¼ 1. 1 1 ð2 2 Þ ¼ ð þ 1 1Þ ¼ 1. 1 1 1 ð3 3 Þ ¼ ð 2 þ 2 Þ ¼ ð2 þ 1 2 1Þ ¼ 2. 1 1 1 ð4 4 Þ ¼ ð2 2 þ 22 Þ ¼ ð3 þ 2 3 2Þ ¼ 3. 1 1 1 ð5 5 Þ ¼ ð3 2 þ 2 32 2Þ ¼ ð5 þ 3 5 3Þ ¼ 5. 1 1 1 ð6 6 Þ ¼ ð5 2 þ 3 52 3Þ ¼ ð8 þ 5 8 5Þ ¼ 8. . We see that the number of walks from 1 to 1 of length l is equal to the lth Fibonacci number. Exercise 2.26 Let be the digraph with vertex set f1; 2; 3; 4g and edge set.

(33) Walks: A Beginner’s Guide to Graphs and Matrices. 33. fð1; 2Þ; ð1; 3Þ; ð1; 4Þ; ð2; 1Þ; ð2; 3Þ; ð2; 4Þ; ð3; 1Þ; ð3; 2Þ; ð3; 4Þ; ð4; 1Þ; ð4; 2Þ; ð4; 3Þg: It suffices to count the number of walks from 1 to 1 of length l in .. Fig. A18. A digraph with four vertices and twelve edges.. Let A be the adjacency matrix of . Then 2. 3. 0 1. 1. 1. 61 0 6 A¼6 41 1. 1 0. 17 7 7: 15. 1 1. 1. 0. We first calculate the eigenvalues of A. Since detðA xIÞ ¼ ðx þ 1Þ3 ðx 3Þ; it follows that 1 and 3 are the eigenvalues of A. eigenvalue 1. Then 2 0 1 61 0 6 6 41 1 1 1. Next, we calculate eigenvectors. Let u be an eigenvector of A with. 0. 32 3 2 3 u1 u1 1 6u 7 6u 7 17 76 2 7 6 27 76 7 ¼ 6 7: 4 u3 5 1 5 4 u3 5. 1. 0. 1 1. u4. u4. Hence u1 þ u2 þ u3 þ u4 ¼ 0: From this, let 2. 1. 3. 6 1 7 6 7 u1 ¼ 6 7; 4 0 5 0. 2. 0. 3. 6 1 7 6 7 u2 ¼ 6 7; 4 1 5. 2 and. 0. 3. 6 0 7 6 7 u3 ¼ 6 7: 4 1 5. 0. 1. Then u1 , u2 , and u3 are eigenvectors of A with eigenvalue 1. Let 2 3 1 617 6 7 u4 ¼ 6 7: 415 1 It is easy to see that u4 is an eigenvector of A with eigenvalue 3. Let U ¼ ½u1 u2 u3 u4 . Then detðUÞ 6¼ 0, so U is invertible. Since ðAl Þ11 ¼ ðAl Þ22 ¼ ðAl Þ33 ¼ ðAl Þ44 , it follows from Remark 2.24 that the number of walks from 1 to 1 of length l in is equal to 3l þ 3 ð1Þl : 4 For example, 30 þ 3 ð1Þ0 ¼ 1. 4 33

(34) l¼1: ¼ 0. 4 32 þ 3 ¼ 3.

(35) l¼2: 4.

(36) l¼0:. 33 3 ¼ 6. 4 34 þ 3

(37) l¼4: ¼ 21. 4 35 3

(38) l¼5: ¼ 60. 4.

(39) l¼3:.

(40) 34. IRIE. Remark A.2. A square matrix B is said to be symmetric if B> ¼ B. Although we have checked that U is invertible in the above, we do not have to check since it is known that a symmetric matrix is always diagonalizable. For your information, while a square matrix may not be diagonalizable, it is always triangularizable. From this, we can show that trðAl Þ ¼ 1l þ þ nl even when A is not diagonalizable, where f1 ; . . . ; n g is the multiset of eigenvalues of A. See, for example, [26] for details. A.3. Section 3. Exercise 3.4 The transposed adjacency matrix of is 2. 3. 0. 1 1. 1. 60 6 6 40. 0 1 0 0. 07 7 7: 15. 1. 0 1. 0. Exercise 3.6 Table A·2 shows ra ðiÞ for i 2 f1; 2; 3; 4g. From this, we estimate the importance of the four pages as follows: page 1 is the most important, page 4 is the second, and pages 2 and 3 are the third. Table A2. In-degrees. i. 1. 2. 3. 4. ra ðiÞ. 3. 1. 1. 2. Exercise 3.9 Figure A·19 shows the weights and the hyperlink matrix of .. Fig. A19. Weighs and hyperlink matrix.. It follows that 1 1 11 þ ¼ ; 3 2 6 1 1 rb ð2Þ ¼ 0 þ 0 þ þ 0 ¼ ; 3 3 1 1 rb ð3Þ ¼ 0 þ 0 þ 0 þ ¼ ; 2 2 1 4 rb ð4Þ ¼ 1 þ 0 þ þ 0 ¼ : 3 3 rb ð1Þ ¼ 0 þ 1 þ. Therefore we estimate the importance of the four pages as follows: page 1 is the most important, page 4 is the second, page 3 is the third, and page 2 is the fourth. Exercise 3.11 Let H be the hyperlink matrix of and let u be an eigenvector of H with eigenvalue 1. Then u1 ¼ 0 u1 þ 1 u2 þ. 1 1 1 1 u3 þ u4 ¼ u2 þ u3 þ u4 ; 3 2 3 2. ðA:1Þ.

(41) Walks: A Beginner’s Guide to Graphs and Matrices. 35. 1 1 u3 þ 0 u4 ¼ u3 ; 3 3 1 1 u3 ¼ 0 u1 þ 0 u2 þ 0 u3 þ u4 ¼ u4 ; 2 2 1 1 u4 ¼ 1 u1 þ 0 u2 þ u3 þ 0 u4 ¼ u1 þ u 3 : 3 3. u2 ¼ 0 u1 þ 0 u2 þ. ðA:2Þ ðA:3Þ ðA:4Þ. By (A·4) and (A·3), u4 ¼ u1 þ. 1 1 u3 ¼ u1 þ u4 : 3 6. Hence u4 ¼. 6 u1 5. and. u3 ¼. 3 u1 : 5. From (A·2), u2 ¼. 1 1 u3 ¼ u1 : 3 5. This implies that 2 3 5 6 1 617 7 rc ¼ 6 7: 15 4 3 5 6 Therefore we estimate the importance of the four pages as follows: page 4 is the most important, page 1 is the second, page 3 is the third, and page 2 is the fourth. Exercise 3.12 Let H be the hyperlink matrix of and let u be an eigenvector of H with eigenvalue 1. Then 2 32 3 2 3 0 0 12 u1 u1 6 76 7 6 7 1 ¼ u 4 0 0 2 54 2 5 4 u2 5: u3 u3 1 0 0 Hence u3 ¼ u1 ¼ u2 and u1 ¼ u3 ; 2 so u3 ¼ u3 =2. This implies that u3 ¼ 0 and u1 ¼ u2 ¼ 0. Therefore H has no eigenvectors with eigenvalue 1. In other words, we cannot define rc . Exercise 3.16 The hyperlink matrix of is 2. 1 2 1 2. 0 0. 6 40 0 1 0. 3 7 5:. 0. Hence 2. 0. 6 S ¼ 40 1. 1 3 1 3 1 3. 1 2 1 2. 3 7 5:. 0. We now calculate rd . Since rd is an eigenvector of S with eigenvalue 1, it follows that 2 3 2 3 32 0 13 12 rd ð1Þ rd ð1Þ 6 7 6 7 76 4 rd ð2Þ 5 ¼ 4 0 13 12 54 rd ð2Þ 5: rd ð3Þ rd ð3Þ 1 13 0 We see that rd ð1Þ ¼ rd ð2Þ since.