线性代数 简明教程 一

线性代数 简明教程

前言

我个人认为我自己与线性代数的渊源是极深的。差不多整一年之前，初三上册的寒假，我在启动某二字二次元风格开放世界游戏时偶然做到了一个世界解谜。与平常无脑过的难度不同，这次的解谜可谓是充满血和汗水的教训——看攻略前千万要搞清楚站位和朝向……于是一步错步步错，耗费了整整半个小时才碰巧还原到原始的状态。自此便有了用严格的数学论证来解决这种世界解谜的想法，然而苦于当时数学功底不够、那些线上线下的教程又对我这种“跳级生”极其的不友好，最终还是将它抛到脑后去了。

但是我最开始想做关于线性代数的内容却是在高一上期末那会，刚好我的竞赛内容推进到了高斯消元相关内容，因而我对线性代数的内容有了一定了解。正巧年末购书有优惠，买了一本Steven J. Leon的《线性代数》（原书第十版）自己学习。深谙零基础学生自学的痛苦的我随即就想要上一篇全网最简明易懂的线性代数教程出来，这篇教程旨在让零基础初学者也能吸收学会线性代数的相关知识点。你可以将它理解成上述《线性代数》著作的一个口语版理解和集注，我所做的就是将书中的晦涩的知识自己吸收后转化为易于读者消化的简明概述。也正是因为其趣味性的必需特点，部分科学定义可能在本教程转述时出现细微的偏颇，还请指出，但在编写过程中我会尽量将原书的科学性与本教程的趣味性、通俗性有机融合起来，从而让读者毫不费力地学习线性代数的知识内容，快乐学习。

重置了有关渲染的插件和脚本，弃用了不美观的katex渲染。该博客目前使用观感更佳的Pandoc进行渲染。

第一节 方程组与矩阵的互相转化

假设我们有一个方程组：。首先将所有未知数提到等号左侧，常数全部移到右侧。我们暂时先忽略掉等号右边的常数项。我们将每行未知数的系数提取出来，放入矩阵的第一行，矩阵的第一行就表示方程组中第一个方程的未知数系数（没有默认为0），以此类推到下边几行，最终你会得到一个列数与未知数个数相等、行数与方程个数相等的矩阵。本例中它长成这个样子：

如此得到的矩阵叫做系数矩阵，顾名思义，它只表示了原方程组的系数，而忽略了常数项。它同时也是一个矩阵，一般地，对于一个矩阵（），它有行列。

此时，如果我们加上等号右侧的常数项，原先的矩阵会变成的。人们为了区分常数和系数，选择在书写时将常数加入到最右侧那一列，并且在最右一列的前面加上竖线分隔系数，如此得到的矩阵叫做增广矩阵。本例中的增广矩阵形式写作：

当矩阵元素不明时（通常是为了举例），我们为了简便表示矩阵本身，采用右下角元素+括号的方式。例如一个矩阵，可以写作：。

第二节 矩阵的基本运算

1. 矩阵加法

仅限构造相同的矩阵，也就是说进行加法运算的两个矩阵行列数必须相同，这样的两个矩阵是同型的。相加时同一行同一列的元素相加即可（增广矩阵同理）。

例如：

矩阵加法满足：结合律、交换律

2. 矩阵减法

矩阵减法是矩阵加法的逆运算，因此对于两个矩阵的形式要求同上，只是相同位置的元素相减而已。

矩阵减法满足：结合律、交换律

3. 标量乘法/矩阵数乘

矩阵的数乘也很简单，让矩阵中每个元素乘以这个数就可以了。

例如：

矩阵数乘满足：交换律、结合律、分配律

4. 矩阵转置

矩阵转置就是将原矩阵的行变成新矩阵的列，直观理解就是顺时针旋转90度后再水平镜像过去。转置用上标表示。

例如：，则

矩阵的主对角线（左上-右下）元素转置前后不变，且具有可逆性[]、数乘不变[]、分配律[]。

有一类特殊矩阵，它转置后恰好就是它自身。这类矩阵被称为对称矩阵，它是自转置的，即。对称矩阵的元素恰好关于主对角线对称，并且是一个的正方形矩阵。这两条性质是对称矩阵的两个基本性质。

5. 矩阵乘法

该内容将在第二章涉及。

第三节 消元

