在两个生成元a 和b 上的自由群 的凯莱图
凯莱图 (英语:Cayley graph ),也叫做凯莱著色图 ,是将离散群 的抽象结构画出的一种图 。它的定义是凯莱定理 (以阿瑟·凯莱 命名)所暗含的。画凯莱图时,要选定群的一个生成元集合 (通常有限),不同选法可能得到不同的凯莱图。凯莱图是组合群论 与几何群论 的中心工具。
假设
G
{\displaystyle G}
是群 ,而
S
{\displaystyle S}
是G的生成集 。凯莱图
Γ
=
Γ
(
G
,
S
)
{\displaystyle \Gamma =\Gamma (G,S)}
,是如下构造的著色的有向图 :
G
{\displaystyle G}
的每个元素
g
{\displaystyle g}
对应一个顶点 。换言之,图
Γ
{\displaystyle \Gamma }
的顶点集合
V
(
Γ
)
{\displaystyle V(\Gamma )}
视为与
G
{\displaystyle G}
等同;
S
{\displaystyle S}
中每个生成元
s
{\displaystyle s}
,对应一种颜色
c
s
{\displaystyle c_{s}}
;
对于任何
g
∈
G
,
s
∈
S
{\displaystyle g\in G,s\in S}
,画一条由元素
g
{\displaystyle g}
至
g
s
{\displaystyle gs}
的有向边 ,染成
c
s
{\displaystyle c_{s}}
色。换言之,边集合
E
(
Γ
)
{\displaystyle E(\Gamma )}
由形如
(
g
,
g
s
)
{\displaystyle (g,gs)}
的有序对构成,边的颜色由
s
∈
S
{\displaystyle s\in S}
确定。
在几何群论中,集合
S
{\displaystyle S}
通常取为有限 、对称(即满足
S
=
S
−
1
{\displaystyle S=S^{-1}}
),并且不包含这个群的单位元
e
{\displaystyle e}
。在这种情况下,凯莱图是简单无向图 :它的边没有方向(由对称性),并且不包含自环 (因为
e
∉
S
{\displaystyle e\notin S}
)。
假设
G
=
Z
{\displaystyle G=\mathbb {Z} }
是无限循环群 (即整数的加法群),而集合
S
{\displaystyle S}
由标准生成元
1
{\displaystyle 1}
和它的逆元(用加法符号为
−
1
{\displaystyle -1}
)构成,则它的凯莱图是无穷链 。
类似地,如果
G
=
Z
n
{\displaystyle G=\mathbb {Z} _{n}}
是
n
{\displaystyle n}
阶循环群 (模
n
{\displaystyle n}
的加法群),而
S
{\displaystyle S}
仍由
G
{\displaystyle G}
的标准生成元
1
{\displaystyle 1}
与逆元
−
1
{\displaystyle -1}
构成,则凯莱图是环图
C
n
{\displaystyle C_{n}}
。
群的直积 的凯莱图(新生成集取为原生成集之笛卡尔积),是对应的凯莱图的笛卡尔积 。因此阿贝尔群
Z
2
{\displaystyle \mathbb {Z} ^{2}}
,关于四个元素
(
±
1
,
±
1
)
{\displaystyle (\pm 1,\pm 1)}
组成的生成集的凯莱图,是平面
R
2
{\displaystyle \mathbb {R} ^{2}}
上的无穷网格 ,而带有类似的生成集的直积
Z
n
×
Z
m
{\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}
的凯莱图,是环面 上的
n
{\displaystyle n}
乘
m
{\displaystyle m}
有限网格。
二面体群
D
4
{\displaystyle D_{4}}
有群展示 :
⟨
a
,
b
|
a
4
=
b
2
=
e
,
a
b
=
b
a
3
⟩
.
{\displaystyle \langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle .}
左图是关于两个生成元
a
{\displaystyle a}
和
b
{\displaystyle b}
的凯莱图,其中红色箭头表示左乘元素
a
{\displaystyle a}
(顺时针旋转
90
∘
{\displaystyle 90^{\circ }}
)。而因为元素
b
{\displaystyle b}
(左右反射)自反 ,所以表示左乘元素
b
{\displaystyle b}
的蓝色线是无方向的,故左图混合了有向边与无向边:它有
8
{\displaystyle 8}
个顶点、
8
{\displaystyle 8}
条有向边 、
4
{\displaystyle 4}
条无向边。二面体群
D
4
{\displaystyle D_{4}}
关于两个生成元
a
{\displaystyle a}
和
b
{\displaystyle b}
的凯莱图。
D
4
{\displaystyle D_{4}}
关于两个自反生成元的凯莱图 同一个群
D
4
{\displaystyle D_{4}}
,亦可画出不同的凯莱图,如右图。
b
{\displaystyle b}
仍表示左右反射,而
c
{\displaystyle c}
则是关于主对角线的反射,以粉红色线表示。由于两个反射皆自反,右边的凯莱图完全无向。对应的群展示是
⟨
b
,
c
∣
b
2
=
c
2
=
e
,
b
c
b
c
=
c
b
c
b
⟩
.
{\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .}
条目开头的图,是两个生成元
a
,
b
{\displaystyle a,b}
上的自由群 ,关于生成集合
S
=
{
a
,
b
,
a
−
1
,
b
−
1
}
{\displaystyle S=\{a,b,a^{-1},b^{-1}\}}
的凯莱图,而正中央的黑点,是单位元
e
{\displaystyle e}
。沿著边向右走表示右乘
a
{\displaystyle a}
,而沿著边向上走表示乘以
b
{\displaystyle b}
。因为自由群没有关系 ,它的凯莱图中没有环 。这个凯莱图是证明巴拿赫-塔斯基悖论 的关键。
右边有离散海森堡群 海森堡群的一部分(颜色仅为方便看清分层)
{
(
1
x
z
0
1
y
0
0
1
)
,
x
,
y
,
z
∈
Z
}
{\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}
的凯莱图。所用的三个生成元
X
,
Y
,
Z
{\displaystyle X,Y,Z}
,分别对应
(
x
,
y
,
z
)
=
(
1
,
0
,
0
)
,
(
0
,
1
,
0
)
,
(
0
,
0
,
1
)
{\displaystyle (x,y,z)=(1,0,0),\ (0,1,0),\ (0,0,1)}
。其关系为
Z
=
X
Y
X
−
1
Y
−
1
,
X
Z
=
Z
X
,
Y
Z
=
Z
Y
{\displaystyle Z=XYX^{-1}Y^{-1},\ XZ=ZX,\ YZ=ZY}
,亦可从图中看出。本群为非交换 无穷群。虽然是三维空间,其凯莱图的增长 却是
4
{\displaystyle 4}
阶的。[来源请求]
群
G
{\displaystyle G}
通过左乘作用 在自身上(参见凯莱定理 )。这个作用可以看作
G
{\displaystyle G}
作用在它的凯莱图上。明确而言,一个元素
h
∈
G
{\displaystyle h\in G}
映射一个顶点
g
∈
V
(
Γ
)
{\displaystyle g\in V(\Gamma )}
到另一个顶点
h
g
∈
V
(
Γ
)
{\displaystyle hg\in V(\Gamma )}
。凯莱图的边集合被这个作用所保存:边
(
g
,
g
s
)
{\displaystyle (g,gs)}
变换成边
(
h
g
,
h
g
s
)
{\displaystyle (hg,hgs)}
。任何群在自身上的左乘作用是简单传递 的,特别是凯莱图是顶点传递 的。事实上,反向的结论也成立,即有下列等价刻划,称为扎比杜西定理 (英语:Sabidussi's Theorem ):
(无标记又无着色)有向图
Γ
{\displaystyle \Gamma }
是群
G
{\displaystyle G}
的某个凯莱图,当且仅当
G
{\displaystyle G}
可作为图自同构 (就是要保存边的集合)作用在
Γ
{\displaystyle \Gamma }
上,且该作用简单传递。[ 1]
要从一个凯莱图
Γ
=
Γ
(
G
,
S
)
{\displaystyle \Gamma =\Gamma (G,S)}
找回群
G
{\displaystyle G}
和生成集
S
{\displaystyle S}
,先选择一个顶点
v
1
∈
V
(
Γ
)
{\displaystyle v_{1}\in V(\Gamma )}
,标上群的单位元
e
{\displaystyle e}
。接著,对
Γ
{\displaystyle \Gamma }
的每个顶点
v
{\displaystyle v}
,
G
{\displaystyle G}
中有唯一元素将
v
1
{\displaystyle v_{1}}
变换到
v
{\displaystyle v}
,于是可以在
v
{\displaystyle v}
处标记该唯一元素。最后要确定
G
{\displaystyle G}
的哪个生成集
S
{\displaystyle S}
,产生凯莱图
Γ
{\displaystyle \Gamma }
,而所求的
S
{\displaystyle S}
就是毗连
v
1
{\displaystyle v_{1}}
的顶点标记的集合。生成集合是有限(这是凯莱图的共同假定)当且仅当这个图是局部有限的(就是说每个顶点仅毗连于有限多条边)。
如果生成集合的成员
s
{\displaystyle s}
是自身的逆元,即
s
=
s
−
1
{\displaystyle s=s^{-1}}
,则它一般被表示为无向边 。
凯莱图
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
本质上依赖于如何选择生成集
S
{\displaystyle S}
。例如,如果生成集合
S
{\displaystyle S}
有
k
{\displaystyle k}
个元素,则凯莱图的每个顶点都有
k
{\displaystyle k}
条有向边 进入,
k
{\displaystyle k}
条有向边外出。当生成集合
S
{\displaystyle S}
为对称集,且有
r
{\displaystyle r}
个元素时,凯莱图是
r
{\displaystyle r}
度的正则图 。
在凯莱图中的环 (“闭合路径”)指示
S
{\displaystyle S}
的元素之间的关系 。在群的凯莱复形 此一更复杂的构造中,对应于关系的闭合路径被用多边形 “填充”。
如果
f
:
G
′
→
G
{\displaystyle f:G'\to G}
是满射 群同态 并且
G
′
{\displaystyle G'}
的生成集合
S
′
{\displaystyle S'}
的元素的像是不同的,则导出图覆叠 映射
f
¯
:
Γ
(
G
′
,
S
′
)
→
Γ
(
G
,
S
)
,
{\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad }
这里的
S
=
f
(
S
′
)
{\displaystyle S=f(S')}
,特别是,如果群
G
{\displaystyle G}
有
k
{\displaystyle k}
个生成元,阶均不为
2
{\displaystyle 2}
,并且这些生成元和它们的逆元构成集合
S
{\displaystyle S}
,则该集合生成的自由群
F
(
S
)
{\displaystyle F(S)}
有到
G
{\displaystyle G}
的满同态(商映射),故
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
被自由群的凯莱图覆盖,即
2
k
{\displaystyle 2k}
度的无限正则树 。
即使集合
S
{\displaystyle S}
不生成群
G
{\displaystyle G}
,仍可以构造图
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
。但是,此情况下,所得的图并不连通 。在这种情况下,这个图的每个连通分支 对应
S
{\displaystyle S}
所生成子群的一个陪集。
对于有限凯莱图(视为无向),其顶点连通性 等于这个图的度 的
2
/
3
{\displaystyle 2/3}
。若生成集极小(即移除任一元素及其逆元,就不再生成整个群),则其顶点连通性等于度数。[ 2] 至于边连通性 ,则在任何情况下皆等于度数。[ 3]
群
G
{\displaystyle G}
的每个乘性特征标
χ
{\displaystyle \chi }
都给出
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
邻接矩阵 的特征向量 。若
G
{\displaystyle G}
为交换群,则对应的特征值 为
λ
χ
=
∑
s
∈
S
χ
(
s
)
.
{\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s).}
特别地,平凡特征标(将所有元素映至常数
1
{\displaystyle 1}
)对应的特征值,等于
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
的度数,即
S
{\displaystyle S}
的元素个数。若
G
{\displaystyle G}
为交换群,则恰有
|
G
|
{\displaystyle |G|}
个特征标,故已足以确定全部特征值。
如果转而把顶点作为固定子群
H
{\displaystyle H}
的右陪集,就得到了一个有关的构造Schreier陪集图 ,它是陪集枚举 或Todd-Coxeter算法 的基础。
研究图的邻接矩阵 特别是应用谱图理论 的定理能洞察群的结构。