4.5. 一些例子

可逆矩阵开根

命题 4.5.1. 设 $A$ 是 $n$ 阶可逆复方阵. 则存在可逆方阵 $B$ 使得 $A=B^2$.

我们首先考虑 $A=J_n(\lambda )$ 是一个 Jordan 块的情况, 即$$A=\lambda I_n+NN=J_n(0)=\left[\begin{array}{cccc}0& 1& & 0\\ & 0& \ddots & \\ & & \ddots & 1\\ 0& & & 0\end{array}\right]$$

我们把 $A$ 写成 $A=\lambda (I_n+{\lambda }^{-1}N)$. 利用函数 $(1+x{)}^{1/2}$ 在 $x=0$ 处的 Taylor 展开$$(1+x{)}^{1/2}=1+\sum _{k=1}^{\infty }\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots \left(\frac{1}{2}-k+1\right)}{k!}{x}^k$$我们得到级数恒等式$$1+x={\left(1+\sum _{k=1}^{\infty }\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots \left(\frac{1}{2}-k+1\right)}{k!}{x}^k\right)}^2$$

代入矩阵 $x={\lambda }^{-1}N$ 并利用 $N^n=0$, 我们得到$$I_n+{\lambda }^{-1}N={\left(I_n+\sum _{k=1}^{n-1}\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots \left(\frac{1}{2}-k+1\right)}{k!}{\lambda }^{-k}{N}^k\right)}^2$$因此我们可以取$$B=\sqrt{\lambda }\left(I_n+\sum _{k=1}^{n-1}\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots \left(\frac{1}{2}-k+1\right)}{k!}{\lambda }^{-k}{N}^k\right)$$

对于一般的情况, 我们可以作相似变换$$A=P\left[\begin{array}{ccc}{J}_{m_1}({\lambda }_1)& & 0\\ & \cdots & \\ 0& \cdots & J_{m_k}({\lambda }_k)\end{array}\right]P^{-1}$$这里每个 $J_{m_i}({\lambda }_1)$ 都是 Jordan 块, 因此可以如上构造 $B_i$ 使得 $J_{m_i}({\lambda }_1)=B_i^2$. 取$$B=P\left[\begin{array}{ccc}{B}_1& & 0\\ & \cdots & \\ 0& \cdots & B_k\end{array}\right]P^{-1}$$则满足 $B^2=A$.

注记. 类似的方法可以证明, 对于 $n$ 阶可逆复方阵和正整数 $k$, 存在可逆方阵 $B$ 使得 $A=B^k$.

指数矩阵

命题 4.5.2. 设 $A$ 是 $n$ 阶复方阵. 则如下矩阵级数$$e^A:=\sum _{k=0}^{\infty }\frac{A^k}{k!}=I_n+A+\frac{A^2}{2!}+\cdots +\frac{A^m}{m!}+\cdots$$收敛到一个可逆矩阵, 并且$$\det (e^A)=e^{\mathrm{Tr}A}$$

我们同样也是先考虑 $A=J_n(\lambda )$ 是一个 Jordan 块的情况, 即$$A=\lambda I_n+NN=J_n(0)=\left[\begin{array}{cccc}0& 1& & 0\\ & 0& \ddots & \\ & & \ddots & 1\\ 0& & & 0\end{array}\right]$$利用 $N^n=0$ 易知 $e^A$ 收敛到 (计算留作练习) $$\begin{array}{rl}{e}^A=& e^{\lambda I_n}{e}^N=e^{\lambda }\left(I_n+N+\frac{N^2}{2!}\cdots +\frac{N^{n-1}}{(n-1)!}\right)\\ =& \left[\begin{array}{cccccc}{e}^{\lambda }& e^{\lambda }& \cdots & \cdots & \frac{e^{\lambda }}{(n-2)!}& \frac{e^{\lambda }}{(n-1)!}\\ & e^{\lambda }& \cdots & \cdots & \cdots & \frac{e^{\lambda }}{(n-2)!}\\ & & \ddots & & & \\ & & & \ddots & & \\ & & & & e^{\lambda }& e^{\lambda }\\ 0& & & & & e^{\lambda }\end{array}\right]\end{array}$$此时有 $\det (e^A)=e^{n\lambda }=e^{\mathrm{Tr}A}$.

