群在计算机科学中扮演着重要的角色。除了为集合上的操作提供一个基本框架外,它们还在密码学、编码理论和图形学中得到了广泛的应用。
定义(群)
假定我们有个集合ð和一个定义在集合ð上的操作⊗:ð×ð→ð 。
那么G:=(ð,⊗),如果满足:
- 封闭性:∀x,y∈ð,x⊗y∈ð
- 结合律:∀x,y,z∈ð,(x⊗y)⊗z=x⊗(y⊗z)
- 单位元:∃e∈ð,∀x∈ð,x⊗e=x且e⊗x=x
- 逆元:∀x∈ð,∃y∈ð,x⊗y=e且y⊗x=e
则称G:=(ð,⊗)为一个群。或者乘法群。有时由于上下文的原因,群上的二元运算亦可为加法,此时该运算通常记为 + ,群元素的运算也被记为如同x+y 的形式,而群也可被称为加法群。此种情况下,往往加法还有可交换的性质。
此外,如果还满足:
∀x,y∈ð,x⊗y=y⊗x,那么就称其为Abelian群。
例1:
G={1,-1}在普通乘法下是群。
证:
1)封闭性:1×1=1 (-1)×(-1)=1 (-1)×1=-1 1×(-1)=-1
2)结合律:成立
3)单位元:1
4)逆元素:1的逆元是1,-1的逆元是-1
例2:
G={0,1,2,,…..,n-1}在mod n的加法下是群。
证:
1)封闭性:除以n的余数只能是 {0,1,2,,…..,n-1},故封闭性成立
2)结合律:成立
3)单位元:0
4)逆元素:对任意元素a有 [a+(n-a)] mod n=0,a的逆元 a^{-1}=n-a。
置换群
定义 G为集合{1,2,3,…,n} 上所有双射的集合,并定义合成映射:
这里 x 是{1,2,3,…,n} 的任意元素。构成一个群,这个群被称为置换群,记为 Sym(n)或S_n。
例集合{1,2,3}的三个元素置换群组成 S_3 .
一般线性群
定义 G 为所有n阶实可逆方阵的集合,乘法 . 为矩阵乘法,则 (G,.) 构成一个群。
这个群称为一般线性群,记为 GL_n(R)。
有了群的概念,我们就可以定义向量空间的概念了。