帕斯卡矩阵

Alan Edelman 和 Gilbert Strang

麻省理工学院数学系

1. 三个帕斯卡矩阵 S、L、U

我们熟悉的杨辉三角（Pascal's triangle）可以用三种不同的矩阵——对称矩阵（symmetric matrix）、下三角矩阵（lower triangular matrix）和上三角矩阵（upper triangular matrix）——以方便的形式来容纳。截断后得到 $n$ 乘 $n$ 的矩阵 $S_n, L_n, U_n$ 。当 $n = 4$ 时，其模式清晰可见：

S_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & 10 \\ 1 & 4 & 10 & 20 \end{bmatrix} \qquad L_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix} \qquad U_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 1 \end{bmatrix}

每个 $S_n$ 的行列式（determinant）都是 1。如果只强调 $\det L_n = 1$ 和 $\det U_n = 1$ ，那就太过特殊了。行列式往往是矩阵内部更深层性质的表面反映。这三个矩阵之间的联系很快就能揭示出来。它对每个 $n$ 都成立：

S = LU \qquad\text{进而}\qquad (\det S) = (\det L)(\det U) = 1.

这个恒等式 $S = LU$ 是线性代数四大矩阵分解（matrix factorization）之一的一个实例：

三角矩阵乘以三角矩阵： $A = LU$ （高斯消元法，Gaussian elimination）
正交矩阵乘以三角矩阵： $A = QR$ （格拉姆-施密特正交化，Gram-Schmidt）
正交矩阵乘以对角矩阵乘以正交矩阵： $A = U\Sigma V^T$ （奇异值 $\Sigma$ ，singular value）
对角化（Diagonalization）： $A = S\Lambda S^{-1}$ （特征值 $\Lambda$ 中的特征值， $S$ 中的特征向量）。对称矩阵允许 $S^{-1} = S^T$ ——谱定理（spectral theorem）中的标准正交特征向量（orthonormal eigenvector）和实特征值（real eigenvalue）。

在 $A = LU$ 中，三角矩阵 $U$ 是消元的目标。主元（pivot）位于其对角线上（它们是比值 $\det A_n / \det A_{n-1}$ ，因此帕斯卡矩阵的主元都是 1）。我们通过记录在 $L$ 中的行变换来达到 $U$ 。然后通过前向消元（forward elimination）和回代（back substitution）求解 $Ax = b$ 。

对于对称正定矩阵（symmetric positive definite matrix），我们可以将 $A = LU$ 对称化为 $S = LL^T$ （有时以 Cholesky 命名）。这正是帕斯卡矩阵的情况，其中 $U = L^T$ ，这一点我们即将证明。

2. 分解 $S = LU$

本文给出 $S = LU$ 的四种证明：

第一种证明：二项式系数满足正确的恒等式
第二种证明： $S, L, U$ 对有向图（directed graph）上的路径进行计数
第三种证明：帕斯卡递归（Pascal's recursion）生成全部三个矩阵
第四种证明： $(1+x)^n$ 的系数具有函数意义

证明 1：矩阵乘法 (Matrix Multiplication)

直接证明将 $LU$ 相乘得到 $S$ 。三个矩阵的行和列均从 0 开始编号（ $i = 0$ ， $j = 0$ ）。那么 $L$ 的 $i,k$ 元素为 $\binom{i}{k}$ （" $i$ 选 $k$ "）。

将 $L$ 的第 $i$ 行乘以 $U = L^T$ 的第 $j$ 列，目标是验证

\sum_{k} L_{ik}U_{kj} = \sum_{k=0}^n \binom{i}{k}\binom{j}{k} = \binom{i+j}{i} = S_{ij}. \tag{1}

将 $i+j$ 个对象分成两组，分别包含 $i$ 个对象和 $j$ 个对象。如果我们从第一组中选取 $i-k$ 个对象，从第二组中选取 $k$ 个对象，那么我们就从 $i+j$ 个对象中选出了 $i$ 个。第一次选择有 $\binom{i}{i-k} = \binom{i}{k}$ 种方式，第二次选择有 $\binom{j}{k}$ 种方式。 $k$ 可以从 $0$ 到 $\min(i,j)$ 之间任意取值，因此总数与方程 $1$ 一致：

\sum_{k=0}^{\min(i,j)} \binom{i}{k}\binom{j}{k} = \binom{i+j}{i}. \tag{2}