对于一般的情况, 我们可以作相似变换$$A=P\left[\begin{array}{ccc}{J}_{m_1}({\lambda }_1)& & 0\\ & \cdots & \\ 0& \cdots & J_{m_k}({\lambda }_k)\end{array}\right]P^{-1}$$则$$e^A=P\left[\begin{array}{ccc}{e}^{J_{m_1}({\lambda }_1)}& & 0\\ & \cdots & \\ 0& \cdots & e^{J_{m_k}({\lambda }_k)}\end{array}\right]P^{-1}$$并且$$\det (e^A)=e^{m_1{\lambda }_1+\cdots +m_k{\lambda }_k}=e^{\mathrm{Tr}A}$$成立. 由于 $e^{\mathrm{Tr}A}\ne 0$, $e^A$ 是可逆矩阵. 实际上, $e^A$ 的逆易知是 $e^{-A}$.

例子 4.5.3. 考虑方阵$$A=\left[\begin{array}{ccc}3& -2& 2\\ 0& 1& 2\\ 0& -1/2& 3\end{array}\right]$$可以验证它相似于如下 Jordan 标准型$$A=P\left[\begin{array}{ccc}3& 0& 0\\ 0& 2& 1\\ 0& 0& 2\end{array}\right]P^{-1}\text{这里}P=\left[\begin{array}{ccc}1& 2& 0\\ 0& 2& 0\\ 0& 1& 1\end{array}\right]P^{-1}=\left[\begin{array}{ccc}1& -1& 0\\ 0& 1/2& 0\\ 0& -1/2& 1\end{array}\right]$$$A$ 有两个 Jordan 块. 因此$$e^A=P\left[\begin{array}{ccc}{e}^3& 0& 0\\ 0& e^2& e^2\\ 0& 0& e^2\end{array}\right]P^{-1}=\left[\begin{array}{ccc}1& 2& 0\\ 0& 2& 0\\ 0& 1& 1\end{array}\right]\left[\begin{array}{ccc}{e}^3& 0& 0\\ 0& e^2& e^2\\ 0& 0& e^2\end{array}\right]\left[\begin{array}{ccc}1& -1& 0\\ 0& 1/2& 0\\ 0& -1/2& 1\end{array}\right]=\left[\begin{array}{ccc}{e}^3& -e^3& 2e^2\\ 0& 0& 2e^2\\ 0& -e^2/2& 2e^2\end{array}\right]$$

极小多项式

由 Cayley–Hamilton 定理, 我们知道 $n$ 阶方阵 $A$ 的特征多项式 $\phi (\lambda )=\det (\lambda I_n-A)$ 是 $A$ 的一个化零多项式, 即满足$$\phi (A)=0$$

实际上满足 $f(A)=0$ 的多项式, 即 $A$ 的化零多项式中, 特征多项式 $\phi (\lambda )$ 并不一定是次数最低的. 例如对于方阵$$A=\left[\begin{array}{cccc}2& 1& 0& 0\\ 0& 2& 0& 0\\ 0& 0& 3& 0\\ 0& 0& 0& 3\end{array}\right]\phi (\lambda )=(\lambda -2{)}^2(\lambda -3{)}^2$$容易验证 $A$ 满足一个 3 次代数方程$$(A-2I_4{)}^2(A-3I_4)=0$$

定义 4.5.4. 方阵 $A$ 的所有非平凡化零多项式中次数最小的首一多项式称为 $A$ 的极小多项式, 记为 $d_A(\lambda )$. 这里首一多项式指的是多项式最高次项的系数是 $1$, 即 $d_A(\lambda )={\lambda }^d+\cdots$.

由 Cayley–Hamilton 定理知 $A$ 有化零多项式, 因此 $A$ 的极小多项式是存在的且次数不超过 $A$ 的阶数. 另一方面, $A$ 的极小多项式是唯一的. 假设 $d_A(\lambda )$ 和 $d_A^{\prime }(\lambda )$ 均为 $A$ 的极小多项式. 则 $d_A(\lambda )$ 和 $d_A^{\prime }(\lambda )$ 的次数相同, 并且 $d_A(\lambda )-d_A^{\prime }(\lambda )$ 是次数更低的化零多项式. 由极小多项式的次数最小性, 说明 $d_A(\lambda )-d_A^{\prime }(\lambda )=0$ 是平凡的, 即 $d_A(\lambda )=d_A^{\prime }(\lambda )$.

