OI-Wiki 线性空间详解从公理化定义到矩阵核空间、像空间与线性基实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki线性空间向量空间是 OI-Wiki 线性代数板块的理论基石从向量加减、数乘的抽象公理到线性相关、秩、子空间、直和等核心概念再到将线性方程组「按列看」从而引出矩阵的核空间与像空间最后通向 OI 中极为常用的线性基算法。阅读本篇后你将掌握线性空间的完整公理化体系、秩与极大线性无关组的计算视角、矩阵核空间/像空间的本质以及线性基尤其是异或线性基在竞赛题目中的构造方法与复杂度分析。本篇以 向量空间原始文档 为骨架并结合仓库内 线性基文档、矩阵文档、线性映射文档、初等变换文档 及其配套源码进行纵深扩充。前置知识从阿贝尔群与域说起线性空间是 $d$ 维欧氏空间$0\leq d\leq 3$等的推广相关概念的关系可参照下文「欧氏空间与线性空间的关系」一节。在给出正式定义之前需要两个前置概念阿贝尔群与域。群一个集合关于某运算封闭满足结合律、单位元与逆元则构成群。若进一步满足交换律则构成阿贝尔群交换群。域一个集合关于四则运算加减乘除封闭则构成域。更形式化的定义含乘法单位元、逆元、分配律等九条公理见仓库文档 抽象代数基本概念中的域一节。为什么这两个概念是前置知识因为线性空间正是把「阿贝尔群上的加法」与「域上的标量乘法」结合在一起得到的代数结构——加法来自群的公理而数乘的系数来自域的标量。顺带一提OI-Wiki 中与群、域、环相关的完整体系可继续阅读 group-theory.md、ring-theory.md、field-theory.md。线性空间的公理化定义线性空间向量空间是线性代数的基本概念与重要研究对象。线性空间是由向量集合 $V$、域 $\Bbb{P}$、加法运算 $$ 和标量乘法数乘组成的模类代数结构。具体来说设 $(V,)$ 是一个阿贝尔群$\Bbb{P}$ 是一个域。定义 $\Bbb{P}$ 中的数与 $V$ 中元素的一种代数运算称为数乘$$ \cdot:\Bbb{P}\times V\mapsto V $$记为 $p\cdot v$ 或 $pv$其中 $p$ 在域 $\Bbb{P}$ 中$v$ 在阿贝尔群 $V$ 中。要求该数乘运算是封闭的运算结果始终有意义也在群 $V$ 中。且满足以下四条公理数乘对向量加法分配律对于 $\mathbf u,\mathbf v\in V,\ a\in \Bbb{P}$$a(\mathbf u\mathbf v)a\mathbf ua\mathbf v$数乘对标量加法分配律对于 $a,b\in \Bbb{P},\ \mathbf u\in V$$(ab)\mathbf ua\mathbf ub\mathbf u$数乘结合律一致于域乘法对于 $a,b\in \Bbb{P},\ \mathbf u\in V$$a(b\mathbf u)(ab)\mathbf u$标量乘法单位元令 $1\in \Bbb{P}$ 是 $\Bbb{P}$ 的乘法单位元则对于 $u\in V$$1\mathbf u\mathbf u$则称代数系统 $(V,,\cdot,\mathbb{P})$ 是 $V$ 关于 $,\cdot$ 构成 $\Bbb{P}$ 上的一个线性空间。其中$\Bbb{P}$ 称为线性空间的基域$V$ 中元素称为向量$\Bbb{P}$ 中元素称为标量。当域 $\Bbb{P}$ 为实数域时称为实线性空间当域 $\Bbb{P}$ 为复数域时称为复线性空间。这是一套极其宽容的公理。不管是一列数还是箭头或是别的什么东西只要满足上述公理都可以认为是向量也就都可以利用线性代数的理论来研究。这正是抽象代数的力量把大量具体对象的共同结构提炼出来一次证明处处可用。另外约定加法群中的零元称为零向量记作 $\mathbf 0$ 或 $\mathbf\theta$原阿贝尔群中向量的加减法与线性空间新定义的数乘统称为线性运算。Note记号约定为行文方便本文对 $V$ 中的元素不做加粗处理并将满足线性空间定义的代数系统 $(V,,\cdot,\mathbb{P})$ 也直接称为线性空间请注意区分。直观理解不是很严谨地说标量乘法对应一种「缩放」基域 $\Bbb{P}$ 中的元素代表缩放的「比例」向量加法对应「叠加」同时$\Bbb{P}$ 中的元素还代表着向量的「坐标」的取值范围。条件 1–4 描述的正是「缩放」与「叠加」的关联方式——缩放与叠加可以交换顺序分配律、连续缩放可以合并结合律、缩放的中性比例是 $1$。可以结合二维平面上的箭头来理解例如 $2(\mathbf u\mathbf v)2\mathbf u2\mathbf v$ 说的就是先把两个箭头首尾相接再拉长两倍等于先把每个箭头拉长两倍再首尾相接。简单性质以下性质均可在群论中找到此处直接列出对线性空间 $(V,,\cdot,\Bbb{P})$$\theta$零向量唯一$\forall\alpha\in V$$-\alpha$负向量唯一$\exists 0\in\mathbb{P}$$\forall\alpha\in V$有 $0\alpha\theta$$\forall k\in\mathbb{P}$有 $k\theta\theta$$(-1)\alpha-\alpha,\ \forall\alpha\in V$无零因子$\forall\alpha\in V,\ k\in\mathbb{P}$有 $k\alpha\theta\implies k0\lor\alpha\theta$加法的消去律$\forall\alpha,\beta,\gamma\in V$有 $\alpha\beta\alpha\gamma\implies\beta\gamma$。实际上加法的消去律是阿贝尔群本身的性质在群论中即可证明。例子哪些对象构成线性空间$\Bbb{P}^n$ 关于数域 $\Bbb{P}$ 上的加法和乘法构成 $\Bbb{P}$ 上的一个线性空间。例如 $\Bbb{P}$ 可以是 $\Bbb{R}$、$\Bbb{C}$、$\Bbb{N}_p$$p$ 为素数等。这是 OI 中最常用的实线性空间 $\Bbb{R}^n$ 的来源。数域 $\Bbb{P}$ 上的 $n\times m$ 阶矩阵 $\Bbb{P}^{n\times m}$ 关于矩阵的加法和数乘构成 $\Bbb{P}$ 上的一个线性空间——注意全体矩阵本身也是一个线性空间矩阵的加法与数乘运算均逐元素进行。数域 $\Bbb{P}$ 上的一元多项式环 $\Bbb{P}[x]$ 关于多项式的加法和数乘构成 $\Bbb{P}$ 上的一个线性空间。区间 $[a,b]$ 上的全体连续函数记作 $C[a,b]$关于「函数加法」和「值与连续函数的数乘」构成值域上的一个线性空间。这四个例子覆盖了数组、矩阵、多项式、函数四类常见对象它们形态迥异却共享同一套线性结构——这正是线性代数普适性的体现。线性相关与线性无关对线性空间 $(V,,\cdot,\Bbb{P})$引入以下核心概念称 $a_1,a_2,\dots,a_n\in V$ 为 $V$ 的一个向量组对于 $k_1,k_2,\dots,k_n\in\Bbb{P}$称 $\sum_{i1}^nk_ia_i$ 为向量组 $a_1,a_2,\dots,a_n$ 的一个线性组合若向量 $\beta\in V$ 可以表示为向量组 $a_1,a_2,\dots,a_n$ 的一个线性组合则称 $\beta$ 能被向量组 $a_1,a_2,\dots,a_n$线性表出对于 $k_1,k_2,\dots,k_n\in\Bbb{P}$若向量组 $a_1,a_2,\dots,a_n$ 满足 $\sum_{i1}^nk_ia_i\theta\iff k_i0\ (i1,2,\dots,n)$则称向量组 $a_1,a_2,\dots,a_n$线性无关否则称其线性相关。规定零向量与任意向量线性相关——这保证了下文关于秩的定义的一致性。线性组合的矩阵乘法形式线性表示或线性相关的式子可以写成矩阵乘法的形式$$ \betak_1a_1k_2a_2\cdotsk_ra_r(a_1,a_2,\cdots,a_r)\begin{pmatrix} k_1 \ k_2 \ \vdots \ k_r \end{pmatrix} $$根据习惯把向量 $a$ 按顺序并排写在左边把标量 $k$ 按顺序竖着写在右边构成一个「列向量」。这里有一个容易混淆的要点标量构成的「列向量」只是方便的形式记号不在空间 $V$ 中与左边的向量有着本质的区别。左边的向量如果恰好是列向量并排拼起来就可以形式上构成一个「矩阵」上述乘积恰好是矩阵中常见的「矩阵左乘列向量」的形式。这个形式与下文密切相关线性表示等价于向量 $\beta$ 落在矩阵 $(a_1,a_2,\cdots,a_r)$ 的像空间里。如果用线性变换的观点看参见 linear-mapping.md线性相关等价于变换后多个向量变换到零向量而线性无关等价于只有零向量本身变换到零向量。性质对线性空间 $(V,,\cdot,\Bbb{P})$若向量组的一部分线性相关则向量组线性相关若向量组线性无关则其任意非空部分均线性无关。简记为「大无关、小无关」「小相关、大相关」含 $\theta$ 的向量组线性相关向量组线性相关当且仅当向量组的某个向量可以由其余向量线性表出若向量 $\beta$ 可被向量组 $a_1,a_2,\dots,a_n$ 线性表出则表出方式唯一当且仅当向量组 $a_1,a_2,\dots,a_n$ 线性无关若向量组 $a_1,a_2,\dots,a_n$ 线性无关则向量 $\beta$ 可被向量组 $a_1,a_2,\dots,a_n$ 线性表出当且仅当向量组 $a_1,a_2,\dots,a_n,\beta$ 线性相关。性质 4 与 5 实际上给出了唯一表出与线性无关之间的等价刻画是判断线性基合法性的理论依据。极大线性无关组与秩线性相关可以理解为「多余」向量组内部有的向量可以被其他向量表出可以删去。删完之后剩下的就是极大线性无关组。对线性空间 $(V,,\cdot,\Bbb{P})$对于向量组 $b_1,b_2,\dots,b_m$令 ${a_1,a_2,\dots,a_n}\subseteq{b_1,b_2,\dots,b_m}$若有向量组 $a_1,a_2,\dots,a_n$ 线性无关$\forall\beta\in{b_1,b_2,\dots,b_m}\setminus{a_1,a_2,\dots,a_n}$向量组 $a_1,a_2,\dots,a_n,\beta$ 线性相关则称向量组 $a_1,a_2,\dots,a_n$ 为向量组 $b_1,b_2,\dots,b_m$ 中的一个极大线性无关组。类似地可定义线性空间 $V$ 的极大线性无关组。规定向量组 $\theta,\theta,\dots,\theta$ 的极大线性无关组为空集于是全 $0$ 矩阵对应的向量组没有极大线性无关组。称向量组 $b_1,b_2,\dots,b_m$ 的极大线性无关组的大小为向量组的秩记作 $\operatorname{rank}{b_1,b_2,\dots,b_m}$规定 $\operatorname{rank}{\theta,\theta,\dots,\theta}0$。于是向量组的秩的定义与矩阵的秩的定义完全一致。与高斯消元、行最简形的奇妙联系从向量组删向量的删法不唯一因此极大线性无关组也不唯一。习惯上从左到右按顺序删。很巧的是按顺序删留下的向量恰好就是「按行看」观点里面高斯消元法剩下的行最简形矩阵中元素 $1$ 所在的列。这句话值得展开。在 OI-Wiki 的 初等变换文档 中可以看到初等变换倍乘、对换、倍加可以将任意矩阵化为行阶梯形、行最简形乃至标准形矩阵而标准形矩阵中含有元素 $1$ 的个数恰好为矩阵的秩。因此「删向量求极大线性无关组」与「高斯消元求秩」是同一件事的两种视角这一联系正是下文线性基「高斯消元法」构造正确性的直观来源。向量组的等价若向量组 $a_1,a_2,\dots,a_n$ 能线性表出向量组 $b_1,b_2,\dots,b_m$ 中的所有向量称向量组 $b_1,b_2,\dots,b_m$ 能被向量组 $a_1,a_2,\dots,a_n$ 线性表出若向量组 $a_1,a_2,\dots,a_n$ 能被向量组 $b_1,b_2,\dots,b_m$ 线性表出且向量组 $b_1,b_2,\dots,b_m$ 能被向量组 $a_1,a_2,\dots,a_n$ 线性表出则称两向量组等价记作 ${a_1,a_2,\dots,a_n}\cong{b_1,b_2,\dots,b_m}$。向量组的等价就是向量组张成的空间相同。张成空间相同的向量组相互等价张成空间不同的向量组不等价。向量组等价比矩阵等价条件更强不仅要求秩相同还要求空间完全一样。因此把两个矩阵横向拼在一起秩不能发生变化。而矩阵等价仅要求秩相同它表示前一个矩阵或空间可以通过可逆变换到达后一个矩阵或空间。性质对线性空间 $(V,,\cdot,\Bbb{P})$设向量组 $a_1,a_2,\dots,a_n$ 能被向量组 $b_1,b_2,\dots,b_m$ 线性表出若 $nm$则向量组 $a_1,a_2,\dots,a_n$ 线性相关若向量组 $a_1,a_2,\dots,a_n$ 线性无关则 $n\leq m$。等价的线性无关向量组的大小相等特别地向量组的任意极大线性无关组的大小均相等这正是秩良定义的依据向量组线性无关当且仅当其秩等于其大小若向量组 $a_1,a_2,\dots,a_n$ 能被向量组 $b_1,b_2,\dots,b_m$ 线性表出则 $\operatorname{rank}{a_1,a_2,\dots,a_n}\leq\operatorname{rank}{b_1,b_2,\dots,b_m}$等价的向量组的秩相等。线性包张成空间对于线性空间 $(V,,\cdot,\Bbb{P})$集合$$ \left{v\sum_{i1}^nk_ia_i:a_i\in V,\ k_i\in\Bbb{P},\ i1,2,\dots,n\right} $$也构成一个线性空间称为由向量组 $a_1,a_2,\dots,a_n$张成的线性空间或线性包记作 $\operatorname{span}{a_1,a_2,\dots,a_n}$。注意这里的 $n$ 个向量 $a$不一定线性无关——张成空间只关心能凑出哪些向量不关心凑法是否唯一。若这组向量恰好线性无关它本身就成为该张成空间的一组基这正是下文线性基的核心思想。线性子空间对线性空间 $(V,,\cdot,\Bbb{P})$若代数系统 $(V_1,,\cdot,\Bbb{P})$ 满足$\varnothing\ne V_1$$V_1\subseteq V$$V_1$ 关于 $,\cdot$ 构成 $\mathbb{P}$ 上的线性空间则称 $V_1$ 为 $V$ 的线性子空间简称子空间记作 $V_1\leq V$。任何空间 $V$ 都有两个平凡子空间它本身 $V$ 与零子空间。零子空间只含零向量不含有线性无关的向量。若第 2 条中的 $\subseteq$ 换为 $\subset$则称 $V_1$ 为 $V$ 的线性真子空间记作 $V_1V$。子空间的判定运算封闭性不难证明线性空间 $V$ 的非空子集 $V_1$ 是其线性子空间当且仅当线性运算在 $V_1$ 上封闭即$\forall u,v\in V_1$$uv\in V_1$$\forall v\in V_1$$\forall k\in \Bbb{P}$$kv\in V_1$。这是一个非常实用的判定准则——在验证某个集合如线性方程组的解集是线性空间时通常只需验证这两条封闭性而不必逐一验证全部八条公理。下文核空间 $N(A)$ 是子空间的事实即由此验证。交、和与直和、直积对线性空间 $(V_1,,\cdot,\Bbb{P})$ 与 $(V_2,,\cdot,\Bbb{P})$交加法和数乘在 $V_1\cap V_2$ 上封闭故 $V_1\cap V_2$ 称为线性空间 $V_1$ 和 $V_2$ 的交。类似地可定义多个线性空间的交 $\bigcap_{i1}^m V_i$。和若线性空间 $V$ 满足 $V{uv\mid u\in V_1,\ v\in V_2}$则称 $V$ 为线性空间 $V_1$ 和 $V_2$ 的和记为 $VV_1V_2$。可以验证$V_1V_2$ 是包含 $V_1\cup V_2$ 的最小子空间。类似地可定义多个线性空间的和 $\sum_{i1}^m V_i$。类比记忆交对应集合论中的交集和对应集合论中的并集的最小线性包——因为 $V_1\cup V_2$ 本身一般不构成线性空间两个子空间的并通常对加法不封闭所以用它们的和来充当线性化的并。直和设 $VV_1V_2$若线性空间 $V$ 中的任意元素 $v$均只能找到唯一一组向量 $v_1,v_2$ 满足 $vv_1v_2$则称 $V$ 为线性空间 $V_1$ 和 $V_2$ 的直和direct sum记为 $V_1\oplus V_2$。类似地可定义多个线性空间的直和 $\bigoplus_{i1}^m V_i$。直积$V_1$ 与 $V_2$ 的直积$V_1\times V_2$ 定义为二者的笛卡儿积关于如下的加法和数乘构成 $\Bbb{P}$ 上的线性空间$:(V_1\times V_2)\times(V_1\times V_2)\mapsto V_1\times V_2;\ ((u_1,v_1),(u_2,v_2))\to (u_1u_2,v_1v_2)$$\cdot:\Bbb{P}\times(V_1\times V_2)\mapsto V_1\times V_2;\ (k,(u,v))\to (ku,kv)$。类似地可定义多个线性空间的直积 $\prod_{i1}^m V_i$。例子$\Bbb{R}^3$ 中的交、和与直和对于线性空间 $V\Bbb{R}^3$设线性空间$V_1:{(x,0,0)\mid x\in\Bbb{R}}$$x$ 轴$V_2:{(x,y,0)\mid x,y\in\Bbb{R}}$$xy$ 平面$V_3:{(0,y,z)\mid y,z\in\Bbb{R}}$$yz$ 平面$V_4:{(x,0,z)\mid x,z\in\Bbb{R}}$$xz$ 平面。则$V_1V_2V$$V_3V$$V_2V_1V_2$$V_1\subset V_2$故和仍为 $V_2$$VV_1\oplus V_3V_2V_3$$x$ 轴与 $yz$ 平面直和恰好张成全空间且交为 ${\theta}$$V_2V_3\leq V$两个平面的和仍是 $V$ 的子空间事实上 $V_2V_3V$。性质令 $V_1,V_2,V_3$ 是关于 $\Bbb{P}$ 的线性空间与集合的交一样线性空间的交满足交换律与结合律$V_1\cap V_2V_2\cap V_1$$V_1\cap(V_2\cap V_3)(V_1\cap V_2)\cap V_3$。类似于集合的并线性空间的和满足交换律与结合律$V_1V_2V_2V_1$$V_1(V_2V_3)(V_1V_2)V_3$。线性空间的交与和有下述注意方向相反的包含关系$V_1\cap (V_2V_3)\supseteq (V_1\cap V_2)(V_1\cap V_3)$$V_1(V_2\cap V_3)\subseteq (V_1V_2)\cap (V_1V_3)$。$\operatorname{span}{a_1,a_2,\dots,a_n}\operatorname{span}{b_1,b_2,\dots,b_m}\operatorname{span}{a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_m}$——和的张成空间等于两组向量合并后的张成空间这是线性基合并算法的理论基石。令 $V_1,V_2$ 是关于 $\Bbb{P}$ 的线性空间则下列诸款等价$V_1V_2V_1\oplus V_2$$\exists \beta\in V_1V_2$使得拆分为 $V_1$ 和 $V_2$ 中的向量和的方式唯一任意 $\to$ 存在$\theta$ 拆分为 $V_1$ 和 $V_2$ 中向量的和的方式唯一$V_1\cap V_2{\theta}$。证明原文档完整给出此处保留以便理解$1\implies 2$由定义立得。$2 \implies 3$令 $\beta\beta_1\beta_2$其中 $\beta_1\in V_1,\ \beta_2\in V_2$。若 $\theta\alpha_1\alpha_2$ 且 $\theta\ne\alpha_1\in V_1,\ \alpha_2\in V_2$则 $\beta\beta\theta(\beta_1\alpha_1)(\beta_2\alpha_2)$。而 $\beta_1\ne\beta_1\alpha_1$与条件矛盾。$3 \implies 4$若 $V_1\cap V_2$ 含非零向量 $\alpha$则 $\theta\alpha(-\alpha)(-\alpha)\alpha$这是 $\theta$ 的两种不同拆分与条件矛盾。$4 \implies 1$若 $V_1V_2$ 不是直和则存在 $\beta\in V_1V_2$ 使得 $\beta\beta_1\beta_2\gamma_1\gamma_2$其中 $\beta_1,\gamma_1\in V_1,\ \beta_2,\gamma_2\in V_2$ 且互不相同。进而 $\theta\ne\beta_1-\gamma_1\gamma_2-\beta_2\in V_1\cap V_2$与条件矛盾。这条等价刻画在 OI 中亦有体现在线性基求交的证明里直和/交空间 $\operatorname{span}\alpha\cap\operatorname{span}\beta$ 的讨论正依赖于第 4 款交为 ${\theta}$这类思想。参见 basis.md 的线性基求交一节。同构设 $V,V$ 均为域 $\Bbb{P}$ 上的线性空间若存在双射$\sigma:V\mapsto V$ 且保持加法与数乘即 $\forall u,v\in V$$\forall k\in\Bbb{P}$ 满足$\sigma(uv)\sigma(u)\sigma(v)$$\sigma(ku)k\sigma(u)$则称 $\sigma$ 是 $V$ 到 $V$ 的同构映射此时称 $V$ 与 $V$同构记为 $V\cong V$。Note若 $\sigma$ 是单射则可定义单同态若 $\sigma$ 是满射则可定义满同态。性质域 $\Bbb{P}$ 上的两线性空间同构当且仅当其维数相等维数的定义参见 线性基文档1 的推论域 $\Bbb{P}$ 上的 $n$ 维线性空间与线性空间 $\Bbb{P}^n$ 同构。本性质说明我们基本上可以将坐标和向量等同看待。这一点在 linear-mapping.md 的坐标一节中得到了更具体的阐述给定基后向量与坐标列向量一一对应所有 $n$ 维空间本质上都是同一个 $\Bbb{P}^n$。欧氏空间与线性空间的关系以我们最熟悉的三维欧氏空间为例其部分相关概念在线性空间中的对应关系如下表三维欧氏空间线性空间向量向量垂直正交即内积为 $0$三向量共线/共面$k$ 个向量线性相关三向量不共面$k$ 个向量线性无关基向量线性基空间的维数空间的维数这张表把高中立体几何的直觉共线、共面、不共面、基向量、维数翻译成了线性空间的抽象语言也是理解下文按列看线性方程组的直观桥梁。应用按列看待线性方程组本节是原文档的重头戏讲述对于线性方程组「按列看」的观点。在 matrix.md 的看待线性方程组的两种视角一节中同样强调过按行看把 $A$ 看作方程组于是有了消元法解方程的过程按列看把 $A$ 看作由列向量组成的向量组$x$ 是未知数系数思考 $A$ 中的这组列向量能不能配上未知数、凑出列向量 $b$。按列看比按行看更新颖在按列看的视角下可以研究线性无关与线性相关。矩阵 $A$ 本身也是由列向量构成的。把 $A$ 本身看成列向量组而 $x$ 是未知数系数思考 $A$ 当中的这组列向量能不能配上未知数凑出列向量 $b$。此时列向量 $x$ 是完全未知的。等式 $Axb$ 整理为$$ \alpha_1 x_1 \alpha_2 x_2 \cdots\alpha_n x_nb $$这时矩阵乘法中位于左边的矩阵 $A$ 可以看作向量组即一组列向量。这组列向量作为一组基张成一个空间问题就变成探讨列向量 $b$ 是否落在这个空间里。按列看解的「自由度」秩是极大线性无关组中向量的个数代表了「约束」那么其余的向量将赋予解的自由度即允许在其他方向赋予冗余的向量。如果记 $n$ 是矩阵 $A$ 的列数即含有的列向量个数记 $r(A)$ 为矩阵 $A$ 的秩则有自由度 $S$$$ Sn-r(A) $$方程组的全体解也构成向量组自由度 $S$ 就是 $Ax0$ 解向量组的秩即下文核空间的维数。方程组的同解两个方程组的公共解定义为两组解的交集。方程组的同解就是方程组的解的集合相等。方程组同解也比矩阵等价条件强不仅要求秩相等还要求把两个矩阵纵向拼在一起之后秩仍然不改变。这里与向量组等价对比向量组等价要求矩阵横向拼接秩不改变。因此有如下关系矩阵等价不一定有对应的向量组等价或者方程组同解但若有向量组等价或者方程组同解必然有对应的矩阵等价秩相同如果矩阵对应的向量组等价那么将矩阵转置后对应的方程组同解反之亦然。矩阵的核空间与像空间这部分内容站在线性空间的角度上叙述在 linear-mapping.md 的线性映射的核空间与像空间一节中还有线性映射视角的对应叙述。核空间对于矩阵 $A$令 $W$ 为方程 $Ax0$ 的全体解 $x$ 构成的集合则 $W$ 是一个线性空间$W$ 的标量域与 $A$ 的元素所在的域相同。称此时的 $W$ 为矩阵 $A$ 的核空间记作 $N(A)$。矩阵 $A$ 的核空间 $N(A)$ 就是方程 $Ax0$ 的解空间根据基的定义该方程的基础解系就是核空间的基如果矩阵 $A$ 是可逆矩阵则 $A$ 的核空间 $N(A)$ 只含零向量核空间的维数正是前文的自由度 $Sn-r(A)$。像空间对于矩阵 $A$它的 $n$ 个列为向量 $\alpha$称 $n$ 个列向量 $\alpha$ 张成的空间为 $A$ 的像空间或列空间记作$$ R(A)\operatorname{span}{\alpha_1,\alpha_2,\cdots,\alpha_n} $$根据维数的定义像空间的维数等于矩阵 $A$ 的秩由定义对于像空间 $R(A)$ 中的每一个元素 $y$均有相应的表示$$ yk_1\alpha_1k_2\alpha_2\cdotsk_n\alpha_n(\alpha_1,\alpha_2,\cdots,\alpha_n)\begin{pmatrix}k_1\k_2\\vdots\k_n\end{pmatrix}A\begin{pmatrix}k_1\k_2\\vdots\k_n\end{pmatrix} $$因此像空间 $R(A)$ 就是对于任意向量 $x$$Ax$ 的值域。行空间同理可以定义 $A$ 的行空间即 $A$ 的转置的值域 $R(A^T)$。由于矩阵的行秩等于列秩行空间的维数也为矩阵的秩因此转置改变像空间而不改变像空间的维数。到这里前文的概念可以建立起完整的对应关系向量组等价$\iff$ 对应矩阵的像空间 $R(A)$ 相同方程组同解$\iff$ 对应矩阵的行空间 $R(A^T)$ 相同。这一节内容还与线性代数的核心定理呼应线性映射 $T$ 的亏加秩等于定义域维数$\dim N(T)\dim R(T)\dim V$在 linear-mapping.md 中有完整叙述即 $n-r(A)$ 正是核空间的维数、$r(A)$ 正是像空间的维数两者之和等于列数 $n$。在 OI 中的延伸线性基线性基是线性空间理论在竞赛中最直接的应用。OI-Wiki 的 线性基文档 指出三维欧氏空间的基向量在线性空间中推广为线性基——称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组Hamel 基或线性基简称基规定线性空间 ${\theta}$ 的基为空集线性空间 $V$ 的维数定义为线性基的元素个数记作 $\dim V$。OI 中一般只涉及两类线性空间$n$ 维实线性空间 $\Bbb{R}^n$ 下的线性基——称为实数线性基$n$ 维布尔域线性空间 $\Bbb{Z}_2^n$ 下的线性基——称为异或线性基$\Bbb{Z}_2$ 中加法为异或、乘法为与可以证明 $\Bbb{Z}_2$ 是域从而 $(\Bbb{Z}_2^n,,\cdot,\Bbb{Z}_2)$ 构成线性空间。异或线性基构造出的基 $B{b_1,\dots,b_n}$ 有如下性质$B$ 中任意非空子集的异或和不为 $0$即 $B$ 线性无关对 $X$ 中的任意元素 $x$都可在 $B$ 中取出若干元素使其异或和为 $x$即 $B$ 张成整个空间对任意满足上两条的集合 $B$其元素个数不会小于 $B$ 的元素个数即 $B$ 是最小张成集。利用异或线性基可以解决判断一个数能否表示成某数集子集的异或和、求方案数、求最大/最小/第 $k$ 大/第 $k$ 小异或和、求排名等问题。两种构造方法贪心法对原集合的每个数 $p$ 转为二进制从高位向低位扫。对于第 $x$ 位是 $1$ 的如果 $a_x$ 不存在那么令 $a_x\leftarrow p$ 并结束扫描如果存在令 $p\leftarrow p~\text{xor}~a_x$。仓库中的模板代码见 basis_1.cpp对应洛谷 P3812 线性基模板其插入与求最大值核心逻辑为ull p[64]; void insert(ull x) { for (int i 63; ~i; --i) { if (!(x i)) // x 的第 i 位是 0 continue; if (!p[i]) { p[i] x; break; } x ^ p[i]; } } // 求异或最大值从高到低贪心 ull ans 0; for (int i 63; ~i; --i) { ans std::max(ans, ans ^ p[i]); }高斯消元法相当于从线性方程组的角度构造线性基正确性显然——它把向量组化为行简化阶梯形矩阵这正是前文极大线性无关组与行最简形矩阵的 $1$ 所在列对应这一结论的体现。仓库中的模板代码见 basis_2.cpp消元后直接将线性基中所有元素异或起来即为最大值。两种方法对比贪心法构造的线性基没有异或和为 $0$ 的子集各数二进制最高位不同高斯消元法构造的线性基高斯消元后的矩阵是一个行简化阶梯形矩阵该性质包含贪心法的两条性质求解第 $k$ 大、判断元素能否被异或得到等经典问题都更加方便。时间复杂度设向量长度为 $n$总数为 $m$异或线性基构造时间复杂度为 $O(nm)$高斯消元法常数略大实数线性基为 $O(n^2m)$。线性基的合并与求交线性基合并暴力将一组线性基插入另一组即可单次合并 $O(n^2)$异或线性基或 $O(n^3)$实数线性基线性基求交即求两线性空间交空间的一组基有朴素算法与 Zassenhaus 算法两种单次求交复杂度同为 $O(n^2)$异或线性基或 $O(n^3)$实数线性基。模板代码见 basis_intersect_1.cpp 与 basis_intersect_2.cpp。线性基的理论根基正是本篇所讲的线性相关/无关、极大线性无关组与张成空间线性基就是原向量组张成空间的一组基而判断某数能否被异或出来本质上就是在判断该向量是否落在张成空间像空间里。小结本文完整梳理了 OI-Wiki 线性代数板块中线性空间这一基础理论的完整脉络公理化定义阿贝尔群 $(V,)$ 域 $\Bbb{P}$ 满足四条公理的数乘 $\cdot$构成 $(V,,\cdot,\Bbb{P})$结构概念线性相关/无关、极大线性无关组与秩、张成空间线性包、子空间、交/和/直和/直积、同构矩阵视角按列看待线性方程组引出解的自由度 $Sn-r(A)$、方程组的同解、矩阵的核空间 $N(A)$ 与像空间 $R(A)$列空间、行空间 $R(A^T)$竞赛应用线性基实数线性基与异或线性基的两种构造方法、复杂度与合并/求交。读懂这篇文档你就同时握住了抽象代数公理与OI 线性基代码之间的全部桥梁——无论是推导线性基求交的正确性还是理解矩阵快速幂、树剖维护链上最大异或和等进阶技巧都离不开这里的基本功。参考资料与延伸阅读丘维声《高等代数下》清华大学出版社OI-Wiki 相关章节线性基、矩阵、线性映射、初等变换、高斯消元、抽象代数基本概念OI-Wiki 配套代码贪心法构造线性基、高斯消元法构造线性基、线性基求交朴素算法、线性基求交Zassenhaus 算法、前缀线性基。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考