第七章

高斯消去、Lu因子分解、Cholsky因子分解、缩减行梯队形式

在这一章中，我们假设所有的向量空间都在r域上，所有的结果不依赖于r的次序，也不依赖于任意域的平方根。

7.1激励示例：曲线插值

曲线插值是计算机图形学和机器人学（路径规划）中经常出现的问题。有很多方法可以解决这个问题，在本节中，我们将描述一个使用三次样条曲线的解决方案。这种样条由三次B’Ezier曲线组成。它们经常被使用，因为它们的实现成本较低，并且比二次B’ezier曲线具有更大的灵活性。

三次B’ezier曲线c（t）（在r2或r3中）由四个控制点列表指定。

（b0，b2，b2，b3），并由方程式参数化给出

c（t）=（1 t）3 b0+3（1 t）2tb1+3（1 t）t2 b2+t3 b3.

显然，t∈[0,1]，点c（t）属于控制点b0、b1、b2、b3的凸壳。多项式

（1−t）3、3（1−t）2t、3（1−t）t2、t3

是三阶伯恩斯坦多项式。

通常，我们只对区间内t值对应的曲线段感兴趣[0,1]。尽管如此，控制点的位置仍然会严重影响曲线段的形状，甚至可能有一个自相交；请参见图7.1、7.2、7.3，以说明各种配置。

一百六十三

图7.1：“标准”b’ezier曲线。

图7.2：带有拐点的B’ezier曲线。

7.1。激励示例：曲线插值

图7.3：自交b’ezier曲线。

插值问题需要找到通过某些给定数据点的曲线，并可能满足一些额外的约束。

B’ezier样条曲线f是由B’ezier曲线（如c1，…，cm（m≥2））的曲线段组成的曲线。我们假设f在[0，m]上定义，因此对于i=1，…，m，

f（t）=Ci（t−i+1），i−1≤t≤i。

通常，在任意两个连接点之间，即在任意两点Ci（1）和Ci+1（0）之间，对于i=1，…，m-1，需要一定的平滑度。我们要求ci（1）=ci+1（0）（c0连续性），通常情况下，ci在1和ci+1在0的导数等于二阶导数。这被称为C2连续性，它确保切线和曲率一致。

有许多插值问题，我们认为其中一个最常见的问题可以表述为：

问题：给定n＋1个数据点x0，…，xn，找到一个C2三次样条曲线F，使得f i（i）＝Xi为i，0±i±n（n＝2）。

解决这个问题的一种方法是找到n+3辅助点d−1，…，dn+1，称为de boor控制点，从中可以找到n b´ezier曲线。事实上，

D−1=X0和DN+1=XN

所以我们只需要找到n+1点，d0，…，dn。

结果表明，N-B’ezier曲线上的C2连续性约束只产生N-1方程，因此可以任意选择D0和DN。在实践中，根据不同的端部条件，如规定的X0和XN速度，选择D0和DN。目前，我们假定给出了d0和dn。

图7.4说明了一个涉及n+1=7+1=8个数据点的插值问题。任意选择控制点D0和D7。

图7.4：通过点X0、X1、X2、X3、X4、X5、X6、X7的C2三次插值样条曲线。

可以看出，d1，…，dn-1由线性系统给出。

.

稍后我们将证明，上面的矩阵是可逆的，因为它是严格对角占优的。

一旦上述系统被解决，b’ezier cubics c1，…，cn的确定如下：

（我们假设n≥2）：对于2≤i≤n−1，控制点（由

控制点（由

控制点（由

图7.5说明了n=7的过程样条插值。

我们现在将描述求解线性系统的各种方法。由于上述系统的矩阵是三对角的，所以有专门的方法比一般的方法更有效。我们将讨论其中的一些方法。

7.2高斯消元

设a为n×n矩阵，设b∈rn为n维向量，并假定a是可逆的。我们的目标是解决系统a x=b。由于假设a是可逆的，我们知道这个系统有一个唯一的解决方案x=a-1b。经验表明，揭示了两个反直觉的事实：

(1) 应避免显式计算a的逆a−1。这是无效的，因为它等于求解n个线性系统au（j）=ej，对于j=1，…，n，其中ej=（0，…，1，…，0）是rn的第j个规范基向量（其中1是第j个槽）。通过这样做，我们可以用n个系统的分辨率来代替单个系统的分辨率，我们仍然需要用a−1乘以b。

图7.5:x0、x1、x2、x3、x4、x5、x6、x7的c2三次插值，带有相关的颜色编码b’ezier cubics。

(2) 我们不能通过计算行列式（使用克莱默公式）来求解（大型）线性系统，因为这种方法需要大量的加法（resp）。乘法）与（n+1）成比例！（响应（N+2）！）.

大多数直接方法（与迭代方法相反，寻找解的近似值）基于的关键思想是，如果a是上三角矩阵，这意味着对于1≤j<i≤n（resp），aij=0。下三角，这意味着对于1≤i<j≤n，aij=0，那么计算解x是微不足道的。实际上，假设A是一个上三角矩阵

那么det（a）=a11a22·······a n n=06，这意味着i=1，…，n时aii=06，我们可以通过反替换从下到上求解系统ax=b。也就是说，首先我们从最后一个方程计算xn，然后将xn的这个值插入到最后一个方程的下一个方程中，并从中计算xn−1，依此类推。这将产生

网络错误	网络错误
网络错误	网络错误 网络错误
网络错误	网络错误	网络错误

注意，可以避免使用行列式来证明，如果a是可逆的，那么a i i=06对于i=1，…，n。事实上，可以直接（通过归纳）证明，当上（或下）三角形矩阵的所有对角项都不为零时，上（或下）三角形矩阵是可逆的。

如果A是下三角，我们用正替换法从上到下求解系统。

因此，我们需要的是一种将矩阵转换为上三角形式的等价矩阵的方法。这可以通过消除来实现。让我们用下面的例子来说明这个方法：

2x+y+z=5

4x−6y=−2

-2X+7Y+2Z=9。

我们可以从第二个和第三个方程中去掉变量x，如下所示：从第二个方程中减去第一个方程的两倍，然后将第一个方程添加到第三个方程中。我们得到了新的系统

2x+y+z=5

−8Y−2Z=−12 8Y+3Z=14。

这一次，我们可以通过将第二个方程添加到第三个方程来消除第三个方程中的变量y：

2x+y+z=5

−8Y−2Z=−12 Z=2.

最后一个系统是上三角形。使用反替换，我们找到了解决方案：z=2，y=1，x=1。

请注意，我们只执行了行操作。一般的方法是使用简单的行操作（即在矩阵的另一行中添加或减去一行的倍数）迭代消除变量，同时将这些操作应用于向量b，以获得一个系统max=mb，其中ma是上三角形。这种方法叫做高斯消元法。但是，该方法在所有情况下都需要一个额外的扭曲：可能需要排列行，如下面的示例所示：

x+y+z=1 x+y+3z=1

2x+5y+8z=1.

为了从第二行和第三行中减去X，我们从第二行中减去第一行，从第三行中减去第一行的两倍：

X+Y+Z=1

2Z=0 3Y+6Z=−1.

现在的问题是y不会出现在第二行；所以，我们不能通过在第三行中加上或减去第二行的倍数来消除y。补救办法很简单：排第二排和第三排！我们得到系统：

X+Y+Z=1

3Y+6Z=−1 2Z=0，

已经是三角形了。另一个需要排列的例子是：

Z=1−2X+7Y+2Z=1 4X−6Y=−1。

首先我们排列第一排和第二排，得到

-2X+7Y+2Z=1 Z=1

4x−6y=−1，

然后我们将第一行的两倍添加到第三行，得到：

-2X+7Y+2Z=1 Z=1

8Y+4Z=1.

我们再次排列第二排和第三排，得到

-2X+7Y+2Z=1

8Y+4Z=1 Z=1，

上三角形系统。当然，在这个例子中，z已经被解决了，我们可以先消除它，但是对于一般的方法，我们需要以一种系统的方式进行。

我们现在描述了应用于线性系统ax=b的高斯消元方法，其中a被假定为可逆的。我们使用变量k来跟踪消除的阶段。最初，k=1。

(1) 第一步是在a的第一列中选择一些非零项ai1。这样的项必须存在，因为a是可逆的（否则，a的第一列将是零向量，a的列将不是线性独立的）。同样地，我们会得到det（a）=0。这种单元的实际选择对该方法的数值稳定性有一定的影响，但稍后将对此进行研究。目前，我们假设做出了一些任意的选择。所选元素被称为消除步骤的支点，并表示为π1（因此，在第一步中，π1=ai1）。

(2) 接下来，我们将与第一行对应的轴排列行（i）。这样的一步叫做旋转。所以在这种排列之后，第一行的第一个元素是非零的。

(3) 现在，我们通过向这些行添加第一行的适当倍数，从除第一行之外的所有行中消除变量x1。更精确地说，我们将−ai1/π1乘以第一行，得到i=2，…，n的第i行。在这个步骤的末尾，第一列中的所有条目都是零，除了第一列。

(4) 将k增加1。如果k=n，停止。否则，k<n，然后在（n−k+1）×（n−k+1）子系统上重复步骤（1）、（2）、（3），通过从当前系统中删除第一个k−1行和k−1列获得。

如果我们让a1=a和）是K−1消除步骤（2≤k≤n）后得到的矩阵，则将kth消除步骤应用于形式的矩阵ak。

.

事实上，请注意

对于所有i，j，其中1≤i≤k−2和i≤j≤n，因为在（k−1）第（k−1）步之后，第一个k−1行保持不变。

稍后我们将证明det（ak）=？det（a）。因此，AK是可逆的。AK是可逆的事实，如果A是可逆的，也可以不用行列式来表示，因为存在一些可逆矩阵mk，这样AK=mk a，我们很快就会看到。

由于ak是可逆的，所以k≤i≤n的某些项是非零的。否则，ak的前k列中的最后n−k+1项将为零，而ak的前k列将在rk−1中生成k向量。但AK的前k列是线性相关的，AK不可逆，这是一个矛盾。这种情况由以下n=5和k=3的矩阵说明：

上述矩阵的前三列是线性相关的。

因此可以选择其中一个k≤i≤n的项作为轴，并将第k行与第i行进行排序，得到矩阵）。新的数据透视是，我们将K列中的条目i=k+1，…，n加上时间行k到行i，归零。在这个步骤的最后，我们得到了ak+1。观察AK的前k-1行与AK+1的前k-1行相同。

高斯消元过程如下图所示：

×××××××。

×××=0×××=0×。

 

×0×0×0×0×0×0×0 0×0

7.3基本矩阵和行操作

很容易知道什么样的矩阵执行高斯消去过程中使用的基本行操作。关键是，如果a=p b，其中a，b是m×n矩阵，p是维m的平方矩阵，如果（通常）我们用a1，…，am和b1，…，bm表示a和b的行，那么公式

给出a中的（i，j）th项表明a的第i行是b行的线性组合：

ai=pi1b1+·····+pimbm。

因此，左边的矩阵乘以一个正方形矩阵就可以执行行操作。类似地，右边的矩阵乘以一个正方形矩阵，就可以执行列操作。

第k行与第i行的置换是通过将左边的a乘以换位矩阵p（i，k）来实现的，换位矩阵p（i，k）是从单位矩阵中获得的矩阵。

7.3。初等矩阵与行运算

通过排列行i和k，即，

例如，如果m=3，

，

然后

.

观察Det（P（I，K））=1。此外，p（i，k）是对称的（p（i，k）>=p（i，k）），p（i，k）−1=p（i，k）。

在置换步骤（2）中，如果需要对第k行和第i行进行置换，则矩阵a在左边乘以矩阵pk，使pk=p（i，k），否则我们设置pk=i。

将β乘以第j行到第i行（i=6 j），将左边的a乘以初等矩阵，

ei，j；β=i+βeij，

哪里

= J

，即，

在左边，i>j，在右边，i<j。索引i是被乘法改变的行的索引。例如，如果m=3，我们想将第1行添加到第3行，因为β=2，j=1，i=3，我们形成

，

然后计算

2B11+B31 2B12+B32········2B1N+B3N

观察ei，j的倒数；β=i+βeij为ei，j；−β=i−βeij，且det（ei，j；β）=1。因此，在步骤3（消除步骤）中，矩阵A左乘形式为ei，k；βi，k，i>k的矩阵的乘积ek。

因此，我们看到

AK+1=EKPAK，

然后

AK=EK−1PK−1 E1P1A。

这证明了之前的声明，对于某些可逆矩阵mk，我们可以选择

mk=ek−1pk−1···e1p1，

可逆矩阵的乘积。

DET（p（i，k））=1和DET（ei，j；β）=1这一事实立即意味着上述事实：我们一直

Det（ak）=？Det（a）。

此外，因为

AK=EK−1PK−1···E1P1A

由于高斯消去停止k=n，矩阵

an=en−1pn−1····e2p2e1p1a

是上三角形。还要注意，如果m=en−1pn−1····e2p2e1p1，那么det（m）=±1，det（a）=±det（an）。

