矩阵
本文介绍线性代数中一个非常重要的内容——矩阵(Matrix),主要讲解矩阵的性质、运算,以及矩阵乘法的一些应用。
向量与矩阵
在线性代数中,向量分为列向量和行向量。
Warning
在中国台湾地区关于「列」与「行」的翻译,恰好与中国大陆地区相反。在 OI Wiki 按照中国大陆地区的习惯,采用列(column)与行(row)的翻译。
线性代数的主要研究对象是列向量,约定使用粗体小写字母表示列向量。在用到大量向量与矩阵的线性代数中,不引起混淆的情况下,在手写时,字母上方的向量记号可以省略不写。
向量也是特殊的矩阵。如果想要表示行向量,需要在粗体小写字母右上方写转置记号。行向量在线性代数中一般表示方程。
引入
矩阵的引入来自于线性方程组。与向量类似,矩阵体现了一种对数据「打包处理」的思想。
例如,将线性方程组:
一般用圆括号或方括号表示矩阵。将上述系数抽出来,写成矩阵乘法的形式:
简记为:
即未知数列向量 x,左乘一个矩阵 A,得到列向量 b。这个式子可以认为是线性代数的基本形式。
线性代数主要研究的运算模型是内积。内积是先相乘再相加,是行向量左乘列向量,得到一个数的过程。
矩阵乘法是内积的拓展。矩阵乘法等价于左边矩阵抽出一行,与右边矩阵抽出一列进行内积,得到结果矩阵的对应元素,口诀「左行右列」。
当研究对象是右边的列向量时,矩阵乘法相当于对列向量进行左乘。在左乘的观点下,矩阵就是对列向量的变换,将矩阵乘法中右边矩阵的每一个列向量进行变换,对应地得到结果矩阵中每一个列向量。
矩阵可以对一个列向量进行变换,也可以对一组列向量进行「打包」变换,甚至可以对整个空间——即全体列向量进行变换。当矩阵被视为对整个空间变换的时候,也就脱离了空间,成为了纯粹变换的存在。
定义
对于矩阵
一般用
同型矩阵
两个矩阵,行数与列数对应相同,称为同型矩阵。
方阵
行数等于列数的矩阵称为方阵。方阵是一种特殊的矩阵。对于「
研究方程组、向量组、矩阵的秩的时候,使用一般的矩阵。研究特征值和特征向量、二次型的时候,使用方阵。
主对角线
方阵中行数等于列数的元素构成主对角线。
对称矩阵
如果方阵的元素关于主对角线对称,即对于任意的
对角矩阵
主对角线之外的元素均为
式中的
对角矩阵是对称矩阵。
如果对角矩阵的元素均为
三角矩阵
如果方阵主对角线左下方的元素均为
两个上(下)三角矩阵的乘积仍然是上(下)三角矩阵。如果对角线元素均非
单位三角矩阵
如果上三角矩阵
两个单位上(下)三角矩阵的乘积仍然是单位上(下)三角矩阵,单位上(下)三角矩阵的逆也是单位上(下)三角矩阵。
运算
矩阵的线性运算
矩阵的线性运算分为加减法与数乘,它们均为逐个元素进行。只有同型矩阵之间可以对应相加减。
矩阵的转置
矩阵的转置,就是在矩阵的右上角写上转置「T」记号,表示将矩阵的行与列互换。
对称矩阵转置前后保持不变。
矩阵乘法
矩阵的乘法是向量内积的推广。
矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。
设
其中矩阵
在矩阵乘法中,结果
线性代数研究的向量多为列向量,根据这样的对矩阵乘法的定义方法,经常研究对列向量左乘一个矩阵的左乘运算,同时也可以在这里看出「打包处理」的思想,同时处理很多个向量内积。
矩阵乘法满足结合律,不满足一般的交换律。
利用结合律,矩阵乘法可以利用 快速幂 的思想来优化。
在比赛中,由于线性递推式可以表示成矩阵乘法的形式,也通常用矩阵快速幂来求线性递推数列的某一项。
优化
首先对于比较小的矩阵,可以考虑直接手动展开循环以减小常数。
可以重新排列循环以提高空间局部性,这样的优化不会改变矩阵乘法的时间复杂度,但是会得到常数级别的提升。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
方阵的逆
方阵
逆矩阵不一定存在。如果存在,可以使用 高斯消元 进行求解。
方阵的行列式
行列式是方阵的一种运算。
参考代码
一般来说,可以用一个二维数组来模拟矩阵。
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 |
|
看待线性方程组的两种视角
看待矩阵 A,或者变换 A,有两种视角。
第一种观点:按行看,观察 A 的每一行。这样一来把 A 看作方程组。于是就有了消元法解方程的过程。
第二种观点:按列看,观察 A 的每一列。A 本身也是由列向量构成的。此时相当于把变换 A 本身看成了列向量组,而 x 是未知数系数,思考 A 当中的这组列向量能不能配上未知数,凑出列向量 b。
例如,文章开头的例子变为:
解方程变为研究,是否可以通过调整三个系数 x,使得给定的三个基向量能够凑出结果的向量。
按列看比按行看更新颖。在按列看的视角下,可以研究线性无关与线性相关。
矩阵乘法的应用
矩阵加速递推
以 斐波那契数列(Fibonacci Sequence) 为例。在斐波那契数列当中,
如果有一道题目让你求斐波那契数列第
根据斐波那契数列 递推公式的矩阵形式:
定义初始矩阵
注意
矩阵乘法不满足交换律,所以一定不能写成
为什么要乘上
下面是求斐波那契数列第
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 |
|
这是一个稍微复杂一些的例子。
我们发现,
但是发现如果矩阵仅有这三个元素
于是考虑构造一个更大的矩阵。
我们希望构造一个递推矩阵可以转移到
转移矩阵即为
矩阵表达修改
「THUSCH 2017」大魔法师
大魔法师小 L 制作了
我们用
小 L 计划施展
-
魔力激发:令区间里每个水晶球中 特定属性 的能量爆发,从而使另一个 特定属性 的能量增强。具体来说,有以下三种可能的表现形式:
- 火元素激发水元素能量:令
。 - 土元素激发火元素能量:令
。 -
水元素激发土元素能量:令
。需要注意的是,增强一种属性的能量并不会改变另一种属性的能量,例如
并不会使 增加或减少。
- 火元素激发水元素能量:令
-
魔力增强:小 L 挥舞法杖,消耗自身
点法力值,来改变区间里每个水晶球的 特定属性 的能量。具体来说,有以下三种可能的表现形式:- 火元素能量定值增强:令
。 - 水元素能量翻倍增强:令
。 - 土元素能量吸收融合:令
。
- 火元素能量定值增强:令
-
魔力释放:小 L 将区间里所有水晶球的能量聚集在一起,融合成一个新的水晶球,然后送给场外观众。生成的水晶球每种属性的能量值等于区间内所有水晶球对应能量值的代数和。需要注意的是,魔力释放的过程不会真正改变区间内水晶球的能量。
值得一提的是,小 L 制造和融合的水晶球的原材料都是定制版的 OI 工厂水晶,所以这些水晶球有一个能量阈值
小 W 为小 L(唯一的)观众,围观了整个表演,并且收到了小 L 在表演中融合的每个水晶球。小 W 想知道,这些水晶球蕴涵的三种属性的能量值分别是多少。
由于矩阵的结合律和分配律成立,单点修改可以自然地推广到区间,即推出矩阵后直接用线段树维护区间矩阵乘积即可。
下面将举几个例子。
「LibreOJ 6208」树上询问
有一棵
给出三种操作:
操作:将 到根的路径上所有点的 操作:将 到根的路径上所有点的-
操作:询问点 的权值
若直接思考,下放操作和维护信息并不是很好想。但是矩阵可以轻松地表达。
定长路径统计
问题描述
给一个
我们将这个图用邻接矩阵
显然,该邻接矩阵对应
假设我们知道长度为
我们可以把它看作矩阵乘法的运算,于是上述转移可以描述为
那么把这个递推式展开可以得到
要计算这个矩阵幂,我们可以使用快速幂(二进制取幂)的思想,在
定长最短路
问题描述
给你一个
我们仍构造这个图的邻接矩阵
显然上述矩阵对应
事实上我们可以类比矩阵乘法,你发现上述转移只是把矩阵乘法的乘积求和变成相加取最小值,于是我们定义这个运算为
于是得到
展开递推式得到
我们仍然可以用矩阵快速幂的方法计算上式,因为它显然是具有结合律的。时间复杂度
限长路径计数/最短路
上述算法只适用于边数固定的情况。然而我们可以改进算法以解决边数小于等于
问题描述
给一个
我们对于每个点
对于求边数小于等于
习题
- 洛谷 P1962 斐波那契数列,即上面的例题,同题 POJ3070
- 洛谷 P1349 广义斐波那契数列,
矩阵需要变化一下 -
洛谷 P1939【模板】矩阵加速(数列),
矩阵变成了 的矩阵,推导过程与上面差不多。本页面部分内容译自博文 Кратчайшие пути фиксированной длины, количества путей фиксированной длины 与其英文翻译版 Number of paths of fixed length/Shortest paths of fixed length。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。
本页面最近更新:2024/8/6 10:54:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Gesrua, StudyingFather, 369Pai, Anguei, CCXXXI, countercurrent-time, dkz051, Enter-tainer, Great-designer, H-J-Granger, Haohu Shen, Henry-ZHR, InsZVA, Ir1d, ksyx, kxccc, leoleoasd, Marcythm, MegaOwIer, Menci, oldherd, ouuan, sshwy, SukkaW, Tiphereth-A, TrisolarisHD, xcmvec
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用