7.9: Linear Dynamical Systems

We began Section 3.3 with an example from ecology which models the evolution of the population of a species of birds as time goes on. As promised, we now complete the example—Example 3.5.1 below.

The bird population was described by computing the female population profile \(\mathbf{v}_k = \left[ \begin{array}{r} a_k \\ j_k \end{array}\right]\) of the species, where \(a_{k}\) and \(j_{k}\) represent the number of adult and juvenile females present \(k\) years after the initial values \(a_{0}\) and \(j_{0}\) were observed. The model assumes that these numbers are related by the following equations:

\[\begin{aligned} a_{k+1} &= \frac{1}{2} a_k + \frac{1}{4}j_k \\ j_{k+1} &= 2a_k\end{aligned} \nonumber \]

If we write \(A = \left[ \begin{array}{rr} \frac{1}{2} & \frac{1}{4} \\ 2 & 0 \end{array}\right]\) the columns \(\mathbf{v}_{k}\) satisfy \(\mathbf{v}_{k+1} = A\mathbf{v}_{k}\) for each \(k = 0, 1, 2, \dots\).

Hence \(\mathbf{v}_{k} = A^{k}\mathbf{v}_{0}\) for each \(k = 1, 2, \dots\). We can now use our diagonalization techniques to determine the population profile \(\mathbf{v}_{k}\) for all values of \(k\) in terms of the initial values.

Example \(\PageIndex{1}\)

Assuming that the initial values were \(a_{0} = 100\) adult females and \(j_{0} = 40\) juvenile females, compute \(a_{k}\) and \(j_{k}\) for \(k = 1, 2, \dots\).

Solution

The characteristic polynomial of the matrix \(A = \left[ \begin{array}{rr} \frac{1}{2} & \frac{1}{4} \\ 2 & 0 \end{array}\right]\) is \(c_{A}(x) = x^{2} - \frac{1}{2}x - \frac{1}{2} = (x - 1)(x + \frac{1}{2})\), so the eigenvalues are \(\lambda_{1} = 1\) and \(\lambda_{2} = -\frac{1}{2}\) and gaussian elimination gives corresponding basic eigenvectors \(\left[ \begin{array}{r} \frac{1}{2} \\ 1 \end{array}\right]\) and \(\left[ \begin{array}{r} -\frac{1}{4} \\ 1 \end{array}\right]\). For convenience, we can use multiples \(\mathbf{x}_1 = \left[ \begin{array}{r} 1 \\ 2 \end{array}\right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{r} -1 \\ 4 \end{array}\right]\) respectively. Hence a diagonalizing matrix is \(P = \left[ \begin{array}{rr} 1 & -1 \\ 2 & 4 \end{array} \right]\) and we obtain

\[P^{-1}AP=D \mbox{ where } D = \left[ \begin{array}{rr} 1 & 0 \\ 0 & -\frac{1}{2} \end{array}\right] \nonumber \]

This gives \(A = PDP^{-1}\) so, for each \(k \geq 0\), we can compute \(A^{k}\) explicitly:

\[\begin{aligned} A^k = PD^kP^{-1} &= \left[ \begin{array}{rr} 1 & -1 \\ 2 & 4 \end{array}\right] \left[ \begin{array}{cc} 1 & 0 \\ 0 & (-\frac{1}{2})^k \end{array}\right] \frac{1}{6} \left[ \begin{array}{rr} 4 & 1 \\ -2 & 1 \end{array}\right] \\ &= \frac{1}{6} \left[ \def\arraystretch{1.25}\begin{array}{cc} 4+2(-\frac{1}{2})^k & 1-(-\frac{1}{2})^k \\ 8-8(-\frac{1}{2})^k & 2+4(-\frac{1}{2})^k \end{array}\right]\end{aligned} \nonumber \]

Hence we obtain

\[\begin{aligned} \left[ \begin{array}{r} a_k \\ j_k \end{array}\right] = \mathbf{v}_k = A^k \mathbf{v}_0 & = \frac{1}{6} \left[ \def\arraystretch{1.25} \begin{array}{cc} 4+2(-\frac{1}{2})^k & 1-(-\frac{1}{2})^k \\ 8-8(-\frac{1}{2})^k & 2+4(-\frac{1}{2})^k \end{array}\right] \left[ \begin{array}{r} 100 \\ 40 \end{array}\right] \\ &= \frac{1}{6} \left[ \def\arraystretch{1.25}\begin{array}{cc} 440 + 160 (-\frac{1}{2})^k \\ 880 - 640 (-\frac{1}{2})^k \end{array}\right]\end{aligned} \nonumber \]

