最大无关组

第十二讲 向量组的最大线性无关组一、考试内容与考试要求考试内容向量组的最大线性无关组；等价向量组；向量组的秩；向量组的秩与矩阵的秩之间的关系；向量的内积；向量空间及其相关概念；n 维向量空间的基变换和坐标变换；过渡矩阵；规范正交基．考试要求（1）理解向量组的最大线性无关组的概念，会求向量组的最大线性无关组；（2）理解向量组的秩的概念，理解矩阵的秩与其行（列）向量组的秩之间的关系，会求向量组的秩；（3）理解向量组等价的概念；（4）了解内积的概念，了解规范正交基；（5）了解n 维向量空间、子空间、基底、维数、坐标等概念；（6）了解基变换和坐标变换公式，会求过渡矩阵．注 考研数学二、三不考向量空间等概念，对数学一的考生要求掌握向量空间的有关内容．二、知识要点引入 当方程组Ax o =（Ax b =）有无穷解时，可以用有限个解表示出来，这有限个解就是解集的基础解系，一个基础解系也就是一个最大线性无关向量组．向量组的秩：是这有限个解的个数，也就是最大无关组中向量的个数，或基础解系中解向量的个数．复习 首先简单复习本讲需要用到的一些知识。

线性表示：1122m m k k k βααα=+++L ，对12,,m k k k L 没有要求，且()(,)()R A R A b m ==<线性相关：1122m m k k k o ααα+++=L ，存在12,,m k k k L 不全为零；线性无关：1122m m k k k o ααα+++=L ，12,,m k k k L 只能全为零．n 维向量组12,,,m αααL 0,0,A m n A m n ⎧≠⎧⎪⎪⎨≠=⎪⎩⎪⎨≠⎧⎪⎪⎨⎪==⎪⎩⎩R(A)=m,m n 线性无关:Ax=o 有唯一零解R(A)<m,m n 线性相关：Ax=o 有非零解 1．定义定义1 设有向量组（I ）：12,,,,r m ααααL L ，满足（1）有r 个向量线性无关，不妨设向量组T ：12,,r αααL 线性无关；（2）向量组（I ）中任意1r +个向量（若有的话）都线性相关．称向量组T 是向量组（I ）的一个最大线性无关向量组（也称最大无关组或极大线性无关向量组）．最大无关组所含向量的个数r 称为向量组的秩，记作R 或12(,,,)m R αααL ．例：向量组10⎛⎫⎪⎝⎭，01⎛⎫ ⎪⎝⎭，23⎛⎫ ⎪⎝⎭是线性相关的． 但1T ：10⎛⎫ ⎪⎝⎭，01⎛⎫ ⎪⎝⎭；2T ：01⎛⎫ ⎪⎝⎭，23⎛⎫ ⎪⎝⎭；3T ：10⎛⎫ ⎪⎝⎭，23⎛⎫ ⎪⎝⎭都是线性无关，都是最大无关组．定义1有等价的描述形式如下：定义1' 设有向量组（I ）：12,,,,r m ααααL L ，满足（1）有r 个向量线性无关，不妨设向量组T ：12,,,r αααL 线性无关；（2）向量组（I ）中任一向量都能由向量组T 线性表示；称向量组T 是向量组（I ）的一个最大线性无关向量组．证明 由定义1证明定义1'．在向量组（I ）中任取一个向量α，若α在12,,r αααL 中，则α可由所在的向量组线性表示，如11001r r r αααα-=+++L ．若α不在12,,,r αααL 中，由12,,,r αααL 的线性无关性及向量组（I ）中任意1r +都线性相关性，知α可由12,,,r αααL 线性表示．由定义1'证明定义1自己证明． 2．注意（1）向量组最大无关组一般不惟一；（2）最大无关组中所含向量个数相同，即向量组的秩惟一；（3）若向量组线性无关，它的最大无关组是惟一的，就是它本身；（4）判断向量组的线性相关与线性无关性的方法：① 由Ax o =的解是有惟一零解或有非零解来判断向量组的线性相关与线性无关性： n 维向量组12,,,m αααL ⎧⎨⎩线性无关:Ax=o 有唯一零解线性相关:Ax=o 有非零解② 由向量组的秩来判断来判断向量组的线性相关与线性无关性：若12(,,,)m R m ααα<L ，向量组线性相关；若12(,,,)m R m ααα=L ，向量组线性无关．（5）矩阵的等价与向量组的等价有区别：两个矩阵的等价是它们同型且秩相等．而两个向量组的等价是它们的秩相等且能相互线性表示．但应注意，若矩阵A 与矩阵B 行（或列）等价，则A 的行（或列）向量组与B 的行（或列）向量组等价。

