1.5 几类特殊矩阵

1.5.1 对称正定矩阵

定义1.16 设 $A \in \mathbb{C}^{n \times n}$

若对所有向量 $x \in \mathbb{C}^n$ 有 $\operatorname{Re}(x^{*}Ax) \geq 0$ , 则称 $A$ 是半正定的;
若对所有非零向量 $x \in \mathbb{C}^n$ 有 $\operatorname{Re}(x^*Ax) > 0$ , 则称 $A$ 是正定的;
若 $A$ 是Hermite的且半正定, 则称 $A$ 为Hermite半正定;
若 $A$ 是Hermite的且正定, 则称 $A$ 为Hermite正定;
若 $A \in \mathbb{R}^{n \times n}$ 是对称的且半正定, 则称 $A$ 为对称半正定;
若 $A \in \mathbb{R}^{n \times n}$ 是对称的且正定, 则称 $A$ 为对称正定.

若对所有向量 $x\in \mathbb{C}^n$ 有 $x^{*}Ax\in \mathbb{R}$ ，则 $A^{*} = A$
A 本讲义中, 正定和半正定矩阵不要求是对称或Hermite.

若 $-A$ 是半正定的, 则称 $A$ 是半负定的; 若 $-A$ 是正定的, 则称 $A$ 是负定的.

定理1.50 设 $A \in \mathbb{C}^{n \times n}$ , 则 $A$ 正定 (或半正定) 的充要条件是矩阵 $H = \frac{1}{2}(A + A^*)$ 正定 (或半正定). (留作练习)

如果 $A$ 是实矩阵, 则只需在实数域中考虑即可.

定理1.51 设 $A \in \mathbb{R}^{n \times n}$ , 则 $A$ 正定 (或半正定) 的充要条件是对任意非零向量 $x \in \mathbb{R}^n$ 有 $x^\top A x > 0$ (或 $x^\top A x \geq 0$ ). （留作练习）

对称正定矩阵的基本性质

设 $A\in \mathbb{C}^{n\times n}$

(1) $A$ Hermite 正定当且仅当 $A$ Hermite 且所有特征值都是正的;
(2) $A$ Hermite 正定当且仅当存在酉矩阵 $U$ 使得 $A = U\Lambda U^{*}$ , 其中 $\Lambda$ 为对角矩阵且对角线均为正实数;
(3) A Hermite 正定当且仅当 $S^{*}AS$ 对称正定, 其中 $S \in \mathbb{C}^{n \times n}$ 是一个任意的非奇异矩阵;
(4) 若 $A$ Hermite 正定, 则 $A$ 的任意主子矩阵都 Hermite 正定;
(5) 若 $A$ Hermite 正定, 则 $A$ 的所有对角线元素都是正的, 且 $\max_{i \neq j} \{|a_{ij}|\} < \max_{i} \{a_{ii}\}$ , 即绝对值最大的元素出现在对角线上.

A 以上结论在实数域中也成立.

平方根

如果 $A$ 是Hermite(半)正定矩阵, 则可以定义其平方根, 即存在唯一的Hermite(半)正定矩阵 $B$ , 使得 $B^{2} = A$ . 事实上, 我们有下面更一般的结论[73].

定理1.52 设 $A \in \mathbb{C}^{n \times n}$ 是一个Hermite半正定矩阵, $k$ 是一个给定的正整数, 则存在唯一的Hermite半正定矩阵 $B \in \mathbb{C}^{n \times n}$ 使得

B ^ {k} = A.

同时，我们还有下面的性质：

(1) $\operatorname{rank}(B) = \operatorname{rank}(A)$ , 因此, 若 $A$ 是正定的, 则 $B$ 也正定;
(2) 如果 $A$ 是实矩阵的, 则 $B$ 也是实矩阵.

特别地, 当 $k = 2$ 时, 称 $B$ 为 $A$ 的平方根, 记为 $A^{\frac{1}{2}}$ .

(留作课外自习)

Hermite 正定矩阵与内积

Hermite 正定矩阵与内积之间有如下的一一对应关系.

定理1.53 设 $(\cdot, \cdot)$ 是 $\mathbb{C}^n$ 上的一个内积, 则存在一个Hermite正定矩阵 $A \in \mathbb{C}^{n \times n}$ 使得

(x, y) = y ^ {*} A x.

反之, 若 $A \in \mathbb{C}^{n \times n}$ 是Hermite正定矩阵, 则

f (x, y) \triangleq y ^ {*} A x

是 $\mathbb{C}^n$ 上的一个内积

(留作练习)

该结论在实数域中也成立.

1.5.2 对角占优矩阵

定义1.17 设 $A \in \mathbb{C}^{n \times n}$ , 若

\left| a _ {i i} \right| \geq \sum_ {j \neq i} \left| a _ {i j} \right|

对所有 $i = 1,2,\dots ,n$ 都成立，且至少有一个不等式严格成立，则称 $A$ 为弱行对角占优，简称弱对角占优或对角占优.若所有不等式都严格成立，则为严格行对角占优或严格对角占优.