Equating top and bottom entries, we obtain exact formulas for \(a_{k}\) and \(j_{k}\):

\[a_k = \frac{220}{3} + \frac{80}{3}\left(-\frac{1}{2}\right)^k \mbox{ and } j_k = \frac{440}{3} + \frac{320}{3}\left(-\frac{1}{2}\right)^k \mbox{ for } k = 1,2,\cdots \nonumber \]

In practice, the exact values of \(a_{k}\) and \(j_{k}\) are not usually required. What is needed is a measure of how these numbers behave for large values of \(k\). This is easy to obtain here. Since \((-\frac{1}{2})^{k}\) is nearly zero for large \(k\), we have the following approximate values

\[a_k \approx \frac{220}{3} \mbox{ and } j_k \approx \frac{440}{3} \mbox{ if } k \mbox{ is large} \nonumber \]

Hence, in the long term, the female population stabilizes with approximately twice as many juveniles as adults.

Definition: Linear Dynamical System

If \(A\) is an \(n \times n\) matrix, a sequence \(\mathbf{v}_{0}, \mathbf{v}_{1}, \mathbf{v}_{2}, \dots\) of columns in \(\mathbb{R}^n\) is called a linear dynamical system if \(\mathbf{v}_{0}\) is specified and \(\mathbf{v}_{1}, \mathbf{v}_{2}, \dots\) are given by the matrix recurrence \(\mathbf{v}_{k+1}= A\mathbf{v}_{k}\) for each \(k \geq 0\). We call \(A\) the migration matrix of the system.

We have \(\mathbf{v}_1 = A\mathbf{v}_0\), then \(\mathbf{v}_2 = A\mathbf{v}_1 = A^{2}\mathbf{v}_0\), and continuing we find

\[\label{eq:dynamicalsyst} \mathbf{v}_k = A^k \mathbf{v}_0 \mbox{ for each } k = 1, 2, \cdots \]

Hence the columns \(\mathbf{v}_{k}\) are determined by the powers \(A^{k}\) of the matrix \(A\) and, as we have seen, these powers can be efficiently computed if \(A\) is diagonalizable. In fact Equation \ref{eq:dynamicalsyst} can be used to give a nice “formula” for the columns \(\mathbf{v}_{k}\) in this case.

Assume that \(A\) is diagonalizable with eigenvalues \(\lambda_{1}, \lambda_{2}, \dots , \lambda_{n}\) and corresponding basic eigenvectors \(\mathbf{x}_{1}, \mathbf{x}_{2}, \dots , \mathbf{x}_{n}\). If \(P = \left[ \begin{array}{cccc} \mathbf{x}_{1} & \mathbf{x}_{2} & \dots & \mathbf{x}_{n} \end{array}\right]\) is a diagonalizing matrix with the \(\mathbf{x}_{i}\) as columns, then \(P\) is invertible and

\[P^{-1}AP=D = \text{diag}(\lambda_1, \lambda_2, \cdots, \lambda_n) \nonumber \]

by Theorem 3.4.1. Hence \(A = PDP^{-1}\) so Equation \ref{eq:dynamicalsyst} and Theorem 3.3.1 give

\[\mathbf{v}_k = A^k \mathbf{v}_0 = (PDP^{-1})^k \mathbf{v}_0 = (PD^kP^{-1}) \mathbf{v}_0 = PD^k (P^{-1}\mathbf{v}_0) \nonumber \]

for each \(k = 1, 2, \dots\). For convenience, we denote the column \(P^{-1}\mathbf{v}_{0}\) arising here as follows:

\[\mathbf{b} = P^{-1} \mathbf{v}_0 = \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right] \nonumber \]

Then matrix multiplication gives

\[\begin{aligned} \mathbf{v}_k & = PD^k (P^{-1} \mathbf{v}_0) \nonumber\\ & = \left[ \begin{array}{cccc} \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \end{array} \right] \left[ \begin{array}{cccc} \lambda_1^k & 0 & \cdots & 0 \\ 0 & \lambda_2^k & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n^k \end{array}\right] \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right] \nonumber\\ &= \left[ \begin{array}{cccc} \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \end{array} \right] \left[ \begin{array}{c} b_1 \lambda_1^k \\ b_2 \lambda_2^k \\ \vdots \\ b_3 \lambda_n^k \end{array} \right] \nonumber\\ &= b_1 \lambda_1^k \mathbf{x}_1 + b_2 \lambda_2^k \mathbf{x}_2 + \cdots + b_n \lambda_n^k \mathbf{x}_n \label{eq:vkformula}\end{aligned} \]