首先我们注意到, 如果 ${\lambda }_0$ 不是 $A$ 的特征值, 则线性方程组$$(A-{\lambda }_0{I}_n)\vec{x}=0$$只有零解, 即 $A-{\lambda }_0{I}_n$ 是可逆矩阵. 因此如果 $f(\lambda )$ 是 $A$ 的化零多项式且 ${\lambda }_0$ 是 $f$ 的一个根, 即有 $f(\lambda )=(\lambda -{\lambda }_0)g(\lambda )$, 则$$f(A)=(A-{\lambda }_0{I}_n)g(A)=0\stackrel{\text{左乘(A−λ0In)−1}}{⟹}g(A)=0$$故 $g(\lambda )$ 也是 $A$ 的化零多项式且次数比 $f$ 低. 这说明 $d_A(\lambda )$ 的根只包含 $A$ 的特征值.

例子 4.5.5. 设 $A=J_n({\lambda }_0)$ 是 $n$ 阶 Jordan 块, 则 $A$ 的最小多项式为$$d_A(\lambda )=(\lambda -{\lambda }_0{)}^n$$

实际上, $A$ 只有一个特征值 ${\lambda }_0$, 其最小多项式形如 $(\lambda -{\lambda }_0{)}^m$. 由于$$N=A-{\lambda }_0{I}_n=\left[\begin{array}{cccc}0& 1& & 0\\ & 0& \ddots & \\ & & \ddots & 1\\ 0& & & 0\end{array}\right]$$满足 $N^{n-1}\ne 0,N^n=0$, 我们得到 $m=n$. 此时 $A$ 的极小多项式等于特征多项式.

命题 4.5.6. 设 $A$ 是 $n$ 阶复方阵, ${\lambda }_1,\cdots ,{\lambda }_s$ 是 $A$ 的所有互不相同的特征值. 则 $A$ 的最小多项式为$$d_A(\lambda )=(\lambda -{\lambda }_1{)}^{d_1}\cdots (\lambda -{\lambda }_s{)}^{d_s}$$其中 $d_i$ 是特征值 ${\lambda }_i$ 的 Jordan 块的最大阶数, 即 $(\lambda -{\lambda }_i{)}^{d_i}$ 是特征值 ${\lambda }_i$ 最高次数的初等因子.

证明: $A$ 相似于 Jordan 标准型$$A=P\left[\begin{array}{cccc}{J}_1& 0& \cdots & 0\\ 0& J_2& \cdots & 0\\ \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & 0& J_s\end{array}\right]P^{-1}$$

对任何多项式 $f(\lambda )$, 我们有$$f(A)=P\left[\begin{array}{cccc}f(J_1)& 0& \cdots & 0\\ 0& f(J_2)& \cdots & 0\\ \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & 0& f(J_s)\end{array}\right]P^{-1}$$因此 $f(A)=0$ 当且仅当对每个 $J_i$ 均有 $f(J_i)$=0. 而每个 $J_i$ 是形如由 Jordan 块构成的方阵$$J_i=\left[\begin{array}{cccc}{J}_{m_i^{(1)}}({\lambda }_i)& 0& \cdots & 0\\ 0& J_{m_i^{(2)}}({\lambda }_i)& \cdots & 0\\ \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & 0& J_{m_i^{(t_i)}}({\lambda }_i)\end{array}\right]$$因此 $f(J_i)=0$ 当且仅当对每个 $f(J_{m_i^{(k)}}({\lambda }_i))=0$. 由例 4.5.5 易知$$d_i=\max \{m_i^{(1)},m_i^{(2)},\cdots ,m_i^{(t_i)}\}$$

$\square$

例子 4.5.7. 方阵 $A=\left[\begin{array}{cccc}2& 1& 0& 0\\ 0& 2& 0& 0\\ 0& 0& 3& 0\\ 0& 0& 0& 3\end{array}\right]$ 的极小多项式为 $(\lambda -2{)}^2(\lambda -3)$.

Google PageRank

PageRank 是 Google 搜索引擎用来排名网页相关性和重要性的算法. 其核心思想是一个网页的重要性与其链接到的网页的重要性的数量和质量有关. 基本数学原理是通过网页数据得到一个大型的矩阵, 然后通过求解最大特征值的特征向量得到排名数据.

我们将互联网看作一个巨大的有向图, 每个节点代表一个网页, 每条有向边代表一个链接, 边的方向表示链接的方向.