矩阵p（i，k）和ei，j；β称为初等矩阵。我们可以将上述讨论概括为以下定理：

定理7.1.（高斯消去）设a为n×n矩阵（可逆与否）。然后有一些可逆矩阵m，所以u=ma是上三角形。支点都是非零的，如果a是可逆的。

证据。我们已经证明了当a可逆时的定理，以及最后一个断言。现在a是奇异的，如果某个支点是零，比如在消去的阶段k。如果是的话，我们必须有；但是在这种情况下，ak+1=ak，我们可以选择pk=ek=i。

注：显然，矩阵m可以计算为

m=en−1pn−1···e2p2e1p1，

但这个表达是没有用的。事实上，我们需要的是m−1；当不需要排列时，结果表明m−1可以立即从矩阵Ek的逆矩阵中获得，并且不需要乘法。

注：不需要求可逆矩阵m，使m a为上三角形，我们可以求可逆矩阵m，使ma为对角矩阵。只需要简单地改变高斯消元。在每个阶段k，在找到轴并执行轴转动后，如有必要，除了将第k行的适当倍数添加到第k行以下的行中，以便使i=k+1，…，n的k列中的条目归零，还将第k行的适当倍数添加到第k行以上的行中。k为使i=1，…，k-1列中的条目归零。除i<k外，这些步骤还通过将左边的矩阵乘以初等矩阵ei，k；βi，k来实现，因此这些矩阵不是下三角矩阵。然而，在这个过程的最后，我们发现an=ma是一个对角矩阵。

这种方法称为高斯-乔丹因式分解。由于该方法比高斯消元法更昂贵，因此在实际应用中应用不多。然而，高斯-乔丹因式分解可用于计算矩阵A的逆矩阵。实际上，我们通过解系统ax（j）=ej（其中ej是rn的第j个标准基向量）找到了a−1的第j列。通过应用高斯-乔丹，我们得到了dj x（j）=mjej形式的系统，其中dj是一个对角矩阵，我们可以立即计算x（j）。

它还需要讨论支点的选择，以及保证在高斯消元过程中不需要排列的条件。我们首先说明了可逆矩阵具有Lu因子分解的必要和充分条件（即，高斯消元不需要旋转）。

7.4 LU因子分解

定义7.1.我们假设一个可逆矩阵A有一个Lu因式分解，如果它可以写成a=Lu，其中u是上三角可逆的，l是下三角的，其中l i i=1代表i=1，…，n。

网络错误
网络错误	网络错误 网络错误 网络错误 网络错误	网络错误	网络错误	网络错误 网络错误
		网络错误	网络错误	网络错误

对角项等于1的下三角矩阵称为单位下三角矩阵。给定一个n×n矩阵a=（a i j），对于1≤k≤n的任何k，让a（1:k，1:k）表示其项为aij的a的次矩阵，其中1≤i，j≤k。例如，如果a是5×5

提案7.2.设a为可逆n×n矩阵。那么A有一个Lu分解

a=lu如果每个矩阵a（1:k，1:k）对于k=1，…，n是可逆的。此外，当a有lu因子分解时，我们有

Det（A（1:K，1:K））=π1π2··································

其中πk是K-1消除步骤后获得的轴。因此，kth轴由

γ

如果k=1，则a11=det（a（1:1,1:1））。

如果k=2，…，n.

证据。首先假设a=lu是a的lu因子分解。

，

其中，l1、l4为单位下三角，u1、u4为上三角。（注：a（1:k，1:k）、l1和u1是k×k矩阵；a2和u2是k×（n-k）矩阵；a3和l3是（n-k）×k矩阵；a4、l4和u4是（n-k）×（n-k）矩阵。）

A（1:k，1:k）=l1u1，

由于u是可逆的，u1也是可逆的（u的行列式是u中对角线项的乘积，是u1和u4中对角线项的乘积）。因为l1是可逆的（因为它的对角线项等于1），我们看到a（1:k，1:k）对于k=1，…，n是可逆的。

相反，假设a（1:k，1:k）对于k=1，…，n是可逆的。我们只需要证明高斯消元不需要旋转。通过K上的归纳证明了第k步不需要转动。

因为a（1:1,1:1）=（a11），所以a11=06，所以k=1。假设前k-1步（2≤k≤n-1）不需要旋转。在这种情况下，我们有

Ek−1···E2e1a=AK，

其中，L=Ek−1····E2e1是单位下三角矩阵，而a k（1:k，1:k）是上三角矩阵，因此l a=ak可以写成

，

其中，l1为单位下三角，u1为上三角。（a（1:k，1:k）、l1和u1再次是k×k矩阵；a2和b2是k×n-k矩阵；a3和l3是（n-k）×k矩阵；a4、l4和b4是（n-k）×n-k矩阵。）但是，

l1a（1:k，1:k））=u1，

其中，l1是可逆的（事实上，det（l1）=1），由于假设a（1:k，1:k）是可逆的，所以u1也是可逆的，这意味着（u1）kk=06，因为u1是上三角形。因此，在步骤k中不需要旋转，建立感应步骤。由于det（l1）=1，我们也有det（u1）=det（l1 a（1:k，1:k））=det（l1）det（a（1:k，1:k））=det（a（1:k，1:k）），并且由于u1是上三角形，并且在其对角线上有轴π1，…，πk，我们得到

Det（A（1:K，1:K））=π1π2··································

如要求。

注：如果三角矩阵是可逆的，且其所有对角项都为非零，则可以避免在命题7.2证明的第一部分使用行列式。

推论7.3。（Lu因子分解）设a为可逆n×n矩阵。如果每一个矩阵a（1:k，1:k）对于k=1，…，n都是可逆的，那么高斯消元不需要旋转，得到一个Lu因式分解a=Lu。

证据。我们在命题7.2中证明了在这种情况下，高斯消元不需要旋转。然后，因为每个初等矩阵ei，k；β都是下三角形（因为我们总是把轴πk安排在它操作的行的上方），因为和eks是ei，k；βi，ks的乘积，从

en−1···e2e1a=u，

当u是上三角矩阵时，我们得到

A=lu，

其中是下三角矩阵。此外，由于每个ei，k；β的对角线条目为1，每个ek的对角线条目也为1。

例7.1。读者应该验证

是一个Lu因子分解。

矩阵A的Lu因式分解存在的一个主要原因是，如果我们需要解几个与同一矩阵A对应的线性系统ax=b，我们可以通过解两个三角形系统来实现这一点

Lw=b，Ux=w。

可逆矩阵A的Lu分解a=Lu存在一定的不对称性，实际上，L的对角项都是1，但对于U，这通常是错误的。这种不对称性可以按如下方式消除：如果

D=诊断（U11，U22，…，UNN）

是由u（支点）中的对角线项组成的对角线矩阵，那么我们假设

U0=D−1U，我们可以写

A=ldu0，

其中L为下三角，U0为上三角，L和U0的所有对角线条目均为1，D为支点的对角线矩阵。这样的分解导致以下定义。

定义7.2.我们假设一个可逆的n×n矩阵a如果可以写成a=l d u0，那么它有一个ldu因式分解，其中l是下三角的，u0是上三角的，l和u0的所有对角项都是1，d是对角矩阵。

我们将很快看到，如果a是实对称的，那么u0=l>。

稍后我们将看到，实对称正定矩阵满足命题7.2的条件。因此，对于含有实对称正定矩阵的线性系统，可以采用高斯消元法求解，而无需旋转。实际上，有可能做得更好：这是Cholsky分解。

如果一个平方可逆矩阵A有一个Lu因式分解，那么在进行高斯消元时，可以找到L和U。回想一下，在步骤k，我们选取了一个支点，该支点由矩阵k的第k列的索引j≥k的条目组成，我们交换了行i和k（如果需要）（旋转步骤），然后将索引j=k+1，…，n的条目归零，在k列中，我们得到了以下步骤：

零

×××

×××。

××××_

×××。

更准确地说，在排列K行和I行（旋转步骤）之后，如果K行下面的K列中的条目是αk+1K，…，αnk，那么我们将−αjk/πk乘以K行添加到J行；该过程如下所示：

②

所有

……__

A（NKK）

如果我们把j=k+1，…，n写成’jk=αjk/πk，…，n，l的第k列是

.

很容易看出（在定理7.5中证明了这一点），通过翻转“ij:

.

此外，如果高斯消元（无旋转）的结果是u=en−1····e1a，那么

1···························0

…

……………………………………………………………

   

0 1 0 0_

Ek=0·······································································

   

………………………………………………………………………………

γ

0·······································

所以Ek的kth列是l-1的kth列。

下面是一个例子说明了该方法。

例7.2。鉴于

，

−−

我们有以下步骤：第一个支点是第1行的π1=1，我们从第2、3和4行减去第1行。我们得到

.

下一个支点是第2行的π2=−2，我们从第4行减去第2行（并将第2行增加0倍到第3行）。我们得到

.

下一个支点是第3行的π3=−2，由于第3列中的第四个条目已经是零，所以我们将第3行的0倍添加到第4行。我们得到

.

程序完成了，我们已经

.

这确实很容易检查

现在我们演示如何扩展上述方法来有效地处理旋转。这是pa=lu因子分解。

7.5 pa=lu因子分解

下面的简单命题表明，原则上，a可以由一些置换矩阵p预乘，从而使pa可以在不使用任何支点的情况下转换为上三角形式。排列在第29.3节中有详细讨论，但目前我们只需要这个定义。关于置换概念（如第29.3节所述）与置换矩阵之间的精确联系，请参见问题7.16。

定义7.3.置换矩阵是一个方阵，每行每列只有一个1，其他地方都是零。

如29.3节所示，每个置换矩阵都是换位矩阵（p（i，k）s）的乘积，并且p与逆p>是可逆的。

提案7.4.设a为可逆n×n矩阵。有一些置换矩阵p，所以（pa）（1:k，1:k）对于k=1，…，n是可逆的。

证据。案例n=1是微不足道的，案例n=2也是如此（如果需要，我们交换行）。如果n≥3，我们通过归纳法进行。因为a是可逆的，所以它的列是线性独立的；特别是，它的第一个n-1列也是线性独立的。删除a的最后一列。由于其余n-1列是线性无关的，因此相应n×（n-1）矩阵中也有n-1个线性无关的行。因此，这些n行的排列使得由前n-1行组成的（n-1）×（n-1）矩阵是可逆的。但是有一个对应的置换矩阵p1，因此p1 a的前n-1行和列形成一个可逆矩阵a0。将诱导假设应用于（n-1）×（n-1）矩阵a0，我们发现存在一些置换矩阵p2（保持第n行不变），因此（p2p1a）（1:k，1:k）是可逆的，对于k=1，…，n-1。因为a在第一个位置是可逆的，p1和p2是可逆的，p1p2a也是可逆的，我们就这样做了。

注：我们也可以用Trefethen和Bau[171]提出的高斯消元步骤的巧妙重新排序来证明7.4号命题（第21课）。实际上，我们知道如果a是可逆的，那么就有置换矩阵π和初等矩阵的乘积。

嗯，所以

an=en−1pn−1····e2p2e1p1a，

其中u=an为上三角形。例如，当n=4时，我们有e3p3e2p2e1p1a=u。我们可以定义新的矩阵，这些矩阵仍然是初等矩阵的乘积，因此我们有

事实上，如果我们允许，而且，我们很容易证实

这是初等矩阵的乘积

.

也可以证明是下三角形（见定理7.5）。

一般来说，我们让

ek0=pn−1···pk+1ekpk−+11··pn−11，

我们有

en0−1···e10 pn−1···p1a=u，

其中每个都是一个下三角矩阵（见定理7.5）。

值得注意的是，如果在高斯消元过程中需要旋转步骤，那么对查找Lu因子分解的算法进行一次非常简单的修改就可以得到矩阵l、u和p，从而使p a=Lu。为了描述这个新方法，因为l的对角线项是1s，所以写起来很方便

L=I+∧。

然后，在对矩阵∧进行旋转高斯消元时，我们对∧（真∧k−1）行进行相同的换位，我们在涉及行k和行i的旋转步骤中对A（真的ak）行进行换位。我们也通过从单位矩阵开始对P进行组装。应用于p的行换位与我们应用于a和∧的行换位相同。下面是一个例子来说明这个方法。

例7.3。鉴于

，

我们有以下步骤序列：我们初始化∧=0和p0=i4。第一个支点是第1行的π1=1，我们从第2、3和4行减去第1行。我们得到

.

下一个支点是第3行的π2=−2，因此我们对第2行和第3行进行排列；我们还将此排列应用于∧和P：

.

接下来，我们从第4行减去第2行（并将第2行的0倍添加到第3行）。我们得到

.

下一个支点是第3行的π3=−2，由于第3列中的第四个条目已经是零，所以我们将第3行的0倍添加到第4行。我们得到

.

程序完成了，我们已经

.

这确实很容易检查