这种形式的求和反映了 $L$ 和 $U$ 的三角性。当 $k > i$ 和 $k > j$ 时，二项式系数为零。

很难想象有比这更简洁的证明了（虽然证明 4 已经非常接近）。但按照这种方式发现 $LU = S$ 的可能性不大。

证明 2：图的粘合 (Gluing Graphs)

第一步是将 $S_{ij}$ 识别为从 $a_i$ 到 $b_j$ 在图 1 所示的向上-向左有向图上的路径数目。

    b3
    ^
    |
    b2
    ^
    |
    b1
    ^
    |
    b0
    ^
    |
    a0 --> a1 --> a2 --> a3

图 1：用于路径计数矩阵 $S$ 的有向图。

只有一条路径从 $a_0$ 直接向上到达 $b_j$ ，这与 $S$ 顶行中的 $S_{0j} = 1$ 一致。一条路径从 $a_i$ 直接向右到达 $b_0$ ，这与 $S_{i0} = 1$ 一致。从这一行和列出发， $S$ 的其余部分基于帕斯卡规则（Pascal's rule） $S_{i-1,j} + S_{i,j-1} = S_{ij}$ 递归构造。路径计数也给出了相同的规则（从而得到相同的矩阵 $S$ ）。

一个典型元素是 $S_{22} = \binom{4}{2} = 6$ 。从 $a_2$ 到 $b_2$ 有 6 条路径（3 条向右出发，3 条向上出发）。向右出发的路径从 $a_{i-1}$ 前往 $b_j$ ；由归纳假设，这些路径由 $S_{i-1,j}$ 计数。向上出发的路径先到达第一层，再从那里到达 $b_j$ 。这些路径由 $S_{i,j-1}$ 计数，帕斯卡规则得以确认。（为此，我们设想整个图向下平移一层，因此实际上我们是在以 $S_{i,j-1}$ 种方式从 $a_i$ 前往 $b_{j-1}$ 。）

现在沿着图 2 中的 $45^\circ$ 线切割该图。我们要证明 $L_{ik}$ 计数从 $a_i$ 到该对角线上 (k,k) 点的路径数。然后 $U_{kj}$ 计数从 $45^\circ$ 线到 $b_j$ 的路径数。

    b3
    ^
    |
    b2
    ^
    |
    b1
    ^
    |
    b0
    ^
    |
    a0 --> a1 --> a2 --> a3
    
    45 度"粘合线 (gluing line)"穿过 $0,0$, $1,1$, $2,2$, $3,3$

图 2： $L$ 计数到达 $45^\circ$ 粘合线的路径。 $U$ 计数上方的路径。

推理同样是归纳法。从 $L_{i0} = 1$ 开始，表示从 $a_i$ 到 (0,0) 的一条向右路径。同时 $L_{ii} = 1$ 表示向上到达 (i,i) 的一条路径。帕斯卡递归（Pascal's recursion）为 $L_{ik} = L_{i-1,k} + L_{i-1,k-1}$ ，这是将杨辉三角放入 $L$ 中所得的结果。

由归纳法， $L_{i-1,k}$ 计数从 $a_i$ 向左出发，然后从 $a_{i-1}$ 到达 (k,k) 的路径。到达 (k,k) 的其他路径从 $a_i$ 向上出发。通过沿 $45^\circ$ 线将图向左下方平移，我们设想这些路径从 $a_{i-1}$ 到达点 (k-1,k-1)。这些向上出发的延续路径由 $L_{i-1,k-1}$ 计数。路径计数与帕斯卡递归一致，因此它们就是 $L$ 的元素。类似地， $U_{kj}$ 计数从 (k,k) 到 $b_j$ 的路径。

接下来只需认识到，图的粘合等价于 $L$ 乘以 $U$ ！项 $L_{ik}U_{kj}$ 计数通过 (k,k) 从 $a_i$ 到 $b_j$ 的路径。然后对 $k$ 求和就计数的了所有路径（并与 $S_{ij}$ 一致）。从 $a_2$ 到 $b_2$ 的 6 条路径来自 $1\cdot 1 + 2\cdot 2 + 1\cdot 1$ 。这就完成了第二种证明。

