本节要介绍一种新的矩阵——置换矩阵

具体来说，当A是一个（m，n）的矩阵时，它的转置是一个（n，m）的矩阵 Transpose if A = [ 1 2 3 0 0 4 ] then A T = [ 1 0 2 0 3 4 ] \text{Transpose}\quad \text{if}\quad A=\begin{bmatrix} 1&2&3\\ 0&0&4 \end{bmatrix}\quad \text{then}\quad A^T=\begin{bmatrix}1&0\\2&0\\3&4\end{bmatrix} TransposeifA=[10​20​34​]thenAT=⎣⎡​123​004​⎦⎤​

A中的行即为AT中的列，A中的列即为AT中的行，即 ( A T ) i j = A j i (A^T)_{ij}=A_{ji} (AT)ij​=Aji​

下三角矩阵的转置是上三角矩阵，但是下三角矩阵的逆依然是下三角矩阵

关于矩阵的转置运算的三个规则 Sum The Transpose of A + B is A T + B T \mathbf{\text{Sum}}\quad \text{The Transpose of}\quad A+B\quad \text{is}\quad A^T+B^T SumThe Transpose ofA+BisAT+BT

Product The Transpose of A B is ( A B ) T = B T A T \mathbf{\text{Product}}\quad \text{The Transpose of}\quad AB\quad \text{is}\quad (AB)^T=B^TA^T ProductThe Transpose ofABis(AB)T=BTAT

Inverse The Transpose of A − 1 is ( A − 1 ) T = ( A T ) − 1 \mathbf{\text{Inverse}}\quad \text{The Transpose of}\quad A^{-1}\quad \text{is}\quad (A^{-1})^T=(A^T)^{-1} InverseThe Transpose ofA−1is(A−1)T=(AT)−1

注意第二个积的转置，当B仅为一个向量 x \mathbf{x} x时，有 ( A x ) T = x T A T (A\mathbf{x})^T=\mathbf{x}^TA^T (Ax)T=xTAT

A x A\mathbf{x} Ax是 A A A的各列的线性组合， x T A T \mathbf{x}^TA^T xTAT是 A T A^T AT的各行的线性组合

我们已经知道关于两个向量x，y的内积为 x i y i x_iy_i xi​yi​的和，表示的方式为 x ⋅ y \mathbf{x}\cdot\mathbf{y} x⋅y

当了解了转置的概念之后，我们可以用转置来表示内积

內积的表示方式为 x T y \mathbf{x^T}\mathbf{y} xTy，外积的表示方式为 x y T \mathbf{xy^T} xyT

其中前者得到的结果是一个数字，后者的结果是一个矩阵

对于一个对称矩阵来说，它本身和它的转置之间没有区别，我们定义对称矩阵 S T = S s i j = s j i S^T=S \quad s_{ij}=s_{ji} ST=Ssij​=sji​

接下来我们将通过 A T A A^TA ATA来构造一个对称矩阵 S S S

某一个矩阵A（可以为矩型），他的转置乘上自身是一个对称的方阵 S = A T A S=A^TA S=ATA A T A = A T ( A T ) T = A T A A^TA=A^T(A^T)^T=A^TA ATA=AT(AT)T=ATA

也可以直接从对应的项上来看， A T A A^TA ATA的（i，j）项和（j，i）项的相乘的两个向量来源是一样的

矩阵 A A T AA^T AAT也是对称的，但是和上述的矩阵是不同的矩阵

对称矩阵的消元

对称矩阵的消元比一般的矩阵更加迅速，因为在处理矩阵时，可以只针对一般的矩阵操作（包含主对角线）

当S是一个对称矩阵的时候，通用的分解LDU，在没有行交换的情况下，变为S=LDLT

要注意到矩阵LDLT的转置(LT)DTLT依然是自身，则消元运算次数从n3/3变为n3/6.

置换矩阵用P来表示，置换矩阵每一行每一列有且仅有一个1，且置换矩阵的转置依然是置换矩阵，可以相同也可以不同，任意两个置换矩阵P1P2的积也依然是置换矩阵

置换矩阵从单位矩阵演变而来，只要将单位矩阵的任意两行进行交换即可得到置换矩阵，即可以是单位矩阵中每一行的任意组合，总共有n!种形式 I = [ 1 1 1 ] P 21 = [ 1 1 1 ] P 32 P 21 = [ 1 1 1 ] I=\left[\begin{array}{lll}1 & &\\& 1& \\& & 1\end{array}\right] \quad P_{21}=\left[\begin{array}{lll}&1 & \\1 & \\&& 1\end{array}\right] \quad P_{32} P_{21}=\left[\begin{array}{ll}&1 & \\ & & 1\\ 1 & &\end{array}\right] I=⎣⎡​1​1​1​⎦⎤​P21​=⎣⎡​1​1​1​⎦⎤​P32​P21​=⎣⎡​1​1​1​⎦⎤​

P 31 = [ 1 1 1 ] P 32 = [ 1 1 1 ] P 21 P 32 = [ 1 1 1 ] P_{31}=\left[\begin{array}{cc}& &1 \\&1 &\\1& &\end{array}\right] \quad P_{32}=\left[\begin{array}{ccc}1 & & \\& &1 \\& 1 & \end{array}\right] \quad P_{21} P_{32}=\left[\begin{array}{cc}& &1 \\1 & &\\&1&\end{array}\right] P31​=⎣⎡​1​1​1​⎦⎤​P32​=⎣⎡​1​1​1​⎦⎤​P21​P32​=⎣⎡​1​1​1​⎦⎤​

任何矩阵左乘一个置换矩阵，即为对原矩阵进行行交换的操作

置换矩阵逆依然还是置换矩阵，左边四个矩阵的逆依然是自身，右边两个矩阵的逆则是彼此

置换矩阵的逆和置换矩阵的转置是一样的，因而 P P T = I PP^T=I PPT=I

在消元之前引入行交换，我们又会得到 P A = L U PA=LU PA=LU

在上一节A=LU分解中我们已经知道了这样一种因式分解的方式，但是在很多情况下我们需要进行行交换来得到主元，以便于后续的消元。

我们将所有的行交换的过程Pij变成一个置换矩阵P来表示 [ 0 1 1 1 2 1 2 7 9 ] → [ 1 2 1 0 1 1 2 7 9 ] → [ 1 2 1 0 1 1 0 3 7 ] → [ 1 2 1 0 1 1 0 0 4 ] \left[\begin{array}{lll}0 & 1 & 1 \\1 & 2 & 1 \\2 & 7 & 9\end{array}\right] \rightarrow\left[\begin{array}{lll}1 & 2 & 1 \\0 & 1 & 1 \\2 & 7 & 9\end{array}\right] \rightarrow\left[\begin{array}{lll}1 & 2 & 1 \\0 & 1 & 1 \\0 & 3 & 7\end{array}\right] \rightarrow\left[\begin{array}{lll}1 & 2 & 1 \\0 & 1 & 1 \\0 & 0 & 4\end{array}\right] ⎣⎡​012​127​119​⎦⎤​→⎣⎡​102​217​119​⎦⎤​→⎣⎡​100​213​117​⎦⎤​→⎣⎡​100​210​114​⎦⎤​

A → P A → l 31 = 2 → l 32 = 3 A\quad \rightarrow\quad PA\quad \rightarrow\quad l_{31}=2\quad \rightarrow\quad l_{32}=3 A→PA→l31​=2→l32​=3

主要的问题就是何时运用置换矩阵P

若A是可逆的，置换矩阵就会把A行的顺序进行调整以便于PA=LU的分解，这必须要满足行交换后的矩阵A有足够的主元使得A可逆