第十二讲向量组的最大线性无关组一、考试内容与考试要求考试内容向量组的最大线性无关组；等价向量组；向量组的秩；向量组的秩与矩阵的秩之间的关系；向量的内积；向量空间及其相关概念；n 维向量空间的基变换和坐标变换；过渡矩阵；规范正交基．考试要求（1）理解向量组的最大线性无关组的概念，会求向量组的最大线性无关组；（2）理解向量组的秩的概念，理解矩阵的秩与其行（列）向量组的秩之间的关系，会求向量组的秩；（3）理解向量组等价的概念；（4）了解内积的概念，了解规范正交基；（5）了解n 维向量空间、子空间、基底、维数、坐标等概念；（6）了解基变换和坐标变换公式，会求过渡矩阵．注考研数学二、三不考向量空间等概念，对数学一的考生要求掌握向量空间的有关内容．二、知识要点引入当方程组Ax o（Ax b ）有无穷解时，可以用有限个解表示出来，这有限个解就是解集的基础解系，一个基础解系也就是一个最大线性无关向量组．向量组的秩：是这有限个解的个数，也就是最大无关组中向量的个数，或基础解系中解向量的个数．复习首先简单复习本讲需要用到的一些知识。

线性表示：k1 1 k2 2 L k m m ，对k1,k2,L k m 没有要求，且R（A） R（A,b）（）m线性相关：k1 1 k2 2 L k m m o，存在k1,k2,L k m不全为零；线性无关：k1 1 k2 2 L k m m o，k1,k2,L k m只能全为零．1．定义定义 1 设有向量组（ I ）：1, 2,L r ,L , m ，满足2）向量组（ I ）中任意 r 1 个向量（若有的话）都线性相关．称向量组 T 是向量组（ I ）的一个最大线性无关向量组（也称最大无关组或极大线性无关向（ 1）有 r 个向量线性无关，不妨设向量组 T ： 1, 2,L , r 线性无关； （ 2）向量组（ I ）中任一向量都能由向量组 T 线性表示；称向量组 T 是向量组（ I ）的一个最大线性无关向量组．证明 由定义 1证明定义 1 ．在向量组（ I ）中任取一个向量 ，若 在 1, 2,L r 中，则 可由所在的向量组线 性表示， 如 r 0 1 L 0 r 1 1 r ．若 不在 1, 2,L , r 中，由 1, 2,L , r 的线性 无关性及向量组（ I ）中任意 r 1 都线性相关性，知可由 1, 2,L , r 线性表示．由定义 1 证明定义 1 自己证明． 2．注意1）有 r 个向量线性无关，不妨设向量组T ： 1, 2,Lr线性无关； n 维向量组2,L , m线性无关 :Ax=o 有唯一零解线性相关： Ax=o 有非零解 R(A)=m,m n A 0,mR(A)<m,mA 0,m量组）．最大无关组所含向量的个数 r 称为向量组的秩， 记作 R 或R( 1, 2,L , m ) ． 例：向量组是线性相关的．组．但 T 1： 10都是线性无关，都是最大无关定义 1 有等价的描述形式如下：定义 1 设有向量组（ I ）： 2,L r ,L , 满足1）向量组最大无关组一般不惟一；2）最大无关组中所含向量个数相同，即向量组的秩惟一； 3）若向量组线性无关，它的最大无关组是惟一的，就是它本身； 4）判断向量组的线性相关与线性无关性的方法：① 由 Ax o 的解是有惟一零解或有非零解来判断向量组的线性相关与线性无关性：线性无关 :Ax=o 有唯一零解 线性相关 :Ax=o 有非零解② 由向量组的秩来判断来判断向量组的线性相关与线性无关性：若 R （ 1, 2,L , m ） m ，向量组线性相关；若 R （ 1, 2,L , m ） m ，向量组线性无 关．（5）矩阵的等价与向量组的等价有区别：两个矩阵的等价是它们同型且秩相等．而两 个向量组的等价是它们的秩相等且能相互线性表示．但应注意，若矩阵 A 与矩阵 B 行（或 列）等价，则 A 的行（或列）向量组与 B 的行（或列）向量组等价。

极大无关组是什么意思
极大无关组言简意赅，就是一个向量组中所有线性无关向量的集合，剩下的就是线性相关的，这个线性相关不是指它们线性相关，是指剩下的向量都可以由无关组的向量线性表示出来。