网络错误		网络错误 网络错误 网络错误 网络错误	网络错误 网络错误 网络错误 网络错误		网络错误 网络错误 网络错误	网络错误 网络错误 网络错误		网络错误 网络错误	网络错误 网络错误
		网络错误 网络错误 网络错误 网络错误	网络错误 网络错误 网络错误 网络错误	网络错误 网络错误 网络错误 网络错误	网络错误 网络错误 网络错误 网络错误	网络错误 网络错误 网络错误		网络错误 网络错误	网络错误 网络错误 网络错误	0 网络错误 1 网络错误 网络错误 网络错误

利用上述例子前面的注释中的思想，我们可以证明下面的定理，用高斯消元的一个简单的适配，证明了计算P、L和U的算法的正确性。

在标准文本中，我们不知道定理7.5的详细证明。尽管Golub和van Loan[80]将这个定理的一个版本表述为他们的定理3.1.4，但他们说“证明是一个混乱的订阅论点。”Meyer[122]还提供了证明的草图（见第3.10节的结尾）。鉴于这种情况，我们提供了一个完整的证据。它确实涉及许多下标和上标，但在我们看来，它包含了一些远远超出符号操作的技术。

定理7.5。对于每个可逆n×n矩阵a，以下保持：

(1) 有一些置换矩阵p，一些上三角矩阵u和一些单位下三角矩阵l，所以pa=lu（回忆一下，i=1，…，n时lii=1）。此外，如果p=i，那么l和u是唯一的，它们是由

无旋转的高斯消元。

(2) 如果en−1…e1a=u是高斯消去的结果，而没有旋转，那么照常写ak=ek−1…e1a（with），并让1≤k≤n−1和k+1≤i≤n。然后

，

其中，L的第k列是Ek−1的第k列，对于k=1，…，N−1。

(3) 写下如果en−a1pk n=−1e·······k−1ep1kp−11a············································

ejj=ej

ejk=pkejk−1pk，对于k=j+1，…，n−1，

和

.

然后，

ejk=pk pk−1···pj+1ejpj+1···pk−1pk u=enn−11··e1n−1pn−1···p1a，

如果我们设置

，

然后

PA=Lu.（†1）

此外，

，

其中ejk是形式的下三角矩阵

，

和

ej=pkejk−1，1≤j≤n−2，j+1≤k≤n−1，k

其中，对于某些i，p k=i或pk=p（k，i），例如k+1≤i≤n；如果pk=6i，这意味着这是通过排列j列中i和k行上的条目获得的。因为矩阵（ejk）−1都是下三角，矩阵l也是下三角。

为了找到l，定义形式的下三角n×n矩阵∧k

按如下迭代方式组装l的列：let

是Ek第k列的最后一个n−k元素，并通过设置感应地定义∧k

对于某些i>k，pk=i或pk=p（k，i）。这意味着在装配l时，需要对∧k-1的k行和i行进行排列，此时需要对ak的k行和i行进行旋转步骤排列。然后

i+∧k=（e1k）−1···（ekk）−1∧k=e1k+····+ekk，

对于k=1，…，n-1，因此

L=I+∧N−1。

定理7.5的证明是非常技术性的，在第7.6节中给出。

我们再次强调，定理7.5的第（3）部分显示了一个显著的事实，即在对矩阵L进行旋转高斯消元的同时，对算法的唯一更改是对∧k−1行进行相同的换位，我们在涉及行k和行i的旋转步骤。我们也可以通过从单位矩阵开始，并将我们应用于a和∧的相同行转置应用于p来组装p。下面是一个例子来说明这个方法。

例7.4。考虑矩阵

.

我们设置p0=i4，也可以设置∧0=0。第一步是使用轴4排列第1行和第2行。我们还将此排列应用于p0：

.

接下来，我们从第2行减去第1行的1/4倍，从第3行减去第1行的1/2倍，然后将第1行的3/4倍加到第4行，开始装配∧：

.

接下来，我们使用轴5排列第2行和第4行。我们还将此排列应用于∧和p：

.

接下来，我们将第2行的1/5倍增加到第3行，并更新∧02：

.

接下来，我们使用轴6排列第3行和第4行。我们还将此排列应用于∧和p：

.

最后，我们从第4行减去第3行的1/3倍，并更新∧03：

.

因此，加上∧3的恒等式，我们得到

.

我们检查一下

，

还有那个

注意，如果你愿意覆盖进化矩阵A的下三角部分，你可以在那里存储进化∧，因为这些条目最终将是零！也不需要显式地保存置换矩阵p。您可以将置换步骤记录在一个额外的列中（记录与应用于行的置换π对应的向量（π（1），…，π（n））。我们让读者写了这样一个大胆而有空间效率的版本的吕分解！

Remark: In Matlab the function lu returns the matrices P,L,U involved in the PA = LU factorization using the call [L,U,P] = lu(A).

As a corollary of Theorem 7.5(1), we can show the following result.

Proposition 7.6. If an invertible real symmetric matrix A has an LU-decomposition, then

A has a factorization of the form A = LDL>,

where L is a lower-triangular matrix whose diagonal entries are equal to 1, and where D consists of the pivots. Furthermore, such a decomposition is unique.

7.6. PROOF OF THEOREM 7.5 ~

Proof. If A has an LU-factorization, then it has an LDU factorization

A = LDU,

where L is lower-triangular, U is upper-triangular, and the diagonal entries of both L and U are equal to 1. Since A is symmetric, we have

LDU = A = A> = U>DL>,

with U> lower-triangular and DL> upper-triangular. By the uniqueness of LU-factorization (Part (1) of Theorem 7.5), we must have L = U> (and DU = DL>), thus U = L>, as claimed.

Remark: It can be shown that Gaussian elimination plus back-substitution requires n3/3+ O(n2) additions, n3/3 + O(n2) multiplications and n2/2 + O(n) divisions.

7.6 Proof of Theorem 7.5 ~

Proof. (1) The only part that has not been proven is the uniqueness part (when P = I). Assume that A is invertible and that A = L1U1 = L2U2, with L1,L2 unit lower-triangular and U1,U2 upper-triangular. Then we have

L−2 1L1 = U2U1−1.

However, it is obvious that L−2 1 is lower-triangular and that U1−1 is upper-triangular, and so L−2 1L1 is lower-triangular and U2U1−1 is upper-triangular. Since the diagonal entries of L1 and L2 are 1, the above equality is only possible if U2U1−1 = I, that is, U1 = U2, and so L1 = L2.

