An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: The Google PageRank Algorithm

The World Wide Web is a vast collection of information, searchable via search engines. A search engine looks for pages that are of interest to the user. In order to be effective, a search engine needs to be able to identify those pages that are relevant to the search criteria provided by the user. This involves determining the relative importance of different web pages by ranking the results of thousands or millions of pages fitting the search criteria. For Google, the PageRank algorithm is their method and is “the heart of our software” as they say. It is this PageRank algorithm that we will learn about later in this section. Eigenvalues and eigenvectors play an important role in this algorithm.

Subsection Introduction

Given a matrix \(A\text{,}\) for some special non-zero vectors \(\vv\) the action of \(A\) on \(\vv\) will be same as scalar multiplication, i.e., \(A\vv=\lambda \vv\) for some scalar \(\lambda\text{.}\) Geometrically, this means that the transformation \(T\) defined by \(T(\vx) = A\vx\) simply stretches or contracts the vector \(\vv\) but does not change its direction. Such a nonzero vector is called an eigenvector of \(A\text{,}\) while the scalar \(\lambda\) is called the corresponding eigenvalue of \(A\text{.}\) The eigenvectors of a matrix tell us quite a bit about the transformation the matrix defines.

Eigenvalues and eigenvectors are used in many applications. Social media like Facebook and Google use eigenvalues to determine the influence of individual members on the network (which can affect advertising) or to rank the importance of web pages. Eigenvalues and eigenvectors appear in quantum physics, where atomic and molecular orbitals can be defined by the eigenvectors of a certain operator. They appear in principal component analysis, used to study large data sets, to diagonalize certain matrices and determine the long term behavior of systems as a result, and in the important singular value decomposition of a matrix. Matrices with real entries can have real or complex eigenvalues, and complex eigenvalues reveal a rotation that is encoded in every real matrix with complex eigenvalues which allows us to better understand certain matrix transformations.

For example, \(\vv= \left[ \begin{array}{c} 1\\1 \end{array} \right]\) is an eigenvector of \(A=\left[ \begin{array}{cc} 2 \amp 1 \\ 3 \amp 0 \end{array} \right]\) corresponding to the eigenvalue \(\lambda=3\) because \(A\vv = \left[ \begin{array}{c} 3\\3 \end{array} \right]\text{,}\) which is equal to \(3\vv\text{.}\) On the other hand, \(\vw= \left[ \begin{array}{c} 1\\2 \end{array} \right]\) is not an eigenvector of \(A=\left[ \begin{array}{cc} 2 \amp 1 \\ 3 \amp 0 \end{array} \right]\) because \(A\vw = \left[ \begin{array}{c} 4\\3 \end{array} \right]\text{,}\) which is not a multiple of \(\vw\text{.}\)

Subsection Eigenvalues and Eigenvectors

Eigenvectors are especially useful in understanding the long-term behavior of dynamical systems, an example of which we will see shortly. The long-term behavior of a dynamical system is quite simple when the initial state vector is an eigenvector and this fact helps us analyze the system in general.

To find eigenvectors, we are interested in determining the vectors \(\vx\) for which \(A\vx\) has the same direction as \(\vx\text{.}\) This will happen when

for some scalar \(\lambda\text{.}\) Of course, \(A\vx = \lambda \vx\) when \(\vx = \vzero\) for every \(A\) and every \(\lambda\text{,}\) but that is uninteresting. So we really want to consider when there is a non-zero vector \(\vx\) so that \(A\vx = \lambda \vx\text{.}\) This prompts the definition of eigenvectors and eigenvalues as in Definition 9.1

In order for a matrix \(A\) to have an eigenvector, one condition \(A\) must satisfy is that \(A\) has to be a square matrix, i.e. an \(n \times n\) matrix. We will find that each \(n\times n\) matrix has only finitely many eigenvalues.

The terms eigenvalue and eigenvector seem to come from Hilbert, using the German “eigen” (roughly translated as “own”, “proper”, or “characteristic”) to emphasize how eigenvectors and eigenvalues are connected to their matrices. To find the eigenvalues and eigenvectors of an \(n \times n\) matrix \(A\text{,}\) we need to find the solutions to the equation

In Preview Activity 9.1, we considered this equation for \(A=\left[ \begin{array}{cr} 6\amp -2 \\ 2\amp 1 \end{array} \right]\) and \(\lambda=5\text{.}\) The homogeneous matrix equation we came up with was

To see the relationship between this homogeneous matrix equation and the eigenvalue-eigenvector equation better, let us consider the eigenvector equation using matrix algebra:

