关于矩阵的冷芝士

#### 这是关于矩阵的一个~~bug~~blog 矩阵是个有趣（并有着广泛应用）的东西， 不过矩阵这玩意儿貌似和线性代数以及向量之类的东西相关，所以学了绝对不亏 **另外，本篇blog 并不一定毫无错误，所以请各位观看的神仙及时指出好让作者修改精进，谢谢。** 还有矩阵求逆的两种方法将会放在最后讲解 ----- ----- ---- 想要学会矩阵求逆的话，首先你得了解几个关于矩阵的概念以及名称的含义 （当然如果你知道这些概念的话可以直接往下跳） # 基本概念 ## 1.矩阵以及矩阵的阶 下图是一个三阶矩阵： ## $$\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}$$ 注意，这里两边的中括号包含所有的 $9$ 个数字。 （即左括号与$1$、$4$、$7$同高，右括号与$3$、$6$、$9$同高，下同） 从这个例子中我们可以看出：一个** 3 行 3 列的矩阵叫做 3 阶矩阵** 具体来讲我们管 **$n*n$ 的矩阵叫做 $n$ 阶矩阵** （下文逆矩阵部分中不加说明的一般就是 $n$ 阶的矩阵） 但如果有一个矩阵是 $2*3$ 的，那么我们称它为 $2*3$ 阶矩阵 更具体的说，**对于 $n*m\ (n\not=m)$的矩阵，我们称它为 $n*m$ 阶矩阵** ## 2. 矩阵的一般运算(一)【矩阵加法】 对于 $A$、$B$ 两个矩阵相加，即矩阵 $A+B$ ，这个运算的结果就是**所有位置上的数一 一对应相加**后所得到的矩阵。 那么 $A$、$B$ 两个矩阵可以进行加法运算的条件就是**两矩阵同阶**（关于阶的概念就在上面） 举个例子： ### $$\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix} + \begin{bmatrix}2&3&5\\6&7&6\\8&3&2\end{bmatrix}=\begin{bmatrix}1+2&2+3&3+5\\4+6&5+7&6+6\\7+8&8+3&9+2\end{bmatrix}=\begin{bmatrix}3&5&8\\10&12&12\\15&11&11\end{bmatrix}$$ 可以看出，这就是简单的加法。 文字描述一下就是： 我们首先将将两个矩阵所有位置一 一对应， 然后我们将各个位置上的两个数相加， 最后将得到的值放回原位置，形成新的矩阵， 并且我们可以得到几个朴素的性质： >>1.结合律： $A+(B+C)=(A+B)+C$ >>2.交换律： $A+B=B+A$ 然后矩阵加法相关的题，我还真没见到过... 至于矩阵减法的运算也与加法类似 ## 3.矩阵的一般运算(二)【矩阵乘法】 这玩意儿详细讲的话又可以写一篇博客了。（比如什么快速幂啊、构造矩阵啊、递推加速啊还有一堆习题什么的。。。） 于是这里我就讲讲一点概念。 首先， $A*B$ 不是随便就能乘的，是要有条件的（和加法类似） 两个矩阵 $A$、$B$ 可以进行乘法运算的条件就是** $A$ 的列数与 $B$ 的行数相等** 举个例子（$2*2$阶 $\times$ $2*2$阶 的矩乘好了）： ### $$\begin{bmatrix}1&2\\4&3\end{bmatrix} \times \begin{bmatrix}5&3\\2&1\end{bmatrix}=\begin{bmatrix}1*5+2*2&1*3+2*1\\4*5+3*2&4*3+3*1\end{bmatrix}=\begin{bmatrix}9&5\\26&15\end{bmatrix}$$ 然鹅这个例子并不能清晰的看出运算法则，于是我们用字母代替数字： ## $$\begin{bmatrix}a&b\\c&d\end{bmatrix} \times \begin{bmatrix}e&f\\g&h\end{bmatrix}=\begin{bmatrix}a*e+b*g&a*f+b*h\\c*e+d*g&c*f+d*h\end{bmatrix}$$ 那么用文字描述的话就是： 我们选定矩阵 A 的第 i 行以及矩阵 B 的第 j 列， 将他们取出来一 一相乘得到一个值， 然后将该值作为结果矩阵第 i 行第 j 列的值， 重复以上步骤后我们最终就可以得到一个新矩阵 此外，矩阵乘法也满足一些性质： >>1.结合律： $A*(B*C)=(A*B)*C$ >>2.~~交换律~~（不满足）： $A*B != B*A$ >>为什么不满足交换律？证明很简单。 >>一个$2*3$阶矩阵$\times$ $3*2$阶的矩阵结果是$2*2$阶的矩阵， >>但是交换后呢？结果就变成了$3*3$阶的矩阵，连阶数都不一样了 >>3.分配律： $A*(B+C)=A*B+A*C$ >>分配律的证明不难（甚至可以硬推），就留给读者自己证明了 那么矩乘有什么意义？~~你问我我问谁~~ 咳咳。这里就涉及到了另一个芝士：**多维向量的乘积可以由矩乘运算得到** 此外，矩乘还有一些其他的实际应用吧，这里我们就不做深究了 至于矩乘的代码呢，还是经常要用的，于是下面给出（结构体代码） ``` struct matrix{ ll a[M][M]; ll* operator [](int x){ return a[x]; } matrix operator *(matrix& b){ static matrix c; for(int i=1;i<=3;++i) for(int j=1;j<=3;++j) c[i][j]=0; for(int i=1;i<=3;++i) for(int j=1;j<=3;++j) for(int k=1;k<=3;++k) c[i][j]+=a[i][k]*b[k][j],c[i][j]%=mod; return c; } inline void print(){ for(int i=1;i<=n;++i,putchar('\n')) for(int j=1;j<=n;++j,putchar(' ')) putchar('0'+a[i][j]); } }F,T; ``` emmm...这里扯点别的，就是**关于 [ ] 的重载**。 这里重载[ ] 之后，我们就可以直接像用数组一样地调用结构体了 比如 原来的 $F.a[i][j]$ 我们可以直接写成 $F[i][j]$ 了 ### 第二种矩阵乘法：矩阵的数乘 这里还有一种矩阵乘法叫做**数乘**，就是**一个实数乘以一个矩阵**，结果其实就是矩阵中的每个元素乘上这个常数，这里就不详解了 ---- 矩乘讲完了。$but$，说完乘法你是不是想到了除法？emmm... 矩除？不存在的。最多是乘以它的逆矩阵？ 于是下面进入逆矩阵部分了 ---- ## 4.单位矩阵 **我们将单位矩阵写作 E ，并且单位矩阵都是 $n$ 阶矩阵** 比如一个 $3$ 阶的单位矩阵长这样： ## $$\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}$$ 如上，单位矩阵就长这样。 那么单位矩阵满足什么性质呢？ >>1.一个矩阵乘上单位矩阵结果是它本身： $A*E=A$ emmm...就这一个性质比较常见。你可以将单位矩阵类比自然数 1 。 ## 5.逆矩阵 **对于一个矩阵 $A$ ，我们将它的逆矩阵写作 $A'$ 或者 $A^{-1}$ ** 那么逆矩阵满足什么性质？ >>1.矩阵 $A$ $\times$ 它的逆矩阵 $A^{-1}$ 的结果是单位矩阵 E ： $A*A^{-1}=E$ 从这里我们可以看出，逆矩阵与[乘法逆元](https://www.cnblogs.com/Judge/p/9383034.html)倒有些相似之处 其实逆矩阵还有一个性质，等下就会讲到了。 emmm...原本是本博客重头戏的逆矩阵，篇幅就这么短...~~还给自己当广告位了~~ ## 6.阶梯型矩阵 阶梯型矩阵其实就是一个矩阵 $A$ 经过**矩阵初等变换**的洗礼后得到**梯形矩阵**。 (其实上面是一般矩阵的阶梯型矩阵定义，对于 n 阶矩阵，它的阶梯型矩阵一般是一个上三角...) 阶梯型矩阵满足条件：每行的不为零的首元按标号呈升序。（百科上的，貌似也不难理解） 举个例子： ## $$\begin{bmatrix}9&5&3&4\\0&6&1&5\\0&0&3&2\\0&0&0&8\end{bmatrix}$$ 注意，阶梯型矩阵每行首元不一定为 $1$ ，更没有强制为 $1$ ，每行首元为 $1$ 的矩阵并不是阶梯型矩阵，仅仅是高斯消元中用来**求方程组的解**所用的矩阵，首元为 $1$ 是为了**方便求解**，请读者不要将两个东西混为一谈，真正的阶梯型矩阵仅使用**矩阵初等变换**即可解出，这里稍微提一下。 那么阶梯型矩阵怎么求呢？ $that's a question.$ 我只能说，了解一下**高斯消元**吧！【模板】高斯消元法：点[这里](https://www.luogu.org/problemnew/show/P3389) 尽管上面说了，阶梯型矩阵严格来讲并不是通过高斯消元求解的，但是与高斯消元的还是有很多相似的运算的 ## 7.矩阵的秩 几何意义上来讲（其实就是线性代数角度吧？），**一个矩阵的秩（rank）**代表这个矩阵**能够跨越的维度数**（没错，就是说**秩为 $x$ 的矩阵**通过每个元素乘以一个**实数**后可以表示**任意的 $x$ 维向量**） 矩阵的秩与**线性相关**这一概念联系非常大 这里有两句关于行秩和列秩的解释： 一个矩阵A的列秩是A的线性独立的纵列的极大数 一个矩阵A的行秩是A的线性独立的横行的极大数 emmm...百度百科貌似都是写给懂的人看的（谁 $TM$ 懂线性相关还不会矩阵的啊！） 行秩和列秩的话，通俗来讲是这样的： 将矩阵做初等行变换后，非零行的个数叫行秩 将其进行初等列变换后，非零列的个数叫列秩 那么你可以理解为一个矩阵的**阶梯型矩阵**中**非零行数** 就是行秩，列秩同理（阶梯型矩阵上文刚刚讲完）。 那么我们可以看出，一个矩阵的行秩与列秩必然相等。 为什么？你试试将一个矩阵对角线翻转一下不就好了？（哎呀这不是矩阵的转置么，等会儿会讲的） 假如说一个矩阵的秩等于它的阶，那么就说这个矩阵**满秩**。 那么如果一个矩阵的秩小于他的阶，那么这个矩阵被称为**奇异矩阵**。 所以如果一个矩阵的秩大于它的阶呢？咳咳，这种情况不存在，**秩数最多等于阶数**。 那么如何计算一个矩阵的秩数？我们可以用定义法求解，就是像上面说的将原矩阵化作阶梯型矩阵然后计算出**非零行数**。 但如果是小数据的人工计算的话，你可以依据**矩阵中有多少行**不能由**矩阵的其他行**变换得到，来求解矩阵的秩（这不是和求解阶梯型矩阵差不多么） 举个例子： ## $$\begin{bmatrix}1&2&3\\2&2&4\\5&6&11\end{bmatrix}$$ 这个矩阵中的第三行就可以通过：(第一行$\times 1$ + 第二行 $\times 2$) 得到 ## $$\begin{bmatrix}1&2&3\\2&2&4\\0&0&0\end{bmatrix}$$ 如果一个矩阵长上面这样，那么这个矩阵的第三行其实也是可以通过其他行乘上 $0$ 得到的，所以这个矩阵是**线性相关**的 这么讲，如果矩阵的某一行可以由其他行拼凑而成的话，那其实我们可以看出这一行元素在线代角度看对**更高维向量的表示**是没有用的，因为它可以由其他行元素拼出来，没有什么存在的价值 这也就是**线性相关**的大致概念了（话说**线性基**里面好像也有线性相关来着，如果你会[线性基](https://www.luogu.org/problemnew/solution/P3812)理解起来会轻松很多吧） 那如果我只是判断当前矩阵是否**满秩**，或者是否是**奇异矩阵**呢？这样的话，我们除了上面**直接把秩数求出来**之外，还有一种方法，就是求**行列式**，关于行列式的求解就在下一节。 ## 8.矩阵的行列式 对于一个矩阵 $A$ ，它的**行列式记作 $|A|$** 举个例子，3阶的行列式的运算是这样的： ## $$|A|=|\begin{matrix}a&b&c\\d&e&f\\g&h&i\end{matrix}|$$ (这里的竖线 $markdown$ 好像还是不能表示) 行列式有着它的**几何意义**（还是线性代数上的）， 就是说 某个矩阵 乘上矩阵 $A$ ，其**有向体积**将会**扩大为原来的 $|A|$ 倍**（准确来说不能讲体积，这个我也不知如何形容，请感性理解） 然后注意这里的体积是有向的（就是说体积有可能神奇的取到负值）。 举个例子，一个 $2$ 阶矩阵 $A$ 的行列式是 $|A|$，那么某个矩阵**乘上 $A$ 后**（当然是满足相乘条件的情况下），这个矩阵在线性代数的平面内表示的**面积**将会扩大 $|A|$ 倍（也就是面积乘上了$|A|$） 至于 $3$ 阶矩阵 $A$ ，某矩阵乘上它后，**体积**就会扩大 $|A|$ 倍。 还有**行列式的用途**，这个其实就是上面提及的，判别矩阵是否**满秩**（或者是否是**奇异矩阵**） ### 那么如何计算矩阵 $A$ 的行列式？ 这个嘛...意会了就觉得不是很难，这里给出两个例子~~聪明的~~你应该就能看懂了 ### eg1:$$ |A|=|\begin{matrix}a&b\\c&d\end{matrix}|=ad-bc$$ 二阶行列式就是**左下右上减右上左下**嘛... 这个二阶的行列式运算还是蛮有意义的（前方线代高能预警！） 其实这个运算就相当于**两个二维向量的叉积** 所谓叉积的**几何意义**其实就是两个向量在二维平面上围出的**平行四边形的面积**，这个看完视频很快就会懂了 ### eg2:$$|A|=|\begin{matrix}a&b&c\\d&e&f\\g&h&i\end{matrix}|=a(ei-fh)-b(di-fg)+c(dh-eg)$$ ### <1>行列展开 那么在这里，我是用行列展开求解的。具体的运算方法得到余子矩阵那里讲（额，剧透了） 不过你可以先看看图解： .................... ### <2>对角线法则 emmm...对于三阶矩阵的行列式运算，还有一种方法，叫做对角线法则，但很遗憾，对角线法则**仅适用于二、三阶矩阵**的行列式运算。 下图就是对角线法则的图解，其中实线是加，虚线是减：  然后求解行列式的话一般来说最多也就让你求二阶或者三阶的，阶再高的话就是计算机的事儿了  另外讲讲同学（bzt大佬%%%）说的做法，$TA$ 的做法是这样的： ### <3>逆序定义法 考虑每行取一个元素，且最终取出的 $n$ 个元素任意两个不在同一列，然后这 $n$ 个数相乘，之后就是一些加减运算了，至于对行列式贡献的正负性，貌似是选出元素**相对位置**的**逆序对个数**的**奇偶性**决定的，咳咳。。。 然后下面是图解：  当然我们可以看出这个方法复杂度有点高，是 $O(n!\times n \log n)$ 的，所以这是人工求的时候才可能采用的方法。 ### <4>初等行列变换 之前说矩阵的时候有讲到过这个东西，在这里的作用其实也就是将原矩阵转换成一个**上三角矩阵**（没错，还是上文说的**阶梯型矩阵**！），当我们求出了这个上三角矩阵（阶梯型矩阵）**对角线上所有元素的乘积**就是原矩阵的行列式值了 这里说是初等行列变换，但网上都说这是高斯消元求解行列式，emmm...但是**行列式**的计算不能直接用到**数乘**的啊！ 如果要问为什么的，你可以想想，假如是一阶矩阵（不为 $0$），那么它随便乘上一个数，行列式就已经改变了，所以单一行的转换是不能用到**数乘**的。 所以请注意：初等行列变换不包含**数乘**（关于**矩阵数乘**的概念在第二节中已经讲过了） 那么这个~~高斯消元法~~行列变换的算法就不详细讲解了，读者可以到[这个博客](https://www.cnblogs.com/GerynOhenz/p/4450417.html)里面去看，这个作者已经写的很详细了，另外那些性质什么的这个博客里面也有（甚至逆序对求法也讲了一丢丢），本博客就不再给出，以节省博客篇幅**~~主要是作者懒~~** 然后这个算法的复杂度？ $O(n^{3})$ 吧... 还有，**行列式**这块对于矩阵比较重要，所以**建议**这个东西要至少理解七八成。 鉴于作者有自知之明，知道自己讲的肯定没有那么生动（毕竟是文字描述），那么就附上一个 B 站上的视频，好让读者们更好理解行列式： ## 视频点[这里](https://www.bilibili.com/video/av6179111?from=search&seid=13830609406234897807) 而对于之前提到的秩呢，这个概念同样很重$(nan)$要$(dong)$，毕竟是和线性相关有联系的，所以也附上个 B 站上的视频： ## 视频点[这里](https://www.bilibili.com/video/av6240005?from=search&seid=13319076494660794774) ---- 记得想学伴随矩阵的求法时看到了一个“矩阵三连”，特别有意思：**伴随矩阵是余子矩阵的转置矩阵**。 $woc$，三个里面没有一个会的，怎么办，我还有救么...（这时候好想开个$Venus$三连：**跳起来，敌敌畏，膜膜膜**） 咳咳，之后我就了解了下这三个矩阵的概念。 --- ## 9.转置矩阵 我们将矩阵** $A$ 的转置矩阵写作 $A^{T}$** 转置矩阵这玩意儿其实非常好理解。 一个矩阵的转置矩阵其实就是它 $(i,j)$ 位置上的数与 $(j,i)$ 位置上的数交换了一下。 讲道理，转置矩阵其实就是将原矩阵左下、右上对角线翻转了一下罢了。 所以矩阵转置完有什么用？~~我也想知道啊！~~ ~~结论：矩阵转置可以令书面表示更省空间（原本是列向量可以写成某个行向量的转置）~~ 此外，一个** $n*m$ 阶的普通矩阵**的转置也是右上左下翻转，转置后的矩阵为一个** $m*n$ 阶的矩阵** ## 10.伴随矩阵 我们将矩阵** $A$ 的伴随矩阵写作 $A^{*}$** （不是那个搜索算法啦 【笑哭） 但对于这玩意儿我只知道它的定义以及一些性质，至于求法？emmm... 一个矩阵 $A$ 的伴随矩阵要满足一下性质： $$A\times A^{*}=|A|\times E$$ 就是说 $A$ 乘上它的**伴随矩阵 $A^{*}$ **之后，结果是**单位矩阵 $E$ 的 $|A|$ 倍** 其次，伴随还满足一系列性质： >>1.如上，$A\times A^{*}=|A|\times E$ >>2.$A$ 的伴随矩阵为其逆矩阵的 $|A|$ 倍： $A^{*}=|A|\times A^{-1}$ >>3.原矩阵和伴随矩阵之间秩的关系： >>>当 $rank(A) = n$ 时, $rank(A^{*}) = n$ >>>当 $rank(A) = n-1$ 时, $rank(A^{*}) = 1$ >>>当 $rank(A) < n-1$ 时, $rank(A^{*}) = 0$ >>4.原矩阵和伴随矩阵之间行列式的关系： $|A^{*}|=|A|^{n-1}$ >>5.当原矩阵可逆时，伴随矩阵可逆：$?B=A^{-1} ? ?C=(A^{*})^{-1}$ 第二个性质就是之前讲逆矩阵的时候没说说的性质，这个性质很好证吧？因为有第一个性质啊！ 第三个性质，死记吧... 第五个性质的话可以运用第三个性质证明...~~满秩的矩阵肯定存在逆矩阵嘛...~~ emmm...其实这里是有证明的啦，当然还是让读者自行解决的好 不过这里还是有个性质没讲，就是伴随矩阵是余子矩阵的转置矩阵什么的，但这个不重要，学完余子矩阵之后你强行代数也可证明。 回到之前说的，伴随矩阵的求法。这个的话，你会逆矩阵的求法就能解出伴随矩阵了（不难懂吧） 但还有另一个求法，不过要用代数余子式求，那就是接下来的内容了 ## 11.（代数）余子式与（代数）余子矩阵 其实你看懂了行列式的话这里就很好理解了。 首先，余子式是**对于矩阵 $A$ 中的一个元素 $A_{i,j}$ 而言**的一个**数值（标量）**，而余子矩阵则是** $A$ 中所有元素的余子式**所构成的一个新矩阵。 那么如何计算矩阵元素 $A_{i,j}$ 的余子式呢？ 方法就是： 先**将原矩阵 $A$ 的第 $i$ 行、第 $j$ 列消掉**，然后求剩下的 **$n-1$ 阶矩阵的行列式**，这样我们就得到了 **$A_{i,j}$ 的余子式**，这时如果将这个元素的余子式乘上 $(-1)^{i+j}\times A_{i,j}$ ，求得的值就是 $A_{i,j}$ 的**代数余子式**，并且由原矩阵中所有元素**代数余子式**构成的矩阵就是原矩阵的**代数余子式矩阵**（之前说余子矩阵可以认为是这玩意儿的缩写），而它的转置矩阵就是上一节说的**伴随矩阵**了 但是证明呢？为什么余子式矩阵的转置矩阵就是伴随矩阵了？这个你可以用定义来解： >>>由于行列式等于**某一行所有元素与其对应代数余子式的乘积之和**， >>>又因为**伴随矩阵的定义**就是与原矩阵相乘结果为单位矩阵的行列式倍， >>>所以这时我们可以将余子矩阵转置一下，让它的任意一行元素**以列的方式排布**， >>>然后就可以和原矩阵愉快地乘起来，得到定义中的**单位矩阵的行列式倍**的矩阵了。 至于更加详细的证明推导，就留给读者吧 emmm...所以这就是上文伴随矩阵中说的另一种求法啦 那么在 **8.行列式** 中作者提到的行列展开其实就是用到了**代数余子式**这个东西，毕竟2阶矩阵的行列式还是好算的嘛 但是为什么代数余子式能够用来求行列式呢？这是个问题，但作者太菜了解决不了，如果你感兴趣的话可以花些时间强行代数证明一下加深影响，或者就是**背个结论**就好了 从上面我们可以看出，用**代数余子式求解行列式**是非常非常烦的一件事（虽说对于小型矩阵尤其是三阶的还是很方便的），这个算法的复杂度已经高达 $n!$ 了！所以一般来讲用初等行列变换求行列式才是明智的选择。 不过这个方法还是可以用来娱乐一下的，比如这里有一份网上来的代码，我就加了点常数优化什么的。 ``` //by Judge #include<bits/stdc++.h> using namespace std; int **array = NULL,m; int** pArray(int **array, int m) { for (int i = 0,j; i < m; ++i,puts("||")) for (printf("||")j = 0; j < m; ++j) printf("%d\t", array[i][j]); return array; } int** inputArray(int** array, int m) { for (int i = 0,j; i < m; ++i,puts("||")) for (printf("||"),j = 0; j < m; ++j) cin >> array[i][j]; return array; } double calMatrix(int ** temp, int m) { int **Matrix = NULL,i; double result=0; if (m == 1) return temp[0][0]; if (m == 2) return temp[0][0]*temp[1][1]-temp[0][1]*temp[1][0]; for (i = 0; i < m; ++i) { Matrix = (int**)malloc(sizeof(int *)*(m-1)); for (int k = 0; k < m - 1; ++k) Matrix[k] = (int *)malloc(sizeof(int)*(m - 1)); for (int k = 1,a=0; k < m&&a<m-1; ++k,++a) for (int j = 0,b=0; j < m&&b<m-1; ++j) if(i^j) Matrix[a][b++] = temp[k][j]; result+=temp[0][i]*pow(-1,i)*calMatrix(Matrix,m-1); } return result; } int main() { printf("please input the matrix order:\n");//输入矩阵阶数 cin >> m,array = (int**)malloc(sizeof(int*)*m); for (int i = 0; i < m; ++i) array[i] = (int*)malloc(sizeof(int)*m); printf("input the array:\n"); inputArray(array, m); // printf("the array you input:\n"); //输出输入的矩阵 // pArray(array, m),puts(""); puts("the value of the matrix is: "); cout<<calMatrix(array, m)<<endl; //输出行列式 return system("pause"),0; } ``` 有点工程级别的感觉... 话说这个仅供娱乐（千万别拿去交了，交了八成就是 $T$ 飞） ---- 然后这些基础知识就大概是告一段落了，接下来就愉快的开始矩阵求逆啦~ --- # 重头戏 · 矩阵求逆 ## 方法一：高斯消元构造逆矩阵 这个方法非常的常见，矩阵求逆板子题题解里随便抽一篇就是高斯解法 实际上的做法（以及原理）上面也说了一半多了，求解的第一步就是将原矩阵化成**阶梯型矩阵**，然后还是各种朴素运算将消成单位矩阵 就直接先上例子好了，假设我们要求逆的矩阵如下： ## $$\begin{bmatrix}2&2&3\\1&-1&0\\-1&2&1\end{bmatrix}$$ 首先我们将原矩阵与一个单位矩阵放在一起：（为了看的清楚一点，我将两个矩阵分开了一点） ## $$\begin{bmatrix}2&2&3&&1&0&0\\1&-1&0&&0&1&0\\-1&2&1&&0&0&1\end{bmatrix}$$ 然后我们方便起见可以将第一行和第二先换一下：（注意，这里和之前提到高斯消元求法不一样，现在交换了的两行最后不需要换回来） ## $$\begin{bmatrix}1&-1&0&&0&1&0\\2&2&3&&1&0&0\\-1&2&1&&0&0&1\end{bmatrix}$$ 接着我们通过初等行列变换让第二行和第三行的首个元素变为 $0$ ： ## $$\begin{bmatrix}1&-1&0&&0&1&0\\0&4&3&&1&-2&0\\0&1&1&&0&1&1\end{bmatrix} $$ 之后我们发现将第三行和第二行交换后更利于计算，那就交换一下： ## $$\begin{bmatrix}1&-1&0&&0&1&0\\0&1&1&&0&1&1\\0&4&3&&1&-2&0\end{bmatrix}$$ 然后用**初等变换**继续消元： ## $$\begin{bmatrix}1&-1&0&&0&1&0\\0&1&1&&0&1&1\\0&0&-1&&1&-6&-4\end{bmatrix}$$ 然后第三行乘上$-1$：（话说之前不是说只能初等变换的么...额，这里不一样，你这么理解吧，毕竟我们的目的是将当前矩阵求逆而不是求行列式，性质不一样的） ## $$\begin{bmatrix}1&-1&0&&0&1&0\\0&1&1&&0&1&1\\0&0&1&&-1&6&4\end{bmatrix}$$ 现在我们已经把各行首元变为 $0$ 了，接下来的任务是处理**左部分矩阵的上三角** 那么我们用第二行消去第一行的第二个元素：（在这里就是第一行加上第二行） ## $$\begin{bmatrix}1&0&1&&0&2&1\\0&1&1&&0&1&1\\0&0&1&&-1&6&4\end{bmatrix}$$ 第三列的元素处理也是一样的道理：（用第三行来减） ## $$\begin{bmatrix}1&0&0&&1&-4&-3\\0&1&0&&1&-5&-3\\0&0&1&&-1&6&4\end{bmatrix}$$ 至此，我们成功的将**左部分矩阵**转换成了一个**单位矩阵**。所以，逆矩阵呢？ 逆矩阵就是右部分矩阵。  确实是这样啊，emmm...不信的话自己检验一下嘛，矩乘也蛮快的 至于为什么会这样呢？ 因为对矩阵 $A$ 进行行**初等变换**，就相当于左乘以**一和初等矩阵**（其实你大可不必在意这个矩阵的含义，因为我也不打算详细讲，不过讲道理其实就是与原矩阵相乘后结果为单位矩阵的矩阵），对A进行初等变换，也就相当于右边乘以一个相同的这个初等矩阵，然后我们考虑左边的矩阵变换之后成了单位矩阵，那么这时候**左边乘上原矩阵 $A$ 之后变回了原矩阵**，所以右边矩阵乘上 $A$ 之后也会变回原来的样子，也就是 一个**单位矩阵 $E$ **，那么就满足条件： $A\times A^{-1}=E$ 了，所以右边的矩阵就是 $A$ 的逆矩阵 但是请注意，一个矩阵的逆矩阵不一定每个元素都是整数，甚至往往是**有理数**（所以 $bzt$ 里让你求取模意义下的逆矩阵,避免一些精度问题） 于是默默放上代码：（又是加工过的“工程级”代码） ``` //by Judge #include <iostream> #include <stdlib.h> using namespace std; int n; static double a[50][50],b[50][50]; //交换当前行与下一行 void exchange(double a[][50],double b[][50],int current_line,int next_line,int all_line_number) { //交换两行 int cl=current_line,nl=next_line,n=all_line_number; for(int i=0; i<n; i++) swap(a[cl][i],a[nl][i]), swap(b[cl][i],b[nl][i]); } void the_data_change_to_1(double a[][50],double b[][50],int m,int n) { //将a[m][m]变成1 if(a[m][m]) { for(int i=m+1; i<n; ++i) a[m][i]=a[m][i]/a[m][m]; for(int i=0; i<n; ++i) b[m][i]=b[m][i]/a[m][m]; return (void)(a[m][m]=1); //change_to_upper_angle_matrix(a,b,m,n);//将a[m][m]之下的元素全部变成0 } while(m+1<n&&!a[m][m]) exchange(a,b,m,m+1,n); if(a[m][m]!=1) the_data_change_to_1(a,b,m,n); } //将a[m][m]之下的元素全部变成0 void change_to_upper_angle_matrix(double a[][50],double b[][50],int m,int n) { if(m+1>=n) return ; for(int i=m+1,t; i<n; ++i,a[i][m]=0) { t=a[i][m]; for(int j=m; j<n; ++j) a[i][j]=a[i][j]-t*a[m][j]; for(int k=0; k<n; ++k) b[i][k]=b[i][k]-t*b[m][k]; } } /*将上三角矩阵变成单位阵*/ void change_to_unit_matrix(double a[][50],double b[][50],int l,int n) { if(l<=0) return ; for(int i=l-1; i>=0; a[i][l]=0,--i) //从a[l-1][l]开始向上，让每个元素都变成0 for(int j=0; j<n; ++j) b[i][j]=b[i][j]-a[i][l]*b[l][j]; --l,change_to_unit_matrix(a,b,l,n); } //打印结果 void print_result(double b[][50],int n) { for(int i=0; i<n; ++i,cout<<endl) for(int j=0; j<n; j++) cout<<b[i][j]<<" "; } int main() { cin>>n; for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) scanf("%lf",a[i]+j); for(int i=0; i<n; ++i) b[i][i]=1; for(int i=0; i<n; ++i) { if(a[i][i]!=1) the_data_change_to_1(a,b,i,n);//将a[i][i]变成 1 if(a[i][i]==1) change_to_upper_angle_matrix(a,b,i,n); //将a[i][i]之下的元素全部变成 0 } change_to_unit_matrix(a,b,n-1,n); return print_result(b,n),0; } ``` 上面这个代码是直接**实数**求解的，但是如果你不嫌烦的话，可以考虑用**分数形式**表示逆矩阵，（也并不是做不到）但这里就不再给出了 另外，用高斯解的方法还是蛮常规的，所以一般来讲我们都用这个方法来求解，至于接下来那个看看就差不多了 ## 方法二：解方程组构造（非同阶）逆矩阵 相信你可能想到过一下算法： 我们可以尝试依照**矩乘的定义**来设未知数求解逆矩阵 拿方法二中的矩阵作例： 原矩阵是这样的： ## $$\begin{bmatrix}2&2&3\\1&-1&0\\-1&2&1\end{bmatrix}$$ 我们直接设一个 $3$ 阶的矩阵，矩阵中的所有元素都未知： ## $$\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}$$ 那么我们可以像之前说的，又矩乘定义得到 $3*3=9$ 个方程：（~~不想打了好累啊~~） ## $$\begin{bmatrix}2*a+2*d+3*g=1\\2*b+2*e+3*h=0\\2*c+2*f+3*i=0\\......\\(-1)*c+2*f+1*i=1\end{bmatrix}$$ 然后我们愉快的解方程。没错，还是用高斯消元解！ 从上面的算法流程我们可以看出，这个算法没毛病！然鹅说起它的复杂度那就真的太高了，足足$O(n^{4})$！ 虽说复杂度是蛮高的，但是相较于前两个算法，对于**小规模数据的人工计算**，这种算法也不失为一个求逆矩阵的好方法 另外你应该看到了标题说的求**非同阶**逆矩阵了吧？（其实讲道理并不是非同阶的并不能说是逆矩阵） 其实非同阶逆矩阵就是可以用刚刚说的方法解的，方法也与上面差别不大，都是**设矩阵求解未知数**。 非同阶求逆矩阵的一般形式就是给出 $n$ 阶矩阵，求一个 $n*m$ 阶矩阵，要求与原矩阵乘积为一个给定的 $n*m$ 阶矩阵 但是我们一般来就就是求一个已知的 $n$ 阶矩阵乘上一个 $n*1$ 阶矩阵后的结果为一个已知的 $n*1$ 矩阵（好吧其实这就是求解多元方程组...） 不过如果你遇到了什么乱七八糟的题目要你求这个东西的话，别忘了这个（复杂度$n^{4}$的渣渣）算法 ## 方法三：我不会啊谁来教教我 首先具体求法如下：（题解里剽来的） ①找到当前方阵（假设是第k个）的主元 ②将主元所在行、列与第k行、第k列交换，并且记录下交换的行和列 ③把第k行第k个元素变成它的逆元（同时判无解：逆元不存在） ④更改当前行（乘上刚才那个逆元） ⑤对矩阵中的其他行做和高斯消元几乎完全一样的操作，只有每行的第k列不一样，具体看代码 ⑥最后把第②步中的交换逆序地交换回去。 emmm...这里要稍微解释一下，板子题里说的逆矩阵是在**模意义下**的逆矩阵，并不是**实数意义下**的逆矩阵，所以上面提到了逆元，（话说这份代码比较难懂，因为它貌似还用了列的变换，更绝的是它还直接在原矩阵上求逆）还有关于实数下的逆矩阵求解也会在下面的下面给出 咳咳，如果下面的代码三分钟之内看不懂的话，直接跳过吧（因为这个做法的原理不知道是什么...） ``` //by Judge(压行狂魔没办法了, ctrl+shift+A 吧) #include<cstdio> #include<iostream> #define ll long long using namespace std; const int mod=1e9+7; const int M=1e5+7; #ifndef Judge #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif inline void cmax(int& a,int b){if(a<b)a=b;} inline void cmin(int& a,int b){if(a>b)a=b;} char buf[1<<21],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} inline void print(int x,char chr='\n'){ if(C>1<<20)Ot(); while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]=chr; } int n,is[405],js[405]; ll a[405][405]; inline ll qpow(ll x,int p){ ll s=1; for(;p;p>>=1,x=x*x%mod) if(p&1) s=s*x%mod; return s; } inline void inv(){ for(int k=1;k<=n;++k){ for(int i=k;i<=n;++i) for(int j=k;j<=n;++j) if(a[i][j]){is[k]=i,js[k]=j;break;} for(int i=1;i<=n;++i) swap(a[k][i],a[is[k]][i]); for(int i=1;i<=n;++i) swap(a[i][k],a[i][js[k]]); if(!a[k][k]){exit(!puts("No Solution"));} a[k][k]=qpow(a[k][k],mod-2); for(int j=1;j<=n;++j) if(j^k) (a[k][j]*=a[k][k])%=mod; for(int i=1;i<=n;++i) if(i^k) for(int j=1;j<=n;++j) if(j^k) (a[i][j]+=mod-a[i][k]*a[k][j]%mod)%=mod; for(int i=1;i<=n;++i) if(i^k) a[i][k]=(mod-a[i][k]*a[k][k]%mod)%mod; } for(int k=n;k;--k){ for(int i=1;i<=n;++i) swap(a[js[k]][i],a[k][i]); for(int i=1;i<=n;++i) swap(a[i][is[k]],a[i][k]); } } int main(){ n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=read(); inv(); for(int i=1;i<=n;print(a[i][n]),++i) for(int j=1;j<n;++j) print(a[i][j],' '); return Ot(),0; } ``` 这个方法虽然看不懂原理，但是很高效...哪个大佬懂的教教我QAQ ---- ---- 从上面层层讲解看来，矩阵和线性代数的关系非常大，而**线性代数**在大学中各个专业基本都是要掌握的，（计算机系还用说？）所以矩阵一定要学好啊 至此，**矩阵求逆的基础芝士**已经讲解完毕了，至于其他关于矩阵的芝士就请读者们自行探究吧 **参考资料**：实在太多记不清 `_(:з」∠)_` **推荐食用**： 程序员的数学③ ——线性代数 工程数学——线性代数