置换矩阵是一种非常实用的数学工具， 其确切定义如下：
一个正方矩阵，若其每一行和每一列有且仅有一个非零元素 1 1 1，则称之为置换矩阵。
顾名思义，其作用是：
当将某一矩阵左乘置换矩阵，相当于将矩阵的行重新排列。 而右乘置换矩阵，则相当于对列重新排列。
因此，当我们想对矩阵的行或列重新排列时，就可以等效地将其写为左/右乘置换矩阵的形式。 插一句题外话，对某矩阵左乘一个对角阵，相当于对其每一行都分别乘上对应的对角元素。 右乘一个对角阵，则相当于每一列乘上一个对角元素。 因此，左乘代表对行操作，右乘代表对列操作。
以一个实例来说明，假设有如下矩阵：
A = [ a 11 a 12 a 13 a 14 a 21 a 22 a 23 a 24 a 31 a 32 a 33 a 34 a 41 a 42 a 43 a 44 a 51 a 52 a 53 a 54 ] A=\left[\begin{array}{llll} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \\ a_{51} & a_{52} & a_{53} & a_{54} \end{array}\right] A=⎣⎢⎢⎢⎢⎡a11a21a31a41a51a12a22a32a42a52a13a23a33a43a53a14a24a34a44a54⎦⎥⎥⎥⎥⎤
和置换矩阵 P 4 = [ 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 ] \boldsymbol{P}_{4}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{array}\right] P4=⎣⎢⎢⎡0010010000011000⎦⎥⎥⎤ 那么我们有: A P 4 = [ a 13 a 12 a 14 a 11 a 23 a 22 a 24 a 21 a 33 a 32 a 34 a 31 a 43 a 42 a 44 a 41 a 53 a 52 a 54 a 51 ] A P_{4}=\left[\begin{array}{llll} a_{13} & a_{12} & a_{14} & a_{11} \\ a_{23} & a_{22} & a_{24} & a_{21} \\ a_{33} & a_{32} & a_{34} & a_{31} \\ a_{43} & a_{42} & a_{44} & a_{41} \\ a_{53} & a_{52} & a_{54} & a_{51} \end{array}\right] AP4=⎣⎢⎢⎢⎢⎡a13a23a33a43a53a12a22a32a42a52a14a24a34a44a54a11a21a31a41a51⎦⎥⎥⎥⎥⎤
注意到， A P 4 AP_4 AP4事实上就是将原矩阵 A A A中的列的顺序重新调换后的结果。我们再来看看这是如何操作的：首先可以将A写为： A = [ a 1 , a 2 , a 3 , a 4 ] A = [a_1,a_2,a_3,a_4] A=[a1,a2,a3,a4] 其中 a n a_n an分别代表第 n n n列。 那么，根据线性代数基本知识，可知， A P 4 AP_4 AP4的第一列由 A p 1 Ap_1 Ap1给出，其中 p 1 p_1 p1代表 P 4 P_4 P4的第一列，也即： [ a 1 , a 2 , a 3 , a 4 ] [ 0 0 1 0 ] = a 3 [a_1,a_2,a_3,a_4]\left[\begin{array}{c}0\\0\\1\\0\end{array}\right] =a_3 [a1,a2,a3,a4]⎣⎢⎢⎡0010⎦⎥⎥⎤=a3 因此， A P 4 AP_4 AP4的第一列就是 A A A的第三列。 其他列的结果可类似得出。 好，我们可以发现其中的规律：
右乘置换矩阵的第 n n n列的非零元素在第 m m m行，则代表将第 m m m列换到第 n n n列。比如 P 4 P_4 P4第一列的1元素在第三行，因此就将 A A A的第3列换到第1列。 这也就是为什么置换矩阵的定义中，要求每一行，每一列均只有一个1的原因，只有这样才能保证最后的结果是将 A A A矩阵的列进行调换。
类似的，假如有： P 5 = [ 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 ] P_{5}=\left[\begin{array}{lllll} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{array}\right] P5=⎣⎢⎢⎢⎢⎡0000100100010000001010000⎦⎥⎥⎥⎥⎤ 则有： P 5 A = [ a 51 a 52 a 53 a 54 a 31 a 32 a 33 a 34 a 21 a 22 a 23 a 24 a 41 a 42 a 43 a 44 a 11 a 12 a 13 a 14 ] P_{5} A=\left[\begin{array}{llll} a_{51} & a_{52} & a_{53} & a_{54} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{41} & a_{42} & a_{43} & a_{44} \\ a_{11} & a_{12} & a_{13} & a_{14} \end{array}\right] P5A=⎣⎢⎢⎢⎢⎡a51a31a21a41a11a52a32a22a42a12a53a33a23a43a13a54a34a24a44a14⎦⎥⎥⎥⎥⎤ 其操作与右乘置换矩阵时类似。 对于左乘的置换矩阵，第 n n n行的非零元素在第 m m m列，则代表将第 m m m行调换到第 n n n行。
接下来介绍下置换矩阵的几个性质，对后面的推导将有所帮助：
- P T P = P P T = I P^TP=PP^T=I PTP=PPT=I，也就是说，置换矩阵是正交矩阵。因此我们也可知 P − 1 = P T P^{-1}=P^T P−1=PT。这也就是说，如果我们通过 P P P矩阵调换了行列的顺序，我们可以通过乘以其转置，将行列顺序复原。
- P T A P P^TAP PTAP与 A A A的对角线元素相同，但顺序可能不同。
接下来，我们讨论问题，如何求出逆矩阵 ( A T A ) − 1 (A^TA)^{-1} (ATA)−1的对角元素结果？
先给出结论为：
[ ( A T A ) − 1 ] n n = 1 a n T a n − a n T A n ( A n T A n ) − 1 A n T a n \left[\left(\mathbf{A}^{T} \mathbf{A}\right)^{-1}\right]_{n n}=\frac{1}{\mathbf{a}_{n}^{T} \mathbf{a}_{n}-\mathbf{a}_{n}^{T} \mathbf{A}_{n}\left(\mathbf{A}_{n}^{T} \mathbf{A}_{n}\right)^{-1} \mathbf{A}_{n}^{T} \mathbf{a}_{n}} [(ATA)−1]nn=anTan−anTAn(AnTAn)−1AnTan1
a n a_n an代表矩阵 A A A的第 n n n列。
我们不妨先考虑最后一个对角元素的求取。 将 A A A矩阵写为： A = [ A n a n ] A=\left[\begin{array}{ll}A_{n} & a_{n}\end{array}\right] A=[Anan]，因此 A T A = [ A n T A n A n T a n a n T A n a n T a n ] A^{T} A=\left[\begin{array}{cc} A_{n}^{T} A_{n} & A_{n}^{T} a_{n} \\ a_{n}^{T} A_{n} & a_{n}^{T} a_{n} \end{array}\right] ATA=[AnTAnanTAnAnTananTan] 此时，我们利用块对角矩阵求逆公式，即： [ A U V D ] − 1 = [ A − 1 + A − 1 U ( D − V A − 1 U ) − 1 V A − 1 − A − 1 U ( D − V A − 1 U ) − 1 − ( D − V A − 1 U ) − 1 V A − 1 ( D − V A − 1 U ) − 1 ] \left[\begin{array}{ll} \boldsymbol{A} & \boldsymbol{U} \\ \boldsymbol{V} & \boldsymbol{D} \end{array}\right]^{-1}=\left[\begin{array}{cc} \boldsymbol{A}^{-1}+\boldsymbol{A}^{-1} \boldsymbol{U}\left(\boldsymbol{D}-\boldsymbol{V} \boldsymbol{A}^{-1} \boldsymbol{U}\right)^{-1} \boldsymbol{V} \boldsymbol{A}^{-1} & -\boldsymbol{A}^{-1} \boldsymbol{U}\left(\boldsymbol{D}-\boldsymbol{V} \boldsymbol{A}^{-1} \boldsymbol{U}\right)^{-1} \\ -\left(\boldsymbol{D}-\boldsymbol{V} \boldsymbol{A}^{-1} \boldsymbol{U}\right)^{-1} \boldsymbol{V} \boldsymbol{A}^{-1} & \left(\boldsymbol{D}-\boldsymbol{V} \boldsymbol{A}^{-1} \boldsymbol{U}\right)^{-1} \end{array}\right] [AVUD]−1=[A−1+A−1U(D−VA−1U)−1VA−1−(D−VA−1U)−1VA−1−A−1U(D−VA−1U)−1(D−VA−1U)−1] 由于我们只关心最后一个对角元素，因此只考虑 ( D − V A − 1 U ) − 1 \left(\boldsymbol{D}-\boldsymbol{V} \boldsymbol{A}^{-1} \boldsymbol{U}\right)^{-1} (D−VA−1U)−1这一项， 我们把 D = a n T a n D=a_n^Ta_n D=anTan， V = a n T A n V=a_n^TA_n V=anTAn， U = A n T a n U=A_n^Ta_n U=AnTan和 A = A n T A n A=A_n^TA_n A=AnTAn代入，即可得到： [ ( A T A ) − 1 ] n n = 1 a n T a n − a n T A n ( A n T A n ) − 1 A n T a n \left[\left(\mathbf{A}^{T} \mathbf{A}\right)^{-1}\right]_{n n}=\frac{1}{\mathbf{a}_{n}^{T} \mathbf{a}_{n}-\mathbf{a}_{n}^{T} \mathbf{A}_{n}\left(\mathbf{A}_{n}^{T} \mathbf{A}_{n}\right)^{-1} \mathbf{A}_{n}^{T} \mathbf{a}_{n}} [(ATA)−1]nn=anTan−anTAn(AnTAn)−1AnTan1 因此，最后一个对角元素的取值得到了证明。接下来，考虑一般情况，假设要求取第 i i i个对角元素。 显然，存在置换矩阵 P P P，有: A P = [ A i , a i ] AP = [A_i, a_i] AP=[Ai,ai] 即将 A A A的第 i i i列 a i a_i ai调换到最后一列，而将最后一列调换到第 i i i列，其他列均不变。因此有： [ ( P T A T A P ) − 1 ] n n = 1 a i T a i − a i T A i ( A i T A i ) − 1 A i T a i [(P^TA^TAP)^{-1}]_{nn} =\frac{1}{\mathbf{a}_{i}^{T} \mathbf{a}_{i}-\mathbf{a}_{i}^{T} \mathbf{A}_{i}\left(\mathbf{A}_{i}^{T} \mathbf{A}_{i}\right)^{-1} \mathbf{A}_{i}^{T} \mathbf{a}_{i}} [(PTATAP)−1]nn=aiTai−aiTAi(AiTAi)−1AiTai1 此时注意到：根据 P − 1 = P T P^{-1}=P^T P−1=PT，我们有： ( P T A T A P ) − 1 = P T ( A T A ) − 1 P (P^TA^TAP)^{-1}=P^T(A^TA)^{-1}P (PTATAP)−1=PT(ATA)−1P 也就是说， ( P T A T A P ) − 1 (P^TA^TAP)^{-1} (PTATAP)−1是将 ( A T A ) − 1 (A^TA)^{-1} (ATA)−1的第 i i i列与最后一列调换，第 i i i行与最后一行调换后的结果。换言之， 我们刚刚求取的 ( P T A T A P ) − 1 (P^TA^TAP)^{-1} (PTATAP)−1的最后一个对角元素就是 ( A T A ) − 1 (A^TA)^{-1} (ATA)−1的第 i i i个对角元素！因此，得证。
对此其实我们也可以看出：
调换顺序后求逆，等价于求逆后再调换顺序，不过前提是形式应为 ( A T A ) − 1 (A^TA)^{-1} (ATA)−1。
