🧩 Matrix Partitioning and Decomposition: Complete Summary
Matrix partitioning refers to dividing or decomposing a matrix either by structure (into blocks) or by algebraic factorization (into special matrices).
It’s fundamental in linear algebra, optimization, and data science.
1️⃣ Structural Partitioning (Block Matrices)
Given a matrix , it can be partitioned as:
Common Forms
- Row-wise partition:
- Column-wise partition:
- Block-diagonal:
Often used in covariance matrices or sparse systems.
- Hierarchical (H-Matrix):
Recursively subdivides into smaller blocks, each approximated by low-rank matrices to accelerate inversion or multiplication.
Example: Schur Complement
If is invertible,
Used in block LU decomposition and Gaussian elimination.
2️⃣ Algebraic Matrix Decomposition
These express as products or sums of structured matrices for easier computation or interpretation.
(1) LU Decomposition
- : lower-triangular
- : upper-triangular
→ Solving linear systems, determinant computation.
(2) QR Decomposition
- : orthogonal ()
- : upper-triangular
→ Least-squares, numerical stability.
(3) Cholesky Decomposition
For symmetric positive-definite
→ Covariance matrices, Kalman filters.
(4) Eigenvalue Decomposition
- : diagonal of eigenvalues
- : eigenvectors
→ Spectral analysis, diagonalization.
(5) Singular Value Decomposition (SVD)
- : orthogonal
- : diagonal with non-negative singular values
→ PCA, compression, recommender systems.
(6) Polar Decomposition
- : orthogonal
- : symmetric positive semidefinite
→ Analogous to magnitude-direction in complex numbers.
(7) Low-Rank Factorization
→ Used in large-scale learning, recommender systems, and matrix completion.
(8) Nonnegative Matrix Factorization (NMF)
→ Topic modeling, interpretable features, signal separation.
(9) Block LU / QR Factorization
Combines structure and decomposition:
where
(10) Tensor and Multiway Decompositions
For multidimensional (tensor) data:
→ Used in multimodal, spatiotemporal, and recommendation tasks.
3️⃣ Summary Table
Type | Form | Applications |
Structural (block) | Schur complement, sparse systems | |
Hierarchical | H-matrix | Fast inversion (PDEs) |
LU / QR / Cholesky | Linear systems, least squares | |
Eigen / SVD | PCA, spectral analysis | |
Low-rank / NMF | Recommender systems, topic modeling | |
Block factorization | Block LU / QR | Structured numerical algorithms |
Tensor decomposition | Tucker / CP | Multimodal and temporal data |
4️⃣ Key Insights
- Structural partitioning exploits sparsity and modularity.
- Algebraic decomposition provides interpretable transformations and stability.
- Modern algorithms often combine both:
block-sparse structures + low-rank approximations.
Would you like me to generate a Notion-friendly diagram (ASCII or Mermaid) showing how matrix partitioning and decomposition relate (e.g., a tree or flowchart)?
这两个问题同样是线性代数在面试中考察“矩阵性质直觉”的经典题目。
下面我为你逐一拆解：
问题一： 的矩阵，如果秩 (Rank) 不到 ，有什么性质？
设矩阵为 ，已知。
这个条件最核心的推论在于 “零空间 (Null Space/Kernel)” 的维度非常大。
1. 零空间维度超过一半 (Rank-Nullity Theorem)
根据 秩-零化度定理（Rank-Nullity Theorem）：
因为 ，所以：
结论： 矩阵 的零空间（也就是满足 的解空间）的维度比它的列空间（值域）还要大。这意味着 把空间中“超过一半”的向量都压缩成了零。
2. 两个这样的矩阵相乘必然有非零零空间交集
这是一个进阶性质，常考。如果你有两个 矩阵 and ，且它们的秩都小于 。
那么它们的零空间必然相交（除了零向量以外）。
- 理由：两个子空间的维度之和 。在 $n$ 维空间中，维度之和大于 n 的两个子空间必然有非平凡的交集。
3. 特征值性质
- 0 是重数很高的特征值： 至少有 个特征值为 0（代数重数至少这么大，几何重数即为零空间维数）。
- 也就是说，矩阵 的特征值中，超过一半都是 0。
4. 幂零性 (可能的陷阱)
虽然零空间很大，但这不代表 或者 是幂零矩阵。
- 反例：
(3x3矩阵)。
秩为 1 (< 1.5)。。
所以，秩很小只能说明它是一个很“扁”的变换，但不一定是幂零的。
问题二：如果 ，矩阵 的秩有什么特性？
这个方程信息量非常大，它直接锁定了 的几何形态。
推导步骤：
1. 证明 是对称矩阵 (Symmetric)
观察方程右边是 ，左边是 。
我们知道对于任何实矩阵， 永远是对称矩阵（因为 ）。
既然 等于一个对称矩阵，那么 必须是对称的。
2. 证明 是幂等矩阵 (Idempotent)
既然 ，我们可以把原方程 中的 替换为 。
3. 几何意义：正交投影矩阵 (Orthogonal Projection Matrix)
同时满足 对称性 () 和 幂等性 () 的实矩阵，在线性代数中被称为 正交投影矩阵。
它表示将向量垂直投影到某个子空间上。
4. 秩的特性
对于投影矩阵（以及所有的幂等矩阵），有一个非常漂亮的性质：
秩 (Rank) 等于 迹 (Trace)。
为什么？（证明微操）
- 因为 ， 的特征值 必须满足 。
- 方程 的根只有 0 和 1。
- 对于对称矩阵，它是可以对角化的。所以 相似于一个对角矩阵 ，对角线上只有 0 和 1。
- 秩 (Rank) 等于非零特征值的个数（也就是 1 的个数）。
- 迹 (Trace) 等于所有特征值之和（也就是 1 的个数，因为 0 不贡献）。
- 所以，。
总结回答：
如果 ，则 是一个正交投影矩阵。它的秩具有以下特性：
- （秩等于主对角线元素之和）。
- 等于特征值为 1 的个数（其余特征值全为 0）。
- 是半正定的。
如果 ，这种矩阵在数学上被称为 对合矩阵 (Involutory Matrix)。
它有很多非常好的性质，面试中如果问到，可以从代数性质、特征值、几何意义和投影关系这四个维度来回答：
1. 它是自身的逆矩阵 (Self-Inverse)
这是最直接的性质。
由 可知：
这也意味着 一定是可逆的（非奇异的）。
2. 特征值 (Eigenvalues) 只能是 1 或 -1
设 是 的特征值，对应的特征向量为 。
两边同时左乘 ：
因为 $A^2 = I$，所以：
因为 $x \neq 0$，所以 $\lambda^2 = 1$。
结论：$\lambda \in \{1, -1\}$。
- 行列式：$\det(A) = \pm 1$。
3. 一定可对角化 (Diagonalizable)
这是面试中的高分回答点。
- 矩阵 的零化多项式是 。
- 因为这个多项式的根（ 和 ）是互不相同的单根 (Distinct roots)。
- 根据线性代数定理：如果一个矩阵的最小多项式没有重根，那么它一定可以对角化。
- 推论： 相似于一个对角矩阵 ，对角线上只有 和 。
4. 几何意义：反射 (Reflection)
如果 且 ，那么 代表某种坐标变换下的**反射（镜像）**操作。
- 它把空间分成了两个互补的子空间：
- （特征值1对应的空间）：在这个空间上的向量保持不变 ()。
- （特征值-1对应的空间）：在这个空间上的向量方向反转 ()。
- 的作用就是沿着 将向量“反射”过 。
5. 与投影矩阵 (Projection) 的紧密关系
这对解决上一题提到的 很有帮助。对合矩阵和投影矩阵是一一对应的。
如果我们令：
那么 $P$ 就是一个投影矩阵（）。
证明：
反之亦然：
如果 是投影矩阵，那么 就是对合矩阵。
直观理解：
意味着把投影的部分放大2倍再减去原向量，或者理解为：保留分量（的部分）不变，把剩下的分量（的部分）取反。这就是反射。