极小相关子集

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

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$ 列可表示为主元列的线性组合：
  • $a_5 = 3 a_2$
  • $a_6 = -5 a_1 + \frac{5}{2} a_4$

极小相关子集

• $\{1, 2, 4, 5\}$ 和 $\{1, 2, 4, 6\}$ 是极小相关子集。
• 任意删除一个元素后，剩下的三个向量线性无关。

应用

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