where \(I_n\) is the \(n \times n\) identity matrix. Notice that this description matches the homogenous equation matrix example above since we simply subtracted 5 from the diagonal terms of the matrix \(A\text{.}\) Hence, to find eigenvalues, we need to find the values of \(\lambda\) so that the homogeneous equation \((A - \lambda I_n)\vx=\vzero\) has non-trivial solutions.

Since an eigenvector of \(A\) corresponding to eigenvalue \(\lambda\) is a non-trivial solution to the homogeneous equation \((A - \lambda I_n)\vx = \vzero\text{,}\) the eigenvalues \(\lambda\) which work are those for which the matrix \(A-\lambda I_n\) has linearly dependent columns, or for which the row echelon form of the matrix \(A-\lambda I_n\) does not have a pivot in every column. When we need to test if a specific \(\lambda\) is an eigenvalue, this method works fine. However, finding which \(\lambda\)'s will work in general involves row reducing a matrix with \(\lambda\)'s subtracted on the diagonal algebraically. For certain types of matrices, this method still provides us the eigenvalues quickly. For general matrices though, row reducing algebraically is not efficient. We will later see an algebraic method which uses the determinants to find the eigenvalues.

Subsection Dynamical Systems

One real-life application of eigenvalues and eigenvectors is in analyzing the long-term behavior of discrete dynamical systems. A dynamical system is a system of variables whose values change with time. In discrete systems, the change is described by defining the values of the variables at time \(t+1\) in terms of the values at time \(t\text{.}\) For example, the discrete dynamical system

relates the value of \(y\) at time \(t+1\) to the value of \(y\) at time \(t\text{.}\) This is in contrast with a differential equation¹⁶ such as

which describes the instantaneous rate of change of \(y(t)\) in terms of \(y\) and \(t\text{.}\)

Discrete dynamical systems can be used in population modeling to provide a simplified model of predator-prey interactions in biology (see Activity 9.4). Other applications include Markov chains (see Exercise 5), age structured population growth models, distillation of a binary ideal mixture of two liquids, cobweb model in economics concerning the interaction of supply and demand for a single good, queuing theory and traffic flow.

Eigenvectors can be used to analyze the long-term behavior of dynamical systems.

A dynamical system is a system of variables whose values change with time. In Activity 9.4, we considered the discrete dynamical system modeling the rabbit and fox population in an area, which is an example of a predator-prey system. The system was given by the equations from (9.1), where \(r_i\) represented the number of rabbits in the area \(i\) years after a starting time value, and \(f_i\) represented the number of foxes in year \(i\text{.}\) In this notation, \(r_0, f_0\) corresponded to the initial population values.

As we saw in Activity 9.4, if we define the state vector as \(\vx_k=\begin{bmatrix}r_k \\ f_k \end{bmatrix}\text{,}\) the system of equations representing the dynamical system can be expressed as

where \(A=\left[ \begin{array}{cr} 1.14 \amp -0.12 \\ 0.08 \amp 0.86 \end{array} \right]\) represents the transition matrix. Note that equation (9.3) encodes infinitely many equations including \(\vx_1 = A\vx_0\text{,}\) \(\vx_2=A\vx_1\text{,}\) \(\vx_3=A\vx_2\text{,}\) and so on. This is a recursive formula for the population values as each year's population values are expressed in terms of the previous year's population values. If we want to calculate \(\vx_{10}\text{,}\) this formula requires first finding the population values for years 1-9. However, we can obtain a non-recursive formula using matrix algebra. If we substitute \(\vx_1 = A\vx_0\) into \(\vx_2=A\vx_1\) and simplify, we find that

Similarly, substituting \(\vx_2=A^2\vx_1\) into the formula for \(\vx_3\) gives

This process can be continued inductively to show that

for every \(k\) value. So to find the population values at any year \(k\text{,}\) we only need to know the initial state vector \(\vx_0\text{.}\)

As you discovered in Activity 9.5, we can use linearly independent eigenvectors of the transition matrix to find a closed formula for the state vector of a dynamical system, as long as the initial state vector can be expressed as a linear combination of the eigenvectors.

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

We learned about eigenvalues and eigenvectors of a matrix in this section.

• A scalar \(\lambda\) is an eigenvalue (or characteristic value) of a square matrix \(A\) if there is a non-zero vector \(\vx\) so that \(A\vx = \lambda \vx\text{.}\)

• A non-zero vector \(\vx\) is an eigenvector (or characteristic vector) of a square matrix \(A\) if there is a scalar \(\lambda\) so that \(A\vx = \lambda \vx\text{.}\)

