1Math 1b Practical — February 22, 2011Digraphs, nonnegative matrices, Google page ranking— Nonnegative matrices —Theorem 1. Let A b e a s quar e matrix of nonnegative real numbers. Then A has aneigenvector e all of whose entries are nonnegative.Proof: Omitted.  There may be several linearly independent nonnegative eigenvectors. For example, theidentity matrix I has many nonnegative eigenvectors (all corresponding to eigenvalue 1).A nonnegative diagonal matrix with distinct diagonal entries has nonnegative eigenvectorscorresponding to different eigenvalues.Here is a stronger version of Theorem 1, and also a strengthening when the nonnegativematrix is irreducible in a sense to be defined later.Theorem 2. Let A be a square matrix of nonnegative real numbers. Let λ be the max-imum of the absolute values |μ| of the eigenvalues μ of A.Thenλ is an eigenvalue of Aand there are nonnegative eigenvectors coresponding to λ.Proof: Also omitted.  Theorem 3 (Perron-Frobenius). Let A be an irreducible square nonnegative matrix.Then A has a unique nonnegative eigenvector e, up to scalar multiples. This eigenvectore has all p ositive entries and the corresp onding eigenvalue λ has algebraic multiplicity 1and the prop er ty that λ ≥|μ| for every eigenvalue μ of A.Proof: Omitted yet again, though we will prove it for probability matrices (to be definedlater) below.The eigenvalue λ in Theorem 2 or 3 may be called the dominant eigenvalue of thematrix A. We remark that there may be real or complex eigenvalues μ = λ but so that|μ| = λ. Such eigenvalues, of course, do not correspond to nonnegative eigenvectors,because μ would be negative or complex. For example,0110 has eigenvalues +1 and −1.(In general, the maximum of the absolute values of the eigenvalues of a matrix is calledthe spectral radius of the matrix.)2Example 1. The eigenvalues of⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0500000030000010001400400030141520035000202000300500000040100133000005210023154200002203020500040043⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠are11.268, 5.167, −3.556 ± 2.351i, 3.269, −2.178 ± 2.212i, 2.167 ± 1.734i, −0.570.For this matrix, there are three nonnegative eigenvalues, but only one nonnegative eigen-vector, up to scalar multiples, namely(0.148, 0.161, 0.343, 0.329, 0.310, 0.142, 0.328, 0.572, 0.286, 0.305).Theorem 4. An eigenvalue λ of a nonnegative matrix A =(aij) that corresponds to anonnegative eigenvector is at least the smallest r ow sum and at least the smallest columnsum of A, and is at most the largest row sum and at mos t the largest column sum of A.That is,mininj=1aij≤ λ ≤ maxinj=1aijandminjni=1aij≤ λ ≤ maxjni=1aij.Proof: We prove only the first of the four inequalities here, and only in the case that thereis a positive eigenvector x =(x1,...,xn)corresponding to λ.Thatx is an eigenvectormeansnj=1xjaij= λxifor each i.Choosei0so that xi0is the smallest of the numbers xi, and consider the instancei = i0of the above equation:λxi0=nj=1xjai0,j≥ xi0nj=1ai0,j.3Now divide by |xi0|, and we see that λ is at least the sum of the matrix entries in rowi0.  — Digraphs —A directed graph (or ‘digraph’) consists of a number of vertices (or ‘nodes’) and edges(or ‘arcs’), each of which joins one vertex to another in a particular direction. One mayimagine the edges as (generally one-way) streets joining various locations, or as cables con-necting electrical components or terminals. It is not too important, but to avoid confusion,we may insist that there is at most one edge directed from a vertex x toavertexy.Wedoallow an edge from x to x,andedgesfromx to y and, back, from y to x when x = y.Itispossible to give a more formal or precise definition of digraph, but we won’t do that here.We can describe small digraphs by diagrams where the vertices are represented bypoints in the plane and the edges by line segments or curves provided with arrows. Thefigure below shows such a diagram for a digraph with 6 vertices and 16 edges.Figure 1An example (actually, it changes over time) of a digraph with an immense number ofvertices and edges is the so-called “internet graph”. The vertices are all websites (URLs),and there is an edge joining website A to website B if and only if A includes a link to B.To each finite digraph we may associate a matrix A =(ai) whose entries are 0’s and1’s. (We speak of a (0, 1)-matrix.) Number the vertices from 1 to n.Letaij=1ifthereis an edge from i to j,andaij=0ifthereisnoedgefromi to j. This may be called theadjacency matrix of the digraph. The adjacency matrix of the digraph in Figure 1 isA =⎛⎜⎜⎜⎜⎜⎝010111100011000110001000110101000110⎞⎟⎟⎟⎟⎟⎠. (∗)An interpretation of powers of the adjacency matrix in terms of the digraph is givenby the theorem below. A (directed) walk of length m in a digraph, from a vertex i to avertex j, is a sequencei = k0,k1,k2,...,km−1,km= j4of m + 1 vertices so that there is an edge directed from kα−1to kαfor α =1, 2,...,m.Theorem 5. Let A be the adjacency matrix of a finite digraph. Then the number ofwalks of length m from a vertex i toavertexj is equal the the (i, j)-entry of Am.Proof: (Note that the theorem is obvious for m = 1, where the numbers are 0 or 1.)First, we must understand the interpretation of the (i, j)-entry of Amfor any matrixm. This is not hard, but the notation may seem messy. The (i, j)-entry of A2isnk=1aikakj;the (i, j)-entry of A3isns,t=1aisastatj;the (i, j)-entry of A4isnp,q,r=1aipapqaqrarj;and so forth. In general, the (i, j)-entry of Amisnk1,k2,...,km−1=1ai,k1ak1,k2···akm−1,m−2akm−1,j.In case that A is the adjacency matrix of a digraph, the aij’s are 0’s and 1’s, and theterms in the summation above are also 0 or 1; in fact,ai,k1ak1,k2···akm−1,m−2akm−1,j=1wheni, k1,...,km−1,j is a walk,0otherwise.thus the summation counts the number of times that i, k1,...,km−1,j is a walk in thedigraph.  For example, if A is as in (∗), the (1, 5)-entry of A2is 1 because there is exactly onewalk 1, 5, 2 in the digraph in Figure 1 from vertex 1 to vertex 2.— The Google page ranking algorithm —The following material has been adapted from a short article by Herb Wilf athttp://www.math.utsc.utoronto.ca/b24/KendallWei.pdf .It contains basic ideas that are used in some way, I undertand, by Google when it presentsus with an ordered list of sites matching our