02_非负矩阵与 M 矩阵

1 .第二讲 非负矩阵与 M 矩阵 • 非负矩阵 • 不可约非负矩阵 • M -矩阵与单调矩阵 • 对角占优 M -矩阵 注记 若无特别注明, 本讲内容都 非负矩阵在很多领域都有重要应用, 如数理经济, 运筹, 图像处理等. 是在 实数域 中讨论. 同样, 它在矩阵理论与数值代数中也扮演着很重要的角色. 

2 .1 非负矩阵 1.1 非负矩阵基本性质 1.2 正矩阵 1.3 非负矩阵的更多性质 2/63 

3 .非负矩阵, 正矩阵 非负矩阵 元素都是非负实数 正矩阵 元素都是正实数 记号说明: 设 A = [aij ] ∈ Rm×n , B = [bij ] ∈ Rm×n , 则 • A≥B ⇐⇒ aij ≥ bij , 1 ≤ i ≤ m, 1 ≤ j ≤ n • A>B ⇐⇒ aij > bij , 1 ≤ i ≤ m, 1 ≤ j ≤ n • 如果 A ≥ B 且 A ̸= B, 则记为 A ⪈ B. • 相类似地, 我们可以定义记号 “≤”, “<” 和 “⪇”. [ ] • A 的绝对值定义为 |A| = |aij | . 3/63 

4 .基本运算 引理 1 设矩阵 A, B ∈ Cn×n , 向量 x ∈ Cn , 则容易验证 (1) |Ax| ≤ |A| |x|; (2) |AB| ≤ |A| |B|; (3) |Ak | ≤ |A|k , k = 1, 2, . . .; (4) ∥A∥F = ∥ |A| ∥F ; (5) |A| ≤ |B| =⇒ ∥A∥F ≤ ∥B∥F . 4/63 

5 .1.1 非负矩阵基本性质 引理 2 设矩阵 A, B, C, D ∈ Rn×n , 向量 x ∈ Rn . (1) 若 0 ≤ A ≤ B, 0 ≤ C ≤ D, 则 0 ≤ AC ≤ BD. (2) 若 0 ≤ A ≤ B, 则 0 ≤ Ak ≤ B k , k = 1, 2, . . .. (3) 若 A > 0 且 x ⪈ 0, 则 Ax > 0. (4) 若 A ≥ 0, x > 0 且 Ax = 0, 则 A = 0. 由这个引理, 我们可以得到一个很有用的结论. 定理 3 设 A ∈ Cn×n , B ∈ Rn×n . 如果 |A| ≤ B, 则 1 ρ(X) = lim ∥X k ∥Fk ρ(A) ≤ ρ(|A|) ≤ ρ(B). (板书) k→∞ 5/63 

6 .由定理 3 可直接得到下面的两个结论. 推论 4 设 A, B ∈ Rn×n , 若 0 ≤ A ≤ B, 则 ρ(A) ≤ ρ(B). 推论 5 设 A = [aij ] ∈ Rn×n 非负, Ak 是 A 的 k 阶主子矩阵, 其中 1 ≤ k ≤ n, 则 ρ(Ak ) ≤ ρ(A). 特别地, 我们有 max aii ≤ ρ(A). 1≤i≤n (练习) 6/63 

7 .非负矩阵的谱半径, 矩阵行和, 矩阵列和 引理 6 设 A ∈ Rn×n 非负. (1) 如果 A 的行和是常数, 则 ρ(A) = ∥A∥∞ . (2) 如果 A 的列和是常数, 则 ρ(A) = ∥A∥1 . (板书) 7/63 

8 .定理 7 设 A 非负, 则 ∑ n ∑ n min aij ≤ ρ(A) ≤ max aij (2.1) 1≤i≤n 1≤i≤n j=1 j=1 且 ∑ n ∑ n min aij ≤ ρ(A) ≤ max aij . (2.2) 1≤j≤n 1≤j≤n i=1 i=1 (板书) 推论 8 设 A ∈ Rn×n 非负. 如果 A 的某一行或某一列的元素都是正 的, 则 ρ(A) > 0. 特别地, 如果 A > 0, 则 ρ(A) > 0. 8/63 

