目录
Schedule
- Inverse of AB, A^T
- Product of elementation matrices
- $A=LU$ (no row exchanges)
Inverse of AB, A^T – AB 和 A^T 的逆
假设 A , B 均可逆,那么 AB 的逆是什么?
AB 的逆是 A 的逆和 B 的逆的逆序相乘,也就是 B^{-1}A^{-1} .
这就像是穿袜子,穿鞋子,所以脱下来也得先脱鞋子再脱袜子.
对于某可逆方阵来说,其转置矩阵的逆是?
对于 AA^{-1}=I 同时进行转置,得到 (A^{-1})^T(A)^T=I .
从而得知对于可逆方阵 A来 说,其转置矩阵 A^T 的逆是 (A^{-1})^T .
注意, 这里提到的是方阵, A^{T} 也是方阵, 故 A^{T} 的左逆和右逆相同.
所以才可以说其转置矩阵 A^T 的逆是 (A^{-1})^T .
为什么对于 AA^{-1} 的转置是 (A^{-1})^T(A)^T ?
假设 A 为 m\times n 矩阵, B 为 n\times p 矩阵,两者均可逆,
则进一步设 AB=C ,其中 C_{ij}=\sum_{k=1}^nA_{ik}B_{kj}.
设 B^TA^T=D ,其中 D_{ij}=\sum_{k=1}^nB^T_{ik}A^T_{kj}.
因为 B^T_{ik} = B_{ki}, A^T_{kj} = A_{jk}, 所以 D_{ij}=\sum_{k=1}^nB^T_{ik}A^T_{kj} = \sum_{k=1}^nA_{jk}B_{ki} = (AB)^T
从而实现证明 (AB)^T=B^TA^T
Product of elimination matrices – 消元矩阵的乘积
对于主元全部非0的可逆矩阵 A ,经过消元后得到 U , 那么对于 A=LU 如何求解 L ?
e.g. 假设有矩阵 A=\begin{bmatrix}2&1\8&7\end{bmatrix} ,经过转换 E_{21}=\begin{bmatrix}1&0\-4&1\end{bmatrix} ,得到矩阵 U=\begin{bmatrix}2&1\0&3\end{bmatrix} , 即:
\begin{bmatrix}1&0\-4&1\end{bmatrix}*\begin{bmatrix}2&1\8&7\end{bmatrix}=\begin{bmatrix}2&1\0&3\end{bmatrix}
对于想求解的 L ,可以从 A=LU 得知, L=E^{-1} ,所以 L=\begin{bmatrix}1&0\4&1\end{bmatrix}.
这里 U 表示的是上三角(Upper triangular)矩阵,而 L 代表的是下三角(Lower triangular)矩阵.
有时候会将主元单独列出来组合一个矩阵,从而形成 A=LDU 的形式. 这里D指的是对角矩阵(Diagonal Matrix).
\begin{bmatrix}2&1\8&7\end{bmatrix}=\begin{bmatrix}1&0\4&1\end{bmatrix} \cdot \begin{bmatrix}2&1\0&3\end{bmatrix}=\begin{bmatrix}1&0\4&1\end{bmatrix} \cdot \begin{bmatrix}2&0\0&3\end{bmatrix} \cdot \begin{bmatrix}1&\frac{1}{2}\0&1\end{bmatrix}
对于 E_{32}E_{31}E_{21}A=U (no row exchanges)的情况下, 如果想得到 A=LU 中的 L ,则可以得出 L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}
对于3维矩阵来说,假设存在如下的变换使得 EA=U ,同时 E_{31}=I ,那么:
\begin{bmatrix}1&0&0\0&1&0\0&-5&1\end{bmatrix} \cdot \begin{bmatrix}1&0&0\-2&1&0\0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\-2&1&0\10&-5&1\end{bmatrix}=E\leftarrow(EA=U)\
\begin{bmatrix}1&0&0\2&1&0\0&0&1\end{bmatrix} \cdot \begin{bmatrix}1&0&0\0&1&0\0&5&1\end{bmatrix}=\begin{bmatrix}1&0&0\2&1&0\0&5&1\end{bmatrix}=L\leftarrow(A=LU)
对于 A=LU ,如果不存在行互换,消元乘数(即消元步骤中需要乘以并减去的倍数)可以直接写入 L 中.
If no row exchanges, multipliers go directly into L.
对于大小为 n \times n 的矩阵 A 的消元,其总步骤数共有多少? 消元的总步骤数是否正比于 n 或 n^2 或 n^3 ?
假设 n=100 , 并且矩阵 A 中没有0(如果有很多0的话操作会快很多), 将一次操作定义为针对一个元素的一次乘法和加法.
第一行不变,将其他行的首个元素系数消除,将进行大约100^2次操作(如果第一行也发生变化的话就正好是100^2次,准确的数字应该是100*99),
同样对第二行进行消元,第二行不变,将第二主元下所有其他系数消除,则进行大约99^2次操作,
依次进行下去,最终总操作数为 Count=n^2+(n-1)^2+\cdots+1^2= \frac{1}{3}n^3
同时,对于右侧的常数向量 b ,总共需要进行 n^2 次操作.
Transposes and Permutations – 转置和置换
对于3维矩阵来说,其置换矩阵有限,如下列举(即互换单位阵各行的所有可能情况),共有 6P ,并且 P^{-1}=P^T :
\begin{bmatrix}1&0&0\0&1&0\0&0&1\end{bmatrix}, \begin{bmatrix}0&1&0\1&0&0\0&0&1\end{bmatrix},\begin{bmatrix}0&0&1\0&1&0\1&0&0\end{bmatrix},\begin{bmatrix}1&0&0\0&0&1\0&1&0\end{bmatrix},\begin{bmatrix}0&1&0\0&0&1\1&0&0\end{bmatrix},\begin{bmatrix}0&0&1\1&0&0\0&1&0\end{bmatrix}