当前位置:首页 >> 数学 >>

§3.2可约和不可约方阵_图文

§3.2 可约和不可约方阵

一、基本概念
1. 置换方阵
N阶方阵P称为置换方阵,如果P是由单位方阵 I n

经过行的置换后所得.
2. 置换相似 设 ? 是集 ? 1,2,?, n? 上的一个置换,则

P ? P? ? ? Pij ?

1, 若? ? i ? ? j ? ? 其中 Pij ? ? ? ?0, 若? ? i ? ? j
目录 上页 下页 返回 结束

North University of China

是由 ? 所确定的置换方阵,即 P? 的第i行是 I n 的 第? ?i ?行. 因此,对任一n阶方阵A, P ? A的第i行

正是A的第 ? ?i ?行, AP?T 的第j列正是A的第? ? j ?列.
所以可以得到
T ?1 T ?1 P ? P , P AP ? P AP ? ? ? ? ? ?

称为与A置换相似.

North University of China

目录 上页 下页 返回

结束

3. A的可约性也可定义如下: n阶方阵A可约

? A有零子矩阵 A[i1 il i1 il ) ? 0,
其中1 ? i1 ? 特别地, A 可约 ? AT 可约;

? il ? n,1 ? l ? n ? 1.

A可约与A的主对角线上元素的任何改动无关.

North University of China

目录 上页 下页 返回

结束

例1

? 1 1 0? ? ? 不可约,因为不具有1×2或 A ? ?1 1 1? ? 0 1 1? ? ?

2×1的零子矩阵. 从而

? 0 1 0? ? ? A ? I ? ? 1 0 1 ? 也不可约. ? 0 1 0? ? ?

North University of China

目录 上页 下页 返回

结束

4. 关键性的概念: 一个n阶方阵 A ? aij 可以对应一个有向图 D? A? : 相连 D? A? 有n个顶点 V1 ,?,Vn . 从 Vi 到 V j用弧 VV i j 当且仅当 aij ? 0 , 这时称 Vi和 V j为弧 VV i j 的起点和

? ?

终点. 起点和终点重合的弧称为环. 有向图可以在
平面上形象地画出来.

North University of China

目录 上页 下页 返回

结束

例2

?1 1 0? ? ? A ? ?1 1 1? ?0 1 1? ? ?
?0 1 1? ? ? B ? ?1 0 1? ?1 0 0? ? ?

D ? A?

D ? B?

North University of China

目录 上页 下页 返回

结束

5. 有关有向图D的一些术语

·从V j 到 Vk 的路:就是顺序相连的一个顶点序列
Vi0 ? V j ,Vi1 , ,Vil ? Vk , 其中 Vit Vit ?1 是 D 中的弧 ?t ? 0,1, , l ?1? , 这条路可记为 ?Vi ,Vi , ,Vi ? .
0 1 l

如果它所经过的顶点 Vi0 ,Vi1 , 相同,则称这条路是简单的.

,Vil 中没有两点

·起点和终点相同的路称为回路.
North University of China
目录 上页 下页 返回 结束

·除起点和终点相同外,所经过的顶点中再没有两
点相同的回路称为简单回路. 例2 中的 D ? B ?有简单路如下,

?V2 ,V3 ,V1 ?,简单回路?V1 ,V2 ,V3 ,V1 ? ?V1 ,V2 ,V1 ? ?V3 ,V1 ,V3 ? ,有回路 ?V1 ,V2 ,V1,V3 ,V1 ? 等等.

North University of China

目录 上页 下页 返回

结束

·D中两个不同的顶点 V j 和 Vk 称为是互通的,
如果既有从 V j 到 Vk 的路,又有从 Vk 到 V j 的路.

若D中任意两个不同的顶点都互通,则称有向图D ·
为强连通的. 根据这个定义,只有一个顶点的图必是强连通的.
D ? B ?都是强连通图. 例2中的 D ? A? ,

North University of China

目录 上页 下页 返回

结束

下例中的图 D ? C ? 不是强连通的:
?0 ? ?? ?0 C ?? ?0 ?0 ? ?0 ?


例3

0 ? ? 0 0? ? 0 0 0 0 0? ? 0 0 ? 0? ? (×表示非零数) 0 0 0 ? 0? 0 0 ? 0 0? ? 0 ? 0 ? 0? ?

D ?C ?

D ?C ?



North University of China

目录 上页 下页 返回

结束

·顶点集的等价类
显然,一个回路上的任意两点必互通. 另外,

图D中顶点间的互通关系是一种等价关系. 所以若
将D的顶点集按互通关系分成等价类,则同一回路

上的所有顶点一定属于同一等价类.
例3的有向图 D ? C ? 的顶点集可以分成三个等价类:

?V1,V2 ,V3? ?V4 ,V5? ?V6 ?

North University of China

目录 上页 下页 返回

结束

现在用图论的术语来刻划方阵的可约性. 定理3 n ? ? 1? 阶方阵A可约 ? D ? A?不强连通. 证