其内涵有：
1、只含零向量的向量组没有极大无关组。

2、一个线性无关向量组的极大无关组就是其本身。

3、极大线性无关组对于每个向量组来说并不唯一。

但是每个向量组的极大线性无关组都含有相同个数的向量。

4、齐次方程组的解向量的极大无关组为基础解系。

线性代数-向量组的线性相关性定义2：给定向量组A:a→1,a→2,a→3,…,a→m和向量b→，如果存在一组数λ1,λ2,λ3,…,λm（不要求∑i=1mλi2≠0），使得b→=λ1a→1+λ2a →2+⋯+λma→m，则向量b→是向量组A的线性组合linear combination，称向量b→能由向量组A线性表示。

对于两个向量组：两个向量组A、B，若A组中每一个向量都可以由向量组B线性表示，则称向量组A可由向量组B线性表示。

等价向量组：若向量组A、B可以相互线性表示，则称两个向量组等价。

定理1：向量b→能由向量组A:a→1,a→2,…,a→m线性表示的充分必要条件为矩阵A=[a→1a→2⋯a→m]的秩等于矩阵A的增广矩阵[A∣b →]=[a→1a→2⋯a→mb→]的秩.定理2：向量组B:b→1,b→2,…,b→l能由向量组A:a→1,a→2,…,a→m线性表示的充分必要条件为矩阵A=[a→1a→2⋯a→m]的秩等于矩阵[A∣B]=[a→1a→2⋯a→mb→1b→2⋯b→l]的秩，即R(A)=R(A,B).P86定理3：设向量组B能由向量组A线性表示，则R(B)≤R(A).P87定义4：给定向量组A，如果存在不全为0 的数k1,k2,…,km使k1a →1+k2a→2+⋯+kma→m=0，一个向量线性相关的充要条件是a→=0.包含零向量的向量组必线性相关.如果一个向量组的部分向量线性相关，则该向量组线性相关。

如果一个向量组线性无关，则其中任一个部分向量组线性无关。

向量组A:a→1,a→2,a→3,…,a→m (m≥2) 线性相关的充要条件是，向量组A至少有一个向量可以由其余向量线性表示。

证明思路：必要性：不妨设λi≠0，移项即可线性表示出a→i。

充分性：a→i=λ1a→1+⋯+λma→m移项得λ1a→1+⋯+λma→m−a→i=0→.设向量组A:a→1,a→2,a→3,…,a→m线性无关，而向量组B:a→1,a→2,a→3,…,a→m,b→线性相关，则向量b→一定可以由向量组A线性表示，且表示式唯一。

求极大无关组的方法极大无关组（Maximal Irredundant Set，MIS）是指一个集合中的元素两两不可作为同一个子集的元素。

简单来说，如果一个集合中的元素可以通过去掉其中的任何一个元素而得到另一个极大无关组，那么这个元素就是多余的。

如何求解一个集合的极大无关组呢？下面我将介绍两种常见的方法：贪心算法和团算法。

1. 贪心算法：贪心算法是一种常用的求解极大无关组的方法。

具体步骤如下：（1）选择一个度数最大的顶点放入极大无关组集合中。

（2）删除该顶点及其相关的边。

（3）重复以上步骤，直到图中的所有顶点都被删除。

贪心算法的时间复杂度取决于每次选择顶点的策略，一般情况下是O(n^2)，其中n是顶点的个数。

2. 团算法：团算法是一种使用图来求解极大无关组的方法。

具体步骤如下：（1）构建一个无向图，其中每个顶点表示集合中的一个元素，边表示两个元素之间有关系。

（2）找到所有的最大团。

（3）对于每个最大团，如果它没有和其他最大团交集，则将其加入极大无关组中。

团算法的时间复杂度取决于图的构建和最大团的搜索方法，一般情况下是O(2^n)，其中n是集合中的元素个数。

总结：贪心算法和团算法都是常用的求解极大无关组的方法。

贪心算法相对简单，适用于规模较小的问题；而团算法适用于规模较大的问题，但时间复杂度较高。

在实际应用中，可以根据问题的规模和复杂度要求选择合适的算法。

同时，还可以探索其他算法，比如基于模拟退火的算法、遗传算法等，来求解极大无关组问题。

这些算法在探索解空间和优化问题时具有一定的优势，但也需要根据具体情况进行选择和调优。

在实际问题中，极大无关组可以用于任务分配、资源分配、决策分析等方面。

通过求解极大无关组，可以得到最优的任务、资源或决策分配方案，提高工作效率和决策准确性。