for each \(k \geq 0\). This is a useful exact formula for the columns \(\mathbf{v}_{k}\). Note that, in particular,

\[\mathbf{v}_{0} = b_{1}\mathbf{x}_{1} + b_{2}\mathbf{x}_{2} + \dots + b_{n}\mathbf{x}_{n} \nonumber \]

However, such an exact formula for \(\mathbf{v}_{k}\) is often not required in practice; all that is needed is to estimate \(\mathbf{v}_{k}\) for large values of \(k\) (as was done in Example 3.3.1). This can be easily done if \(A\) has a largest eigenvalue. An eigenvalue \(\lambda\) of a matrix \(A\) is called a dominant eigenvalue of \(A\) if it has multiplicity \(1\) and

\[| \lambda | > | \mu | \mbox{ for all eigenvalues } \mu \neq \lambda \nonumber \]

where \(|\lambda |\) denotes the absolute value of the number \(\lambda\). For example, \(\lambda_{1} = 1\) is dominant in Example 3.3.1.

Returning to the above discussion, suppose that \(A\) has a dominant eigenvalue. By choosing the order in which the columns \(\mathbf{x}_{i}\) are placed in \(P\), we may assume that \(\lambda_{1}\) is dominant among the eigenvalues \(\lambda_{1}, \lambda_{2}, \dots , \lambda_{n}\) of \(A\) (see the discussion following Example 3.4.1). Now recall the exact expression for \(\mathbf{v}_{k}\) in Equation \ref{eq:vkformula} above:

\[\mathbf{v}_k = b_1 \lambda_1^k \mathbf{x}_1 + b_2 \lambda_2^k \mathbf{x}_2 + \cdots + b_n \lambda_n^k \mathbf{x}_n \nonumber \]

Take \(\lambda_1^k\) out as a common factor in this equation to get

\[\mathbf{v}_k = \lambda_1^k \left[ b_1 \mathbf{x}_1 + b_2 \left( \frac{\lambda_2}{\lambda_1}\right)^k \mathbf{x}_2 + \cdots + b_n \left( \frac{\lambda_n}{\lambda_1}\right)^k \mathbf{x}_n \right] \nonumber \]

for each \(k \geq 0\). Since \(\lambda_{1}\) is dominant, we have \(|\lambda_{i}| < |\lambda_{1}|\) for each \(i \geq 2\), so each of the numbers \((\lambda_{i} /\lambda_{1})^{k}\) become small in absolute value as \(k\) increases. Hence \(\mathbf{v}_{k}\) is approximately equal to the first term \(\lambda_1^k b_1 \mathbf{x}_1\), and we write this as \(\mathbf{v}_k \approx \lambda_1^k b_1 \mathbf{x}_1\). These observations are summarized in the following theorem (together with the above exact formula for \(\mathbf{v}_{k}\)).

Theorem \(\PageIndex{1}\)

Consider the dynamical system \(\mathbf{v}_{0}, \mathbf{v}_{1}, \mathbf{v}_{2}, \dots\) with matrix recurrence

\[\mathbf{v}_{k+1} = A \mathbf{v}_k \mbox{ for } k \geq 0 \nonumber \]

where \(A\) and \(\mathbf{v}_{0}\) are given. Assume that \(A\) is a diagonalizable \(n \times n\) matrix with eigenvalues \(\lambda_{1}, \lambda_{2}, \dots , \lambda_{n}\) and corresponding basic eigenvectors \(\mathbf{x}_{1}, \mathbf{x}_{2}, \dots , \mathbf{x}_{n}\), and let \(P = \left[ \begin{array}{cccc} \mathbf{x}_{1} & \mathbf{x}_{2} & \dots & \mathbf{x}_{n} \end{array}\right]\) be the diagonalizing matrix. Then an exact formula for \(\mathbf{v}_{k}\) is

\[\mathbf{v}_k = b_1 \lambda_1^k \mathbf{x}_1 + b_2 \lambda_2^k \mathbf{x}_2 + \cdots + b_n \lambda_n^k \mathbf{x}_n \mbox{ for each } k \geq 0 \nonumber \]

where the coefficients \(b_{i}\) come from