(2) When P = I, we have , where Ek is the product of n − k elementary matrices of the form Ei,k;−`i, where Ei,k;−`i subtracts `i times row k from row i,

with 1, and k + 1 ≤ i ≤ n. Then it is immediately verified that

还有那个

如果我们把LK定义为

网络错误	网络错误 网络错误 网络错误 网络错误

Lk=Lk−1ek−1，2≤k≤n−1，

因为右边乘以Ek−1会将‘i乘以第i列添加到第k列（矩阵Lk−1的），i>k，而Lk−1的第i列只有非零项1作为其第i个元素。

自从

Lk=e1−1···ek−1，1≤k≤n−1，

我们得出结论，L=ln−1，证明了我们关于L形状的主张。

（3）

第1步。证明（†1）。

首先，我们通过对k的归纳来证明

.

对于k=1，我们有，因为，所以我们的断言无关紧要。

如果k≥2，

AK+1=EKPAK，

根据归纳假设，

7.6。定理7.5的证明~

因为pk是标识或换位，pk2=i，所以通过插入

pkpk如下所示，我们可以写

AK+1=EKPAK

=EKPEKK−11···E2K−1E1K−1PK−1···P1A

=ek pkekk−11（pk pk）···（pkpk）e2k−1（pkpk）e1k−1（pkpk）pk−1···p1a=ek（pkkk−11pk）··（pke2k−1pk）（pke1k−1pk）pkpk−1···p1a。

所以我们建立了归纳假设。对于k=n-2，我们得到

如权利要求所述，因数分解pa=lu

P=PN−1···P1

L=（E1n−1）−1····（ENN−11）−1

很清楚。

第2步。证明矩阵（EJK）−1是下三角形。为了实现这一点，我们证明了矩阵ejk是一个非常特殊形式的严格下三角矩阵。

因为对于j=1，…，n-2，我们有ejj=ej，

ejk=pkejk−1pk，k=j+1，…，n−1，

由于pk−1=pk，我们得到（ej j）−1=ej−1，对于j=1，…，n−1，对于j=1，…，n−2，我们得到

.

自从

p k=p（k，i）是一个换位，或者pk=i，所以pk2=i，我们得到

（ejk）−1=pk（ejk−1）−1pk=pk（i+ejk−1）pk=pk2+pk ejk−1 pk=i+pk ejk−1 pk。

因此，我们有

（ejk）−1=i+pk ejk−1 pk，1≤j≤n−2，j+1≤k≤n−1。

我们证明了对于j=1，…，n-1，对于k=j，…，n-1，每个都是下三角矩阵，并且

，

对于某些i，p k=i或pk=p（k，i），使得k+1≤i≤n。

对于每个j（1≤j≤n-1），我们通过诱导k=j，…，n-1继续。因为（ejj）−1=ej−1，并且因为ej−1是上述形式，所以基本情况成立。

对于诱导步骤，我们只需要考虑p k=p（k，i）是换位的情况，因为pk=i的情况是微不足道的。我们得弄清楚）是什么。然而，自从

因为k+1≤i≤n和j≤k−1，右边的ejk−1乘以p（k，i）将排列列i和k，它们是零列，所以

，

因此，

.

但是自从

（ejk）−1=i+ejk，

我们推断ej=p（k，i）ejk−1。钾

7.6。定理7.5的证明~

我们还知道，将左边的ejk−1乘以p（k，i）将排列行i和k，这表明ejk具有所需的形式，如所述。因为所有EJK都是严格的下三角形

（ejk）−1=i+ejk为下三角形，因此产品

也是下三角形。

第3步。将L表示为L=I+∧n−1，带∧。

从第（3）部分的步骤1，我们知道

.

我们通过对k的归纳证明

对于k=1，…，n-1。

如果k=1，我们有和

因为（，我们发现我们得到∧，基本步骤成立。

自（与

并且Eikejk=0，如果i<j，如第（2）部分所述，对于涉及Lk的乘积的计算，我们得到

（三）

同样，如果i≥k+1且j≤k−1且自

（ejk）−1=i+pkejk−1，1≤j≤n−2，j+1≤k≤n−1，

我们得到

.（）

通过归纳假设，

，

从（），我们得到

.

使用（），我们推断

.

因为ekk=ek，我们得到

.

但是，根据定义

i+∧k=（i+pk∧k−1）ek−1，

这证明了

，（？）

并完成了验证该公式的诱导步骤。

如果我们用k+1代替k再次应用方程（），我们就得到

，

与（†）一起，我们获得，

，

同时完成了该公式的验证的诱导步骤。对于k=n−1 in（†），我们得到所需方程：l=i+∧n−1。

7.7。处理迂回错误；旋转策略

7.7处理迂回错误；关键策略

现在让我们简单地评论一下轴的选择。虽然理论上可以选择任何轴，但舍入误差的可能性意味着选择非常小的轴不是一个好主意。下面的例子说明了这一点。考虑线性系统

10−4x+y=1 x+y=2。

因为10-4是非零的，它可以作为支点，我们得到

10−4X+Y=1

（1−104）Y=2−104。

因此，确切的解决方案是

.

−−

但是，如果四舍五入发生在第四个数字上，则104−1=9999和104−2=9998都将四舍五入到9990，然后解为x=0和y=1，与x≈1和y≈1的精确解相差甚远。问题是我们选了一个非常小的支点。如果我们对方程进行排列，支点是1，在消去之后，我们得到系统。

X+Y=2

（1−10−4）Y=1−2×10−4。

这一次，1−10−4=0.9999和1−2×10−4=0.9998四舍五入为0.999，溶液为x=1，y=1，更接近精确的溶液。

为了解决这个问题，我们可以使用部分旋转策略。这包括在步骤k（1≤k≤n-1）中选择一个条目，以便

.

通过最大化支点的值，我们避免被不希望的小支点分割。注：矩阵a被称为严格的列对角占优iff

，对于j=1，…，n

（响应严格行对角占优iff

，对于i=1，…，n.）

例如，第7.1节中讨论的曲线插值问题的矩阵是严格对角占优的列（和行）。

很长一段时间以来（1900年以前，比如阿达玛），人们都知道，如果矩阵A严格地是列对角占优的（resp）。严格的对角占优行），那么它是可逆的。也可以证明，如果a严格地是对角占优的列，那么

部分旋转的高斯消元实际上不需要旋转（见问题7.12）。

另一种称为完全旋转的策略是选择某个条目，其中k≤i，j≤n，这样

.

然而，在这种方法中，如果所选的轴不在K列中，也需要排列列。这是通过在右边乘以置换矩阵来实现的。然而，在实践中，完全旋转往往过于昂贵，而部分旋转是选择的方法。

LU分解特别有效的一个特殊情况是三对角矩阵的情况，我们现在考虑。

7.8三对角矩阵的高斯消去

考虑三对角矩阵

γ

B1

α2

γ

 

A=

γ

γ

γ

γ

γ

定义序列

δ0=1，δ1=b1，

网络错误 网络错误 网络错误	网络错误 网络错误 网络错误	网络错误 网络错误 网络错误		网络错误 网络错误 网络错误 网络错误 网络错误 网络错误 网络错误 网络错误 网络错误 网络错误

δk=bkδk−1−akck−1δk−2，2≤k≤n。

7.8。三对角矩阵的高斯消元

提案7.7.如果a是上面的三对角矩阵，那么k=1，…，n的δk=det（a（1:k，1:k））。

证据。通过将DET（a（1:k，1:k））扩展到其最后一行，该命题随后是对k的归纳。

定理7.8。如果a是上面的三对角矩阵，k=1，…，n的δk=06，则a具有以下Lu因子分解：

.

证据。由于δk=det（a（1:k，1:k））=06，对于k=1，…，n，根据定理7.5（和命题7.2），我们知道a有一个唯一的Lu因式分解。因此，只需检查提议的因子分解是否有效即可。我们很容易查到

因为δk=bkδk−1−akck−1δk−2。

因此，有一个简单的方法来求解线性系统ax=d，其中a是三对角的（而δk=06，k=1，…，n）。为此，可以方便地“挤压”定义的对角矩阵∆使∆k k=δk/δk−1进入因式分解，以便a=（l∆）（∆−1u），并且如果我们允许

，

A=（L∆）（∆−1U）写为

γ

γ

γ

γ

γ

γ

γ

γ

γ

….__

γ

γ

1锌-2__

γ

1锌-1__

γ

一

因此，系统ax=d可以通过构造三个序列来解决：第一，序列

，

−−

对应于递推δk=bkδk−1−akck−1δk−2，通过将该方程的两边除以δk−1得到，下一步

−−

对应于求解系统L∆w=d，最后

xn=wn，xk=wk−zkxk+1，k=n−1，n−2，…，1，

对应于求解系统∆−1ux=w。

备注：可以验证，这需要3（n-1）次加法、3（n-1）次乘法和2n次除法，总共需要8n-6次运算，这比高斯消元所需的O（2n 3/3）要少得多。

我们现在考虑对称正定矩阵（SPD矩阵）的特殊情况。

7.9 SPD矩阵和Cholesky分解

回想n×n实对称矩阵a是正定iff

x>ax>0，所有x∈rn，x=06。

等价地，A是对称正定的，如果它的所有特征值都是严格正的。关于对称正定矩阵A的下列事实很容易建立（有些留作练习）：

(1) 矩阵A是可逆的。（实际上，如果ax=0，那么x>ax=0，这意味着x=0。）

(2) 对于i=1，…，n，我们有aii>0（只要观察x=ei，rn的第i个标准基向量，我们有

(3) 对于每一个n×n实可逆矩阵z，矩阵z>az是实对称正定的，如果a是实对称正定的。

(4) n×n实对称正定矩阵的集合是凸的。这意味着，如果a和b是两个n×n对称正定矩阵，那么对于任何一个λ∈r，当0≤λ≤1时，矩阵（1−λ）a+λb也是对称正定的。很明显，因为A和B是对称的，（1-λ）A+λB也是对称的。对于任何非零x∈rn，我们有x>ax>0和x>bx>0，所以

x>（（1−λ）a+λb）x=（1−λ）x>ax+λx>bx>0，

因为0≤λ≤1，所以1−λ≥0且λ≥0，且1−λ和λ不能同时为零。

(5) n×n实对称正定矩阵的集合是一个圆锥体。这意味着，如果a是对称正定，如果λ>0是任何实数，则λa是对称正定。显然，λa是对称的，对于非零x∈rn，我们有x>ax>0，由于λ>0，我们有x>λax=λx>ax>0。

注：对于复杂的m×n矩阵a，我们将矩阵a定义为m×n矩阵。

A=（艾杰）。然后我们定义a为n×m矩阵a=（a）>=（a>）。如果a=a，n×n复矩阵a是厄米提安矩阵。这是实对称矩阵概念的复杂模拟。厄米矩阵A是正定的如果

z az>0表示所有z∈cn，z=06。

很容易证明厄米正定矩阵的性质（1）-（5）成立；用替换>。

当2×2实对称矩阵A为正定时，它的性质具有指导意义。

写

然后我们有了

.

如果上面的表达式对于所有非零向量都是严格正的，那么对于x=1，y=0我们得到a>0，对于x=0，y=1我们得到b>0。然后我们可以写

.（？）

由于a>0，如果ab−c2≤0，那么我们可以选择y>0，使第二个项为负或零，我们可以设置x=−（c/a）y使第一个项为零，在这种情况下，ax2+2xy+by2≤0，因此我们必须使ab−c2>0。

相反，如果a>0，b>0且ab>c2，则对于任意（x，y）=（06，0），如果y=0，则x=06，且（†）的第一项为正，如果y=06，则（†）的第二项为正。因此，对称矩阵a是正定iff

A>0，B>0，AB>C2.（）

注意ab−c2=det（a），所以第三个条件表示det（a）>0。

观察条件b>0是多余的，因为如果a>0和ab>c2，那么我们必须得到b>0（同样b>0和ab>c2意味着a>0）。

我们可以通过把（a，b，c）看作是x，y，z轴上的坐标，来可视化r3中2×2实对称正定矩阵的空间。由（）中的严格不等式确定的轨迹对应于方程x y=z2圆锥体边上不包含原点且x>0和y>0的区域。当z=δ固定时，方程xy=δ2定义了平面z=δ中的双曲线。方程xy=z2的圆锥体由穿过原点的直线组成，这些直线与平面z=1中的双曲xy=1相接触。我们只考虑这条双曲线的分支，对于它x>0和y>0。见图7.6。

不难证明实对称正定矩阵的逆矩阵也是实对称正定矩阵，但两个实对称正定矩阵的乘积可能不是对称正定矩阵，如下例所示：

.

根据上述准则，左边的两个矩阵是实对称正定的，而右边的矩阵不是均匀对称的，并且

，

即使它的特征值是实的和正的。

接下来，我们证明了实对称正定矩阵具有形式a=b b>的特殊Lu因式分解，其中b是对角元素严格为正的下三角矩阵。这就是乔尔斯基因式分解。

首先，我们注意到一个对称正定矩阵满足命题7.2的条件。

提案7.9.如果a是实对称正定矩阵，那么a（1:k，1:k）是对称正定的，因此k=1，…，n是可逆的。

图7.6:r3中表面xy=z2的两个视图。曲面与一个常数z平面的交集产生一条双曲线。与2×2对称正定矩阵相关联的区域位于绿色边的“前面”。

证据。因为a是对称的，所以每个a（1:k，1:k）也是对称的。当W＝Rk，当1个k k为n时，x＝rn为i＝1，…，k，Xi＝0的向量i＝k+1，…，n，因为a是对称正定的，x＝ax＞0，x＝06，x＝06。这尤其适用于从非零向量w∈Rk（如前所定义）获得的所有向量x，并且清楚

x>ax=w>a（1:k，1:k）w，

这意味着a（1:k，1:k）是正定的。因此，根据上面的事实1，a（1:k，1:k）也是可逆的。

命题7.9也适用于复厄米特正定矩阵。命题

7.9可以加强如下：实对称（或复厄米特）矩阵a是正定的iff det（a（1:k，1:k））>0，对于k=1，…，n。

上述事实被称为西尔维斯特准则。我们将在建立Cholsky因子分解之后证明它。

设a为n×n实对称正定矩阵并写出

，

其中c是（n-1）×（n-1）对称矩阵，w是（n√-1）×1矩阵。因为a是对称正定的，a11>0，我们可以计算α=a11。诀窍是我们可以将

，

-

也就是说，作为a=b1a1b1>，其中b1是带有正对角线入口的下三角形。因此，b1是可逆的，根据上面的事实（3），a1也是对称正定的。

备注：矩阵c−ww>/a11被称为矩阵（a11）的schur补码。

定理7.10。（乔尔斯基因式分解）设A为实对称正定矩阵。然后有一些真正的下三角矩阵b，所以a=bb>。此外，可以选择B，使其对角线元素严格为正，在这种情况下，B是唯一的。

证据。我们通过对a的维数n的归纳来进行，对于n=1，我们必须有a11>0，如果我们让α=√a11和b=（α），这个定理就很简单了。如前所述，如果n≥2，我们必须使a11>0，我们可以写

，

-

式中α=√a11，矩阵b1可逆，且

-

是对称正定的。然而，这意味着c−ww>/a11也是对称正定的（考虑x>a1x对于x=06和x1=0的每x∈rn）。因此，我们可以将归纳假设应用于c−ww>/a11（这是一个（n−1）×（n−1）矩阵），我们找到一个唯一的下三角矩阵l，其中有正对角项，因此

C−WW>/A11=ll>。

但是我们得到

因此，如果我们

，

我们有一个唯一的下三角矩阵，有正的对角项和a=bb>。

备注：利用一个Lu分解的唯一性，也可以建立Cholesky分解的唯一性。实际上，如果b1和b2是下三角带正对角项，如果我们让∆1（resp.∆2）是由b1的对角线项组成的对角线矩阵。b2）因此（∆k）ii=（bk）ii，对于k=1,2，我们有两个lu分解

对于b1∆−1 1，b2∆−2，1个单位下三角和∆上三角。通过Lu因式分解的唯一性（定理7.5（1）），我们得到

，

第二个方程得出

b1∆1=b2∆2.（）

b1∆1的对角线入口为（b1）2ii，同样地，b2∆2的对角线入口为（b2）2ii，因此上述方程表明：

（b1）2II=（b2）2II，I=1，…，N.

既然b1和b2的对角线入口都是正的，我们必须

（b1）i i=（b2）ii，i=1，…，n；

也就是说，∆1=∆2，由于两者都是可逆的，我们从（）得出结论，b1=b2。

定理7.10也适用于复厄米特正定矩阵。在这种情况下，对于一些具有正对角项的唯一下三角矩阵b，我们有a=bb。

定理7.10的证明立即产生了一种算法，通过求解下三角矩阵b，从a计算b，使a=bb>（其中a和b都是实矩阵）。对于j=1，…，n，

J−1！1/2

bj j=aj j−xb2j k，

K＝1

对于i=j+1，…，n（和j=1，…，n-1）

J−1！

X

bij=aij bikbj k/bj j j.

K＝1

网络错误
网络错误 网络错误	网络错误			网络错误 网络错误
		网络错误 网络错误	网络错误		网络错误
网络错误

上面的公式用于从上到下计算b的jth列，使用之前计算的b的第一个j-1列和矩阵a。在n=3的情况下，a=bb>

B11B31 B21B31+B22B32 B231+B232+B233

我们对a的第一列进行分析，比较条目，并发现

A11=B211 A21=B11B21 A31=B11B31

接下来，我们使用之前计算的B21和B31表达式对A的第二列进行计算，以发现

A22=B221+B222

A32=B21B31+B22B32。

最后，我们使用A的第三列和以前为B31和B32计算的表达式确定B33为

.

例如，如果

我们发现了

我们把它作为一个练习来寻找相似的公式（包括共轭），将一个复厄米正定矩阵A作为a=bb因子。下面的matlab程序实现了cholesky分解。

函数b=cholesky（a）n=大小（a，1）；b=零（n，n）；对于j=1:n-1；如果j=1

b（1,1）=sqrt（a（1,1））；对于i=2:n

b（i，1）=a（i，1）/b（1，1）；结束

其他的

b（j，j）=sqrt（a（j，j）-b（j，1:j-1）*b（j，1:j-1）’；对于i=j+1:n

b（i，j）=（a（i，j）-b（i，1:j-1）*b（j，1:j-1）’/b（j，j）；结束

结束

结束

b（n，n）=sqrt（a（n，n）-b（n，1:n-1）*b（n，1:n-1）’；结束

如果我们在下面的矩阵上运行上述算法

Cholesky因式分解可用于求解线性系统a x=b，其中a为对称正定：求解两个系统b w=b和b>x=w。

注：可以看出，该方法需要n3/6+o（n2）加法、n3/6+o（n2）乘法、n2/2+o（n）除法和o（n）平方根提取法。因此，Cholesky方法需要高斯消去所需操作数量的一半（因为高斯消去需要n3/3+o（n2）加法、n3/3+o（n2）乘法和n2/2+o（n）除法）。它还需要一半的空间（只需要B，而不是L和U）。此外，可以证明，Cholesky的方法在数值上是稳定的（见Trefetten和Bau[171]，第23讲）。在matlab中，chol函数返回下三角矩阵b，这样a=bb>使用调用b=chol（a，“lower”）。

注：如果a=b b>，其中b为任意可逆矩阵，则a为对称正定。

证据。显然，b b>是对称的，由于b是可逆的，b>是可逆的，并且

x>ax=x>b b>x=（b>x）>b>x，

很明显，如果x=0.6，x>ax>0

我们现在给出了对称矩阵正定的三个条件。

提案7.11.设a为任意n×n实对称矩阵。以下条件等效：

(a) A是正定的。

(b) a的所有主要未成年人都是正的；即：Det（a（1:k，1:k））>0，对于k=1，…，n

（西尔维斯特标准）。

(c) a有一个lu因子分解，所有的支点都是正的。

(d) a有一个ldl>因子分解，d中的所有支点都是正的。

证据。根据命题7.9，如果a是对称正定的，那么每个矩阵a（1:k，1:k）对于k=1，…，n是对称正定的。

k）=q>q，对于某些可逆矩阵q，那么det（a（1:k，1:k））=det（q）2>0。这表明（a）意味着（b）。

如果k=1，…，n的det（a（1:k，1:k））>0，则每个a（1:k，1:k）都是可逆的。通过

命题7.2，矩阵A有一个Lu因式分解，由于支点πk由

γ

如果k=1，则a11=det（a（1:1,1:1））。

如果k=2，…，n，

我们看到πk>0，对于k=1，…，n。因此（b）意味着（c）。

假设A有一个LU因子分解，并且所有的支点都是正的。由于a是对称的，这意味着a具有形式的因式分解

A=低密度脂蛋白>，

l下三角，1在对角线上，其中d是对角线上有正项的对角线矩阵（支点）。这表明（c）意味着（d）。

如果我们形成了对角矩阵，那么在因子分解a=ldl>中，所有的支点都是d正的。

√d=diag（√π1，…，√πn）

γ

如果我们让b=l d，那么我们有

A=bb>，

与B下三角和可逆。根据命题7.11之前的评论，a是肯定的。因此，（d）表示（a）。

准则（c）给出了一个简单的计算测试来检查对称矩阵是否是正定的。对称矩阵是正定的还有一个准则：它的特征值必须是正的。我们必须学习对称矩阵的谱定理来建立这个准则。

命题7.11也适用于复厄米特正定矩阵，在（d）中，因子分解ldl>被ldl替换。

关于高斯消去、Lu因子分解和Cholesky因子分解的稳定性分析和有效实现方法，请参见demmel[49]、Trefethen和Bau[171]、Ciarlet[41]、Golub和van Loan[80]、Meyer[122]、Strang[164、165]和Kincaid和Cheney[100]。

7.10缩减行梯队形式（RREF）

第7.2节所述的高斯消元也可应用于矩形矩阵。对于任何矩形m×n矩阵a，这产生了一种确定系统ax=b是否可解的方法和系统可解时所有解的描述。

结果表明，如果我们把所有的支点都重定为1，讨论就简单了，为此我们需要第三类初等矩阵。对于任何λ=06，设ei，λ为n×n对角矩阵

1_

…

 

1_

 

ei，λ=λ，

 

1_

 

…γ

一

（ei，λ）i i=λ（1≤i≤n）。注意，ei，λ也由下式给出

ei，λ=i+（λ−1）eii，

并且，ei，λ与

ei，λ−1=ei，λ−1.

现在，在K-1消除步骤之后，如果底部

在当前矩阵的第k列中，ak是非零的，因此可以选择一个轴πk，在必要的行排列之后，我们还将行k除以πk以获得轴1，并且不仅使K列中的所有条目i=k+1，…，m归零，而且还使所有条目i=1，…，k−1，so t归零。k列中唯一的非零项是k行中的1。这些行操作是通过将左边的元素矩阵相乘来实现的。

如果=0，则转到K+1列。

当第k列包含一个轴时，将矩阵转换为rref的过程的第k阶段包括以下三个步骤：

0 0 0 0 0××××_

（k）

0 0 0 aik××0 0××_

0 0 0××0 0 0××0

	网络错误	网络错误 网络错误	网络错误 网络错误		网络错误	网络错误 网络错误	网络错误 网络错误	网络错误 网络错误	网络错误 网络错误

0 0×1×x x x x x x x x x x_elim⇒0 0 1×x

0 0=0 0 0××。

××××××××_

0 0 0 0 0 0 0

0 0×0×0 0×0×0

如果第k列不包含轴，我们只需继续下一列。

结果是，在执行这些消除步骤之后，我们得到了一个特殊形状的矩阵，简称为缩减行梯队矩阵，简称为RREF。

下面是一个例子说明这个过程：从矩阵开始

，

我们执行以下步骤

，

从第2行和第3行中减去第1行；

，

选择轴2和排列第2行和第3行后，将第2行除以2，从第3行减去第2行；

，

第3行除以−1/2后，第1行减去第3行，第2行减去（3/2）×第3行。

很明显，列1、2和4是线性独立的，列3是列1和列2的线性组合，列5是列的线性组合。

1,2，4。

一般来说，导致缩减梯队矩阵的步骤序列不是唯一的。例如，我们可以选择1而不是2作为矩阵A2中的第二个轴。然而，从任何给定矩阵中获得的简化行梯队矩阵是唯一的；也就是说，它不依赖于在简化过程中遵循的步骤序列。这一事实不容易严格证明，但我们稍后会证明。

如果我们想解形式为ax=b的线性方程组，我们将初等行运算同时应用于矩阵a和右侧b。为了方便起见，我们形成了增广矩阵（a，b），即将b作为额外列添加到矩阵中得到的m×n+1矩阵。A.例如，如果

而且，

那么增广矩阵是

.

现在对于任何矩阵m，因为

M（A，B）=（MA，MB）

对（a，b）执行基本行操作等同于同时对a和b执行操作。例如，考虑系统

它的增广矩阵是矩阵

如上所述，因此应用于该矩阵的还原步骤生成系统

x1+2x3=2 x2+3x3=−1 x4=3。

这个简化后的系统与原系统具有相同的解集，显然x3可以任意选择。因此，我们的系统有无穷多的解

x1=2−2x3，x2=−1−3x3，x4=3，

其中，x3是任意的。

下面的命题表明系统ax=b的解集是由任何行操作序列保留的。

提案7.12。给定任意m×n矩阵a和任意向量b∈rm，对于任意初等行操作序列e1，…，ek，如果p=ek···e1和（a0，b0）=p（a，b），则ax=b的解与a0x=b0的解相同。

证据。因为每个基本行操作ei都是可逆的，所以p也是可逆的，并且（a0，b0）=p（a，b），那么a0=pa和b0=pb。如果x是原始系统ax=b的解，那么两边乘以p，我们得到pax=pb；也就是说，a0x=b0，那么x是新系统的解。相反，假设x是新系统的解，即a0x=b0。

因为a0=pa，b0=pb，p是可逆的，我们得到

ax=p−1a0x=p−1b0=b，

所以x是原始系统的解ax=b。

另一个重要事实是：

提案7.13。给定m×n矩阵a，对于任何行操作序列e1，…，ek，如果p=ek···e1和b=pa，则a行和b行所跨越的子空间是相同的。因此，A和B具有相同的行排名。此外，矩阵A和B也具有相同的（列）秩。

证据。由于b=p a，从先前的观察来看，b的行是a行的线性组合，因此b的行跨度是a行跨度的子空间。由于p是可逆的，a=p−1b，因此通过相同的推理，a的行跨度是a行跨度的子空间。因此，A行和B行所跨越的子空间是相同的，这意味着A和B具有相同的行秩。

命题7.12意味着系统ax=0和bx=0具有相同的解。由于ax是a列的线性组合，bx是b列的线性组合，a中的最大线性独立列数等于b中的最大线性独立列数，即a和b具有相同的秩。

备注：A列和B列所跨越的子空间可以不同！但是，它们的尺寸必须相同。

我们将在第7.14节中说明行等级等于列等级。这也将在10.13号提案中得到证明，现在让我们精确地定义什么是缩减的行梯队矩阵。

定义7.4.M×N矩阵A是一个简化的行梯队矩阵，如果满足以下条件：

(a) 每行的第一个非零条目是1。此条目称为透视。

(b) 第i+1行的第一个非零条目位于第一行的第一个非零条目的右侧。

(c) 透视图上方的条目为零。

如果一个矩阵满足上述条件，我们也可以说它是缩减行梯队形式，简称为rref。

请注意，条件（b）意味着透视下的条目也是零。例如，矩阵

是缩减的行梯队矩阵。一般而言，RREF中的矩阵具有以下形状：

如果最后一行包含数据透视。

下面的命题表明，使用行操作可以将每个矩阵转换为缩减的行梯队形式。

提案7.14.对于任何m×n矩阵a，都有一个行操作序列e1，…，ek，如果p=ek···e1，那么u=pa是一个缩减的行梯队矩阵。

证据。我们在m上进行归纳。如果m=1，那么这一行中的所有项都是零，因此a=0，或者如果a j是a中的第一个非零项，则让p=（a−j 1）（1×1矩阵）；显然，pa是一个缩减的行梯队矩阵。

现在假设m≥2。如果a=0，我们就这样做了，所以假设a=0.6，因为a=06，有一个最左边的列j是非零的，所以在jth列中选择任何轴π=aij，排列行i和行1，如果需要，将新的第一行乘以π−1，然后通过减去sui清除列j中的其他条目。表1行的倍数。在这个过程的最后，我们有一个矩阵a1，它的形状如下：

，

式中表示任意标量，或更简洁地说

，

7.11。RREF，自由变量，齐次系统

其中d是A（m-1）×N-J矩阵（b是1 J矩阵）。如果j=n，我们就完了。

否则，根据应用于的归纳假设，有一个行操作序列将d转换为缩减的行梯队矩阵r0，并且这些行操作不会影响a1的第一行，这意味着a1被缩减为该形式的矩阵。

.

由于r0是一个约化行梯队矩阵，因此矩阵r满足约化行梯队形式的条件（a）和（b）。最后，通过减去包含一个轴的R0行的适当倍数，可以清除R0中所有轴上的条目。得到的矩阵也满足条件（c），诱导步骤完成。

备注：有一个名为rref的matlab函数，可以将任何矩阵转换为其缩减的行梯队形式。

如果a是任意矩阵，如果r是a的缩减行梯队形式，则命题7.13的第二部分可以稍微尖锐一点，因为缩减行梯队矩阵的结构清楚地表明其秩等于支点数。

提案7.15。矩阵a的秩等于其rref r中的支点数。

7.11 RREF、自由变量和齐次线性系统

对于形式为ax=b的系统，我们可以将约简过程应用于增广矩阵（a，b），以获得约简行梯队矩阵（a0，b0），这样系统a0x=b0具有与原始系统ax=b相同的解。约简系统a0x=b0的优点是存在一个si通过简单的测试，检查该系统是否可解，如果可解，则找出其解。

实际上，如果矩阵a0的任何一行为零，并且b0中的相应条目为非零，那么它是一个轴，我们得到了“方程”

0＝1，

这意味着系统a0x=b0没有解决方案。另一方面，如果b0中没有轴，那么对于b0 i=06的每一行i，a0中都有一列j，其中第一行的条目是1（轴）。因此，如果列k不包含轴，我们可以将任意值赋给变量xk，然后求解轴变量。例如，如果我们考虑减少的行梯队矩阵

，

由于第三个方程是0=1，所以没有解a0x=b0。另一方面，简化系统

有解决方案。我们可以任意选取非Pivot列对应的变量x2、x4，然后求解x3（使用第二个方程）和x1（使用第一个方程）。

上述推理证明了以下定理：

定理7.16。如果任何系统ax=b，其中a是m×n矩阵，如果增广矩阵（a，b）是缩减的行梯队矩阵，那么系统ax=b有一个解，如果b中没有轴。在这种情况下，如果列j不包含轴，可以将任意值赋给变量xj。

定义7.5.非透视变量通常称为自由变量。

把命题7.14和定理7.16放在一起，我们得到了一个判定系统ax=b是否有解的标准：将增广系统（a，b）转换成一个行缩减梯队矩阵（a0，b0），并检查b0是否没有支点。

备注：在编写实现行约简的程序时，当到达矩阵A的最后一列时，我们可能会停止。在这种情况下，系统ax=b是否可解的测试是行约简矩阵a0没有索引i>r的零行，这样b0i=06（其中r是支点数，b0是行约简的右侧）。

如果我们有一个齐次系统a x=0，这意味着b=0，当然x=0总是一个解，但是定理7.16意味着如果系统ax=0比方程有更多的变量，那么它有一些非零解（我们称之为非平凡解）。

提案7.17。给定任意一个齐次系统a x=0的m方程在n个变量中，如果m<n，则存在一个非零向量x∈rn，这样ax=0。

证据。将矩阵A转换为缩减的行梯队矩阵a0。我们知道ax=0 iff a0x=0。如果r是a0的支点数，我们必须有r≤m，因此根据定理7.16，我们可以将任意值赋给n-r>0非支点变量，得到非平凡解。

定理7.16也可用于描述平方矩阵可逆的情况。首先，请注意以下简单但重要的事实：

如果一个正方形的n×n矩阵a是一个行约化的梯队矩阵，那么a是一个单位，或者a的底行是零。

提案7.18。设a为尺寸n的平方矩阵。以下条件等效：

7.11。RREF，自由变量，齐次系统

(a) 矩阵A可以通过一系列基本的行操作降为单位。

(b) 矩阵A是初等矩阵的乘积。

(c) 矩阵A是可逆的。

(d) 齐次方程组ax=0只有平凡解x=0。

证据。首先，我们证明（a）意味着（b）。如果（a）可以通过一系列行操作e1，…，ep简化为标识，这意味着ep···e1a=i。由于每个ei都是可逆的，我们得到

A=e1−1···ep−1，

其中，每个ei-1也是基本行操作，因此（b）保持不变。现在，如果（b）成立，因为基本行操作是可逆的，那么a是可逆的，（c）成立。如果a是可逆的，我们已经观察到齐次系统a x=0只有平凡解x=0，因为从ax=0，我们得到了−1ax=a−10，也就是x=0。它仍然需要证明（d）意味着（a），为此，我们证明了反面：如果（a）不成立，那么（d）不成立。

利用我们关于降方矩阵的基本观察，如果a不降为恒等式，则a降为一行梯队矩阵a0，其底行为零。假设a0=p a，其中p是基本行操作的产物。因为a0的底行是零，系统a0 x=0最多有n-1个非平凡方程，根据命题7.17，这个系统有一个非平凡解x。但是，ax=p−1ax=0，x=06，这与系统ax=0假设只有平凡解的事实相矛盾。因此，（d）意味着（a）证明是完整的。

命题7.18给出了一种计算可逆矩阵A的逆矩阵的方法：用初等行运算将A简化为恒等式，得到

ep···e1a=i.

把两边乘以1，我们得到

A−1=ep···e1。

从实际的角度出发，我们可以通过将单位矩阵的n列加到a中得到的增广n×2n矩阵（a，in）简化成行梯队，从而建立产品ep·····e1，这只是执行高斯-乔丹程序的另一种方法。下面是一个例子：让我们找出矩阵的逆矩阵

.

我们形成2×4块矩阵

并应用基本行操作将a约化为标识。例如：

从第2行减去第1行，

从第1行减去4×第2行，

，

从第2行减去第1行。因此

.

命题7.18也可以用来给出一个基本证明，如果一个方阵A有一个左逆B（resp.右倒数b），使b a=i（resp.a b=i），那么a是可逆的，a−1=b。这是一个有趣的练习，试试看！

7.12 RREF形式的唯一性

为了完备性，我们证明了矩阵的约化行梯队形式是唯一的。下面给出的整洁的证据是借用并改编自W.Kahan。

提案7.19。设A为任意m×n矩阵。如果u和v是通过应用两个基本行操作序列e1，…，ep和f1，…，fq从a获得的两个缩减行梯队矩阵，那么

u=ep···e1a和v=fq···f1a，

则u=v，ep···e1=fq···f1。换句话说，任何矩阵的缩减行梯队形式都是唯一的。

7.12。RREF的唯一性

证据。让

C=ep····e1f1····fq−1

以便

u=c v和v=c−1u。

我们通过在n上的归纳证明u=v（和c=i）。

设j代表中单位矩阵的第j列，设uj=uj、vj=vj、cj=cj和aj=aj分别为u、v、c和a的第j列。

首先，我声称uj=0 iff vj=0 iff aj=0。

实际上，如果vj=0，那么（因为u=cv）uj=cvj=0，如果uj=0，那么vj=c−1uj=0。由于u=ep···e1a，我们也得到aj=0 iff uj=0。

因此，我们可以通过从u、v和a中删除由零组成的列来简化我们的任务，因为它们将具有相应的索引。我们仍然用n来表示a的列数。注意，因为u和v是没有零列的缩减行梯队矩阵，所以我们必须有u1=v1=`1。