类似地，可以定义列对角占优和严格列对角占优

定理1.54 若 $A \in \mathbb{C}^{n \times n}$ 是严格对角占优矩阵, 则 $A$ 非奇异. (板书)

证明. 我们使用反证法. 假设 $A$ 奇异, 即 $Ax = 0$ 存在非零解, 不妨设为 $x = [x_{1}, x_{2}, \ldots, x_{n}]^{\top}$ . 不失一般性, 设下标 $k$ 满足 $\|x\|_{\infty} = |x_{k}|$ , 则 $|x_{k}| > 0$ . 考察 $Ax = 0$ 的第 $k$ 个方程:

a _ {k 1} x _ {1} + a _ {k 2} x _ {2} + \dots + a _ {k n} x _ {n} = 0.

可得

\left| a _ {k k} \right| = \frac {1}{\left| x _ {k} \right|} \left| \sum_ {j = 1, j \neq i} ^ {n} a _ {k j} x _ {j} \right| \leq \sum_ {j = 1, j \neq i} ^ {n} \left| a _ {k j} \right| \cdot \frac {\left| x _ {j} \right|}{\left| x _ {k} \right|} \leq \sum_ {j = 1, j \neq i} ^ {n} \left| a _ {k j} \right|,

这与 $A$ 严格对角占优矛盾. 所以 $A$ 非奇异

如果 $A$ 是严格对角占优的, 则可以给出 $\| A^{-1}\| _1$ 的一个估计.

定理1.55 [57] 设 $A \in \mathbb{R}^{n \times n}$ 严格列对角占优, 记

\delta \triangleq \min _ {1 \leq j \leq n} \left(\left| a _ {j j} \right| - \sum_ {i = 1} ^ {n} \left| a _ {i j} \right|\right) > 0,

则有

\left\| A ^ {- 1} \right\| _ {1} \leq \delta^ {- 1}.

该定理中的 $\delta$ 是衡量对角占优程度的一个重要指标：如果 $\delta$ 接近于0，则表示对角占优性很弱.

1.5.3 不可约矩阵

定义1.18 设 $A \in \mathbb{C}^{n \times n}$ , 如果存在置换矩阵 $P$ 使得 $PAP^{\top}$ 为块上三角矩阵, 即

P A P ^ {\top} = \left[ \begin{array}{c c} A _ {1 1} & A _ {1 2} \\ 0 & A _ {2 2} \end{array} \right], \quad A _ {1 1} \in \mathbb {C} ^ {k \times k}, \quad A _ {2 2} \in \mathbb {C} ^ {(n - k) \times (n - k)} \tag {1.11}

其中 $1 \leq k < n$ , 则称 $A$ 是可约的, 否则就称 $A$ 为不可约的.

如果 $A$ 是 $1 \times 1$ 矩阵, 则 $A$ 不可约当且仅当 $A$ 非零.

如果 $A \in \mathbb{C}^{n \times n}$ 是可约的, 则 $A$ 至少有 $n - 1$ 个零.

不可约的意义

若 $A$ 可约, 即存在置换矩阵 $P$ , 使得

P A P ^ {\mathsf {T}} = \left[ \begin{array}{c c} A _ {1 1} & A _ {1 2} \\ 0 & A _ {2 2} \end{array} \right],

则线性方程组 $Ax = b$ 等价于 $PAP^{\mathsf{T}}Px = Pb$ . 记 $y \triangleq Px, f \triangleq Pb$ , 则

\left[ \begin{array}{c c} A _ {1 1} & A _ {1 2} \\ 0 & A _ {2 2} \end{array} \right] \left[ \begin{array}{c} y _ {1} \\ y _ {2} \end{array} \right] = \left[ \begin{array}{c} f _ {1} \\ f _ {2} \end{array} \right].

因此, 原方程组就转化为下面两个更小规模的子方程组