上图表示有 4 个网页 A、B、C、D, 链接关系如下:

•	A 链接到 B 和 C
•	B 链接到 C
•	C 链接到 A 和 D
•	D 链接到 A

PageRank 算法将给每个网页 $i$ 匹配一个 PageRank 值 $r_i$, $r_i$ 的值越大表示其越重要. 其基本思想是这个 PageRank 值是通过网络关系来体现的: 如果更多更重要的网页关联到某个网页, 那么这个网页本身也更重要. 具体而言, 引入链接关系矩阵 $M=(m_{ij})$:

•	如果网页 $j$ 链接到网页 $i$, 则$$m_{ij}=\frac{1}{L(j)}$$其中 $L(j)$ 是所有从网页 $j$ 链出的边数.
•	如果网页 $j$ 没有链接到网页 $i$, 则 $m_{ij}=0$

$m_{ij}$ 表现了从网页 $j$ 链接到网页 $i$ 的权重. 例如对上图所示 4 个网络, 其链接关系矩阵为$$M=\left[\begin{array}{cccc}0& 0& 1/2& 1\\ 1/2& 0& 0& 0\\ 1/2& 1& 0& 0\\ 0& 0& 1/2& 0\end{array}\right]$$这里我们用 $i=1,2,3,4$ 来分别表示网页 A,B,C,D. 例如

•	$m_{13}=1/2$, 因为网页 C 链接到网页 A, 且网页 C 的出链数量为 2 (链接到 A 和 D) .
•	$m_{21}=1/2$, 因为网页 A 链接到网页 B, 且网页 A 的出链数量为 2 (链接到 B 和 C) .
•	$m_{32}=1$, 因为网页 B 链接到网页 C, 且网页 B 的出链数量为 1 (链接到 C) .
•	$m_{23}=0$, 因为没有链接从网页 C 链接到网页 B.

PageRank 算法用来计算每个网页 PageRank 权重 $r(i)$ 的方法为: 一个网页的 PageRank 值等于所有链接到它的网页的 PageRank 值的加权平均, 权重为链接概率. 具体公式为: $$r_i=\sum _j{m}_{ij}{r}_j$$

我们把所有网页的 PageRank 权重 $\{r_i\}$ 组合为列向量 $\vec{r}$, 则上述方程可以写成矩阵形式$$M\vec{r}=\vec{r}$$因此寻找网页的 PageRank 值即为求解链接关系矩阵 $M$ 属于特征值 $1$ 的特征向量.

上述 4 个网页的例子中, 求解 $M\vec{r}=\vec{r}$ 可以得到归一化的 PageRank 值$$\vec{r}=\left[\begin{array}{c}1/3\\ 1/6\\ 1/3\\ 1/6\end{array}\right]$$因此 $A,C$ 重要性最高, $B,D$ 次之. 这个结果和图示是相符合的.

$M$ 是否有特征值 $1$?

首先观察到每个网页链出的总权重是 $1$, 即对每个 $j$ 有$$\sum _i{m}_{ij}=1$$写成矩阵的形式为$$M^T\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right]=\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right]$$这表明 $M$ 的转置 $M^T$ 有一个属于特征值 $1$ 的特征向量. 由于 $M^T$ 和 $M$ 具有相同的特征多项式, 这说明 $M$ 一定有特征值 $1$, 因此方程 $M\vec{r}=\vec{r}$ 是有解的.

$M$ 的属于特征值 $1$ 的特征子空间 $V_1$ 是否是 $1$ 维的?

如果特征子空间 $V_1$ 是 $1$ 维的话, 那么得到唯一的一个 PageRank 向量 $\vec{r}$ (不同特征向量差一个系数, 可以通过设置归一化条件 ${\sum }_i{r}_i=1$ 把这个系数固定) . 然而实际上很容易找到 $\dim V_1>1$ 的例子, 这给用 PageRank 算法来准确地衡量网页的重要性造成了困难.