• To find the eigenvectors of an \(n \times n\) matrix \(A\) corresponding to an eigenvalue \(\lambda\text{,}\) we determine the non-trivial solutions to \((A - \lambda I_n)\vx=\vzero\) where \(I_n\) is the \(n\times n\) identity matrix.

• We study eigenvectors and eigenvalues because the eigenvectors tell us quite a bit about the transformation corresponding to the matrix. These eigenvectors arise in many applications in physics, chemistry, statistics, economics, biology, sociology and other areas, and help understand the long-term behavior of dynamical systems.

• A dynamical system is a system of variables whose values change with time. In linear dynamical systems, the change in the state vector from one time period to the next is expressed by matrix multiplication by the transition matrix \(A\text{.}\) The eigenvectors of \(A\) provide us a simple method to express the state vector at any given time period in terms of the initial state vector. Specifically, if the initial state vector is \(\vx_0=a\vv_0+b\vw_0\) where \(\vv_0, \vw_0\) are eigenvectors corresponding to eigenvalues \(\lambda_1, \lambda_2\text{,}\) we have

  \begin{equation*} \vx_k = A^k \vx_0 = \lambda_1^k a \vv_0 + \lambda_2^k b \vw_0\,\text{.} \end{equation*}

Subsection Project: Understanding the PageRank Algorithm

Sergey Brin and Lawrence Page, the founders of Google, decided that the importance of a web page can be judged by the number of links to it as well as the importance of those pages. It is this idea that leads to the PageRank algorithm.¹⁷ Google uses this algorithm (and others) to order search engine results. According to Google:¹⁸

PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.

To rank how “important” a website is, we need to make some assumptions. We assume that a person visits a page and then surfs the web by selecting a link from that page — all links on a given page are assigned the same probability of being chosen. As an example, assume a small set of seven pages 1, 2, 3, 4, 5, 6, and 7 with links between the pages given by the arrows as shown in Figure 9.5.¹⁹ So, for example, there is a hyperlink from page 4 to page 3, but no hyperlink in the opposite direction. If a web surfer starts on page 5, then there is probability of \(\frac{1}{2}\) that this person will surf to page 6 and a probability of \(\frac{1}{2}\) that the surfer will move to page 4. If there is no link leaving a page, as in the case of page 3, then the probability of remaining there is 1.

To rank pages, we need to know how likely it is that a surfer will land on a given page. In our seven page example, a person can land on page 3 from page 4 with a probability of \(\frac{1}{2}\) or from page 6 with a probability of \(\frac{1}{3}\text{.}\) If there is a link from a page we assume that the surfer leaves the page, and if there are no links from a page then the surfer stays on that page. We also assume that the surfer does not use the “Back” key. This information for our seven page internet example can be summarized in a transition matrix \(T\) whose \(i,j\)th entry is the probability that a surfer lands on page \(i\) from page \(j\text{.}\)

Let us assume in our seven page internet that a user starts on page 6. That is, the probability that the user is initially on page 6 is 1, and so the probability that the user is on some other page is 0. This information can be encapsulated in a state vector

Since there are links from page 6 to pages 3, 5, and 7, there is a \(\frac{1}{3}\) probability that the surfer will next move to one of these pages. That means that at the next step, the state vector \(\vx_1\) for this user will be

Note that

As the user continues to surf the internet, the probabilities that the surfer is on a given page after the second, third, and fourth steps are given in the state vectors

In general, the probabilities that the surfer is on a given page after the \(n\)th step is given by the state vector

This example illustrates the general nature of what is called a Markov process (see Definition 9.4). The two properties of the transition matrix \(T\) make \(T\) a special kind of matrix.

In a Markov process, each generation depends only on the preceding generation and there may be a limiting value as we let the process continue indefinitely. We can test to see if that happens for this Markov process defined by \(T\) by doing some experimentation.

If there is a limit of the sequence \(\{T^n\vx_0\}\) (in other words, if there is a vector \(\vv\) such that \(\vv = \ds \lim_{n \to \infty} T^n \vx_0\)), we call this limit a steady-state or equilibrium vector. Such a steady-state vector has another important property. Since \(T\) is independent of \(n\) we have

Equation (9.8) shows that a steady state vector \(\vv\) is an eigenvector for \(T\) with eigenvalue 1. We can interpret the steady-state vector for \(T\) in an important way. Let \(t_j\) be the fraction of time we spend on page \(j\) and let \(l_j\) be the number of links on page \(j\text{.}\) Then the fraction of the time that we end up on page \(i\) coming from page \(j\) is \(\frac{t_j}{l_j}\text{.}\) If we sum over all the pages linked to page \(i\) we have that