\left\{ \begin{array}{l} A _ {2 2} y _ {2} = f _ {2}, \\ A _ {1 1} y _ {1} = f _ {1} - A _ {1 2} y _ {2}. \end{array} \right.

显然, 求解这两个方程组比求解原方程组所需的运算量更少.

对于特征值问题, $A$ 的特征值就是 $A_{11}$ 和 $A_{22}$ 的特征值的并, 因此也只需考虑子矩阵 $A_{11}$ 和

$A_{22}$ 的特征值即可.

如果 $A_{22}$ 或 $A_{11}$ 仍然是可约的, 则可以转化为更小规模的子问题, 直到不可约为止. 因此我们在讨论某些算法的性质时, 一般只需考虑不可约情形.

由于 $PAP^{\top}$ 保持 $A$ 的对角线元素仍然在对角线上, 因此由定理 1.59 可知, 主对角线元素是否为零并不影响矩阵的可约性.

推论1.56 设 $A = [a_{ij}] \in \mathbb{C}^{n \times n}$ 不可约, 则 $A + D$ 也不可约, 其中 $D$ 是任意对角矩阵. 特别地, $B \triangleq A - \mathrm{diag}(a_{11}, a_{22}, \ldots, a_{nn})$ 不可约.

如果 $A$ 可约, 即存在置换矩阵 $P$ 使得 $PAP^{\top}$ 具有(1.11)的形式, 则对任意正整数 $k$ , 有

P A ^ {k} P ^ {\intercal} = \left(P A P ^ {\intercal}\right) ^ {k} = \left[ \begin{array}{c c} A _ {1 1} ^ {k} & \tilde {A} _ {1 2} ^ {(k)} \\ 0 & A _ {2 2} ^ {k} \end{array} \right]. \tag {1.12}

于是我们有下面的结论

定理1.57 设 $A \in \mathbb{C}^{n \times n}$ . 若 $A$ 可约, 则 $A^k$ 也可约. 反之, 若存在一个正整数 $k$ , 使得 $A^k$ 是不可约的, 则 $A$ 也不可约.

需要指出的是, 不可约矩阵的幂不一定是不可约的. 如 $A = \left[ \begin{array}{ll} -1 & 1 \\ 1 & 1 \end{array} \right]$ 不可约, 但 $A^2 = \left[ \begin{array}{ll}2 & 0 \\ 0 & 2 \end{array} \right]$ 可约.

下面的定理给出了一个矩阵不可约的充要条件

定理1.58 设 $A = [a_{ij}] \in \mathbb{C}^{n \times n}$ , 指标集 $\mathbb{Z}_n = \{1, 2, \dots, n\}$ , 则 $A$ 可约的充要条件是存在非空指标集 $S, T \subset \mathbb{Z}_n$ 满足 $S \oplus T = \mathbb{Z}_n$ , 使得

a _ {i j} = 0, \quad i \in \mathcal {S}, \quad j \in \mathcal {T}.

(板书)

证明. 必要性. 设 $A$ 可约, 即存在置换矩阵 $P$ 使得 $PAP^{\mathsf{T}} = \left[ \begin{array}{cc}A_{11} & A_{12}\\ 0 & A_{22} \end{array} \right]$ . 设 $PA$ 是将 $A$ 的第 $i_1,i_2,\ldots ,i_k$ 行置换到前 $k$ 行, 则 $PAP^{\mathsf{T}}$ 是将 $PA$ 的第 $i_1,i_2,\ldots ,i_k$ 列置换到前 $k$ 列. 令 $\mathcal{T} = \{i_1,i_2,\dots ,i_k\}, S = \mathbb{Z}\setminus \mathcal{T}$ , 则有

a _ {i j} = 0, \quad i \in \mathcal {S}, \quad j \in \mathcal {T}.

充分性. 设存在非空集合 $S$ 和 $\mathcal{T}$ 满足 $J \oplus \mathcal{T} = \mathbb{Z}_n$ , 使得对任意 $i \in S, j \in \mathcal{T}$ 都有 $a_{ij} = 0$ . 设 $\mathcal{T} = \{i_1, i_2, \ldots, i_k\}$ , 构造置换矩阵 $P$ , 其作用是将矩阵 $A$ 的第 $i_1, i_2, \ldots, i_k$ 行置换到前 $k$ 行, 则

$PAP^{\mathsf{T}}$ 的第 $k + 1$ 行至第 $n$ 行和前 $k$ 列组成的子矩阵是0矩阵,故 $PAP^{\mathsf{T}}$ 具有(1.11)结构,即 $A$ 可约. □

下面是判断矩阵是否可约的另一个充要条件

定理1.59 设 $A = [a_{ij}] \in \mathbb{C}^{n \times n}$ , 指标集 $\mathbb{Z}_n = \{1, 2, \dots, n\}$ , 则 $A$ 可约的充要条件是存在两个相异的正整数 $k, l \in \mathbb{Z}_n$ , 使得对任意指标序列 $\{i_1, i_2, \dots, i_r\} \subseteq \mathbb{Z}_n$ , 都有

a _ {k i _ {1}} a _ {i _ {1} i _ {2}} \dots a _ {i _ {r} l} = 0.

这里 $r > 0$ 是任意正整数

(留作课外自习)

定理1.60的等价描述

矩阵 $A = [a_{ij}]\in \mathbb{C}^{n\times n}$ 不可约的充要条件是：对任意两个相异正整数 $k,l\in \mathbb{Z}_n$ ，都存在一个指标序列 $\{i_1,i_2,\dots ,i_m\} \subseteq \mathbb{Z}_n$ 使得

a _ {k i _ {1}} a _ {i _ {1} i _ {2}} \dots a _ {i _ {m} l} \neq 0.

如果用有向图表示矩阵, 则不可约当且仅当有向图是强连通的, 即任意两个节点之间都存在一条路径.

我们知道, 严格对角占优矩阵是非奇异的. 如果 $A$ 是不可约对角占优矩阵, 则可以同样证明 $A$ 是非奇异的.

定理1.60 设 $A \in \mathbb{C}^{n \times n}$ 是不可约的弱对角占优矩阵, 则 $A$ 非奇异.