按照一般思路（就是我们在小学学的方法），我们会选择通过方程互相加减各自的倍数，达到消去未知数的目的。这种方法在矩阵上同样适用，而且它有一个贼高坤的名称：高斯消元法（Gaussian Elimination）。

回忆一下我们从出生就会用的消元原理，我们的目标就是让每个未知数都对应一个常数项，那么它的值就可以直接用常数除以系数的方式求出。矩阵中也是如此，为了能够化简出可直接求解的矩阵，我们在此引入初等行变换的概念：

1. 交换某两行
2. 把矩阵的某一行同乘以一个非零的数
3. 把某行的若干倍加和到另一行

这三条很容易理解。第一条：相当于交换方程组顺序，不影响计算；第二条：相当于对某一行方程放缩某倍，它等价于原方程；第三条：相当于前两条的融合，也是消元的关键一招。这三条规则在之后的初等矩阵内容中会再次出现。

首先从一个例子讲起，让读者感受一下初等行变换的魅力：

考虑这个方程组：

按照如上所述，将它转写成增广矩阵的形式：

我们总结一下常用的消元原理，应用到矩阵上就是：

1. 枚举每一列，选出无序组中第列系数绝对值最大的一行，并移到无序组的最上边。（变换规则一）
2. 行通过自乘，将第列的系数变成，并标记为有序。（变换规则二）
3. 通过加减有序组中某一行的非零倍，将之后所有行的第列系数化为。（变换规则三）

令矩阵（有序组用绿色表示）

枚举第一列，。开始时，所有行均无序。选出绝对值最大的那一项，本例中为第二行，进行移动，原矩阵变为：

第二步，自乘并标记有序，因此第一行除以，原矩阵就变成了：

第三步，将无序组的第列消成。本例中，我们让第二行减去二倍第一行；第三行直接减去第一行，得到：

枚举第二列，此时。第一步，选出第二列系数绝对值最大的那一行，移到无序组最上端。本例中无需移动，自乘，标记有序，原矩阵为：

最终的最终，第三行减倍第二行，得到我们心心念念的化简后的矩阵：

为什么把矩阵化简成这种金字塔型的形式呢？你会发现：最后一行仅有一个带系数的未知数，我们直接求，。向上一行，现在相当于常数，移到常数中与合并，也可直接求了……经过如上的反代操作，三个未知数都会被求出来。至此我们才发现这个三角形矩阵的魅力之处。

一般地，对于一个矩阵，如果它的非零系数呈阶梯形分布，则称这类矩阵为行阶梯形矩阵。将非零系数挑出来，它们组成的是一个上三角形矩阵；对应地，零项就会组成下三角矩阵。上三角矩阵通常以表示、下三角矩阵通常用表示。

原方程组有唯一解：

第四节 秩

类比一元二次方程的根存在性判别法——判别式法，即对于一元二次方程，根的个数。那么，矩阵方程是否也有类似的根存在性判别方法呢？

答案是有的，而且不止一种，这意味着“矩阵是否有解”这样的问题会有多种解决方案。现在介绍的是最为简单常用的一种——秩。

在线性代数中，一个矩阵A的列秩是A的线性独立的纵列的极大数目。类似地，行秩是A的线性无关的横行的极大数目。即如果把矩阵看成一个个行向量或者列向量，秩就是这些行向量或者列向量的秩，也就是极大无关组中所含向量的个数。

……咱们抛掉这种看也看不懂的高级语文句法，听我给你总结：

通俗来讲，把一个矩阵化成最简形式（特指行阶梯形）后，非零行的个数就是矩阵的秩。这其实是秩的最大线性无关组的定义。再次白话总结：如果存在三个行向量（列向量一样的，保证所有向量都是行/列向量即可）：。根据高中数学中立体几何的知识——和显然是共线的（就是值的最简比相同，本例中均为）像这样共线的两个向量，拉到线性代数中就说他们是线性相关的；反之是线性无关的，例如本例中和这两组向量互相不共线，它们互相都是线性无关的。

矩阵的秩用表示[、、、等均可]。

现在明白了吧，如果一个矩阵的某两行线性相关，它们都会被初等行变换第三条狠狠薄纱——在乘/除一个非零数后相减，其中一行就会被全部消成0，从方程组角度来看就是，带什么值都成立（相当于浪费了一行）。

当然上边这一段也有表述不准确之处，假设有一个增广矩阵。初等行变换第三条秒了第一、第二行，然而事情有些不对劲了……