索赔。如果u和v是没有零列的缩减行梯队矩阵，因此u=cv，对于所有k≥1，如果k≤n，那么‘k出现在u中，iff’k出现在v中，如果‘k确实出现在u中，那么

\1. ` k表示U和V中同一列索引jk；

\2. U和V的第一个JK列匹配；

\3. 索引k+1到m的坐标均等于0的u和v（列索引>jk）中的后续列也匹配。让nk是这样一列的最右边的索引，如果没有，则使用nk=jk。

\4. C的第一个NK列与中的第一个NK列匹配。

我们通过对K的归纳来证明这一主张。

对于基本情况k=1，我们已经知道u1=v1=`1。我们也有

c1=c1=cv1=u1=1.

如果vj=某些λ∈r的λ’1，则

u j=uj=cvj=cvj=λc1=λc1=λ1=vj。

使用c−1的一个类似的论点表明，如果uj=λ` 1，那么vj=uj。因此，u和v的所有列与“1”成比例匹配，这就建立了基本情况。注意，如果“2”出现在u中，那么它必须同时出现在u和v中，对于相同的索引，如果不是，则n1=n和u=v。

下一步我们将证明归纳步骤。如果nk=n，那么u=v，我们就完成了。否则，k+1同时出现在u和v中，在这种情况下，通过归纳假设的（2）和（3），它同时出现在u和v中，对于相同的指数，比如jk+1。因此，UJK+1=VJK+1=`K+1。接下来是