一个（需要极力抵制的）推广来自于从图中删除边。我们可能删除从 $a_1$ 到 $a_0$ 的边。这将取消所有先向右到 $a_0$ 再向上的路径。全 1 的第 0 行从 $S$ 的所有其他行中被减去，这正是高斯消元法的第一步。

证明 3：高斯消元法 (Gaussian Elimination)

消元的步骤依次在每个主元下方产生零，一列一列地进行。 $S$ （以及 $L$ ）中的第一个主元是其左上角的元素 1。通常我们将第一个方程的倍数减去下方的方程。对于帕斯卡矩阵，Brawer 和 Pirovino 注意到可以将每一行减去其下方的行。

消元矩阵 $E$ 的元素为 $E_{ii} = 1$ 和 $E_{i,i-1} = -1$ 。对于 4 乘 4 矩阵，你可以看到下一个更小的 $L$ 是如何出现的：

EL_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & L_3 \end{bmatrix}. \tag{3}

$E$ 乘以 $L$ 得到帕斯卡递归 $L_{ik} - L_{i-1,k} = L_{i-1,k-1}$ ，产生更小的矩阵 $L_{n-1}$ ——如 $3$ 中那样向下平移。

这提示了一种归纳证明。假设 $L_{n-1}U_{n-1} = S_{n-1}$ 。那么方程 $3$ 及其转置给出

(EL_n)(U_nE^T) = \begin{bmatrix} 1 & 0 \\ 0 & L_{n-1} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & U_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & S_{n-1} \end{bmatrix}. \tag{4}

我们希望最后一个矩阵与 $ES_nE^T$ 一致。然后我们可以左乘 $E^{-1}$ 和右乘 $(E^T)^{-1}$ ，从而得出结论 $L_nU_n = S_n$ 。

考察 $ES_nE^T$ 的 $i,j$ 元素：

(ES_n)_{ij} = S_{ij} - S_{i-1,j}

(ES_nE^T)_{ij} = (S_{ij} - S_{i-1,j}) - (S_{i,j-1} - S_{i-1,j-1}).

在最后一个表达式中，前三项相互抵消，剩下 $S_{i-1,j-1}$ 。这就是更小矩阵 $S_{n-1}$ 的 (i,j) 元素，如 $4$ 中那样向下平移。归纳法完成。

这种"算法式"方法可能在没有预先知道 $LU = S$ 的情况下导向该结论。在图中，乘以 $E$ 就像删除所有从右侧到达 $45^\circ$ 线的水平边。那么所有路径必须向上到达该线。在计数时，我们可以将它们的最后一步视为当然——留下一个缩小一阶的三角形图（正好对应 $L_{n-1}$ ！）。

从 $S$ 到 $U$ 的完整消元对应于删除 $45^\circ$ 线以下的所有水平边。那么 $L = I$ ，因为每条到达该线的路径都是径直向上的。消元通常清空 $S$ 的列（以及边的列），但这不会留下一个更小的 $S_{n-1}$ 。好的消元顺序是每次乘以 $E$ 来删除一条对角线上的水平边。这就给出了证明 3 中的归纳法。

3. $L$ 的幂、逆矩阵和对数

在准备证明 4 时，我们考虑 $L$ 的"函数"意义。每一个在零点附近的泰勒级数（Taylor series）都是一个系数向量 $a = (a_0, a_1, a_2, \ldots)$ 与矩向量（moment vector） $v = (1, x, x^2, \ldots)$ 的内积。泰勒级数表示一个函数 $f(x)$ ：

\sum a_k x^k = a^T v = a^T L^{-1} L v. \tag{5}

这里 $L$ 成为一个无穷三角矩阵，包含了整个杨辉三角。乘以 $Lv$ 表明 $5$ 以 $1+x$ 的幂级数结束：

Lv = \begin{bmatrix} 1 & 0 & 0 & 0 & \cdots \\ 1 & 1 & 0 & 0 & \cdots \\ 1 & 2 & 1 & 0 & \cdots \\ 1 & 3 & 3 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \\ x^3 \\ \vdots \end{bmatrix} = \begin{bmatrix} 1 \\ 1+x \\ (1+x)^2 \\ (1+x)^3 \\ \vdots \end{bmatrix}. \tag{6}

这个简单的乘法 $6$ 非常有用。第二次乘以 $L$ 将得到 $2+x$ 的幂。乘以 $L^p$ 给出 $p+x$ 的幂。