第二行不乐意了，它还存留这最后一点倔强，好像在说：“你总结的不对呢~真是雑鱼~”。但是明眼人都看得出来，这种事情是绝对不可能发生的，也就是无解。按照刚刚说的，这个增广矩阵的秩，可是它对应的系数矩阵的秩，就有且，于是我们就找到了矩阵无解的一个条件了。矩阵无解的充要条件是。

再考虑有无穷解的情况：无非就是出现了的情况，此时可以代任何值。与无解不同，这次的最简行阶梯形矩阵，无论是系数矩阵还是增广矩阵形式，它们的秩都是相同的，并且都浪费了至少一行方程式。我们知道：一个三元一次方程组是无法用相异的（行向量形式表示下不共线）两个方程解出唯一值的，相反，解形如：表明由确定、而又由确定，然而这俩都不确定，导致这两个数可以取无穷多的值，也就导致矩阵有无穷组解。综上：矩阵有无穷组解的充要条件是（为未知数个数）。

最后就是有唯一解：如果一切进行顺利的话，既没有全零行，也没有无解行。那么此时系数矩阵和增广矩阵的秩会相同，且等于未知数个数，即。

总结，假设一个由个未知数组成的最简行阶梯形矩阵、以及它的增广矩阵。矩阵解的个数。

例1.1.1 Delivery Mathematics 快递员的数学题

「稻妻狛荷屋的人气跨国快递员绮良良在送货途中遇到了一个难题，你作为无所不知无所不晓的旅行者自然是乐意地接下了她的委托。当你来到委托地点时，你发现这是一道解谜题目……」

稻妻号称最难的方块解谜是一组由个正方体可旋转方块组成的阵列，击打其中的某个方块会使得与之相关联的其他方块共同旋转一个特定角度。在这个谜题中，每个方块每次仅能水平顺时针旋转90度，传动方式在下图给出。问若要使所有方块同时朝向北方，需要如何击打方块？给出任意可行解，但需要保证每个方块旋转的次数不超过4（不击打也可以，相当于次数为0）。

由于钟离先生远在海那一头的璃月喝茶听评书、宵宫也正忙着制作夏日祭的烟花而无法抽身、香菱在万民堂做饭、安柏在侦察蒙德郊区、芙宁娜忙着吃蛋糕……总之没有其他人召唤物能帮你解决这个问题，你只能凭借自己的力量解开这个谜题。

问题分析：首先我们要搞清楚传动规则，我们会发现当你击打了一个方块，包括它在内、再按顺时针方向数两个方块都在旋转相同的角度。这也是这道题被称作难题的原因之一，只用想象力是很难想象的出来的……于是为了用代数方法解决该问题，我们选择用四个未知数、四个方程表示每个方块操作后的状态，问题解决的标志既为四个方块的状态均为（表示北方）。

算法设计：考虑到单个方块每旋转四次就相当于一次循环，因此我们重定义方向标，从北开始，顺时针方向将方位标记为。这么做可以避免一些复杂的取模运算。接着我们根据传动规则表示每个方块的状态，令方块1-4被击打次数分别为。以方块1为例：击打自己、3号和4号都会导致1号顺时针旋转90°，再算上1号初始朝向为，得到：。其他方块以此类推，解析出的方程组对其求解即可。这样的矩阵一定有唯一解，每个未知数都以表示，将一个自然数代入值即可解出答案。

解：设方块1-4的击打次数分别为，设朝向从北方按顺时针方向分别为。

根据传动规则，有如下线性方程组：

增广矩阵形式为：

（化简过程略），行阶梯形式为：

因为系数矩阵的秩与增广矩阵的秩相同且都等于未知数个数，因此矩阵有唯一解。易知的合法值满足的数学关系，此处求最小值，令，得到。

因此，最佳方案是暴击击打2号和3号方块各两次。

后日谈：有些读者可能会问，这个难道不是有无穷解吗？为什么上边说这个矩阵只有唯一解？其实这个矩阵确实只有唯一解，因为，造成它有无数组解的原因是这个自然数。我们在开头只为这个矩阵设定了四个未知数，因此矩阵只有四个元，因而有唯一解。

洛谷习题：

1. P3389 [模板] 高斯消元法
2. P2455 [SDOI2006] 线性方程组
3. P4035 [JSOI2008] 球形空间产生器

