前言

最近在预习线性代数 (实际上什么也没学懂) 随便写几篇博客水一水，主要是很久没写博客了。

正文

话不多说，直接开始！

矩阵乘法

暴力操作显然是可以做到 $O(n^3)$​ 这也是它的实用复杂度，然而有很多优化的计算方法。

以下几种算法均基于矩阵分块。

Strassen算法

通过将矩阵分为2*2，通过设置中间变量的方式将原本8次乘法优化为7次乘法和18次加法。

如此通过主定理即可求出时间复杂度

\[T(n)=7*T(n/2)+T(n^2)\\ T(n)=O(n^{\log_27})\approx O(n^{2.81})\]

目前最优算法时间复杂度约为 $O(n^{2.37})$ ，推荐一下这篇文章，但我好像看不太懂。

此外多线程，GPU等均可优化矩阵乘法。

矩阵求逆

矩阵求逆可以通过矩阵的初等变换实现 $O(n^3)$ 的矩阵求逆。伴随矩阵法似乎更慢。

然而我们有一下公式

\[\left[ \begin{array}{cc} A & B\\ C & D\\ \end{array} \right] ^{-1}= \left[ \begin{matrix} A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} & -A^{-1}B(D-CA^{-1}B)^{-1}\\ -(D-CA^{-1}B)^{-1}CA^{-1} & (D-CA^{-1}B)^{-1}\\ \end{matrix} \right]\]

观察到有2个小矩阵求逆，6个矩阵乘法。

因此矩阵求逆时间复杂度等价于矩阵乘法

行列式

通过行列式的变换可以实现 $O(n^3)$ 的行列式计算

此外，我们可以推导

\[\det \left[ \begin{matrix} A & B\\ C & D\\ \end{matrix} \right]= \left[ \begin{matrix} A & 0\\ C & D-CA^{-1}B\\ \end{matrix} \right]= \det(A)det(D-CA^{-1}B)\]

线性方程组

我们可以高斯消元，克莱姆法则，但我们都会求逆矩阵了，我们就可以直接乘以逆矩阵解线性方程组。