$L^p$ 的 $i,j$ 元素必定是 $p^{i-j}\binom{i}{j}$ ，正如早期研究者所观察到的（此处显示 4 乘 4 的情况）：

L^p = \begin{bmatrix} 1 & 0 & 0 & 0 \\ p & 1 & 0 & 0 \\ p^2 & 2p & 1 & 0 \\ p^3 & 3p^2 & 3p & 1 \end{bmatrix} \qquad\text{以及}\qquad L^p L^q = L^{p+q}. \tag{7}

对于所有矩阵大小 $n = 1, 2, \ldots$ ，幂 $L^p$ 是群 $\mathbb{Z}$ 和 $\mathbb{R}$ （整数 $p$ 和实数 $p$ ）的一个表示。逆矩阵 $L^{-1}$ 具有 $p = -1$ 时的相同形式。Call 和 Velleman 发现了 $L^{-1}$ ，即 $DLD^{-1}$ ：

L^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ -1 & 3 & -3 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ & & & \\ & & DLD^{-1} & \\ & & & \end{bmatrix} \qquad\text{其中 } D = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix}. \tag{8}

$L^p$ 具有指数形式 $e^{Ap}$ ，我们可以计算 $A = \log L$ ：

A = \lim_{p\to 0} \frac{e^{Ap} - I}{p} = \lim_{p\to 0} \frac{L^p - I}{p} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 & 0 \end{bmatrix}. \tag{9}

级数 $L = e^A = I + A + A^2/2! + \cdots$ 只有 $n$ 项。它产生了 $L$ 中的二项式系数。该矩阵 $A$ 没有负的子行列式（subdeterminant）。因此其指数 $L$ 也是全正（totally positive）的，乘积 $S = LU$ 也如此。

4. 帕斯卡特征值 (Pascal Eigenvalues)

简要评述特征值： $L$ 和 $U$ 的特征值就是它们的对角元，全部为 1。对方程 $8$ 中的 $L^{-1} = DLD^{-1}$ 进行转置可得 $U^{-1} = DUD^{-1}$ 。因此 $L$ 和 $U$ 与其逆矩阵相似（矩阵总是与其转置相似）。

更为显著的是 $S^{-1}$ 与 $S$ 相似。 $S$ 的特征值必须成对互为倒数 $\lambda$ 和 $1/\lambda$ ，因为相似矩阵具有相同的特征值：

S^{-1} = U^{-1}L^{-1} = DU D^{-1} D L D^{-1} = (DU)(LU)(U^{-1}D^{-1}) = (DU)S(DU)^{-1}. \tag{10}

3 乘 3 对称帕斯卡矩阵的特征值为 $\lambda_1 = 4 + \sqrt{15}$ ， $\lambda_2 = 4 - \sqrt{15}$ ，以及 $\lambda_3 = 1$ 。于是 $\lambda_1\lambda_2 = 1$ 构成一对倒数，而 $\lambda_3 = 1$ 是自倒数的。Higham 优秀著作中的参考文献，以及 MATLAB 中的 help pascal，引出了 $S = \text{pascal}(n)$ 的其他性质。

5. 证明 4：函数的相等性 (Equality of Functions)

如果对足够多的向量 $v$ 验证了 $Sv = LUv$ ，我们就有理由得出结论 $S = LU$ 。我们的第四种也是最喜欢的证明选择了无穷向量 $v = (1, x, x^2, \ldots)$ 。 $Sv$ 的顶行展示了几何级数（geometric series） $1 + x + x^2 + \cdots = 1/(1-x)$ 。将 $Sv$ 的每一行乘以该顶行即可得到下一行。 $S$ 的函数意义体现在二项式定理（binomial theorem）中。

我们需要 $|x| < 1$ 以保证收敛（ $x$ 可以是复数）：

Sv = \begin{bmatrix} 1 & 1 & 1 & 1 & \cdots \\ 1 & 2 & 3 & 4 & \cdots \\ 1 & 3 & 6 & 10 & \cdots \\ 1 & 4 & 10 & 20 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \\ x^3 \\ \vdots \end{bmatrix} = \begin{bmatrix} \frac{1}{1-x} \\ \frac{1}{(1-x)^2} \\ \frac{1}{(1-x)^3} \\ \frac{1}{(1-x)^4} \\ \vdots \end{bmatrix}. \tag{11}