第二章 矩阵乘法

第一节 什么是矩阵乘法

你经常能在各种线性代数的书上看到这样一串定义式：。这对于自学者（比如说我自己）其实是非常不友好的。他们在举例计算时很容易被绕进去，不仅计算速度慢不说，还很容易出错……那我在此举出一个简记方法：

将左边的矩阵的每一行看作每个未知数都代了确定值的方程、右边的矩阵每一列看作是前者方程的未知数系数。二者相乘本质上就是让未知数和系数匹配上，并计算出结果放入结果矩阵的特定位置。这个特定位置也有讲究——计算时我们需要固定一个行/列，相对应地我们需要遍历另一个矩阵的列/行，遍历的方向就是这个“特定位置”的排布方向，当遍历完一轮，开始下一轮时，这个“特定位置”的起始点将移到下一行/列，若固定一列则右移一列；反之下移一行。看以下例子来加深理解：

这是固定特定列求值的例子，固定行求值留给读者自行实操。不想再做图了，我太懒了

那么什么样的矩阵才能进行乘法运算呢？答案是一个和一个的矩阵，观察规律，我们发现前矩阵的列数需要等于后矩阵的行数。根据如上概括的矩阵乘法的意义——即搭配未知数与系数。显然，当后一个矩阵的列数大于前一个矩阵的行数时，我们进行系数配对时就会发现多出几个失配的系数。矩阵乘法国不养闲人，这种单身汉显然是不可以光天化日下大摇大摆出来遛弯的。因此保证其中一个矩阵的行数等于另一个矩阵的列数后方可相乘。

类比四则运算的乘法，矩阵乘法是否也有结合律、分配律和交换律呢？很遗憾，不完全是，前二者是矩阵乘法运算所具备的性质、但最后那个交换律不是。不是所有的矩阵相乘都满足乘法交换律，举几个特例：同型零矩阵相乘、一个矩阵（可逆）和它的逆矩阵相乘，矩阵乘法满足交换律的充要条件证明过于复杂烧脑，此处不做陈述主要是我也不会证qwq……。

证明：一般矩阵不满足乘法交换律

假设一般矩阵，一般矩阵，则可以进行，因为的行数和的行数均为。得到的乘积是一个矩阵；反过来，无法进行，因为的列数不等于的行数，即。

假设。和均可进行，假设乘积为。当时，根据矩阵乘法的计算式，得到；当时，根据计算公式得。一般情况下，。得证。

矩阵和数字一样，也有幂次方的计算。特殊地，任意非零矩阵的零次幂都是一个的单位矩阵。主对角线的值全是1，其余元素均为0的矩阵叫做单位矩阵，用字母表示；零矩阵的任何非零正整数次幂都是一个零矩阵，零矩阵的元素全部是0，用字母表示。一个的单位矩阵是这样的：。在算法设计中，经常用类似于大数快速幂（位运算版本）的方式快速计算矩阵的幂次方。

例2.1.1 Akasha Browser with Irminsul Kernel 世界树搜索引擎

你作为刚刚清除了须弥世界树痼疾的英雄旅行者，突然对虚空终端的运作方式有了兴趣。你从大贤者那里了解逼问到，虚空终端实质上是一个仅显示搜索结果的前端程序，但关键词搜索功能却是基于须弥地下空间的世界树。带着这个疑问，你再次来到了世界树前，见到了小吉祥草王大人，希望能让她告诉你世界树的运作方式……

背景知识： 一般浏览器的结果返回功能大多数依赖于矩阵运算，这里属于最简单的一种——我们只需要矩阵的乘法运算（某些情况下会用到转置）。然而随着科技的快步发展，数据量的快速增加，这种方式如今只在很小的范围内被使用（由于码量小思维简单，它有时会在个人博客的关键词搜索功能中被用到）；目前广泛使用的一种是向量相似性搜索，它本质上是在一定范围内搜索与目标向量辐角最为接近的已有向量，在“矩阵的几何表示”章节中会涉及到。这里介绍的是简单匹配搜索。

问题分析：因为矩阵乘法本质上是未知数和系数的配对求值，我们需要构造一个方法来使得“搜索内容”和“已有内容”配对。并且搜索引擎总会返回与你搜索的内容最为相似的结果，搜索“比尔·盖茨”，第一条肯定是关于他个人的介绍，而绝对不可能是一则寻狗启示……因此，我们设计的矩阵必须能在经历一轮运算后能够正确返回每个关键词出现的频率（简单点说就是出现次数），这样虚空终端才能对频率进行排序，并返回频率最大的那个结果。