? ?? 设A可约,则
?1 ? i1 ? ? il ? n,1 ? l ? n ? 1
il | i1 il ? ? 0 . 转换成 D ? A?的语言,就是

使 A? ?i1

可将 D ? A?的顶点集 V ? ?V1 ,

,Vn ?划分成两个(非

空)子集 V ' ? Vi1 , Vil 和 V ?? ? V
North University of China

?

?

\ V ?,而在
目录 上页 下页 返回 结束

D ? A? 中没有起点属于V ?,终点属于V ??的弧. 因此

V ?中任一顶点不能通到 V ?? 中的顶点,故 D ? A?不强
连通.

North University of China

目录 上页 下页 返回

结束

? ?? :设D ? A?不强连通. 则其顶点集V 按互通
关系可划分成 k ? 1个(非空)等价类 U1 ,

,U k.

因此这k类中至少有一类,不妨设为U1 ,使D ? A?中 没有起点属于U1而终点不属于 U1 的弧(简称为没

有弧离开 U1 . 因为若每个U i ? i ? 1,

, k ? 都有弧

离开的话,则不难得知 D ? A? 中将有一个回路,它

North University of China

目录 上页 下页 返回

结束

Vi ,?,Vi ? ,其中 的顶点不属于同一类). 记 U1 ? ?
1 l

1 ? i1 ?
A? ?i1 il | i1

? il ? n , 1 ? l ? n ?1,则有
il ? ? 0.

矩阵与图之间有如下最基本的联系: 命题 设 A ? aij 是 n ? ? 1? 阶非负方阵. 则在

? ?

North University of China

目录 上页 下页 返回

结束

l p , q ? A ?位置处的元素 ?pq ? 0 当且仅当 D ? A? A 中?
l

中有V p 到 Vq 的长为l的路. 证 D ? A?中有路

?V

p

? Vi0 ,Vi1 , ,Vil ?1 ,Vil ? Vq ? a pi1 ai1i2

?

ail ?1q ? ? Al ? ? 0.
pq

North University of China

目录 上页 下页 返回

结束

由此易得不可约非负方阵的下述刻划:
定理4 设A是n ? ? 1?阶非负方阵. 则 A不可约当 且仅当 ? I n ? A?
n ?1

?0.



A不可约 ? D ? A?强连通 ?对任给的
D ? A?中有从 V p 到
pq

p?q

l ? n ? 1 ? ? Al ? ? 0 ? I ? A ? ? ? I ? A?
n ?1

Vq 的路,并不妨设路长
? An?1 ? 0

? 0.

North University of China

目录 上页 下页 返回

结束

定理4可以推广为下述整齐的形式: 定理 4? 设A是 n ? ? 1? 阶非负方阵. 则下列各性 质是互相等价的: 1)A不可约; 2)存在某个(复系数)多项式 f ? x ?,使得 f ? A? ? 0; 3)I ? A ?

?A

m ?1

? 0 ,这里m是A的最小多

项式 mA ? x ? 的次数; m ?1 4)? I ? A? ? 0; 5)? I ? A?
n ?1

? 0.
目录 上页 下页 返回 结束

North University of China

证 只需证明 2 ? ? 3? . 作欧氏除法

f ? x ? ? q ? x ? mA ? x ? ? r ? x ? ,deg r ? x ? ? m 因此有
f ? A? ? r ? A ? ? 0 . 令

r ? x ? ? b1 x m?1 ?
则易得 b ? I ? A ?

? bm?1 x ? bm , b ? max bi ? 0
? Am?1 ? ? r ? A? ? 0, 从而得3).
1?i ? m

下面通过有向图 D ? A? 来分析一般方阵A的组合结构

North University of China

目录 上页 下页 返回

结束

二、一般方阵A的组合结构
先将 D ? D ? A? 的顶点集按互通关系划分成等价类
U1 , ,U k ? k ? 1? . 则

i)D在顶点集的每个子集 U i 上诱导出一 个子图 U i 如下:

U i 的顶点集是 U i 、 U i 的弧的集合,就是
D中所有那些起点和终点都属于 U i 的弧. 显然,
North University of China
目录 上页 下页 返回 结束

U i 是强连通的,称为D的一个强连通分支.
在例3中,有3个强连通分支 ?V1 ,V2 ,V3? 、 ?V4 ,V5 ?

和 ?V6 ? .
ii)对两个等价类 U i 和 U j ? i ? j ?,不可能既

有起点属于 U i 而终点属于 U j 的弧,又有起点属 于 U j而终点属于 U i 的弧. 因此,如果把每个U i

North University of China

目录 上页 下页 返回

结束

缩成一点 U i ,则从D可得另一个有向图 D*,

D 的顶点集是

*

?u1 ,

, uk ? , D* 中有从 ui 到