c k+1=ck+1=cvjk+1=ujk+1=k+1，

因此，c的第一个jk+1列与in的第一个jk+1列匹配。

考虑后面的任何列vj（j>j k+1），其（k+1）之外的元素都将消失。那么vj是vj左边v列的线性组合，所以

uj=cvj=vj。

因为C的前k+1列与中的第一列匹配。同样，任何后面的uj列（j>j k+1），其元素超过（k+1）th都消失，等于vj。因此，u和v（索引>jk+1）中元素超过（k+1）th的所有后续列也都消失匹配，因此c的第一个nk+1列与c的第一个nk+1列匹配，完成了诱导假设。

我们现在可以证明u=v（回想一下，我们可以假设u和v没有零列）。我们之前注意到，u1=v1=`1，所以有一个最大的k≤n，这样‘k出现在u中。那么前面的声明意味着u和v的所有列都匹配，这意味着u=v。

行梯队形式的约简也提供了一种描述形式为ax=b的线性系统解集的方法。

7.13使用RREF求解线性系统

首先，我们得到以下简单的结果。

提案7.20。设a为任意m×n矩阵，设b∈rm为任意向量。如果系统

ax=b有一个解，那么这个系统所有解的集合z就是集合

Z=X0+KER（A）=X0+X AX=0，

式中，X0∈Rn是系统a x=b的任意解，即a x0=b（X0称为特殊解），式中，Ker（a）=x∈Rn Ax=0，则是与ax=b相关的齐次系统的解集。

证据。假设系统ax=b是可解的，让x0和x1是任意两个解，这样ax0=b和ax1=b。从第二个方程中减去第一个方程，我们得到

A（x1−x0）=0，

也就是说，x1−x0∈ker（a）。因此，z x0+ker（a），其中x0是ax=b的一个特殊解，反之，如果ax0=b，那么对于任何z∈ker（a），我们有az=0，因此

A（X0+Z）=a x0+a z=b+0=b，

这表明X0+Ker（a）z。因此，z=X0+Ker（a）。

给定一个线性系统ax=b，将增广矩阵（a，b）简化为其行梯队形式（a0，b0）。如前所示，系统ax=b有一个解决方案，如果b0不包含支点。假设是这样。那么，如果（a0，b0）有r个支点，这意味着a0有r个支点，因为b0没有支点，我们知道im的前r列出现在a0中。

我们可以排列a0的列，并相应地在x中重新编号变量，这样im的第一个r列与a0的第一个r列相匹配，然后我们的简化梯队矩阵的形式（r，b0）为

和

其中f是r×（n-r）矩阵，d∈rr。注意r有m-r零行。

那是因为

，

我们看到了

是rx=b0的一个特殊解，因此ax=b。换句话说，我们通过将b0的第一个r分量分配给透视变量，并将非透视变量（自由变量）设置为零得到一个特殊解。

以下是Kumpel Thorpe之前的施工示例。线性系统

x1−x2+x3+x4−2x5=−1

−2x1+2x2−x3+x5=2 x1−x2+2x3+3x4−5x5=−1，

用增广矩阵表示

，

其中a是3×5矩阵。读者应该发现这个系统的行梯队形式是

.

3×5矩阵a0的秩为2。我们排列第二列和第三列（相当于交换变量x2和x3）以形成

.

然后给出了这个线性系统的一个特殊解

.

我们还可以找到一个使用f的核（空空间）的基，如果x=（u，v）在a的核中，其中u∈r r和v∈rn−r，那么x也在r的核中，这意味着rx=0；也就是说，

.

因此，u=−fv和ker（a）由形式的所有向量组成。

对于任意的v∈r n−r，它遵循矩阵的n−r列

子矩阵，因此列构成了内核的基础。这是因为线性无关。总之，如果n包含单位矩阵n1，…，n in−n−r ras aa是n的列，那么方程ax=b的一般解由下式给出：

，

其中xr+1，…，xn是自由变量；也就是说，非透视变量。回到上一个例子，我们看到了

，

一般的解决办法是

.

在一般情况下，当轴对应的列与自由变量对应的列混合时，我们发现特殊的解决方案如下。设I1·············<Ir为支点对应列的索引。为k=1，…，r指定透视变量xik，并将所有其他变量设置为0。为了找到核的一个基础，我们形成了n-r向量nk，如下所示。设j1<·······<jn−r为自由变量对应列的指数。对于与自由变量（1≤k≤n−r）相对应的每列jk，形成定义的向量nk，以便条目等于jk列中第一个r条目的负数（翻转这些条目的符号）；设为1，并将所有其他条目设为零。如果索引jk的列（对应于自由变量xjk）是

α1_

……γ

 

αR_

，0

 

…γ

零

然后向量nk由

1 0

……γ

I1−1 0 I1−α1 I1+1 0

……γ

IR1 0

IR−αR。

红外+1 0

……__

JK−1 0 JK 1 JK+1 0

………__

N 0

位置jk中的1确保n1，…，nn-r是线性独立的。

作为上述方法的一个例子，考虑找到满足以下性质的n×n矩阵a∈mn（r）的子空间v的基的问题：

\1. 每行中的条目之和具有相同的值（例如c1）；

\2. 每列中条目的总和具有相同的值（例如c2）。

结果表明，c1=c2，与上述条件对应的2n-2方程是线性无关的。我们把这些事实的证明留作有趣的练习。利用对偶定理（定理10.1）可以证明，满足上述方程的矩阵的空间V的维数是n2−（2n−2）。让我们考虑n=4的情况。有6个方程，空间V有维度10。这些方程是

A11+A12+A13+A14−A21−A22−A23−A24=0 A21+A22+A23+A24−A31−A32−A33−A34=0 A31+A32+A33+A34−A41−A42−A43−A44=0 A11+A21+A41−A12−A22−A42=0 A12+A22+A32+A42−A13−A33−A43=0 A13+A23+A33+A43−A14−A24−A34−A44=0，

相应的矩阵是

1 1 1 1−1−1 0 0 0 0 0 0 0 0 0 0_

0 0 0 1 1 1 1 1−1−1 0 0 0 0_

γ

A=01−01 00 00 01−01 00 11−11 01 01−11−01−01。

 

0 1−1 0 0 1−1 0 0 1−1 0 1−1 0_

0 0 1−1 0 0 1−1 0 0 1−1 0 0 1−1

对行梯队形式进行约简的结果在RREF中生成以下矩阵：

支点变量索引的列表pivlist和自由变量索引的列表free list由下式给出：

pivlist=（1,2,3,4,5,9），freelist=（6,7,8,10,11,12,13,14,15,16）。

应用该算法求出u核的基，得到以下16×10

读者应该检查一下，在bk的j列中，最下面的粗体1属于自由列表中索引为jth元素的行，在bk的j列中，索引为pivlist的条目的符号是u列中对应t的6个条目的翻转符号。o自由职业者的第j个指数。现在我们可以从bk中读出构成v基础的4×4矩阵：bk的每一列对应一个已连接行的矩阵。我们得到以下10个矩阵：

1−1 0 1 0−1 0 1 0−1

−1 1 0−1 0 1 0−1 0 0 1

M1=0 0 0，M2=0 0 0，M3=0 0 0，

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1−1 0 1 0−1 0 1 0−1

0 0 0 0 0 0 0 0 0 0 0

M4=−1 10 0，M5=−1 0 1 0，M6=−1 0 0 1，

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

−2 1 1 1−1 0 1 1−1 0 1

m7=11 00 00 00 00，m8=11 00 00 00 00，m9=11 00 00 00 00，

1 0 0 0 0 1 0 0 0 0 1 0

−1 1 0_

M10=11 00 00 00 00。

0 0 0 1

回想一下，幻方是一个方阵，它满足关于每一行和每一列中条目之和为同一个数字的两个条件，以及主下降对角线和主上升对角线相加为该公共数字的附加两个约束。此外，这些条目还需要是正整数。对于n=4，附加的两个方程是

A22+A33+A44−A12−A13−A14=0 A41+A32+A23−A11−A12−A13=0，

矩阵为幻方的8个方程是线性无关的。再次，通过行消除，我们得到了“广义幻方”的基础，其条目不限于正整数。我们找到了8个矩阵的基。对于n=3，我们找到3个矩阵的基。

如果一个幻方的项恰好是整数1,2…，n2，则称其为正态。因为这些条目的总和是

，

由于每一行（和每一列）的和都是相同的数字，所以这个公共值（魔法和）是

.

很容易看出n=2没有正规的魔方。对于n=3，魔法和为15，对于n=4，魔法和为34，对于n=5，魔法和为65。

在n=3的情况下，我们有一个附加条件，行和列加起来是15，所以我们得到了一个由两个数字x1，x2参数化的解；也就是说，

.

因此，为了找到一个正规的幻方，我们有额外的不等式约束。

x1+x2>5 x1<10 x2<10 2x1+x2<20

2x1+x2>10 x1>0 x2>0 x1+x2<15，

7.14。初等矩阵和列运算

矩阵中的所有9个条目都必须是不同的。经过一个冗长的案例分析，我们发现了一个显著的事实，那就是有一个独特的正态魔方（直到旋转和反射）：

结果表明，n=4有880个不同的法向幻方，n=5有275305224个法向幻方（直到旋转和反射）。即使对于n=4，也需要大量的工作才能将它们全部列举出来！找到n>5的魔方数量是一个悬而未决的问题！

7.14基本矩阵和柱运算

我们不需要在矩阵A上执行基本的行操作，而是可以执行基本的列操作，这意味着我们用右边的基本矩阵乘以a。作为基本的行和列操作，p（i，k），ei，j；β，ei，λ执行以下操作：

\1. 作为行操作，p（i，k）将行i和行k进行排列。

\2. 作为列操作，p（i，k）排列列i和列k。

\3. p（i，k）的倒数是p（i，k）本身。

\4. 作为一个行操作，ei，j；β将β乘以j行加到i行。

\5. 作为列操作，ei，j；β将β乘以列i添加到列j（注意索引中的开关）。

\6. ei，j的倒数；β为ei，j；−β。

\7. 作为行操作，ei，λ将行i乘以λ。

\8. 作为列操作，ei，λ将列i乘以λ。

\9. ei的倒数，λ为ei，λ−1。

我们可以定义约化柱梯队矩阵的概念，并证明每个矩阵都可以约化为唯一的约化柱梯队形式。对于任意m×n矩阵a，如果我们首先将a转换成它的缩减行梯队形式r，很容易看出我们可以应用基本列操作，将r简化为该形式的矩阵。

，

其中r是支点数（在行缩减过程中获得）。因此，对于每个m×n矩阵a，存在两个初等矩阵序列e1，…，ep和f1，…，fq，这样

.

右边的矩阵称为A的秩正规型，很明显，R是A的秩，作为推论，我们得到了以下重要结果，其证明是直接的。

提案7.21。矩阵A及其转置a>具有相同的秩。

7.15运输和扩张~

在这一部分中，我们描述了向量空间e的线性同构，它使某个超平面中的每个向量保持不变。这些映射结果是线性映射，在一些合适的基础上由形式为ei，j；β（transvections）或ei，λ（expansations）的初等矩阵表示。此外，交通量生成SL（e）组，而扩张生成GL（e）组。

设h为e中的任何超平面，并选取一些（非零）向量v∈e，使v/∈h，

e=h kv。

假设f:e→e是一个线性同构，使得f（u）=u代表所有u∈h，而f不是同一性。我们有

f（v）=h+αv，对于一些h∈h和一些α∈k，

当α=06时，因为否则我们会得到f（v）=h=f（h），因为h∈h，与f的注入率（v=6h，因为v/∈h）相矛盾。对于任何x∈e，如果我们写

x=y+tv，对于某些y∈h和一些t∈k，

那么f（x）=f（y）+f（t v）=y+tf（v）=y+th+tαv，

因为αx=αy+tαv，我们得到

F（x）−αx=（1−α）y+th

f（x）−x=t（h+（α−1）v）。

如果e是有限维的，通过选择由v和h的基向量组成的e的基，那么f的矩阵是一个下三角矩阵，其对角项都是1，除了第一个等于α的项。因此，Det（f）=α。

案例1。α=1.6

7.15。转移和扩张~

我们有f（x）=αx iff（1−α）y+th=0 iff

如果我们让w=h+（α-1）v，对于y=（t/（α-1））h，我们有

说明f（x）=αx iff x∈kw。注意w/∈h，因为α=16和v/∈h。

因此，

e=h千瓦，

f是h上的单位和d=kw线上α的放大率。

定义7.6.给定一个向量空间e，对于e中的任意超平面h，任意非零向量u∈e，使u 6∈h，任意标量α=06，1，一个线性映射f，使f（x）=x表示所有x∈h，f（x）=αx表示每个x∈d=ku，称为超平面h，方向d，尺度因子α的扩张。

如果πh和πd是e对h和d的投影，那么我们有

F（x）=πH（x）+απD（x）。

f的倒数由

F−1（x）=πH（x）+α−1πD（x）。

当1时，我们有f2=id，f是关于超平面h方向的对称性。这种情况包括H的正交反射。

案例2。α=1.

在这种情况下，f（x）−x=th，

也就是说，f（x）−x∈kh代表所有x∈e，假设超平面h是作为某种线性形式的核，并设a=（v）。我们有a=06，因为v/∈h。对于任何x∈e，我们有（x−a−1（x）v）=（x）−a−1（x）（v）=（x）−（x）=0，

这表明x−a−1（x）v∈h代表所有x∈e，由于h中的每一个向量都被f固定，我们得到

X−A−1（X）V=F（X−A−1（X）V）

=f（x）−a−1（x）f（v）

所以

f（x）=x+（x）（f（a−1v）−a−1v）。

由于f（z）−z∈k h对于所有z∈e，我们得出u=f（a−1v）−a−1v=βh对于某些β∈k，所以（u）=0，并且我们有

f（x）=x+（x）u，（u）=0.（）

如上定义的线性图由τ_，u表示。

相反，对于方程（）给出的任何线性映射f=τ，u，式中，τ是一个非零线性形式，u是一些向量u∈e，因此，如果u=0，则f是恒等式，因此假设u=06。如果是的话，我们有f（x）=x iff（x）=0，也就是说，iff x∈h。我们还声称f的倒数是通过将u改为-u得到的。实际上，我们检查了一个更一般的事实，即

τ，u_τ，w=τ，u+w.

事实上，利用这个事实，我们有

τ，u（τ，w（x））=τ，w（x）+（τ_，w（x））u

=，w（x）+（（x）+（x）（w））u

=τ，w（x）+（x）u

=x+（x）w+（x）u=x+_（x）（u+w）。

对于v=−u，如权利要求所述，我们有τ，u+v=_，0=id，所以τ，u−1=τ，−u。

因此，我们证明了e的每一个线性同构使某个超平面h中的每一个向量保持不变，并具有f（x）−x∈h（对于所有x∈e）由方程（）定义的映射τ，u给出的性质，式中，ω是定义h的某个非零线性形式，u是h中的某个向量。平均τ_，u=id iff u=0。

定义7.7.给定e中的任意超平面h，对于任意非零非线性形式，其中，定义h（即h=ker（））和任意非零向量u h，线性映射f=τ，u（x）=x+（x）u，（u）=0，

对于所有x∈e，称为超平面h和方向u的矢量变换。图f=τ_，u使h中的每一个矢量保持不变，f（x）−x∈ku表示所有x∈e。

以上参数显示以下结果。

提案7.22。设f:e→e为一个双射线性映射，假设f=6 id，f（x）=x，表示所有x∈h，其中h是e中的某个超平面，如果有一些非零向量u∈e，使得u/∈h和f（u）−u∈h，则f是超平面h的变换；否则，f是超平面的扩张。H.

7.15。转移和扩张~

证据。用上面的符号表示，对于一些v/∈h，我们有f（v）=h+αv，α=06，并写出u=y+tv，y∈h，t=06，因为u/∈h。如果f（u）−u∈h，从

F（U）−U=T（H+（α−1）V）

我们得到（α−1）v∈h，由于v/∈h，我们必须得到α=1，并且我们证明f是一个transvection。否则，α=06，1，我们证明了f是一个膨胀。

如果e是有限维，那么α=Det（f），我们也有以下结果。

提案7.23。设f:e→e为有限维向量空间e的一个双射线性映射，假设f=6 id，且f（x）=x表示所有x∈h，其中h是e中的某个超平面。如果det（f）=1，则f是超平面h的一个矢量化；否则，f是超平面h的一个扩张。

假设f是超平面h和方向u的扩张，并假设det（f）=α=06，1。选取e的基（u，e2，…，en），其中（e2，…，en）是h的基，则f的矩阵形式为α0···0

0 1 0_

………………，

γ

0 0 1

它是形式的初等矩阵。相反，很明显，形式ei，α，α=06，1的每一个初等矩阵都是一个扩张。

现在，假设f是超平面h的一个矢量和u∈h的方向，选取一些v/∈h，并选取h的一些基（u，e3，…，en），使（v，u，e3，…，en）是e的基，因为f（v）−v∈ku，f的矩阵是

1 0···0

α10_

………………，

0 0···1

它是e2，1；α形式的初等矩阵。相反，很明显，形式ei，j；α（α=0）6的每一个初等矩阵都是一个transvection。

下面的命题是一个有趣的练习，需要很好地掌握基本的行操作ei，j；β；参见问题7.10和7.11。

提案7.24。给定任意可逆n×n矩阵a，有一个矩阵s

，

α=det（a），其中s是形式为ei，j；β的初等矩阵的乘积；也就是说，s是transvections的组成。

令人惊讶的是，每一个交通工具都是两个扩张的组成部分！

提案7.25。如果场k不具有特征2，则超平面h的每个矢量f可以写成f=d2 d1，其中d1、d2是超平面h的扩张，d1的方向可以任意选择。

证据。选取超平面h的扩张d1和比例因子α=06，1。然后，d2=f d−1使h中的每个矢量保持不变，det（d2）=α−1=16。根据命题7.23，线性映射d2是超平面h的扩张，我们得到f=d2 d1，如所述。

注意，在命题7.25中，我们可以选取α=-1；也就是说，超平面H的每一个矢量化都是关于超平面H的两个对称的组成，其中一个对称可以任意选取。

备注：建议7.25只要k=6 0,1。

现在得到以下重要结果。

定理7.26。设e为特征不等于2的场k上的任何有限维向量空间。然后由变换生成sl（e）组，由扩张生成gl（e）组。

证据。考虑任意f∈sl（e），并让a作为其任何基的矩阵。根据命题7.24，有一个矩阵

，

α=Det（a），其中s是形式为ei，j；β的初等矩阵的乘积。由于det（a）=1，我们得到α=1，并且证明了结果。另外，如果f是可逆的，但f/∈sl（e），则上述方程表明en，α是一个扩张，s是一个扩张的乘积，根据命题7.25，每个扩张都是两个扩张的组合。因此，第二个结果也得到了证明。

我们通过证明任意两个矢量在gl（e）中是共轭的来结束这一节。

设τ_，u（u=0）6为一个矢量，设g∈gl（e）为任意可逆线性映射。我们有

（gτ，u_g−1）（x）=g（g−1（x）+（g−1（x））u）=x+（g−1（x））g（u）。

让我们找出由线性形式x→7_（g−1（x））确定的超平面。这是一组向量x∈e，使得（g−1（x））=0，其中包含iff g−1（x）∈h iff x∈g（h）。因此，Ker（_g−1）=g（h）=h0，我们得到g（u）∈g（h）=h0，所以gτ，u g−1是超平面h0=g（h）和方向u0=g（u）（带u0∈h0）的变换。

7.16。总结

相反地，让τψ，u0是一些矢量（u0=0）6。选取一些向量v，v0，使_（v）=ψ（v0）=1，这样

e=h kv=h0 kv0。

存在一个线性映射g∈gl（e），使得g（u）=u0，g（v）=v0，和g（h）=h0。要定义g，选择一个基（v，u，e2，…，en-1），其中（u，e2，…，en-1）是h的基，选择一个基（v0，u0，e02，…，e0n-1），其中（u0，e02，…，en0-1）是h0的基；然后定义g，使g（v）=v0，g（u）=u0，g（ei）=g（e0i），对于i=2，…，n-1。如果n=2，则ei和e0i丢失。那么，我们有了

（g_τ，u_g−1）（x）=x+（g−1（x））u0.

现在，_g−1也决定了超平面h0=g（h），所以我们有_g−1=λψ用于k中的一些非零λ。由于v0=g（v），我们得到

⑨（v）=⑨g−1（v0）=λψ（v0）、

既然ω（v）=ψ（v0）=1，我们必须有λ=1。接下来是

（g_τ，u_g−1）（x）=x+ψ（x）u0=τψ，u0（x）。

总之，我们几乎证明了以下所有部分的结果。

提案7.27。设e为任意有限维向量空间。对于每一个横矢量τ，u（u=06）和每一个线性图g \τ，u g-1是超平面横矢量τψ，ug（h0（）和方向0 6=0）的横矢量，有一些（u）（即，g \9702;（τe\\（τe\，u）这样的，g \9702; 9702; 9702\9702;，u \\为每一个其他1；其他G−

单词任何两个transvections（=6 id）在gl（e）中是共轭的。此外，如果n≥3，则可以选择上述线性同构g，使g∈sl（e）。

证据。我们只需要证明，如果n≥3，那么对于任何两个交通量τ，u和τψ，u0

（u，u0=0）6，有一些g∈sl（e），例如τψ，u0=gτ，u g−1。和以前一样，我们选择一个基（v，u，e2，…，en-1），其中（u，e2，…，en-1）是h的基，我们选择一个基（

）是h0的基础，我们将g定义为唯一的线性映射，这样

g（v）=v0，g（u）=u0，g（ei）=ei0，对于i=1，…，n-1。但在这种情况下，h和h0=g（h）的维数都至少为2，所以在包括u0在内的h0的任何基中，都有一些独立于u0的基向量，我们可以用这样一种方式重新缩放，即g在两个基上的矩阵具有行列式+1。

7.16总结

本章的主要概念和结果如下：

• 不能通过计算行列式来求解（大）线性系统。

• 上三角（下三角）矩阵。

• 反替换法求解（正替换法）。

• 高斯消去。

• 排列行。

• 旋转消除步骤的中心；旋转

• 换位矩阵；初等矩阵。

• 高斯消元定理（定理7.1）。

• 高斯-乔丹因子分解。

• lulu——因式分解（命题因式分解；an7.2存在的充分必要条件）。

• LDU因子分解。

• “pa=lu定理”（定理7.5）。

• 对称矩阵的因式分解。

• 避免小支点：部分支点；完全支点。

• 三对角矩阵的高斯消去。

• 三对角矩阵的Lu因子分解。

• 对称正定矩阵（SPD矩阵）。

• 乔尔斯基因式分解（定理7.10）。

• 对称矩阵为正定的准则；西尔维斯特准则。

• 减少的行梯队形式。

• 把一个矩形矩阵简化成它的行梯队形式。

• 并求出其解，利用行梯队形式的约简来决定系统的特殊解和齐次系统的基ax=b是否可解，

ax=0.

• 魔方。

• 转移和扩张。

7.17问题

问题7.1。用高斯消去法求解下列线性系统：

.

问题7.2。用高斯消去法求解下列线性系统：

.

问题7.3。考虑矩阵

.

当应用高斯消元时，在第二个轴位置，哪个C值为零？在第三个支点位置，C的哪个值为零？在这种情况下，你对矩阵A有什么看法？问题7.4。解决系统问题

使用示例7.1中的lu因子分解。

问题7.5。将rref应用于矩阵

.

问题7.6.将rref应用于矩阵

.

问题7.7。（1）证明2×2矩阵A的子空间的维数，使每一行的条目之和相同（即c1），每一列的条目之和相同（即c2）为2。

(2) 证明了2×2矩阵A的子空间的维数，使得每一行的条目之和是相同的（如c1），每一列的条目之和是相同的（如c2），c1=c2也是2。证明每一个这样的矩阵都是

，

并给出这个子空间的基础。

(3) 证明了3×3矩阵A的子空间的维数，使得每一行的条目之和相同（如c1），每一列的条目之和相同（如c2），c1=c2为5。首先说明上述约束是由一组方程给出的。

A11_

A12_

1 1 1−1−1 0 0 0 A13 0

0 0 1 1 1−1−1 a21 0 1−1 0 1−1 0 a22=0。

γ

   

0 1−1 0 1−1 0 1−1 a23 0

0 1 1−1 0 0−1 0 0 A31 0

 

A32 A33

证明满足上述约束的每一个矩阵都是这样的

，

用a，b，c，d，e∈r.找到这个子空间的基。（使用该方法查找矩阵核心的基础）。

问题7.8。如果a是n×n对称矩阵，b是任意n×n可逆矩阵，证明a是正定的iff b>ab是正定的。

问题7.9。（1）考虑矩阵

.

找到三个形式为e2,1；β1，e3,2；β2，e4,3；β3的矩阵，这样

e4,3；β3e3,2；β2e2,1；β1a4=u4

其中U4是上三角矩阵。计算

m=e4,3；β3e3,2；β2e2,1；β1

检查一下。

.

(2) 现在考虑矩阵

	网络错误 网络错误 网络错误	网络错误 网络错误 网络错误	网络错误 网络错误	网络错误 网络错误 网络错误 网络错误 网络错误

找到四个形式为e2,1；β1，e3,2；β2，e4,3；β3，e5,4；β4的矩阵，这样

e5,4；β4e4,3；β3e3,2；β2e2,1；β1a5=u5

其中U5是上三角矩阵。计算

m=e5,4；β4e4,3；β3e3,2；β2e2,1；β1

检查一下。

 

0 0 5/4−1_

0 0 0 0 6/5

(3) 编写一个matlab程序，定义函数ematrix（n，i，j，b），它是n×n矩阵，将b乘以j行加到i行。还编写一些matlab代码，生成n×n矩阵，并推广矩阵a4和a5。

用你的程序找出哪五个矩阵ei，j；β把a6减少到上三角矩阵

.

也可以用你的程序计算出哪六个矩阵ei，j；β将a7减少到上三角。-

(4) 求下三角矩阵l6和l7，这样

L6U6=A6

和

L7U7=A7。

(5) 可以很自然地推测，有n−1矩阵的形式ei，j；β可以减少

也就是说，

e2,1；1/2，e3,2；2/3，e4,3；3/4，···，en，n-1；（n-1）/n.

也可以自然地推测下三角矩阵ln

lnun=安

由给出

网络错误
	网络错误 网络错误 网络错误	网络错误 网络错误 网络错误	网络错误 网络错误	网络错误 网络错误 网络错误

ln=e2,1；−1/2e3,2；−2/3e4,3；−3/4····en，n−1；−（n−1）/n，

−

证明上述猜想。

(6) 证明a−n1的最后一列是

1/（N+1）

2/（n+1）

……。n/（n+1）问题7.10。（1）设A为任意可逆2×2矩阵

.

证明存在可逆矩阵，这样

，

其中，s是形式ei，j；β的最多四个基本矩阵的乘积。

得出如下结论：sl（2）中的每一个矩阵a（det（a）=+1的可逆2×2矩阵a组）最多是ei，j；β形式的四个基本矩阵的乘积。对于任何a=06，1，给出如上所述的显式因子分解

.

A=-1的分解是什么？

（2）回想一下，旋转矩阵r（群so（2）的成员）是形式的矩阵。

.

证明如果θ=6Kπ（带k∈z），任何旋转矩阵都可以写成一个乘积。

R=ulu，

其中u是上三角形，l是下三角形

.

因此，每个平面旋转（θ=π时围绕原点的翻转除外）都可以写成三个剪切变换的组合！

问题7.11。（1）记住，ei，d是对角矩阵

ei，d=诊断（1，…，1，d，1，…，1）

其对角线项均为+1，但（i，i）第n项等于d。

给定任意n×n矩阵a，对于任意一对（i，j）不同的行指数（1≤i，j≤n），证明存在两个初等矩阵e1（i，j）和e2（i，j），形式为ek，`；β，这样