\[\mathbf{b} = P^{-1} \mathbf{v}_0 = \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right] \nonumber \]

Moreover, if \(A\) has dominanteigenvalue \(\lambda_{1}\), then \(\mathbf{v}_{k}\) is approximated by

\[\mathbf{v}_k = b_1 \lambda_1^k \mathbf{x}_1 \mbox{ for sufficiently large } k. \nonumber \]

Example \(\PageIndex{2}\)

Returning to Example 3.3.1, we see that \(\lambda_{1} = 1\) is the dominant eigenvalue, with eigenvector \(\mathbf{x}_1 = \left[ \begin{array}{c} 1 \\ 2 \end{array} \right]\). Here \(P = \left[ \begin{array}{rr} 1 & -1 \\ 2 & 4 \end{array} \right]\) and \(\mathbf{v}_0 = \left[ \begin{array}{c} 100 \\ 40 \end{array} \right]\) so \(P^{-1} \mathbf{v}_0 = \frac{1}{3} \left[ \begin{array}{r} 220 \\ -80 \end{array}\right]\). Hence \(b_1 = \frac{220}{3}\) in the notation of Theorem 3.5.1, so

\[\left[ \begin{array}{c} a_k \\ j_k \end{array} \right] = \mathbf{v}_k \approx b_1\lambda_1^k \mathbf{x}_1 = \frac{220}{3} 1^k \left[ \begin{array}{r} 1 \\ 2 \end{array} \right] \nonumber \]

where \(k\) is large. Hence \(a_k \approx \frac{220}{3}\) and \(j_k \approx \frac{440}{3}\) as in Example 3.5.1.

This next example uses Theorem 3.5.1 to solve a “linear recurrence.” See also Section 3.4.

Example \(\PageIndex{3}\)

Suppose a sequence \(x_{0}, x_{1}, x_{2}, \dots\) is determined by insisting that

\[x_0 = 1, x_1 = -1, \mbox{ and } x_{k+2} = 2x_k - x_{k+1} \mbox{ for every } k\geq 0 \nonumber \]

Find a formula for \(x_{k}\) in terms of \(k\).

Solution

Using the linear recurrence \(x_{k+2} = 2x_{k} - x_{k+1}\) repeatedly gives

\[x_2 = 2 x_0 - x_1 = 3, \quad x_3 = 2x_1 - x_2 = -5, \quad x_4 = 11, \quad x_5 = -21, \dots \nonumber \]

so the \(x_{i}\) are determined but no pattern is apparent. The idea is to find \(\mathbf{v}_k = \left[ \begin{array}{c} x_k \\ x_{k+1} \end{array} \right]\) for each \(k\) instead, and then retrieve \(x_{k}\) as the top component of \(\mathbf{v}_{k}\). The reason this works is that the linear recurrence guarantees that these \(\mathbf{v}_{k}\) are a dynamical system:

\[\mathbf{v}_{k+1} = \left[ \begin{array}{c} x_{k+1} \\ x_{k+2} \end{array}\right] = \left[ \begin{array}{c} x_{k+1} \\ 2x_k - x_{k+1} \end{array} \right] = A \mathbf{v}_k \mbox{ where } A = \left[ \begin{array}{rr} 0 & 1 \\ 2 & -1 \end{array} \right] \nonumber \]

The eigenvalues of \(A\) are \(\lambda_{1} = -2\) and \(\lambda_{2} = 1\) with eigenvectors \(\mathbf{x}_1 = \left[ \begin{array}{r} 1 \\ -2 \end{array}\right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{r} 1 \\ 1 \end{array}\right]\), so the diagonalizing matrix is \(P = \left[ \begin{array}{rr} 1 & 1 \\ -2 & 1 \end{array} \right]\).

Moreover, \(\mathbf{b} = P_0^{-1} \mathbf{v}_0 = \frac{1}{3} \left[ \begin{array}{c} 2 \\ 1 \end{array}\right]\) so the exact formula for \(\mathbf{v}_{k}\) is

\[\left[ \begin{array}{c} x_k \\ x_{k+1} \end{array} \right] = \mathbf{v}_k = b_1 \lambda_1^k \mathbf{x}_1 + b_2 \lambda_2^k \mathbf{x}_2 = \frac{2}{3} (-2)^k \left[ \begin{array}{r} 1 \\ -2 \end{array} \right] + \frac{1}{3} 1^k \left[ \begin{array}{r} 1 \\ 1 \end{array}\right] \nonumber \]