算法设计：不妨考虑这样几个矩阵——其中一个存储关键词、另一个存储搜索内容。比如我需要将几篇论文（为方便使用英文表示，并且假设词根相同的单词为同一个单词，即不考虑词汇变形）《Basic Structure of Elemental Monuments》（元素方碑的底层构造）、《Junior Elemental Reaction》（初等元素反应）、《Advanced Elemental Theory》（高等元素论）、《Architectural Structure in the Mausoleum of King Deshret》（赤王陵的建筑结构）以及《Advanced Sumeru Linguistic Analysis》（高等须弥语音学解析）。我们在此次挑选一些关键词存储（方便读者观察）：Structure、Element、Junior和Advanced。为每篇论文编号1-5，矩阵如下图：

假如热爱学习的艾尔海森来到了教令院的大图书馆，它想测试一下这全新开发的文献查询系统，输入了Advanced一词。假设已录入数据库就是以上形式，我们如何构造一个“查询矩阵”来和数据库矩阵进行运算呢？

首先根据矩阵乘法的前提要求，这个查询矩阵必须是四行。不妨让每行代表我们的词库词语，艾尔海森输入的是Advanced——即对应数据库矩阵的第四列（未知数），我们要配对它的系数，因此它必须在第四行，才能保证系数正确匹配未知数。同理，查询矩阵的第一行对应Structure、第二行Element、第三行Junior。他输入了一个Advanced，因此我们的查询矩阵如下图：

乘法的目的是将二者匹配起来，得到的结果如下图：

返回矩阵的数字代表关键词在对应数据库项中的出现次数，也就是说，如果此时再加入一篇论文《Advanced Usage of the Word Advanced》（“Advanced”一词的进阶用法），返回矩阵的最后一行（第六行）会出现一个。经过虚空终端的一轮排序，它自然就会来到第一位的位置。如果要分别查询两个不同关键词，在查询矩阵右侧再加一列即可，返回矩阵中多出的一列就是新关键词的出现次数；如果需要同时查询两个关键词，在同一列对应位置写入即可……

后日谈：可靠情报称——愚人众第二席执行官“博士”伙同教令院高层贤者向世界树中加入了大量带有重复词语标题的、正文中充满了强烈心理暗示的催眠文献，须弥民众所佩戴的虚空终端中写入的关键词查询算法自动按关键词出现频率返回结果、其内置的播放功能在结果返回后自动激活，播放其中内容，导致须弥大范围民众出现意识不清、报告称出现“重复经历同一天”、“既视感”等异常现象。后续调查正持续跟进中……——《蒸汽鸟报》记者 夏洛蒂 须弥的大范围“失控”已被证明是须弥民众针对教令院的一次毫无意义的武装暴动，目前已被教令院大贤者和“博士”联合镇压。主要组织者纳西妲、旅行者已被尽数羁押等候问讯。——教令院

例2.1.2 Light Novel Query 轻小说查询

八重堂的主编八重神子最近在为轻小说的事情发愁……并不是因为销量不够，正相反：八重堂最近推出了一项跨国销售项目，各种经典作品被远销往了枫丹廷。这就牵涉出一个问题——枫丹的市民们不想远离枫丹城区、横穿须弥沙漠、翻越璃月高山、躲避稻妻雷暴就为了看一看有哪些轻小说符合自己的独特口味……于是八重神子找到了见多识广的你，希望你能帮她做出一套轻小说内容检索系统。当然作为报酬给你的原石和摩拉是肯定是不会少的……

当然，这套系统有一定要求。因为有很多轻小说为了吸引读者，取的标题和内容是完全对不上号的，神子的想法是做一套正文内容检索——每本轻小说的总字数在出版时就统计好了，但是苦于稻妻的信息存储技术不是很发达，神子希望存储在数据库矩阵里的数据尽可能小。请问该如何设计符合要求的存储算法？

问题分析：每本书中特定的词可能重复出现成百上千次（同样用英文单词表示，且同词根不同词形的两个词算作同一个单词参与计数），我们的要求是让数据尽可能小，既然总字数都已经给出了，我们不妨使用指定词出现的频率来表示这个词的出现次数（单词出现次数=全书总词数×出现频率）。这样的搜索方法叫做相对频率搜索。