为了解决这个困难, PageRank 算法引入了一个阻尼因子 $d$(通常设置为 0.85). 阻尼因子表示用户有 $d$ 的概率点击链接, $1-d$ 的概率随机跳转到任意一个网页. 改进后的链接关系矩阵为$$\hat{M}=dM+(1-d)S$$这里 $S$ 的每个矩阵元都是 $1/n$ ($n$ 是网页的总个数) $$S=\left[\begin{array}{cccc}1/n& 1/n& \cdots & 1/n\\ 1/n& 1/n& \cdots & 1/n\\ \cdots & \cdots & \cdots & \cdots \\ 1/n& 1/n& \cdots & 1/n\end{array}\right]$$$\hat{M}$ 的每一列加起来仍然是 $1$, 因此仍然有特征值 $1$. 改进的 PageRank 计算公式为$$\hat{M}\vec{r}=\vec{r}$$

命题 4.5.8. $\hat{M}$ 的特征子空间 $V_1$ 是 1 维的.

证明: 首先观察到 $\hat{M}$ 的每个矩阵元 ${\hat{m}}_{ij}>0$. 假设 $\vec{r}\in V_1$ 是任意一个特征向量, 即满足$$\hat{M}\vec{r}=\vec{r}$$我们说明 $\vec{r}$ 的每个分量不可能即有正数又有负数. 实际上, 假如 $r_i$ 中即有正数也有负数. 由于 ${\hat{m}}_{ij}>0$, 我们有$$|\sum _j{\hat{m}}_{ij}{r}_j|<\sum _j{\hat{m}}_{ij}|r_j|$$

由特征向量方程 $r_i={\sum }_j{\hat{m}}_{ij}{r}_j$, 得到$$|r_i|=|\sum _j{\hat{m}}_{ij}{r}_j|<\sum _j{\hat{m}}_{ij}|r_j|$$两边对 $i$ 求和, 并利用 ${\sum }_i{\hat{m}}_{ij}=1$, 我们得到$$\sum _i|r_i|<\sum _{i,j}{\hat{m}}_{ij}|r_j|=\sum _j|r_j|$$矛盾. 这说明 $\vec{r}$ 的每个分量不可能即有正数又有负数.

现在假设 $\dim V_1>1$. 设 $\vec{r}$ 和 $\vec{s}$ 是 $V_1$ 中两个线性无关的特征向量. 不妨设 $\vec{r},\vec{s}$ 的分量都是非负的, 因此 ${\sum }_i{r}_i>0,{\sum }_i{s}_i>0$. 取非零实数 $a,b$ 使得$$a(\sum _i{r}_i)+b(\sum _i{s}_i)=0$$

考虑线性组合 $a\vec{r}+b\vec{s}$. 由于 $a\vec{r}+b\vec{s}\in V_1$, 上述讨论知它每个分量不可能即有正数又有负数. 由 $a,b$ 的取法, 向量 $a\vec{r}+b\vec{s}$ 的所有分量求和是 $0$, 因此必然有 $a\vec{r}+b\vec{s}=0$. 这与 $\vec{r},\vec{s}$ 线性无关的假设矛盾. 因此假设 $\dim V_1>1$ 不成立, 故 $\dim V_1=1$.

$\square$

这个命题说明, 在考虑阻尼因子后, 用改进的算法的确得到一个确定的 PageRank 向量. 可以进一步证明 (见习题) , $\hat{M}$ 的根子空间 $R_1$ 也是 $1$ 维的, 即 $V_1=R_1$.

如何计算 PageRank 向量?

实际应用中网页的数量是非常多的, 改进的链接关系矩阵 $\hat{M}$ 是一个巨大的矩阵. 如何有效的计算 PageRank 向量 $\vec{r}$ ? 这里关键的一个性质是如下命题.

命题 4.5.9. 设 $\lambda$ 是改进的链接关系矩阵 $\hat{M}$ 的一个特征值, 则 $|\lambda |\le 1$.