9 .一个推广的结论 设 X 非奇异, 则 ρ(X −1 AX) = ρ(A). 令 X = diag(x1 , x2 , . . . , xn ), xi > 0, i = 1, 2, . . . , n. 由定理 7 可得 推论 9 设 A 非负. 则对任意正向量 x = [x1 , x2 , . . . , xn ]⊺ , 有 1 ∑ 1 ∑ n n min aij xj ≤ ρ(A) ≤ max aij xj (2.3) 1≤i≤n xi 1≤i≤n xi j=1 j=1 和 ∑ n aij ∑ n aij min xj ≤ ρ(A) ≤ max xj . (2.4) 1≤j≤n i=1 xi 1≤j≤n i=1 xi 9/63 

10 .非负矩阵谱半径的一个估计 定理 10 设 A ∈ Rn×n 非负, x ∈ Rn 为正向量. (1) 如果 αx ≤ Ax ≤ βx, 则 α ≤ ρ(A) ≤ β. (2) 如果 αx < Ax < βx, 则 α < ρ(A) < β. (板书) 由这个定理立即可得: 推论 11 设 A ∈ Rn×n 非负. 如果 A 有正特征向量, 则其对应的特征 值一定是 ρ(A), 即若 A ≥ 0, x > 0 且 Ax = λx, 则 λ = ρ(A). 10/63 

11 .1.2 正矩阵 正矩阵除了具有非负矩阵的性质外, 还具有一些特殊的性质. 引理 12 设 A ∈ Rn×n 是正矩阵, 如果存在非零向量 x ∈ Cn 使得 Ax = λx 且 |λ| = ρ(A), 则 A|x| = ρ(A) |x| 且 |x| > 0. (板书) 推论 13 设 A 是正矩阵, 则 ρ(A) 是 A 的一个特征值, 且存在一个正 向量 x ∈ Rn 使得 Ax = ρ(A)x. (板书) 将上面的结论作用到 A⊺ , 则可以得到下面的结论. 推论 14 设 A 是正矩阵, 则存在一个正向量 y ∈ Rn 使得 A⊺ y = ρ(A)y, 即 y ⊺ A = ρ(A)y ⊺ . 11/63 

12 .引理 15 设 A 是正矩阵. 若存在非零向量 x ∈ Cn 满足 Ax = λx 且 |λ| = ρ(A), 则存在一个实数 θ ∈ R 使得 e−i θ x = |x| > 0. (板书) 推论 16 设 A 是正矩阵. 如果 λ 是 A 的特征值, 且 λ ̸= ρ(A), 则 |λ| < ρ(A), 也就是说, 如果 λ 是 A 的特征值, 且 |λ| = ρ(A), 则 λ = ρ(A). (板书) 推论 17 设 A 是正矩阵, 则 ρ(A) 是 A 的几何重数为 1 的特征值. (板书) 由推论 17 可知, 如果 z 是对应于 ρ(A) 的特征向量, 则 |z| > 0, 即与 ρ(A) 对应的特征向量一定不含零分量. 12/63 

13 .推论 18 设 A ∈ Rn×n 是正矩阵, 则存在唯一的正向量 x ∈ Rn 使得 ∑ n x 称为 A 的 (右) Perron 向量, Ax = ρ(A) x 且 xi = 1. i=1 ρ(A) 称为 A 的 Perron 根. 引理 19 设 A 是正矩阵, x, y ∈ Rn 分别为 ρ(A) 的左, 右正特征向量, 且 x⊺ y = 1. 定义矩阵 L ≜ xy ⊺ , 则 L > 0 且 k k (1) (A − ρ(A) L) = Ak − (ρ(A)) L, k = 1, 2, ...; (2) A − ρ(A)L 的所有非零特征值均为 A 的特征值; (3) ρ (A − ρ(A) L) < ρ(A); ( )k 1 (4) lim A = xy ⊺ . 若取 x 为 A 的 (右) Perron 向 k→∞ ρ(A) 量, 则 y 唯一确定, 称为 A 的 左 Perron 向量. (板书) 13/63 

14 .定理 20 设 A ∈ Rn×n 是正矩阵, 则特征值 ρ(A) 的代数重数为 1, 即 λ = ρ(A) 是 A 的单重特征值. (板书) 定理 21 (Perron 定理) 设 A ∈ Rn×n 是正矩阵, 则 (1) ρ(A) > 0; (2) ρ(A) 是 A 的单重特征值; (3) A 的所有其它特征值的模都小于 ρ(A); (4) 存在正向量 x ∈ Rn , 使得 Ax = ρ(A) x, 同时, 如果 y ∈ Rn 是 ρ(A) 对应的特征向量, 则 |y| > 0; ( )k 1 Perron 定理 是正矩阵的一个 (5) lim A = xy ⊺ > 0 其中 x, y 为定理 19 中的向量. 著名定理. k→∞ ρ(A) 14/63 