算法设计：大致原理和例2.1.1里的一模一样，只是数据库矩阵存储的不再是出现总次数，而是对应词的相对频率。因而图例2.1.3可以变化为如下形式：

明显一看，第三篇文章出现Advanced的频率最高，应该优先返回。但是这个例子并不是很好（明明说了按内容搜索你还在这搜索标题），但是当加入大量的正文内容时，这个方法的优势也就体现出来了。这里由于篇幅图太大耗我洛谷高级图床空间，我也懒得写那么多字原因就不举过长的例子，本例仅作对相对频率搜索的原理的理解。

后日谈：八重堂轻小说搜索引擎被教令院照搬去做了论文的查询系统……

第二节 初等矩阵与矩阵递推

假设存在一个的单位矩阵，对只进行一次初等行变换得到的矩阵叫做初等矩阵，通常用表示。一个矩阵的行变换和列变换都可以用初等矩阵的乘法进行。

仅交换了两行的单位矩阵称作第I类初等矩阵（只进行了初等行变换第一条），将它左乘到一个矩阵前，可以进行相应的行运算；右乘到一个矩阵后可以进行相应的列运算。比如，一个第I类初等矩阵（交换第一、二行），和一个矩阵。左乘就是（交换一、二行）；右乘就是（交换一、二列）。

仅将某一行乘以一个非零倍数的矩阵叫做第II类初等矩阵（只进行了初等行变换第二条），左乘行运算、右乘列运算。例如一个第II类初等矩阵（第一行乘3）和一个矩阵。（第一行乘3）；（第一列乘3）。

仅将某一行的非零倍加到另一行上的矩阵叫做第III类初等矩阵（只进行了初等行变换第三条），同样是左乘行运算、右乘列运算，但是有一点点小不同，不要根据思维定势随便写答案！例如一个第III类初等矩阵（第二行乘2加到第一行）和祖传的矩阵。（第二行的2倍加到第一行）；（第一列的2倍加到第二列）。注意初等矩阵的行列变换与乘法后矩阵的行列变换，哪一行/列乘了倍数、哪一行/列被加上了！

因此我们可以不必使用高斯消元，仅使用初等矩阵乘法也可以达到将普通矩阵消元变成最简行阶梯形矩阵！而且它可以进行列运算，甚至比高斯消元法更高级一点。

接下来是我们的矩阵递推。大家都知道斐波那契数列，它的前两项均为1，此后的每一项都是前两项之和，即。大多数信息竞赛生在学习到递归算法时都会被要求写程序求解斐波那契数列的某一项，当然代码也非常的简单，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <bits/stdc++.h>
using namespace std;

long long fib(int n) {
	if (n == 1 || n == 2) return 1;
	return fib(n - 1) + fib(n - 2);
}

int main() {
	int n;
	cin>>n;
	cout<<fib(n)<<endl;
	return 0;
}

这段代码其实就是照搬了上面的通项公式，但是递归有个弊端就是效率和内存，当为百万级别、甚至十亿级别时它就显得很小丑了。那么我们如何用矩阵加速计算呢？我们用斐波那契数列的递推来向读者介绍矩阵递推的操作方法：

首先我们将通项公式变成我们想要求的形式，为了便于输出，要求结果矩阵的第一个元素就是答案，因此结果矩阵就是：。又因为，并且。我们还需要保证初始矩阵在经历一轮变换前后，始终都是同型的，这里是的矩阵，操作后也应该是的矩阵。于是我们的递推矩阵应该是一个矩阵。不妨将递推矩阵的每一行从上至下分别表示为和的系数，由以上二式可得：。别急，左边还有一列未填满——我们希望每次操作都会把矩阵元素整体向左移一个位置，就好像一个滑动窗口（但不是单调队列），我们的第一列也可以求出来了。最终就是

那么求数列第项——每次右乘都相当于多求出一项，并且当只被乘了一次时，结果矩阵的第一个元素是。因此要让第项来到第一个位置，我们需要进行次乘法，也就是的第一行第一列元素。可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <bits/stdc++.h>
#define MOD 1000000007
#define N 15
using namespace std;

typedef long long ll;

int n = 2; // 递推矩阵行列数均为2 