Equating top entries gives the desired formula for \(x_{k}\):

\[x_k = \frac{1}{3} \left[ 2(-2)^k +1 \right] \mbox{ for all } k = 0, 1, 2, \dots \nonumber \]

The reader should check this for the first few values of \(k\).

Graphical Description of Dynamical Systems

If a dynamical system \(\mathbf{v}_{k+1} = A\mathbf{v}_{k}\) is given, the sequence \(\mathbf{v}_{0}, \mathbf{v}_{1}, \mathbf{v}_{2}, \dots\) is called the trajectory of the system starting at \(\mathbf{v}_{0}\). It is instructive to obtain a graphical plot of the system by writing \(\mathbf{v}_k = \left[ \begin{array}{c} x_k \\ y_k \end{array} \right]\) and plotting the successive values as points in the plane, identifying \(\mathbf{v}_{k}\) with the point \((x_{k}, y_{k})\) in the plane. We give several examples which illustrate properties of dynamical systems. For ease of calculation we assume that the matrix \(A\) is simple, usually diagonal.

Example \(\PageIndex{4}\)

Let \(A = \left[ \begin{array}{cc} \frac{1}{2} & 0 \\ 0 & \frac{1}{3} \end{array}\right]\) Then the eigenvalues are \(\frac{1}{2}\) and \(\frac{1}{3}\), with corresponding eigenvectors \(\mathbf{x}_1 = \left[ \begin{array}{r} 1\\ 0 \end{array} \right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{c} 0 \\ 1 \end{array}\right]\).

The exact formula is

\[\mathbf{v}_k = b_1 \left( \frac{1}{2}\right)^k \left[ \begin{array}{r} 1 \\ 0 \end{array}\right] + b_2 \left( \frac{1}{3} \right)^k \left[ \begin{array}{r} 0 \\ 1 \end{array} \right] \nonumber \]

for \(k = 0, 1, 2, \dots\) by Theorem 3.5.1, where the coefficients \(b_{1}\) and \(b_{2}\) depend on the initial point \(\mathbf{v}_{0}\). Several trajectories are plotted in the diagram and, for each choice of \(\mathbf{v}_{0}\), the trajectories converge toward the origin because both eigenvalues are less than \(1\) in absolute value. For this reason, the origin is called an attractor for the system.

Example \(\PageIndex{5}\)

Let \(A = \left[ \begin{array}{cc} \frac{3}{2} & 0 \\ 0 & \frac{4}{3} \end{array}\right]\). Here the eigenvalues are \(\frac{3}{2}\) and \(\frac{4}{3}\), with corresponding eigenvectors \(\mathbf{x}_1 = \left[ \begin{array}{r} 1 \\ 0 \end{array}\right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{r} 0 \\ 1 \end{array}\right]\) as before. The exact formula is

\[\mathbf{v}_k = b_1 \left( \frac{3}{2}\right)^k \left[ \begin{array}{r} 1 \\ 0 \end{array}\right] + b_2 \left( \frac{4}{3} \right)^k \left[ \begin{array}{r} 0 \\ 1 \end{array} \right] \nonumber \]

for \(k = 0, 1, 2, \dots\). Since both eigenvalues are greater than \(1\) in absolute value, the trajectories diverge away from the origin for every choice of initial point \(V_{0}\). For this reason, the origin is called a repellor for the system.

Example \(\PageIndex{6}\)

Let \(A = \left[ \begin{array}{rr} 1 & -\frac{1}{2} \\ -\frac{1}{2} & 1 \end{array}\right]\). Now the eigenvalues are \(\frac{3}{2}\) and \(\frac{1}{2}\), with corresponding eigenvectors \(\mathbf{x}_1 = \left[ \begin{array}{r} -1 \\ 1 \end{array}\right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{r} 1 \\ 1 \end{array}\right]\) The exact formula is

\[\mathbf{v}_k = b_1 \left( \frac{3}{2} \right)^k \left[ \begin{array}{r} -1 \\ 1 \end{array}\right] + b_2 \left( \frac{1}{2} \right)^k \left[ \begin{array}{r} 1 \\ 1 \end{array}\right] \nonumber \]

for \(k = 0, 1, 2, \dots\). In this case \(\frac{3}{2}\) is the dominant eigenvalue so, if \(b_{1} \neq 0\), we have \(\mathbf{v}_k \approx b_1 \left( \frac{3}{2} \right)^k \left[ \begin{array}{r} -1 \\ 1 \end{array}\right]\) for large \(k\) and \(\mathbf{v}_{k}\) is approaching the line \(y = -x\).