Notice that this is essentially the same process we used to obtain \(\vx_n\) from \(\vx_{n-1}\text{,}\) and so we can interpret the steady-state vector \(\vv\) as telling us what fraction of a random web surfer's time was spent at each web page. If we assume that the time spent at a web page is a measure of its importance, then the steady-state vector tells us the relative importance of each web page. So this steady-state vector provides the page rankings for us. In other words,

The importance of a webpage may be measured by the relative size of the corresponding entry in the steady-state vector for an appropriately chosen Markov chain.

Project Activity 9.6 illustrates one problem with our seven page internet. The steady-state vector shows that page 3 is the only important page, but that hardly seems reasonable in the example since there are other pages that must have some importance. The problem is that page 3 is a “dangling” page and does not lead anywhere. Once a surfer reaches that page, they are stuck there, overemphasizing its importance. So this dangling page acts like a sink, ultimately drawing all surfers to it. To adjust for dangling pages, we make the assumption that if a surfer reaches a dangling page (one with no links emanating from it), the surfer will jump to any page on the web with equal probability. So in our seven page example, once a surfer reaches page 3 the surfer will jump to any page on the web with probability \(\frac{1}{7}\text{.}\)

There is one more issue to address before we can consider ourselves ready to rank web pages. Consider the example of the five page internet shown in Figure 9.7.

Project Activity 9.9 shows that it is possible to construct an internet so that the corresponding Markov chain does not have a limit, even after adjusting for dangling pages. This is a significant problem if we want to provide a relative ranking of all web pages regardless of where a surfer starts. To fix this problem we need to make one final adjustment to arrive at a type of transition matrix that always provides a limit for our Markov chain.

Note that the transition matrix from Project Activity 9.9 is not regular. Regular matrices have some especially nice properties, as the following theorem describes. We will not prove this theorem, but use it in the remainder of this project. The theorem shows that if we have a regular transition matrix, then there will a limit of the state vectors \(\vx_n\text{,}\) and that this limit has a very interesting property.

Having a regular transition matrix \(T\) ensures that there is always the same limit \(\vv\) to the sequence \(T^k \vx_0\) for any starting vector \(\vx_0\text{.}\) As mentioned before, the entries in \(\vv = \ds \lim_{n \to \infty} T^n \vx_0\) can be interpreted as telling us what fraction of the random surfer's time was spent at each webpage. If we interpret the amount of time a surfer spends at a page as a measure of the page's importance, then this steady-state vector \(\vv\) provides a ranking of the relative importance of each page in the web. This is the essence of Google's PageRank.

To make our final adjustment in the transition matrix to be sure that we obtain a regular matrix, we need to deal with the problems of “loops” in our internet. Loops, as illustrated in Project Activity 9.9, can act as sinks just like the dangling pages we saw earlier and condemn a user that enters such a loop to spend his/her time only on those pages in the loop. Quite boring! To account for this problem, we make a second adjustment.

Let \(p\) be a number between 0 and 1 (Google supposedly uses \(p=0.85\)). Suppose a surfer is on page \(i\text{.}\) We assume with probability \(p\) that the surfer will chose any link on page \(i\) with equal probability. We make the additional assumption with probability \(1-p\) that the surfer will select with equal probability any page on the web.

If \(T\) is a transition matrix, incorporating the method we used to deal with dangling pages, then the adjusted transition matrix \(G\) (the Google matrix) is

where \(Q\) is the matrix all of whose entries are \(\frac{1}{n}\text{,}\) where \(n\) is the number of pages in the internet (\(n=7\) in our seven page example). Since all of the entries of \(G\) are positive, \(G\) is a regular stochastic matrix.

We conclude with two observations. Consider the role of the parameter \(p\) in our final adjustment. Notice that if \(p=1\text{,}\) then \(G = T\) and we have the original hyperlink structure of the web. However, if \(p=0\text{,}\) then \(G = \frac{1}{n} I_n\text{,}\) where \(I_n\) is the \(n \times n\) identity matrix with \(n\) as the number of pages in the web. In this case, every page is linked to every other page and a random surfer spends equal time on any page. Here we have lost all of the character of the linked structure of the web. Choosing \(p\) close to 1 retains much of the original hyperlink structure of the web.

Finally, the matrices that model the web are HUGE, and so the methods we used in this project to approximate the steady-state vectors are not practical. There are many methods for approximating eigenvectors that are often used in these situations, some of which we discuss in a later section.