15 .1.3 非负矩阵的更多性质 正矩阵的一些性质可以推广到非负矩阵情形. 引理 22 设 A ∈ Rn×n 非负, 则 (1) ρ(A) 是 A 的特征值; (2) 存在向量 x ⪈ 0 和 y ⪈ 0, 使得 ⊺ Ax = ρ(A)x, A y = ρ(A)y. (板书) 需要指出的是, 正矩阵的谱半径一定是正的, 但对于非负矩阵, 其谱半 径可能为 0, 如严格非负下三角矩阵. 15/63 

16 .引理 23 设 A ∈ Rn×n 非负. 如果存在实数 α ∈ R 和向量 x ∈ Rn , 使 得 x ⪈ 0 且 Ax ≥ αx, 则 ρ(A) ≥ α. (板书) 注记 该结论与定理 10 类似, 但定理 10 中要求 x > 0. 引理 24 设 A ∈ Rn×n 非负, 则 1 ∑ n ρ(A) = max min aij xj . x∈R , x⪈0 1≤i≤n, xi ̸=0 n xi j=1 (板书) 16/63 

17 .引理 25 设 A ∈ Rn×n 非负且存在正的左特征向量. 如果存在向量 x ⪈ 0 满足 Ax ≥ ρ(A) x 或 Ax ≤ ρ(A) x, 则 Ax = ρ(A) x. (板书) 注记 ] [ 1 0 需要指出的是, 非负矩阵不一定存在正特征向量, 如 A = . 0 2 注记 由前面结论可知: 如果 A ≥ 0, 则 ρ(A) 是 A 的特征值, 但不一定是 单重的. 例如 A = I, 则 ρ(A) = 1 是 A 的特征值, 且重数为 n. 因此, 对于一般的非负矩阵, 无法定义 “Perron 向量”. 17/63 

18 .λ = ρ(A) 是单重特征值的一个充分条件: 定理 26 设 A ∈ Rn×n 非负. 如果存在正整数 k 使得 Ak > 0, 则 ρ(A) 是 A 的单重特征值. (板书) 非负矩阵的数值域半径与谱半径之间的关系: 推论 27 设 A ∈ Rn×n 是非负矩阵, 则 ( ) r(A) = ρ H(A) . (板书) 18/63 

19 .2 不可约非负矩阵 2.1 可约与不可约 2.2 不可约非负矩阵 2.3 本原矩阵 2.4 随机矩阵 19/63 

20 .2.1 可约与不可约 定义 1 设 A ∈ Cn×n , n ≥ 2. 如果存在一个置换矩阵 P 使得 [ ] ⊺ A11 A12 P AP = , A11 ∈ Cr×r , A22 ∈ C(n−r)×(n−r) 0 A22 其中 1 ≤ r < n, 则称 A 是可约的, 否则就称 A 为 不可约的. • 如果 A 是 1 × 1 矩阵, 则 A 不可约当且仅当 A 非零. • 如果 A ∈ Cn×n 是可约的, 则 A 至少有 n − 1 的零. • 如果 A 是可约的, 则 A 的特征值为 A11 和 A22 特征值的并. • 如果 A 是可约的, 则 Ax = b 等价于两个子方程. 20/63 

21 .如果 A 可约, 则对任意正整数 k, 有 [ ] (k) k ⊺ ⊺ k Ak11 A˜12 P A P = (P AP ) = . (2.5) 0 Ak22 所以我们有下面的结论: 引理 28 若 A 可约, 则 Ak 也可约. 反之, 若存在一个正整数 k, 使得 Ak 是不可约的, 则 A 也不可约. 注记 需要指出的是, [ 在一般情况下, ] 不可约矩阵的幂不一定是不可约的. [ ] −1 1 2 0 如A= 不可约, 但 A2 = 可约. 1 1 0 2 21/63 

22 .矩阵不可约的一个充要条件 定理 29 设 A = [aij ] ∈ Cn×n , 指标集 Zn = {1, 2, . . . , n}. 则 A 可约 的充要条件是存在两个互不相交的非空子集 S 和 T 满足 S ⊕ T = Zn , 且对任意的 i ∈ S 和 j ∈ T 有 aij = 0. (板书) 注记 由定理 29 可知, 主对角线元素是否为零并不影响矩阵的可约性. 推论 30 设 A 不可约, 则 B ≜ A − diag(a11 , a22 , . . . , ann ) 也不可约. 22/63 

23 .矩阵是否可约的另一个充要条件 定理 31 设 A = [aij ] ∈ Cn×n , 指标集 Zn = {1, 2, . . . , n}. 则 A 可约 的充要条件是存在两个相异的正整数 k, l ∈ Zn , 使得对任意指标序 列 {i1 , i2 , . . . , ir } ⊆ Zn , 都有 aki1 ai1 i2 · · · air l = 0. 这里 r > 0 是任意正整数. (板书) 等价描述: 矩阵 A = [aij ] ∈ Cn×n 不可约的充要条件是: 对任意两个 相异正整数 k, l ∈ Zn , 都存在一个指标序列 {i1 , i2 , . . . , im } ⊆ Zn 使得 aki1 ai1 i2 · · · aim l ̸= 0. 23/63 

24 .可约矩阵的规范型 [ ] A11 A12 如果 中的子矩阵 A11 或 A22 仍然是可约的, 则我们还可 0 A22 以将它们置换成块上三角形式. 依此类推, 最后可得: 存在一个置换矩阵 P 使得   A11 A12 · · · A1k    0 A22 · · · A2k  ⊺  P AP =  . ..  (2.6) .. .. ,  .. . . .  0 0 · · · Akk 其中 Aii (i = 1, 2, . . . , k) 为不可约或为零. 我们称 (2.6) 为可约矩阵 A 的 规范型 (Normal Form). 24/63 

25 .非负矩阵谱半径为零的充要条件 定理 32 设 A ∈ Rn×n 非负, 则 ρ(A) = 0 的充要条件是 A 可约且其 规范型是一个严格上三角矩阵. (练习) 注记 一个有意思的现象: 通常, 如果某个元素全不为零的矩阵具有某种 性质, 则这个性质往往能推广到不可约矩阵. 25/63 

26 .2.2 不可约非负矩阵 非负矩阵不可约的一个充要条件: 引理 33 设 A ∈ Rn×n 非负, 则 A 不可约的充要条件是 (I + A)n−1 > 0. (板书) 由引理 33 和引理 28, 我们可得下面的结论. 推论 34 设 A ∈ Rn×n 非负且对角线元素全为正. 则 A 不可约的充 要条件是 An−1 > 0. 26/63 

27 .引理 35 设 A ∈ Cn×n . 如果 ρ(A) < 1, 则 I − A 非奇异且 (I − A)−1 = I + A + A2 + · · · . (2.7) 反之, 如果 (2.7) 右端的级数收敛, 则 ρ(A) < 1. (板书) 定理 36 设 A ∈ Rn×n 非负. 如果 ρ(A) < 1, 则 A 不可约的充要条件 是 (I − A)−1 > 0. (板书) 对上面的结论做进一步推广: 推论 37 设 A ∈ Rn×n 非负, 实数 α 满足 α > ρ(A), 则 A 不可约的充 要条件是 (αI − A)−1 > 0. (练习) 27/63 

28 .Perron-Frobenius 定理 定理 38 (Perron-Frobenius) 设 A ∈ Rn×n 非负不可约, 则 (1) ρ(A) > 0; (2) ρ(A) 是 A 的单重特征值; (3) 存在唯一的正向量 x, 满足 ∥x∥1 = 1, 使得 Ax = ρ(A) x; (4) 存在唯一的正向量 y, 满足 y ⊺ x = 1, 使得 A⊺ y = ρ(A) y; 我们称定理 38 中的正向量 x (5) A 的所有非负特征向量都对应于特征值 λ = ρ(A). 和 y 分别为 A 的右 Perron 向 (板书) 量和左 Perron 向量. 28/63 

29 .推论 39 设 A 非负不可约, 向量 x ⪈ 0. 则下面的结论成立: (1) 若 Ax ≥ ρ(A) x 或 Ax ≤ ρ(A) x, 则 Ax = ρ(A) x; (2) 若 Ax ≥ αx, 则 ρ(A) ≥ α, 进一步, 若 Ax ̸= αx, 则 ρ(A) > α; (3) 若 Ax ≤ βx, 则 ρ(A) ≤ β 且 x > 0, 进一步, 若 Ax ̸= βx, 则 ρ(A) < β. (板书) 29/63