置换矩阵的应用：逆矩阵的对角线元素求法

置换矩阵是一种非常实用的数学工具，其确切定义如下：

一个正方矩阵，若其每一行和每一列有且仅有一个非零元素 $1$ ，则称之为置换矩阵。

顾名思义，其作用是：

当将某一矩阵左乘置换矩阵，相当于将矩阵的行重新排列。而右乘置换矩阵，则相当于对列重新排列。

因此，当我们想对矩阵的行或列重新排列时，就可以等效地将其写为左/右乘置换矩阵的形式。插一句题外话，对某矩阵左乘一个对角阵，相当于对其每一行都分别乘上对应的对角元素。右乘一个对角阵，则相当于每一列乘上一个对角元素。因此，左乘代表对行操作，右乘代表对列操作。

以一个实例来说明，假设有如下矩阵：

$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]$

注意到， $AP_4$ 事实上就是将原矩阵 $A$ 中的列的顺序重新调换后的结果。我们再来看看这是如何操作的：首先可以将A写为：
$A = [a_1,a_2,a_3,a_4]$
其中 $a_n$ 分别代表第 $n$ 列。那么，根据线性代数基本知识，可知， $AP_4$ 的第一列由 $Ap_1$ 给出，其中 $p_1$ 代表 $P_4$ 的第一列，也即：
$[a_1,a_2,a_3,a_4]\left[\begin{array}{c}0\\0\\1\\0\end{array}\right] =a_3$
因此， $AP_4$ 的第一列就是 $A$ 的第三列。其他列的结果可类似得出。好，我们可以发现其中的规律：

右乘置换矩阵的第 $n$ 列的非零元素在第 $m$ 行，则代表将第 $m$ 列换到第 $n$ 列。比如 $P_4$ 第一列的1元素在第三行，因此就将 $A$ 的第3列换到第1列。这也就是为什么置换矩阵的定义中，要求每一行，每一列均只有一个1的原因，只有这样才能保证最后的结果是将 $A$ 矩阵的列进行调换。

接下来介绍下置换矩阵的几个性质，对后面的推导将有所帮助：

$P^TP=PP^T=I$ ，也就是说，置换矩阵是正交矩阵。因此我们也可知 $P^{-1}=P^T$ 。这也就是说，如果我们通过 $P$ 矩阵调换了行列的顺序，我们可以通过乘以其转置，将行列顺序复原。
$P^TAP$ 与 $A$ 的对角线元素相同，但顺序可能不同。

接下来，我们讨论问题，如何求出逆矩阵 $A^TA)^{-1}$ 的对角元素结果？

先给出结论为：

$\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}}$

$a_n$ 代表矩阵 $A$ 的第 $n$ 列。

我们不妨先考虑最后一个对角元素的求取。将 $A$ 矩阵写为： $A=\left[\begin{array}{ll}A_{n} & a_{n}\end{array}\right]$ ，因此
$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]$
此时，我们利用块对角矩阵求逆公式，即：
$\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]$
由于我们只关心最后一个对角元素，因此只考虑 $\left(\boldsymbol{D}-\boldsymbol{V} \boldsymbol{A}^{-1} \boldsymbol{U}\right)^{-1}$ 这一项，我们把 $D=a_n^Ta_n$ ， $V=a_n^TA_n$ ， $U=A_n^Ta_n$ 和 $A=A_n^TA_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}}$
因此，最后一个对角元素的取值得到了证明。接下来，考虑一般情况，假设要求取第 $i$ 个对角元素。显然，存在置换矩阵 $P$ ，有:
$AP = [A_i, a_i]$
即将 $A$ 的第 $i$ 列 $a_i$ 调换到最后一列，而将最后一列调换到第 $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}}$
此时注意到：根据 $P^{-1}=P^T$ ，我们有：
$P^TA^TAP)^{-1}=P^T(A^TA)^{-1}P$
也就是说， $P^TA^TAP)^{-1}$ 是将 $A^TA)^{-1}$ 的第 $i$ 列与最后一列调换，第 $i$ 行与最后一行调换后的结果。换言之，我们刚刚求取的 $P^TA^TAP)^{-1}$ 的最后一个对角元素就是 $A^TA)^{-1}$ 的第 $i$ 个对角元素！因此，得证。