struct Matrix {
	ll mat[N][N];

	Matrix() {
		memset(mat, 0.0, sizeof mat); // 初始化时内部变量自动置零，无需每次定义变量时再置零 
	}

	void I() {
		for (int i = 1; i <= n; i++) mat[i][i] = 1; // 构造2×2单位矩阵 
	}
}; 

Matrix operator *(const Matrix &l, const Matrix &r) {
	// 重载乘法运算符，实现矩阵乘法 
	Matrix res;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				// res.mat[i][j] = (res.mat[i][j] + l.mat[i][k] * r.mat[k][j] % MOD) % MOD; // 取模用这个 
				res.mat[i][j] += l.mat[i][k] * r.mat[k][j];
			}
		}
	}
	return res;
}

Matrix qpow(Matrix a, ll b) {
	Matrix res;
	res.I();
	while (b) {
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

int main() {
	int a;
	cin>>a;

	Matrix A;
	A.mat[1][1] = A.mat[1][2] = 1; // 初始矩阵 
	Matrix M;
	M.mat[1][2] = M.mat[2][2] = M.mat[2][1] = 1; // 递推矩阵 
	A = A * qpow(M, a - 1);
	cout<<A.mat[1][1]<<endl;
	return 0;
}

它的时间复杂度可以做到，是递推矩阵长/宽，这里是；是幂指数。因此这里的时间复杂度是：，比朴素斐波那契递推的强了不少！

例2.2.1 Lost Control! Blubberbeast's Reproduction 膨膨兽泛滥危机

由于枫丹水质的大幅改善，膨膨兽的天敌数量锐减，枫丹城区近海的膨膨兽也得到了更多的食物，进而开始大量地繁殖。水质改善的第一年，已登记的膨膨兽数量是6765头，恰好是斐波那契数列的第20项。第二年，膨膨兽数量没有变化，之后的每一年，膨膨兽数量都是前两年之和的，已知膨膨兽的平均寿命是15年、枫丹廷近海能承载的最大膨膨兽数量是90万只。那么请问15年后近海的膨膨兽数量是多少？这15年内枫丹廷是否需要向近海投放膨膨兽的天敌以遏制后者疯狂繁殖？（结果出现出现小数则向上取整）

问题分析：这是一道标准的矩阵快速幂递推问题，它基于斐波那契数列递推、却比它更高级。首先，它的初始值不再是而是，其次，从第三项起，每一项都是前两项和的一个倍数，这里是。那我们怎么构造递推矩阵来解决问题呢？

算法设计： 已知初始矩阵。根据题目描述很容易写出通项公式：。我们要保证初始矩阵经过一次递推后，得到的新矩阵与初始矩阵同型，因此根据矩阵乘法定义，我们的递推矩阵必须是一个矩阵。于是拿出祖传单位矩阵模板开始构造递推矩阵！

对于前项和的问题，前面已经给出了，因而我们的递推矩阵变成了；接下来解决倍数问题——根据通项公式，和的系数都是，我们构造递推矩阵时也要考虑到这一点，当时，递推公式展开如下：。如果第一行代表的系数、第二行代表的系数，第二列显然应该同时乘以0.85，左边一列的作用是使原矩阵整体向左移一个位置。最后我们的递推矩阵就是。直接将初始矩阵右端乘以递推矩阵的幂次方就可以了。注意因为初始矩阵的右侧是第二年的膨膨兽个数，乘以递推矩阵本身（一次方），会让第二年的膨膨兽个数移到结果矩阵的前端，要想让第一项变成第15年的个数，递推矩阵的幂必须是，即。

代码实现上，仅需将矩阵和矩阵的初始值改变就可以了。

最终结果：875076。结果小于90万，因此不需要投放天敌。

后日谈：那如果将系数改变为呢？输出的结果将是977427，接近100万了。因此但凡枫丹水质再好那么一点点，使得这个系数升高了0.1，那么枫丹廷说不定都会变成膨膨兽的第二家园了！

洛谷例题：

1. P3390 [模板] 矩阵快速幂
2. P1962 斐波那契数列
3. P1349 广义斐波那契数列
4. P1939 矩阵加速（数列）
5. P3216 [HNOI2011] 数学作业

第三章 矩阵的逆

第一节 浅谈矩阵的“逆”

“逆”这个词相信你早已听说过：同余意义下存在乘法逆元，大多数矩阵也存在逆矩阵。“逆”普遍用来描述不同意义下的“倒数”的概念，倒数一般满足的性质，即本体×本体的逆=单位一。矩阵中的“单位一”是单位矩阵，也因此我们的逆矩阵需要满足这个式子：，并且这个式子倒过来也必须成立（为数不多的满足矩阵乘法交换律的情况之一）。

如果对于一个矩阵，存在另一个矩阵，使得：成立。则称矩阵是可逆的，或称之为非奇异的，矩阵是矩阵的逆矩阵，通常表示成。特殊地，单位矩阵的逆矩阵是它本身，即；零矩阵不可逆，或称之为奇异的，即不可能存在矩阵，使得。类比实数运算，的倒数永远是它本身、没有倒数，因为分母为，没有意义；，同时。

第二节 行列式

行列式是一种函数，写出来有点像矩阵的绝对值。它可以用来判断一个矩阵是否有解、也可以定量分析线性变换对原向量的影响。矩阵的行列式通常用或者是表示。这一节主要介绍行列式判断矩阵是否可逆。

矩阵的行列式为。特殊地，矩阵的行列式就是的值。当一个矩阵的行列式为时，它是奇异的、也就是不可逆的；反之则非奇异/可逆。

那我们在上边只提到了两种方阵，那对于、、的方阵又该怎么办呢？答案是分而治之——分治！

第三节 代数余子式

我们拿出祖传的矩阵，我们随机在其中挑选一位受害者。我个人看第二行第一列的元素不太顺眼，作为矩阵的定义者，我有权利将它变成自己所喜欢的样子，因此我把元素拿掉。可是拿掉以后它还是个！于是我将它所在的那一行以及那一列全部剔除，把剩下的元素按照原来的相对顺序靠拢，组成一个新的矩阵。现在整个矩阵没有元素了，看上去清爽多了~~~

像上边这样，将阶行列式中元素（）所在的第行、第列所有元素删去，剩下元素组成的新阶行列式叫做原行列式的余子式，用表示，代表它是删去原矩阵第行和第列得到的余子式。它通常将一个高阶行列式拆分为一个个低阶行列式便于计算，这其中就是用到了分治（子问题递归）的思想。

我们要计算整个矩阵的行列式，就需要拆开余子式。最终分治成多个的矩阵求其行列式并加和起来。有一个定理：当时，一个的方阵的行列式可以表示成任意行/列的余子式展开，即：

日常做题时，通常选取最多的那一行/列进行展开以减少计算量。

第四节 矩阵的逆

第一节解释清楚了逆矩阵的概念，那么如何求逆矩阵呢？首先是前提——判断矩阵是否可逆！我们引入矩阵行等价的概念：

如果一个矩阵能经过有限次初等行变换得到另一个矩阵，则称与是行等价的。比如说你交换一个矩阵的两行（初等行变换第一条）得到的矩阵本质上还是原来的矩阵，因为如果当你把变换前后的矩阵拆分成一个个行向量，它们在坐标系上的关系不变（交换两行向量不变，同乘倍数向量共线还挺押韵）。联系到第二节的初等矩阵知识，初等行变换可以转化为矩阵左乘初等矩阵，定义可以转换为如下的数学语言：如果存在矩阵和矩阵，使得成立，则称与是行等价的；相应的，初等矩阵右乘就对应两个矩阵列等价。

矩阵行等价有反身性、传递性。例如：与行等价，与行等价，则以下两条均成立：

1. 与行等价
2. 与行等价

相应的，若有方程组，使得。在等号两端同时乘一个符合乘法运算条件的矩阵，新的方程与先前的方程的解相同。第二个方程与第一个方程就是一组等价方程组。

当且仅当与是等价方程组时，增广矩阵与行等价。这个推论的证明需要用到一个定理：若为一个初等矩阵，则它是非奇异的，且和是同类型矩阵。

证明：根据初等矩阵的定义，它是由单位矩阵经过单次初等行变换而来。根据行变换类型的不同，分为三种情况讨论：

第一种，为第I类初等矩阵。假设它由单位矩阵交换第和第行而来，左乘同样的矩阵，进行相应行运算——右边的矩阵将交换行，因为原本就是交换行得来的。因此左乘后原式，根据逆矩阵的定义：的逆矩阵就是它本身，即，因此二者同类型，都是第I类初等矩阵。