复矩阵的QR分解

复矩阵的QR分解

定义：QR分解

设 \(A\) 是一个 \(m \times n\) 复矩阵，且 \(m \geq n\)。如果存在一个 \(m \times r\) 酉矩阵 \(Q\) 和一个 \(r \times r\) 上三角矩阵 \(R\)，使得

\[A = QR \]

则称此分解为 \(A\) 的 QR 分解，其中 \(r=\mathrm{rank}(A)\)。（当 \(Q\) 是 \(m \times n\) 矩阵且满足 \(Q^*Q = I_n\) 时，称为经济型 QR 分解。）

定理：列满秩矩阵QR分解的存在性与唯一性

任意列满秩复矩阵 \(A \in \mathbb{C}^{m \times n}\) 都存在一个 \(m \times n\) 酉矩阵 \(Q\) 和一个 \(n \times n\) 上三角矩阵 \(R\)，使得

\[A = QR \]

如果进一步要求 \(R\) 的对角元为正实数，则该分解是唯一的。

证明：存在性

我们使用 Gram-Schmidt 正交化过程来构造证明。设 \(A = [a_1, a_2, \dots, a_n]\)，其中 \(a_i \in \mathbb{C}^m\) 是 \(A\) 的列向量。

1. 正交化过程
   定义：

   • \(u_1 = a_1\)
   • \(q_1 = \dfrac{u_1}{\|u_1\|}\)
   • 对于 \(k = 2, 3, \dots, n\)：
     \[u_k = a_k - \sum_{j=1}^{k-1} \langle a_k, q_j \rangle q_j \]
     \[q_k = \dfrac{u_k}{\|u_k\|} \quad (\text{如果 } u_k \neq 0) \]

   其中 \(\langle x, y \rangle = y^\dagger x\) 是复向量空间中的内积。

2. 构造 QR 分解
   令 \(Q = [q_1, q_2, \dots, q_n]\)，则 \(Q^\dagger Q = I_n\)。
   定义上三角矩阵 \(R\) 的元素为：

   \[r_{ij} = \begin{cases} \langle a_j, q_i \rangle, & \text{如果 } i \leq j \\ 0, & \text{如果 } i > j \end{cases}\]

   特别地，\(r_{kk} = \|u_k\|\)。

3. 验证分解
   对于每个 \(k = 1, 2, \dots, n\)，有：

   \[a_k = \sum_{i=1}^k r_{ik}q_i = \sum_{i=1}^k \langle a_k, q_i \rangle q_i \]

   因此：

   \[A = [a_1, a_2, \dots, a_n] = [q_1, q_2, \dots, q_n]R = QR \]

证明：唯一性

假设有两个不同的分解 \(A = Q_1 R_1 = Q_2 R_2\)，那么：

\[Q_2^* Q_1 = R_2 R_1^{-1} \]

• 左边是酉矩阵的乘积，仍然是酉矩阵；
• 右边是两个上三角矩阵的乘积，仍然是上三角矩阵；
• 一个既是酉矩阵又是上三角矩阵的矩阵必须是对角矩阵；
• 由于 \(R_1, R_2\) 对角线都是正实数，且乘积为单位矩阵，这个对角矩阵只能是单位矩阵。

因此 \(Q_1 = Q_2, R_1 = R_2\)

定理：一般的复矩阵的QR分解

对于任意复矩阵 \(A \in \mathbb{C}^{m \times n}\)，存在一个 \(m \times r\) 酉矩阵 \(Q\)，一个 \(r \times n\) 上梯形矩阵 \(R\)，一个置换矩阵 \(P \in \mathbb{C}^{n \times n}\)，使得

\[AP = QR \]

其中，\(r = \mathrm{rank}(A) \leq n\)。

证明

我们用置换矩阵 \(P \in \mathbb{C}^{n \times n}\) 作用于 \(A\) 的列向量组，使得 \(AP\) 的前 \(r\) 个向量线性无关。不妨设 \(AP = [a_1, a_2, \dots, a_n]\)，则 \(a_1, \dots, a_r\) 线性无关。

设 \([a_1, \dots, a_r] = A_r \in \mathbb{C}^{m \times r}\) 列满秩，则根据上一个定理，存在一个 \(m \times r\) 酉矩阵 \(Q_r\) 和一个 \(r \times r\) 上三角矩阵 \(R_r\)，使得

\[A_r = Q_r R_r \]

对于 \(k = r + 1, \dots, n\)，存在 \(x_k \in \mathbb{C}^r\) 使得 \(a_k = A_r x_k = Q_r R_r x_k\)，记 \(y_k = R_r x_k \in \mathbb{C}^r\)，令 \(R_r^\prime = [y_{r+1}, \dots, y_n] \in \mathbb{C}^{r \times (n-r)}\)，则

\[AP = Q_r \begin{bmatrix} R_r & R_r^\prime \end{bmatrix} := QR \]

其中 \(R\) 为上梯形矩阵。

注记

上面的定理可以进一步扩充：\(Q\) 的列向量可以扩充为一组单位正交基得到 \(\overline{Q} = \begin{bmatrix} Q & Q_{\perp} \end{bmatrix}\) 为 \(m \times m\) 酉矩阵，于是相应的 \(R\) 变成了

\[\overline{R} = \begin{bmatrix} R \\ 0 \end{bmatrix} \]

因此，

\[A = \begin{bmatrix} Q & Q_{\perp} \end{bmatrix} \begin{bmatrix} R \\ 0 \end{bmatrix} \]

这成为完全 QR 分解，但是这种分解是不唯一的。

示例：秩亏缺矩阵的QR分解

考虑秩为1的矩阵：

\[A = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \\ 1 & 2 & 3 \end{bmatrix} \]

一种可能的 QR 分解为：

\[Q = \begin{bmatrix} \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{3}} & 0 & -\frac{2}{\sqrt{6}} \end{bmatrix}, \quad R = \begin{bmatrix} \sqrt{3} & 2\sqrt{3} & 3\sqrt{3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

另一种分解为：

\[Q = \begin{bmatrix} \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{3}} & 0 & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix}, \quad R = \begin{bmatrix} \sqrt{3} & 2\sqrt{3} & 3\sqrt{3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

两者都满足 \(A = QR\)，说明分解不唯一。

注记

完全 QR 分解不唯一的根本原因是：\(Q_{\perp}\) 不唯一，其列向量可以随意换位置。