However, if \(b_{1} = 0\), then \(\mathbf{v}_k = b_2 \left( \frac{1}{2} \right)^k \left[ \begin{array}{r} 1 \\ 1 \end{array}\right]\) and so approaches the origin along the line \(y = x\). In general the trajectories appear as in the diagram, and the origin is called a saddle point for the dynamical system in this case.

Example \(\PageIndex{7}\)

Let \(A = \left[ \begin{array}{rr} 0 & \frac{1}{2} \\ -\frac{1}{2} & 0 \end{array}\right]\). Now the characteristic polynomial is \(c_{A}(x) = x^{2} + \frac{1}{4}\), so the eigenvalues are the complex numbers \(\frac{i}{2}\) and \(-\frac{i}{2}\) where \(i^{2} = -1\). Hence \(A\) is not diagonalizable as a real matrix. However, the trajectories are not difficult to describe. If we start with \(\mathbf{v}_0 = \left[ \begin{array}{r} 1 \\ 1 \end{array}\right]\) then the trajectory begins as

\[\mathbf{v}_1 = \left[ \def\arraystretch{1.25}\begin{array}{r} \frac{1}{2} \\ -\frac{1}{2} \end{array}\right], \mathbf{v}_2 = \left[ \def\arraystretch{1.25}\begin{array}{r} -\frac{1}{4} \\ -\frac{1}{4} \end{array}\right], \mathbf{v}_3 = \left[ \def\arraystretch{1.25}\begin{array}{r} -\frac{1}{8} \\ \frac{1}{8} \end{array}\right], \mathbf{v}_4 = \left[ \def\arraystretch{1.25}\begin{array}{r} \frac{1}{16} \\ \frac{1}{16} \end{array}\right], \mathbf{v}_5 = \left[ \def\arraystretch{1.25}\begin{array}{r} \frac{1}{32} \\ -\frac{1}{32} \end{array}\right], \mathbf{v}_6 = \left[ \def\arraystretch{1.25}\begin{array}{r} -\frac{1}{64} \\ -\frac{1}{64} \end{array}\right], \dots \nonumber \]

The first five of these points are plotted in the diagram. Here each trajectory spirals in toward the origin, so the origin is an attractor. Note that the two (complex) eigenvalues have absolute value less than 1 here. If they had absolute value greater than 1, the trajectories would spiral out from the origin.

Google PageRank

Dominant eigenvalues are useful to the Google search engine for finding information on the Web. If an information query comes in from a client, Google has a sophisticated method of establishing the “relevance” of each site to that query. When the relevant sites have been determined, they are placed in order of importance using a ranking of all sites called the PageRank. The relevant sites with the highest PageRank are the ones presented to the client. It is the construction of the PageRank that is our interest here.

The Web contains many links from one site to another. Google interprets a link from site \(j\) to site \(i\) as a “vote” for the importance of site \(i\). Hence if site \(i\) has more links to it than does site \(j\), then \(i\) is regarded as more “important” and assigned a higher PageRank. One way to look at this is to view the sites as vertices in a huge directed graph (see Section 2.2). Then if site \(j\) links to site \(i\) there is an edge from \(j\) to \(i\), and hence the \((i, j)\)-entry is a \(1\) in the associated adjacency matrix (called the connectivity matrix in this context). Thus a large number of \(1\)s in row \(i\) of this matrix is a measure of the PageRank of site \(i\).⁵

However this does not take into account the PageRank of the sites that link to \(i\). Intuitively, the higher the rank of these sites, the higher the rank of site \(i\). One approach is to compute a dominant eigenvector \(\mathbf{x}\) for the connectivity matrix. In most cases the entries of \(\mathbf{x}\) can be chosen to be positive with sum 1. Each site corresponds to an entry of \(\mathbf{x}\), so the sum of the entries of sites linking to a given site \(i\) is a measure of the rank of site \(i\). In fact, Google chooses the PageRank of a site so that it is proportional to this sum.⁶

---

5. For more on PageRank, visit https://en.Wikipedia.org/wiki/PageRank.
6. See the articles “Searching the web with eigenvectors” by Herbert S. Wilf, UMAP Journal 23(2), 2002, pages 101–103, and “The worlds largest matrix computation: Google’s PageRank is an eigenvector of a matrix of order 2.7 billion” by Cleve Moler, Matlab News and Notes, October 2002, pages 12–13.