u j 的弧当且仅当D中至少有一条起点属于U i
而终点属于U j的弧 . 这个有k个顶点的有向图 D*反映了D的k个强连通分 支间的关系.

North University of China

目录 上页 下页 返回

结束

iii) D* 一定没有回路,从而 D* 中一定有某

个顶点 u j,使得 D*中没有以 u j为起点的弧,称
这种顶点 u j 为 D*的末端点. 取D为例3中的 D ? c ? ,则 D* 有三个顶点

u1

?V1 ,V2 ,V3?

u2

?V4 ,V5? u3 ?V6 ?

其中 u2 是末端点.

North University of China

目录 上页 下页 返回

结束

iv)设 D* 有g个末端点 u1 ,?, u g . 若 g ? k ,则
当在 D* 中去掉这g个顶点以及以这些顶点之一为终点 的所有弧后,得到一个顶点集为 ?u g ?1 ,

, uk ? 的有向

图,记为 D* ? ?u1 , , ug ?. 易见这个有向图仍没有回路 因此它也有一些末端点,设其末端点为ug ?1 ,
* D ? ?u1 , 再按同法讨论图

, ug ? h

, u g ? 及其h个末端点

North University of China

目录 上页 下页 返回

结束

ug ?1 ,

, ug ? h,得到 D* ? ?u1 , , ug ? ? ?ug ?1 , , ug ?h ? .

这样继续下去,最后可以得到这样的结论: 可将 D* 的所有顶点适当重新标号成为:

u1 ,

, ug , ug ?1 ,

, uk 其中 u1 ,

, ug是 D * 的末端点,

而对每个 q, g ? q ? k ,一定有 p

? q,使 D* 中

有弧 uq u p ,但一定没有弧 uqur ,q ? r .

North University of China

目录 上页 下页 返回

结束

V j j ? Ki ?, 则 Ki 是 v)回到方阵A,若记 U i ? ?

?1,

, n? 的非空真子集. 若将 K i 中的数按递增顺序

排列,但仍记为 K i ,则由i)~ iv)可知 A? Ki | Ki ?
不可约 ? i ? 1,

, k ? ;A ? ? Ki | Ki ? ? 0 ? i ? 1,

, g? ;

A? 对g ? q ? r ? k , ? Kq | Kr ? ? ? 0,而
A? ? K q | K1 ? ?, , A? ? K q .| K q ?1 ? ? 不全为零矩阵.

North University of China

目录 上页 下页 返回

结束

vi)最后指出,对 ?1, , n? 上的一个置换 ? ,
T T D P AP P AP 所对应的有向图 ? ? ? ?不过是对 D ? A? 的 ? ?

顶点重新标号所得:将 D ? A? 的顶点 Vi 改标为

V? (i ) ? i ? 1,

, n ? .反过来也是如此:将D ? A?的顶点重

新标号所得的正是某个与A置换相似的矩阵所对应 的有向图.

North University of China

目录 上页 下页 返回

结束

归纳起来,我们得到了任一n阶方阵在置换相似 下的如下标准形: 定理5 设A是n阶方阵,则A必置换相似于如下的 分块下三角形:
? A1 ? ? ? ? ? ? ? 0 ?*?? ? ? ? ? ? Ag ?1,1 Ag ?1, g ? ? ? ? ? ? ? A Akg ? k1
North University of China

? ? ? ? 0 ? ? ? ? Ag ? ? ? ? ? ? ? ?? ? ? Ag ?1 0? ? ? ? ? ? ? ? ? ? Ak , g ?1 Ak ? ? 0
目录 上页 下页 返回 结束

其中A1 ,

, Ag , Ag ?1 ,

, Ak 都是不可约方阵,而且对

Aq1 , g?q?k ,

, Aq ,q ?1 不全是零矩阵.

(*)称为A的一个置换相似标准形. 如记 Ai ? A? Ki | Ki ? ? i ? 1, , k ? ,即子块 Ai 是由A的标 号属于K i 的行、列所组成, 则

K1
作为集 ?1,

Kg

K g ?1

Kk

, n? 的(无序)划分是由A本身所唯一确

定的. 特别地,数k和g是由A所唯一确定的.
North University of China
目录 上页 下页 返回 结束

例4 例3的C置换相似于

?0 ?? ? ? ? ? T ? P ? CP ? ? ?0 ? ?0 ? ? ?0 ?

? 0 0 0 ? ? 0 ? 0 0 0 0 0 ? 0 ? 0 0 ?

? 0? ? ? ? ? 0? ? ? ? ? 0? ?
结束

North University of China

目录 上页 下页 返回

其中:

K1 ? ?4,5? , K 2 ? ?1,2,3? , K3 ? ?6? , k ? 3, g ? 1, ?1 2 3 4 5 6? ? ?? ? 4 5 1 2 3 6 ? ?
一般来说,对角块 A1 , 块 Ai 都并非唯一确定的.

, Ak 的次序以及每个对角

North University of China

目录 上页 下页 返回

结束