证明: 设复列向量 $\vec{\alpha }\in {\mathbb{C}}^n$ 是属于特征值 $\lambda$ 的一个特征向量: $\hat{M}\vec{\alpha }=\lambda \vec{\alpha }$. 考虑如下行向量$$E_{\vec{\alpha }}=\left[\begin{array}{cccc}{b}_1& b_2& \cdots & b_n\end{array}\right]\text{这里}{b}_i=\{\begin{array}{ll}\frac{{\bar{\alpha }}_i}{|{\alpha }_i|}& {\alpha }_i\ne 0\\ 0& {\alpha }_i=0\end{array}$$

记$$E_{\vec{\alpha }}\hat{M}=\left[\begin{array}{cccc}{k}_1& k_2& \cdots & k_n\end{array}\right]$$由于 ${\sum }_i{\hat{m}}_{ij}=1$ 并且每个 ${\hat{m}}_{ij}>0$ 知$$|k_j|=|\sum _i{b}_i{\hat{m}}_{ij}|\le \sum _i{\hat{m}}_{ij}=1$$

由方程 $\hat{M}\vec{\alpha }=\lambda \vec{\alpha }$ 得到 $E_{\vec{\alpha }}\hat{M}\vec{\alpha }=\lambda E_{\vec{\alpha }}\vec{\alpha }$, 即$$\sum _i{k}_i{\alpha }_i=\lambda \sum _i|{\alpha }_i|$$因此$$\lambda =\frac{\sum _i{k}_i{\alpha }_i}{\sum _i|{\alpha }_i|}⟹|\lambda |\le \frac{\sum _i|k_i||{\alpha }_i|}{\sum _i|{\alpha }_i|}\le 1$$

$\square$

可以进一步证明, 满足 $|\lambda |=1$ 的特征值只有 $\lambda =1$ (见习题) . 由命题 4.5.8 和命题 4.5.9 以及 Jordan 标准型知, 改进的链接关系矩阵 $\hat{M}$ 相似于$$\hat{M}=P\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& J_{m_1}({\lambda }_1)& \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & \cdots & J_{m_k}({\lambda }_k)\end{array}\right]P^{-1}$$这里 Jordan 块 $J_{m_i}({\lambda }_i)$ 对应的特征值 ${\lambda }_i$ 均满足 $|{\lambda }_i|<1$. 对于这样的 Jordan 块, 可以证明 (见习题) $$\underset{N\to \infty }{\lim }{J}_{m_i}({\lambda }_i{)}^N=0$$

因此$$\underset{N\to \infty }{\lim }{\hat{M}}^N=\underset{N\to \infty }{\lim }P\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& J_{m_1}({\lambda }_1{)}^N& \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & \cdots & J_{m_k}({\lambda }_k{)}^N\end{array}\right]P^{-1}=P\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 0& \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots \\ 0& \cdots & \cdots & 0\end{array}\right]P^{-1}$$

设 $P$ 的列向量为$$P=\left[\begin{array}{cccc}{\vec{\beta }}_1& {\vec{\beta }}_2& \cdots & {\vec{\beta }}_n\end{array}\right]$$由构造知 ${\vec{\beta }}_1$ 是特征值 $1$ 的特征向量. 我们得到$$\underset{N\to \infty }{\lim }{\hat{M}}^N=\left[\begin{array}{cccc}{\vec{\beta }}_1& 0& \cdots & 0\end{array}\right]P^{-1}$$

现在取一个初始向量 ${\vec{r}}_0$, 设$$P^{-1}{\vec{r}}_0=\left[\begin{array}{c}{a}_1\\ a_2\\ \cdots \\ a_n\end{array}\right]$$并且 $a_1\ne 0$. 则$$\underset{N\to \infty }{\lim }{\hat{M}}^N{\vec{r}}_0=a_1{\beta }_1$$收敛到特征值 $1$ 的一个特征向量!

这给出了如下计算 PageRank 向量 $\vec{r}$ 的算法: 取初始向量$${\vec{r}}_0=\left[\begin{array}{c}1/n\\ 1/n\\ ⋮\\ 1/n\end{array}\right]$$即初始时把所有网页的 PageRank 值都设置为 $1/n$. 然后开始迭代计算$$\begin{array}{rl}{\vec{r}}_1& =\hat{M}{\vec{r}}_0\\ {\vec{r}}_2& =\hat{M}{\vec{r}}_1={\hat{M}}^2{\vec{r}}_0\\ & ⋮\\ {\vec{r}}_N& ={\hat{M}}^N{\vec{r}}_0\end{array}$$

注意到$$\begin{array}{rl}\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]{\vec{r}}_k=& \left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]\hat{M}{\vec{r}}_{k-1}\\ =& \left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]{\vec{r}}_{k-1}\\ =& \cdots \\ =& \left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]{\vec{r}}_0=1\end{array}$$因此每个迭代的向量 ${\vec{r}}_k$ 的所有分量的和都是 $1$, 即都是归一化的. 当 $N$ 充分大时, 多次迭代得到的向量 ${\vec{r}}_N$ 即给出了 PageRank 向量 $\vec{r}$ 的近似值.