线性代数 简明教程
前言
我个人认为我自己与线性代数的渊源是极深的。差不多整一年之前,初三上册的寒假,我在启动某二字二次元风格开放世界游戏时偶然做到了一个世界解谜。与平常无脑过的难度不同,这次的解谜可谓是充满血和汗水的教训——看攻略前千万要搞清楚站位和朝向……于是一步错步步错,耗费了整整半个小时才碰巧还原到原始的状态。自此便有了用严格的数学论证来解决这种世界解谜的想法,然而苦于当时数学功底不够、那些线上线下的教程又对我这种“跳级生”极其的不友好,最终还是将它抛到脑后去了。
但是我最开始想做关于线性代数的内容却是在高一上期末那会,刚好我的竞赛内容推进到了高斯消元相关内容,因而我对线性代数的内容有了一定了解。正巧年末购书有优惠,买了一本Steven J. Leon的《线性代数》(原书第十版)自己学习。深谙零基础学生自学的痛苦的我随即就想要上一篇全网最简明易懂的线性代数教程出来,这篇教程旨在让零基础初学者也能吸收学会线性代数的相关知识点。你可以将它理解成上述《线性代数》著作的一个口语版理解和集注,我所做的就是将书中的晦涩的知识自己吸收后转化为易于读者消化的简明概述。也正是因为其趣味性的必需特点,部分科学定义可能在本教程转述时出现细微的偏颇,还请指出,但在编写过程中我会尽量将原书的科学性与本教程的趣味性、通俗性有机融合起来,从而让读者毫不费力地学习线性代数的知识内容,快乐学习。
重置了有关
第一节 方程组与矩阵的互相转化
假设我们有一个方程组:
如此得到的矩阵叫做系数矩阵,顾名思义,它只表示了原方程组的系数,而忽略了常数项。它同时也是一个
此时,如果我们加上等号右侧的常数项,原先的
当矩阵元素不明时(通常是为了举例),我们为了简便表示矩阵本身,采用右下角元素+括号的方式。例如一个
第二节 矩阵的基本运算
1. 矩阵加法
仅限构造相同的矩阵,也就是说进行加法运算的两个矩阵行列数必须相同,这样的两个矩阵是同型的。相加时同一行同一列的元素相加即可(增广矩阵同理)。
例如:
矩阵加法满足:结合律、交换律
2. 矩阵减法
矩阵减法是矩阵加法的逆运算,因此对于两个矩阵的形式要求同上,只是相同位置的元素相减而已。
矩阵减法满足:结合律、交换律
3. 标量乘法/矩阵数乘
矩阵的数乘也很简单,让矩阵中每个元素乘以这个数就可以了。
例如:
矩阵数乘满足:交换律、结合律、分配律
4. 矩阵转置
矩阵转置就是将原矩阵的行变成新矩阵的列,直观理解就是顺时针旋转90度后再水平镜像过去。转置用上标
例如:
矩阵的主对角线(左上-右下)元素转置前后不变,且具有可逆性[
有一类特殊矩阵,它转置后恰好就是它自身。这类矩阵被称为对称矩阵,它是自转置的,即
5. 矩阵乘法
该内容将在第二章涉及。
第三节 消元
按照一般思路(就是我们在小学学的方法),我们会选择通过方程互相加减各自的倍数,达到消去未知数的目的。这种方法在矩阵上同样适用,而且它有一个贼高坤的名称:高斯消元法(Gaussian Elimination)。
回忆一下我们从出生就会用的消元原理,我们的目标就是让每个未知数都对应一个常数项,那么它的值就可以直接用常数除以系数的方式求出。矩阵中也是如此,为了能够化简出可直接求解的矩阵,我们在此引入初等行变换的概念:
- 交换某两行
- 把矩阵的某一行同乘以一个非零的数
- 把某行的若干倍加和到另一行
这三条很容易理解。第一条:相当于交换方程组顺序,不影响计算;第二条:相当于对某一行方程放缩某倍,它等价于原方程;第三条:相当于前两条的融合,也是消元的关键一招。这三条规则在之后的初等矩阵内容中会再次出现。
首先从一个例子讲起,让读者感受一下初等行变换的魅力:
考虑这个方程组:
按照如上所述,将它转写成增广矩阵的形式:
我们总结一下常用的消元原理,应用到矩阵上就是:
- 枚举每一列
,选出无序组中第 列系数绝对值最大的一行 ,并移到无序组的最上边。(变换规则一) 行通过自乘,将第 列的系数变成 ,并标记 为有序。(变换规则二)- 通过加减有序组中某一行的非零倍,将之后所有行的第
列系数化为 。(变换规则三)
令矩阵
枚举第一列,
第二步,自乘并标记有序,因此第一行除以
第三步,将无序组的第
枚举第二列,此时
最终的最终,第三行减
为什么把矩阵化简成这种金字塔型的形式呢?你会发现:最后一行仅有一个带系数的未知数
一般地,对于一个矩阵,如果它的非零系数呈阶梯形分布,则称这类矩阵为行阶梯形矩阵。将非零系数挑出来,它们组成的是一个上三角形矩阵;对应地,零项就会组成下三角矩阵。上三角矩阵通常以
原方程组有唯一解:
第四节 秩
类比一元二次方程的根存在性判别法——
答案是有的,而且不止一种,这意味着“矩阵是否有解”这样的问题会有多种解决方案。现在介绍的是最为简单常用的一种——秩。
在线性代数中,一个矩阵A的列秩是A的线性独立的纵列的极大数目。类似地,行秩是A的线性无关的横行的极大数目。即如果把矩阵看成一个个行向量或者列向量,秩就是这些行向量或者列向量的秩,也就是极大无关组中所含向量的个数。
……咱们抛掉这种看也看不懂的高级语文句法,听我给你总结:
通俗来讲,把一个矩阵化成最简形式(特指行阶梯形)后,非零行的个数就是矩阵的秩。这其实是秩的最大线性无关组的定义。再次白话总结:如果存在三个行向量(列向量一样的,保证所有向量都是行/列向量即可):
矩阵
现在明白了吧,如果一个矩阵的某两行线性相关,它们都会被初等行变换第三条狠狠薄纱——在乘/除一个非零数后相减,其中一行就会被全部消成0,从方程组角度来看就是
当然上边这一段也有表述不准确之处,假设有一个增广矩阵
第二行不乐意了,它还存留这最后一点倔强,好像在说:“你总结的不对呢~真是雑鱼~”。但是明眼人都看得出来,
再考虑有无穷解的情况:无非就是出现了
最后就是有唯一解:如果一切进行顺利的话,既没有全零行,也没有无解行。那么此时系数矩阵和增广矩阵的秩会相同,且等于未知数个数,即
总结,假设一个由
例1.1.1 Delivery Mathematics 快递员的数学题
「稻妻狛荷屋的人气跨国快递员绮良良在送货途中遇到了一个难题,你作为无所不知无所不晓的旅行者自然是乐意地接下了她的委托。当你来到委托地点时,你发现这是一道解谜题目……」
稻妻号称最难的方块解谜是一组由
个正方体可旋转方块组成的阵列,击打其中的某个方块会使得与之相关联的其他方块共同旋转一个特定角度。在这个谜题中,每个方块每次仅能水平顺时针旋转90度,传动方式在下图给出。问若要使所有方块同时朝向北方,需要如何击打方块?给出任意可行解,但需要保证每个方块旋转的次数不超过4(不击打也可以,相当于次数为0)。 由于钟离先生远在海那一头的璃月喝茶听评书、宵宫也正忙着制作夏日祭的烟花而无法抽身、香菱在万民堂做饭、安柏在侦察蒙德郊区、芙宁娜忙着吃蛋糕……总之没有其他人
召唤物能帮你解决这个问题,你只能凭借自己的力量解开这个谜题。
问题分析:首先我们要搞清楚传动规则,我们会发现当你击打了一个方块,包括它在内、再按顺时针方向数两个方块都在旋转相同的角度。这也是这道题被称作难题的原因之一,只用想象力是很难想象的出来的……于是为了用代数方法解决该问题,我们选择用四个未知数、四个方程表示每个方块操作后的状态,问题解决的标志既为四个方块的状态均为
算法设计:考虑到单个方块每旋转四次就相当于一次循环,因此我们重定义方向标,从北开始,顺时针方向将方位标记为
解:设方块1-4的击打次数分别为
根据传动规则,有如下线性方程组:
增广矩阵形式为:
(化简过程略),行阶梯形式为:
因为系数矩阵的秩与增广矩阵的秩相同且都等于未知数个数
因此,最佳方案是暴击击打2号和3号方块各两次。
后日谈:有些读者可能会问,这个难道不是有无穷解吗?为什么上边说这个矩阵只有唯一解?其实这个矩阵确实只有唯一解,因为
洛谷习题:
第二章 矩阵乘法
第一节 什么是矩阵乘法
你经常能在各种线性代数的书上看到这样一串定义式:比如说我自己)其实是非常不友好的。他们在举例计算时很容易被
将左边的矩阵的每一行看作每个未知数都代了确定值的方程、右边的矩阵每一列看作是前者方程的未知数系数。二者相乘本质上就是让未知数和系数匹配上,并计算出结果放入结果矩阵的特定位置。这个特定位置也有讲究——计算时我们需要固定一个行/列,相对应地我们需要遍历另一个矩阵的列/行,遍历的方向就是这个“特定位置”的排布方向,当遍历完一轮,开始下一轮时,这个“特定位置”的起始点将移到下一行/列,若固定一列则右移一列;反之下移一行。看以下例子来加深理解:
这是固定特定列求值的例子,固定行求值留给读者自行实操。不想再做图了,我太懒了
那么什么样的矩阵才能进行乘法运算呢?答案是一个矩阵乘法国不养闲人,这种单身汉显然是不可以光天化日下大摇大摆出来遛弯的。因此保证其中一个矩阵的行数等于另一个矩阵的列数后方可相乘。
类比四则运算的乘法,矩阵乘法是否也有结合律、分配律和交换律呢?很遗憾,不完全是,前二者是矩阵乘法运算所具备的性质、但最后那个交换律不是。不是所有的矩阵相乘都满足乘法交换律,举几个特例:同型零矩阵相乘、一个矩阵(可逆)和它的逆矩阵相乘,矩阵乘法满足交换律的充要条件证明过于复杂烧脑,此处不做陈述主要是我也不会证qwq……。
证明:一般矩阵不满足乘法交换律
假设一般矩阵
假设
矩阵和数字一样,也有幂次方的计算。特殊地,任意
例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类初等矩阵
仅将某一行的非零倍加到另一行上的矩阵叫做第III类初等矩阵(只进行了初等行变换第三条),同样是左乘行运算、右乘列运算,但是有一点点小不同,不要根据思维定势随便写答案!例如一个第III类初等矩阵
因此我们可以不必使用高斯消元,仅使用初等矩阵乘法也可以达到将普通矩阵消元变成最简行阶梯形矩阵!而且它可以进行列运算,甚至比高斯消元法更高级一点。
接下来是我们的矩阵递推。大家都知道斐波那契数列,它的前两项均为1,此后的每一项都是前两项之和,即
1 |
|
这段代码其实就是照搬了上面的通项公式,但是递归有个弊端就是效率和内存,当
首先我们将通项公式变成我们想要求的形式,为了便于输出,要求结果矩阵的第一个元素就是答案,因此结果矩阵就是:
那么求数列第
1 |
|
它的时间复杂度可以做到
例2.2.1 Lost Control! Blubberbeast's Reproduction 膨膨兽泛滥危机
由于枫丹水质的大幅改善,膨膨兽的天敌数量锐减,枫丹城区近海的膨膨兽也得到了更多的食物,进而开始大量地繁殖。水质改善的第一年,已登记的膨膨兽数量是6765头,恰好是斐波那契数列的第20项。第二年,膨膨兽数量没有变化,之后的每一年,膨膨兽数量都是前两年之和的
,已知膨膨兽的平均寿命是15年、枫丹廷近海能承载的最大膨膨兽数量是90万只。那么请问15年后近海的膨膨兽数量是多少?这15年内枫丹廷是否需要向近海投放膨膨兽的天敌以遏制后者疯狂繁殖?(结果出现出现小数则向上取整)
问题分析:这是一道标准的矩阵快速幂递推问题,它基于斐波那契数列递推、却比它更高级。首先,它的初始值不再是
算法设计: 已知初始矩阵
对于前项和的问题,前面已经给出了,因而我们的递推矩阵变成了
代码实现上,仅需将
最终结果:875076
。结果小于90万,因此不需要投放天敌。
后日谈:那如果将系数改变为977427
,接近100万了。因此但凡枫丹水质再好那么一点点,使得这个系数升高了0.1,那么枫丹廷说不定都会变成膨膨兽的第二家园了!
洛谷例题:
第三章 矩阵的逆
第一节 浅谈矩阵的“逆”
“逆”这个词相信你早已听说过:同余意义下存在乘法逆元,大多数矩阵也存在逆矩阵。“逆”普遍用来描述不同意义下的“倒数”的概念,倒数一般满足
如果对于一个矩阵
第二节 行列式
行列式是一种函数,写出来有点像矩阵的绝对值。它可以用来判断一个矩阵是否有解、也可以定量分析线性变换对原向量的影响。矩阵
那我们在上边只提到了两种方阵,那对于
第三节 代数余子式
我们拿出祖传的
像上边这样,将
我们要计算整个
日常做题时,通常选取
第四节 矩阵的逆
第一节解释清楚了逆矩阵的概念,那么如何求逆矩阵呢?首先是前提——判断矩阵是否可逆!我们引入矩阵行等价的概念:
如果一个矩阵还挺押韵)。联系到第二节的初等矩阵知识,初等行变换可以转化为矩阵左乘初等矩阵,定义可以转换为如下的数学语言:如果存在矩阵
矩阵行等价有反身性、传递性。例如:
与 行等价 与 行等价
相应的,若有方程组,使得
当且仅当
证明:根据初等矩阵的定义,它是由单位矩阵
第一种,
第二种,
第三种,
定理得证。
两个非奇异矩阵等价的条件是:假设
是非奇异的 只有平凡解 与 行等价
在矩阵运算中,(因为实在是太显而易见了所以很平凡)
证明:首先证第一条可以导出第二条。假设
再证第二条可以导出第三条。
最后证第三条可以导出第一条。根据行等价的定义,必有
证毕
根据第三条,我们就可以知道一个求逆矩阵的方法了:既然
例3.4.1 How Aranaras Measure Timeflow 兰那罗的时间观念
你在须弥冒险时,遇到了森林可爱的孩子们——兰那罗。这些小小的生物有着与世无争的纯净心灵、以及大大的胸怀。你们一同冒险,击败了桓那兰那故土的污秽化身,拯救了须弥森林。然而,在和兰那罗对话期间,除开他们奇妙的比喻之外,还有一件事情是你久久无法忘怀的——他们的时间单位。你听过最多的是“种子长成大树”、“太阳升起又落下”、“落落梅从出生到长大”、“大树长成雨林”……
假如你们经过很长一段时间的交谈,你渐渐明确了各种时间描述词之间的数学关系,关系如下表。请你求出每个描述词所对应的时间间隔
已知大树长成雨林的时间是种子长成大树的50倍;树木从种子长成大树的期间,落落莓已经生长过整整15次了(由种子出生到果实成熟和从成熟到下一颗种子扎根生长的时间相同);兰那罗从种子长成大树期间,普通人已从黑发少年变为白发苍苍的老人了;普通人从青年到老年的时间足够让三颗种子先后成长为大树;一片树木生长成为雨林,不仅足够让
问题分析:既然各个描述词对应时长的倍数关系都已给出,我们可以两两列出方程组求解。这里我们用到矩阵的逆来方便求出方程的解。
算法设计:首先将各个描述词用未知数表示出来,再用数学关系表示出题干中各个描述词的关系,如此得到的5个方程恰好能使矩阵有唯一解。因为一般的方程
解:设“大树长成雨林”、“树木从种子长成大树”、“兰那罗从种子变成大树”、“落落莓从扎根到成熟”以及“普通人从少年到老年”的时间分别为
整理得:
对应系数矩阵
两侧同时乘以
高斯消元后,将
根据方程
即
因此,“大树长成雨林”的时间是
最后,森林会记住一切。
第五节 行列式的性质
感谢初等矩阵的加持,我们需要记背的知识点又多了不少呢……
我们在第三节说了,用余子式计算矩阵行列式时,需要按照同一列或者是同一行展开。为什么不能沿对角线或者是其他花里胡哨的顺序算余子式呢?下面有个引理告诉你原因:
设
不难发现,
假如
假如
推广到
根据
因此对于
洛谷例题:
第四章 向量空间
第一节 欧几里得向量空间
简称欧氏空间,
如果仅把
事实不然,我们发现,无论这个向量的起点如何变化,它们的方向(辐角)、长度(模长)相同,它们可以经过平移变换成同一个向量。只要确定以上这两项的值,一个
(向量
根据勾股定理可以计算出向量的长度,这叫做向量的模长,
高中数学教材在虚数那一章还有一个选学知识(2023版)——辐角。尽管它标成“选学”,其实我们早在三角函数的几何表示里就接触过辐角了:一个起点是原点的向量可以看作是它从
我们定义向量的数乘运算:辐角不变,模长相乘。图示:
(
我们定义向量的加法,参见高中物理合力与分力的知识。矢量(既有方向又有大小的量)的加法遵循平行四边形法则,平行四边形法则如下图:
即以要进行加法的两个共起点向量为平行四边形的相邻边,做出完整的平行四边形,它们的和向量的起点与前两个向量起点相同,终点是平行四边形的对角顶点。上图中
和平行四边形法则等价的还有三角形法则:
即将其中一个向量的起点平移到另一个向量的终点处,和向量的起点是后者的起点,终点是前者的终点。上图中
在向量表示中:
减法则是坐标相减,将减数向量做反向同模长的反向量再进行加法运算即可。
由于矩阵可以拆分成一个个列向量和行向量,而且矩阵的加法与数乘均与刚刚介绍的向量的加法与数乘规则相同。因此矩阵具备表示向量组的条件,称之为向量空间。向量空间中定义的加法和数乘需要满足如下几条(假设
好多啊ccc,其实就是需要把“加法”定义成正统的加法(满足交换律、结合律);“数乘”定义为正规的数乘(满足结合律、分配律,没有交换律)。可以发现矩阵的加法和数乘和它完美匹配!因此矩阵可以作为一个向量空间。
于是,向量空间
当然有时我们并不需要那么多空间,好比一个人住一个城市……先不提城市各项环节能否正常运作,如果只是用来溜达的,那也是太过巨大了,有些地方可能你一辈子也取不到,还不如开始就不要。向量空间其实也可以像这样压缩范围,并且压缩后的向量空间也必须是全集
在矩阵中,也存在零空间。它表现为矩阵方程
例4.1.1 Merusea Village Portal 海露村传送门
自从你来到枫丹,知晓了水仙十字结社的秘密之后,奇怪的事情开始在你身边上演……
你在海露村遇见了抽象派美露莘大画师玛梅赫、以及一只发条机关狗西摩尔。很不巧,玛梅赫的作画颜料用完了,于是你们前去收集更加纯净的矿物颜料,期间玛梅赫邀请你们进入一个粉色的漩涡虫洞。或许是因为你前一天冒险到深夜,在这个温暖且舒适的环境下来了困意。一闭眼,再一睁眼,迎接你的不是如同往常一般的新地下区域——而是一片温暖的、舒适的粉色幻境——你被一个人丢在这个传送通道里了!
为了不让派蒙着急,同时也为了你能尽快在下一次困意席卷前逃出这个空间,你需要确定这个传送门是否为“同维度空间卷曲型”——即传送过程中不发生维度的变化。你需要证明你身处的空间是一个三维空间的子空间,这样才能使用正确的方法逃出生天。你发现你的身高和体宽的比值是原来的一半、但是体宽不变。请证明你所在的空间是是三维空间的子空间。
问题分析:首先要根据已有的信息判断该向量空间是否为三维向量空间的子集,然后再验证加法与数乘的封闭性,只有当二者均成立时才能够证明该空间是三维空间的子空间。
算法设计:根据题干最后一句话,我们不妨将主人公设为三维坐标系原点,按照
解:根据变换关系,得到该向量空间的集合形式
因此,所在空间
后日谈:其实是你网卡了渲染出错了……和什么三维不三维空间没啥关系……
第二节 基底、张成与张集
假设
我们都知道,
如果
- 若
,则 为 的子空间 - 向量平面
中一组向量的张成是 中包含这组向量的最小子空间
对于第一条,因为你怎么拟合平面,都不可能让你的平面比整个空间的维度更高,而且无论以什么系数搭配向量,它们所得的新向量都在整体空间内,第一条就能很简明的证明了。第二条性质,首先空间内向量的张成必为整个空间的子空间,毕竟用的都是数乘和加法,用的向量也都在空间内,总不能算一下加法向量就跑到空间外边去了吧,此外,因为数乘和加法的封闭性,任何经过这两个向量的空间都包含其张成,因此它是最小的。
和张成相对,如果
基底,大家在高中立体几何部分学过了。当时的定义是:平面内不共线的两个向量叫做这个平面的一组基底。然而这段话可以用线性代数的语言原原本本描述出来:“在
例4.2.1 Al-Ahmar's Trial 赤王的试炼
你和婕德一行人在圣显厅前击败了图谋不轨的镀金旅团,并在他们搭起的营帐里发现了一封密信。上面写着若想进入圣显厅,需先过三关试炼。为了能够一探黄金梦乡的秘密,你接下了完成三重试炼的任务,然而当你真正进入到第一重试炼时,却发现事情并没有这么简单……
你进入了试炼场地,却发现整个世界天旋地转。最终安定下来,你发现赤王的神奇科技把你带入了一个
维空间内。这还没完,四周又有整齐排列的空气墙阻挡了你的通路。经过好一顿摸索,你终于发现这是一个 维空间,于是你开始建立空间坐标系,五个坐标轴分别是 ,假设你现在所在的地方是原点 ,通关点 。四周的空气墙限制了你仅能沿着与向量 平行的方向行动。请问如何安排前进方向使得你能够从起点 到达终点 ?
问题分析:这个问题明显是让我们用
解:明显地,题中五个向量互相线性无关,因此可以作为该平面的一组基。由于向量加法和数乘运算的封闭性,且路径向量
设
因此,应在
因此一旦选定了平面的基底,该平面上所有的向量都可以用这组基底唯一表示出来,具体操作是使待求向量
基底可以表示平面内所有的向量,故
第三节 线性基
第二节里我们讲了向量空间的基底,基底其实还有一个名称叫线性基。平面中所有向量唯一对应一种基底的线性组合。在OI中常常被用于求第
一组值的异或和可以看做该空间内异或线性基的向量的异或组合,由于基底表示向量的唯一性:原集合中的数可以通过异或线性基里的基向量唯一确定。它有如下几个性质,事实上,它和普通平面内的实数线性基有相似之处:
- 原序列中任何元素都可以通过异或线性基内的元素异或得到
- 异或线性基不存在重复元素,且在保证性质一的前提下,它的元素最少
异或运算也有一个特殊性质,若
根据以上性质构造计算方法:
1 | void insert(ll x) { |
由于一般题目中数据范围是1e18
,而转换为二进制位就有unsigned long long
,线性基p
数组至少需要60
位。
有时并不是所有的插入操作都会成功,因为要保证异或线性基里的向量互相线性无关。存储操作本质上是拆分二进制位,然后将它尽量表示为已有基向量的异或和,好像除去每个人身上的共同特征,只保留人的独特个性一般。如果拆到最后再也拆不了了,证明它是独特的,可以加入其中。反之,这个数就可以被其他数通过异或运算代替,没必要加它,返回插入失败。可以有下面的代码:
1 | bool insert(ll x) { |
如果是求一个数能否被这个异或线性基表示出来,将最后一行改为return !x;
即可(能表示即不可插入,不能表示即可以插入)。若某次插入失败,证明flag = false
,在插入失败后设为true
表示需要特判
线性基用于求解一组数的异或和最值问题,有下面求最值的三个例子。它们无一例外使用了贪心法:
1. 求最大值
1 | ll xorMax() { |
为什么从高位开始遍历?我们都知道如果一个数字的某位数大于另一个数字相同位置的数(两数数量级相同,即十进制下位数相同),那么前者是大于后者的。根据异或的运算法则:“不同为ans
的高位此时是0
,若进行异或运算的同位数字是0
,即二者相同,结果为0
,不会变得更小;反之若异或运算的对应二进制位为1
,当前位异或结果是1
,变大了,因此ans
高位为1
,运算数对应位为0
,结果为1
,不会变得更大;若运算数当前位是1
异或结果为0
,变小了,所以
2. 求最小值
1 | ll xorMin() { |
我们知道,可以通过任意组合(异或运算)异或线性基中的元素来得出各种新的元素,若
3. 求第
这才是异或线性基的高级玩法
为了求第rebuild
。
1 | void rebuild() { |
接着我们需要特判
1 | ll queryKMax(ll k) { |
除了求值,异或线性基还可以合并,甚至于求它和另一个异或线性基的交集与并集。所以异或线性基是一种数据结构。封装在一个结构体XorBase
里:
1 | struct XorBase { |
4. 并集
思路就是枚举异或线性基
1 | XorBase Union(XorBase A, XorBase B) { |
5. 交集
如果一个异或线性基里的元素插入到另一个异或线性基里会失败,则将它插入到交集异或线性基中。
1 | XorBase Intersect(XorBase A, XorBase B) { |
例4.3.1 DMG Bonus 核爆
作为一名资深神原玩家,你希望能在新限定五星角色初进卡池时尽快拿下全网首个999w核爆记录,以此证明自己的实力。现在你已经在游戏里做好了很多伤害加成型的食物,准备在boss战时一展身手。战斗开始时,你首先给角色吃下了基础食物(每局开始前必吃的食物),它的效果是在300秒内单角色爆发伤害增加
,但是同时它有一个副作用…… 基础食物生效期内,如果角色吃下其他伤害加成型的食物,总伤害加成的百分比数值将是各种食物的伤害百分比数值的异或之和,即
, 表示 , 为异或符号。各种食物的伤害加成在下边给出,如果不吃任何加成型食品(也不吃基础食品),爆发伤害期望值为 。吃完所有食物后,如果你用增伤角色施加了 的爆发增伤。请问你的最大爆发伤害能否达到 ,即 ?若不能,最高伤害是多少?(令每种食物只有一份,且食物效果均可叠加,结果四舍五入到万位)
编号 | 加成效果 |
---|---|
1 | 270% |
2 | 200% |
3 | 280% |
4 | 200% |
5 | 180% |
6 | 150% |
7 | 75% |
问题分析:题干信息已经很明显了,这是一道异或线性基的最大和问题。根据上文所述程序计算即可。
算法实现:这里使用的是结构体封装版本的异或线性基计算代码:
1 |
|
运行代码,在输入框输入:
1 | 7 |
结果输出:8162000.000
。小于所给的816
万。
洛谷例题: