极小相关子集

极小相关子集刻画“最小冗余”：把线性相关降到最小的结构。

极小相关子集是指满足以下两个条件的列向量子集：

1. 子集本身是线性相关的。
2. 子集的任何真子集都是线性无关的。

换句话说，这类子集是最小的线性相关子集，一旦去掉其中任意一个向量，剩下的向量就会变成线性无关。极小相关子集在线性代数中提供了一种有效的方法来分析矩阵的线性相关性，帮助确定向量集合中的最小冗余结构，进而简化计算和理解线性系统的性质。

定义

设矩阵 $A \in \mathbb{R}^{n \times m}$ 的列向量为 $a_1, a_2, \dots, a_m$。定义子集 $J \subseteq \{1, 2, \dots, m\}$，对应的子矩阵为 $A[J]$。

极小相关子集 $J$ 满足以下条件：

1. $\text{rank}(A[J]) < |J|$
   表示子矩阵的秩小于子集元素的数量，意味着向量线性相关。
2. 对于任意真子集 $I \subset J$，有 $\text{rank}(A[I]) = |I|$
   说明真子集是线性无关的。

极小相关子集是线性相关向量的“核心”集合：整个集合线性相关，但去掉其中任何一个向量后，剩余部分都线性无关——每个向量都“缺一不可”。

性质

1. 在 $\mathbb{R}^n$ 空间中，任意多于 $n$ 个向量的子集必然线性相关。
2. 极小相关子集反映了向量间的线性关系，描述了最小的冗余集合。

计算

1. 计算矩阵的秩

• 通过高斯消元法或行简化（行最简形，Reduced Row Echelon Form, RREF）计算矩阵的秩。
• 确定矩阵最多能包含多少个线性无关的列向量。

2. 找出主元列（Pivot Columns）

• 主元列是线性无关的列。
• 非主元列可以由主元列的线性组合表示。

3. 构造包含非主元列的子集

• 非主元列可由主元列线性表示，因此非主元列与它所依赖的主元列组成的子集是线性相关的。
• 从中筛选出满足“任一真子集线性无关”的集合，即为极小相关子集。

示例

设矩阵

$$A = \begin{pmatrix} 1 & 0 & 0 & -2 & 0 & 0 \\ 0 & 1 & 0 & -2 & -3 & -5 \\ -2 & -2 & 0 & 4 & 6 & 0 \end{pmatrix}$$

• 计算得出 $\text{rank}(A) = 3$。
• 主元列为第 $1, 2, 4$ 列，即 $\{a_1, a_2, a_4\}$。
• 第 $5, 6$ 列可表示为主元列的线性组合（第 $3$ 列为零向量）：
  • $a_5 = -3 a_2$
  • $a_6 = 5 a_1 + \frac{5}{2} a_4$

极小相关子集

• $\{2, 5\}$ 是极小相关子集：$a_5=-3a_2$，即 $3a_2+a_5=0$；这里 $a_2,a_5$ 都非零，所以两个单元素真子集均线性无关。零向量构成的单元素集合则是例外。
• $\{1, 4, 6\}$ 是极小相关子集：$a_6=5a_1+\frac{5}{2}a_4$，且其任一真子集 $\{a_1,a_4\}$、$\{a_1,a_6\}$、$\{a_4,a_6\}$ 都线性无关。
• $\{3\}$ 也构成极小相关子集：零向量单独即线性相关。
• 注意 $\{1,2,4,5\}$、$\{1,2,4,6\}$ 虽线性相关，但因包含相关子集 $\{2,5\}$ 或 $\{1,4,6\}$，不是极小相关子集。

应用

• 电路分析： 极小相关子集类似于电路中的冗余路径。
• 网络流问题： 在图论和网络流问题中，极小相关子集可以描述路径的依赖关系。
• 数据降维： 通过找出极小相关子集，可以帮助在机器学习中去除冗余特征，简化数据表示。