同样的结果也应来自 $LUv$ 。第一步 $Uv$ 具有额外的 $x$ 幂次，因为行已被平移：

Uv = \begin{bmatrix} 1 & 1 & 1 & 1 & \cdots \\ 0 & 1 & 2 & 3 & \cdots \\ 0 & 0 & 1 & 3 & \cdots \\ 0 & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \\ x^3 \\ \vdots \end{bmatrix} = \begin{bmatrix} \frac{1}{1-x} \\ \frac{x}{(1-x)^2} \\ \frac{x^2}{(1-x)^3} \\ \frac{x^3}{(1-x)^4} \\ \vdots \end{bmatrix}. \tag{12}

将 $1/(1-x)$ 因子提取出来， $Uv$ 的分量就是 $a = x/(1-x)$ 的幂次。

现在乘以 $L$ ，由于所有求和都是有限的，收敛不成问题。 $L$ 的第 $n$ 行包含 $(1+a)^n = \left(1 + \frac{x}{1-x}\right)^n = \left(\frac{1}{1-x}\right)^n$ 的二项式系数：

LUv = \begin{bmatrix} 1 & 0 & 0 & 0 & \cdots \\ 1 & 1 & 0 & 0 & \cdots \\ 1 & 2 & 1 & 0 & \cdots \\ 1 & 3 & 3 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} \frac{1}{1-x} \\ \frac{x}{(1-x)^2} \\ \frac{x^2}{(1-x)^3} \\ \frac{x^3}{(1-x)^4} \\ \vdots \end{bmatrix} = \begin{bmatrix} \frac{1}{1-x} \\ \frac{1}{(1-x)^2} \\ \frac{1}{(1-x)^3} \\ \frac{1}{(1-x)^4} \\ \vdots \end{bmatrix}. \tag{13}

因此对于向量 $v = (1, x, x^2, \ldots)$ ，有 $Sv = LUv$ 。这是否意味着 $S = LU$ ？取 $x = 0$ 得到坐标向量 $v_0 = (1, 0, 0, \ldots)$ 。那么 $Sv_0 = LUv_0$ 意味着 $S$ 和 $LU$ 的第一列一致（它们全是 1）。如果我们能从 $v$ 中构造出其他坐标向量，那么 $S$ 和 $LU$ 的所有列必然一致。

得到 $(0, 1, 0, \ldots)$ 的最快方法是在 $x = 0$ 处对 $v$ 求导。引入 $v_\epsilon = (1, \epsilon, \epsilon^2, \ldots)$ 并构造 $v_\epsilon$ 和 $v_0$ 的线性组合：

S\left(\frac{v_\epsilon - v_0}{\epsilon}\right) = LU\left(\frac{v_\epsilon - v_0}{\epsilon}\right). \tag{14}

令 $\epsilon \to 0$ 。每个级数都一致收敛（uniformly convergent），每个函数都是解析的（analytic），每个导数都是合法的。更高阶的导数给出其他坐标向量， $S$ 和 $LU$ 的列完全相同。通过处理无穷矩阵， $S = LU$ 对所有阶数 $n$ 同时得到确认。

另一种方法是将坐标向量视为（连续统个） $v$ 的线性组合，使用柯西积分定理（Cauchy's integral theorem）在 $x = z = 0$ 附近进行。

这些函数式的证明需要分析学家的参与，因为独自工作的代数学家可能会将 $S$ 作用在 $S_v$ 上。这个正矩阵的幂次会突然因为 $(1-x)^{-n} = -1/x$ 而变为负数。如果再乘以 $S$ 发现 $S^3 v = -v$ ，情况就更糟了：

S^2 v = \begin{bmatrix} -1/x \\ -(x-1)/x^2 \\ -(x-1)^2/x^3 \\ \vdots \end{bmatrix} \qquad\text{以及}\qquad S^3 v = \begin{bmatrix} -1 \\ -x \\ -x^2 \\ \vdots \end{bmatrix} = -v. \tag{15}

我们似乎证明了 $S^3 = -I$ 。这可能存在一些微小的收敛问题。这并没有困扰到 Cauchy（在他状态好的时候），并且我们一定看到了他的几何级数 $1/(1-2)$ 的矩阵推广：

1 + 2 + 4 + 8 + \cdots = -1. \tag{16}

6. 莫比乌斯矩阵 (Mobius Matrices)