ej、−1e1（i，j）e2（i，j）e1（i，j）a=p（i，j）a，

通过排列行i和行j从矩阵a中得到的矩阵。等价地，我们得到

e1（i，j）e2（i，j）e1（i，j）a=ej，−1p（i，j）a，

通过排列第i行和第j行并将第j行乘以−1得到的矩阵。

证明对于每一个i=2，…，n，存在四个初等矩阵e3（i，d），e4（i，d），e5（i，d），e6（i，d），形式为ek，`；β，这样

e6（i，d）e5（i，d）e4（i，d）e3（i，d）en，d=ei，d.

当d=-1时会发生什么，也就是说，会发生什么样的简化？

证明了所有置换矩阵都可以写成形式Ek、`；β和形式En、−1的初等运算的乘积。

(2) 证明对于每一个可逆n×n矩阵a，都有一个矩阵s

，

d=det（a），其中s是Ek形式的初等矩阵的乘积，`；β。

特别是，sl（n）中的每一个矩阵（det（a）=+1的可逆n×n矩阵A组）都可以写成Ek、`；β形式的初等矩阵的乘积。证明最多需要n（n+1）−2这样的转换。

(3) 证明sl（n）中的每一个矩阵最多可以写成（n−1）（max n，3+1）形式的初等矩阵`；β的乘积。

问题7.12。矩阵A称为严格的列对角占优iff

，对于j=1，…，n

证明了如果a是严格的列对角占优，则带部分旋转的高斯消元不需要旋转，a是可逆的。

问题7.13。（1）求下三角矩阵e，使

1 0 0 0 1 0 0 0

E 11 12 01 00=00 11 01 00。

1 3 3 1 0 1 2 1

(2) 产品（左边）有什么效果

e4,3；-1e3,2；-1e4,3；-1e2,1；-1e3,2；-1e4,3；-1

在矩阵上

.

(3) 求矩阵pa3的逆矩阵。

(4) 考虑（n+1）×（n+1）帕斯卡矩阵pan，其第i行由二项式系数给出。

，

与1≤i≤n+1，1≤j≤n+1，并与通常惯例

=0，如果j>i。

矩阵pa3如问题（c）所示，pa4如下所示：

求n个初等矩阵Eik，jk；βk，这样

.

利用上面的证明，pan的逆矩阵是下三角矩阵，其第i行由有符号的二项式系数给出。

，

1≤i≤n+1，1≤j≤n+1。例如，

10 0 0 0_

−1 1 0 0 0_

PA−4 1=1−2 1 0。

 

−1 3−3 1 0_

1−4 6−4 1

暗示。给定任意n×n矩阵a，将a乘以初等矩阵ei，j；右边的β得到矩阵aei，j；β，其中β乘以第i列加到第j列。

问题7.14。（1）在matlab中实现了将矩形矩阵转换成缩排梯队形式的方法。

(2) 用上述方法求可逆N×N矩阵A的逆矩阵，将其应用于通过将单位矩阵的n列添加到a得到的N×2N矩阵[ai]。

(3) 考虑矩阵

使用您的程序，找到n=4，…，20的行缩减梯队形式a。

同时运行matlab rref函数并比较结果。

即使对于较小的n值，您的程序也可能与rref不一致。问题在于，某些轴非常小，而规范化步骤（使轴1成为轴1）会导致舍入错误。使用公差参数来解决此问题。

你能推测出A的等级是多少？

(4) 证明矩阵A具有以下行约简形式：

1 0−1−2····−（n−2）

0 1 2 3················································

…………………………………

γ

0 0 0 0 0··0

从上面推断A的等级为2。

暗示。一些精心选择的行操作序列。

(5) 使用程序显示，如果在a的每个对角线条目中添加大于或等于（2/25）n2的任何数字，将得到可逆矩阵！实际上，运行matlab函数chol应该会告诉您这些矩阵是spd（对称、正定）。

问题7.15。设A为n×n复厄米特正定矩阵。证明了下三角矩阵b的正对角项a=bb由以下公式给出：对于j=1，…，n，

，

对于i=j+1，…，n（和j=1，…，n-1）

J−1！

X

bij=aij bikbj k/bj j j.

K＝1

问题7.16。（排列和排列矩阵）排列可以看作是排列矩阵行的操作。例如，排列

对应于矩阵

.

观察矩阵pπ在每一行和每一列上都有一个1，所有其他项都为零，如果我们将任意4×4矩阵a乘以左边的pπ，则A的行按排列π排列；也就是说，pπa的第（i）行是a的第i行。例如，

.

等价地，pπa的第i行是a的第π−1（i）行。为了使矩阵pπ将a的第i行移动到π（i）第i行，pπ的第i行必须在第一列中有1，在其他地方都有0；这意味着pπ的第i列包含基向量eπ（i），即在π（i）的位置上有一个1，其他地方都有零。

这是一般情况，并导致以下定义。

定义7.8.对于任意置换π：【n】→【n】，表示π的置换矩阵pπ=（pij）是由

；

等价地，pπ的jth列是基向量eπ（j）。置换矩阵p是形式pπ的任何矩阵（其中p是n×n矩阵，π：[n]→[n]是置换，对于某些n≥1）。

注：关于置换矩阵的符号有一个混淆点。置换矩阵p通过对a的行进行置换而在左边乘法作用于矩阵a。如前所述，这意味着pπa的第i行是a的第i行，或者等于pπa的第i行是a的第π−1（i）行。但是观察到中心的行索引第i行的s是π−1（i），而不是π（i）！请参见以下示例：

，

哪里

π−1（1）=4π−1（2）=3π−1（3）=1π−1（4）=2.

证明以下结果

(1) 给定任意两个置换π1，π2:[n]→[n]，置换矩阵pπ2_π1代表π1和π2的组成，等于置换矩阵pπ1和pπ2代表π1和π2的积pπ2pπ1；即，

Pπ2_π1=Pπ2Pπ1.

(2) 表示置换π1的逆矩阵pπ1−1是表示置换π1的矩阵pπ1的逆矩阵pπ−11；也就是说，

.

此外，

Pπ−11=（Pπ1）>。

(3) 证明如果p是与换位相关的矩阵，那么det（p）=-1。

(4) 证明如果p是一个置换矩阵，那么det（p）=1。

(5) 使用置换矩阵给出另一个事实证明，用于表示置换π的置换数的奇偶性仅依赖于π。