真正的代数学家会在群表示（group representation）的框架中寻找帕斯卡类型的矩阵。假设无穷矩阵 $S, U, L$ 分别表示我们在证明 4 中遇到的莫比乌斯变换（Mobius transformation） $x \mapsto 1/(1-x)$ 、 $x \mapsto x/(1-x)$ 和 $x \mapsto x+1$ 。那么 $LU = S$ 将有一个更短的证明 5，通过复合来自 $L$ 和 $U$ 的 $y = x/(1-x)$ 和 $z = y + 1$ ：

z = \frac{x}{1-x} + 1 = \frac{1}{1-x}.

我们希望研究更大一类形如 $(ax+b)/(cx+d)$ 的"莫比乌斯矩阵"。一个有限维表示导致 $M^3 = I$ ，其中旋转矩阵带有交替符号，在 MATLAB 中称为 M = pascal(n, 2)。以下是 $n = 3$ 的情况：

M = \begin{bmatrix} 1 & 1 & 1 \\ -2 & -1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \qquad\text{因为}\qquad M\begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} = \begin{bmatrix} 1 \\ 1-x \\ (1-x)^2 \end{bmatrix}

且 $M^3 = I$ ：

M^3 = \begin{bmatrix} 1 & 1 & 1 \\ -2 & -1 & 0 \\ 1 & 0 & 0 \end{bmatrix}^3 = I.

Waterhouse 应用这一思想（模 $p$ ）证明了 Strauss 的一个定理：如果 $n$ 是 $p$ 的幂，则 $S^3 = I \pmod{p}$ 。基于帕斯卡矩阵的数字变换（digital transform）似乎很有可能等待被发掘。如果杨辉三角最终成为应用数学的一部分，那将是既讽刺又美妙的。

7. 结论：对杨辉三角的两种观点

帕斯卡并非第一个构造出他的三角形的人。Edwards 描述了其元素的逐步发现过程，在波斯（Omar Khayyam 本人）、中国、欧洲和印度。证明属于帕斯卡（包括一个归纳证明，后来成为数学家的典范）。我们非常欣赏 James Bernoulli 的观点，他通过计算 $1^p + \cdots + N^p$ 完成了与幂次的联系：

"这个表格具有真正非凡且令人钦佩的性质；因为除了隐藏着组合学的奥秘之外，熟悉数学更高领域的人都知道，它还掌握着该学科其余部分最重要的秘密。"

没有人能说得比这更好了。但我们这个时代的一位天才表达了不同的想法，我们友善的读者肯定不会认同：

"这里面存在的关系如此之多，以至于当有人发现一个新的恒等式时，除了发现者本人之外，已经没有太多人会对此感到兴奋了！"

8. 参考文献 References

Robert Brawer and Magnus Pirovino, The Linear Algebra of the Pascal Matrix, Linear Algebra and Its Applications 174 (1992), 13-23.
Gregory Call and Daniel Velleman, Pascal's Matrices, American Math. Monthly 100 $1993$ .
E.B. Curtis, David Ingerman and J.A. Morrow, Circular planar graphs and resistor networks, Linear Algebra and Its Applications 283 $1998$ 115-150.
A.W.F. Edwards, Pascal's Arithmetical Triangle: The Story of a Mathematical Idea, Charles Griffin, 1987 and Johns Hopkins University Press, 2002.
N.J. Higham, Accuracy and Stability in Numerical Algorithms, SIAM, 1996.
Peter Hilton and Jean Pederson, Looking into Pascal's Triangle: Combinatorics, Arithmetic, and Geometry, Math. Magazine 60 (1987), 305-316.
David Ingerman, Discrete and continuous inverse boundary problems on a disc, Ph.D. Thesis, University of Washington, 1997.
Samuel Karlin, Total Positivity, Vol. 1, Stanford University Press, 1968.
Donald Knuth, Fundamental Algorithms: Vol. I, The Art of Computer Programming, Addison-Wesley, 1973.
Gilbert Strang, Introduction to Linear Algebra, 3rd edition, Wellesley-Cambridge Press, 2003.
W.C. Waterhouse, The map behind a binomial coefficient matrix over Z/pZ, Linear Algebra and Its Applications 105 (1988), 195-198.

来源：MIT OpenCourseWare, 18.06 Linear Algebra, Spring 2010

阅读声明