可逆矩阵及其在保密通信中的应用
摘 要 本文在可逆矩阵的定义、性质及求法的基础上,讨论了判断可逆矩阵的方法、分块可逆矩阵的求法以及可逆矩阵的一类求法,并通过实例给出了具体应用.介绍了保密通信及可逆矩阵在其中的应用.
关键词 矩阵理论;可逆矩阵;保密通信;伴随矩阵;性质
0 引言
随着科学技术的不断进步,矩阵理论已成为众多高科技邻域不可或缺的组成部分.而逆矩阵是其非常重要并且是较难理解的一部分内容,但在许多线性代数教科书中逆矩阵相关知识点却零零散散,而且忽略了其重要实际应用,以至于让很多人错误地认为逆矩阵没有多大用处.为了能具体地、形象地认识逆矩阵,将抽象的知识具体的表现出来,掌握其本质,更能简单的运用到实际当中.在我们学过的高等代数教材中对可逆矩阵给出了明确的定义,但未对可逆矩阵的求解方法详细的介绍,本文主要讨论可逆矩阵的求解方法及其在保密通信中的应用.
1 可逆矩阵
定义1 在线性代数中,对于任意一个n阶方阵A,如果有n阶方阵B,使得AB=BA=E,其中E为n阶单位矩阵,则称A是可逆的,且B是A的逆矩阵,记作A.
若方阵A的逆矩阵存在,则称A为非奇异方阵或可逆矩阵. 1.2 可逆矩阵的性质
-1
性质1 若A是可逆的,则A也可逆,且A-1
()A
-1
-1
=A.
-1
-1-1
性质2 若A、B是两个同阶可逆矩阵,则AB也可逆,且(AB)=BA.
性质3 若可逆矩阵A的转置矩阵为A,则A
T
()
T-1
=(A
-1T
)
.
性质4 若A是可逆矩阵,则有A-1=A. 1.3 可逆矩阵的判定
-1
定理1 初等变换不改变矩阵的可逆性.
证明 设A经过一次初等行变换得到B,那么存在一个初等矩阵E,使得
EA=B.由于初等矩阵可逆,当A可逆时,EA也可逆,即B可逆。另一方面,
A=E-1B,当B可逆时,E-1B可逆,即A可逆.对列变换的情形可类似的证明.
1.4 几个充要条件 定理2 A可逆⇔A≅In. 定理3 A可逆⇔A=P1
Ps,Pi是初等矩阵.
证明 设A可逆,则A的等价标准形为In,即 存在初等矩阵P1,P2,
-1-1
于是A=P1P2
-1-1
=P1P2
,Ps,Q1,,Q2,,Qt使得PsP2PAQ11,Q2Qt=In,
-1-1
PIQsnt-1-1PsQt
Q2-1Q1-1 Q2-1Q1-1
故A可表示成一些初等矩阵的乘积.
定理4 A可逆⇔只经过行初等变化为In. 证明 因为A可逆⇔存在 初等矩阵P1,P2,等变换化成E.
定理5 设A,B是两个n阶矩阵,则AB=AB. 推论1 设A1,A2,
-1
Ps⇔Ps
-1-1
s次初P2P1A=E⇔A经过
,P12s使得A=PP
,As都是n阶矩阵,则
A1,A2,,As=A1A2
定理6 A可逆⇔A≠0.
As.
证明 必要性 设A可逆,则存在A-1使得AA-1=E由定理5得
AA-1=A-1A=E=1所以A≠0.
充分性 若A≠0,由定理2,存在P1,P2,
使得Ps
,Ps,Q1,,Q2,,Qt
P2PAQ11,Q2Qt=In
-1-1
于是A=P1P2
-1-1
=P1P2
-1-1
PIQsnt-1-1PsQt
Q2-1Q1-1 Q2-1Q1-1
故A可逆.
1.5逆矩阵的求法 1.5.1初等变换法 原理 设 ps
则ps
p1A=E,ps
p1A,ps
p1E=A-1
p1E)=(E,A-1).
p1(A,E)=(ps
⎛223⎫ ⎪-1
例1 设A= 1-10⎪,判定A是否可逆,若可逆,求A.
-121⎪⎝⎭
解 因为A≠0所以A可逆
⎛223100⎫ ⎪r1-2r2
→ (AE)= 1-10010⎪−−−r3-r2
-121001⎪⎝⎭
⎛0431-20⎫r+r ⎪r12-43r3
→ r1r2 1-10010⎪−−−
011011⎪r2r3⎝⎭⎛101021⎫ ⎪r1+r3011011→ r2+r3 ⎪−−− 00-11-6-4⎪r3⨯(-1)⎝⎭⎛1001-4-3⎫ ⎪-101015-3=EA() ⎪ 001-164⎪⎝⎭
故
⎛1-4-3⎫
⎪A-1= 15-3 ⎪.
-164⎪⎝⎭
1.5.2伴随矩阵法
定义2 设Aij是矩阵
⎛a11 A=
a⎝n1
中元素aij的代数余子式,矩阵
a1n⎫⎪⎪ ann⎪⎭
⎛A11
A*=
A⎝m1
称为A的伴随矩阵.
1.5.3求逆矩阵的公式
-1A=
A1n⎫
⎪⎪ Amn⎪⎭
1*
A(牢记AA*=A*A=AE). A
⎛123⎫ ⎪-1
例2 设A= 221⎪ 判定A是否可逆,若可逆,求A.
343⎪⎝⎭
解 因为A=2,所以
A可逆。又A11=2,A12=-3,A13=2,
-2⎫
5⎪⎪ -3
2⎪1-1⎪⎭3
A21=6,A22=-6,A23=2,A31=-4,A32=5,A33=-2 所以
⎛1
26-4⎛⎫
1*1 3⎪A-1=A= -3-65⎪= -
A2 2⎪
⎝22-2⎭ 1
⎝
⎛1 3-1
所以 A= -
2 1⎝
-2⎫5⎪⎪ . -3
2⎪1-1⎪⎭3
1.6可逆分块矩阵的逆矩阵
1.6.1缺角阵的逆矩阵
设A,B分别是m,n阶可逆矩阵,则有Laplace定理知m+n阶分块矩阵
⎛A0⎫D= ⎪
0B⎝⎭
⎛X11
是可逆矩阵,得到D进行相同的分块,令D=
⎝X21
-1
-1
X12⎫
⎪由于 X22⎭
⎛A0⎫⎛X11
DD= ⎪ X0B⎝⎭⎝21
-1X12⎫⎛Em
⎪= 0X22⎭⎝
(1)(2) (3)(4)
0⎫ ⎪En⎭
根据分块矩阵的乘法计算出左端,并比较等式两边,得
⎧AX11=Em
⎪AX12=0⎪⎨
⎪CX11+BX21=0⎪⎩CX12+BX22=En
有(1)、(2)式得X11=A-1,X12=A-10=0 代入(4)式得X22=B-1
代入(3)式得BX21=-CX11=-CA-1,所以X21=-B-1CA-1
-1
⎛A-1
所以 D= -1-1
⎝-BCA
0⎫
. -1⎪B⎭
1.6.2利用分块矩阵的知识可得下列公式 设A,B可逆.
-1
⎛A-1⎛A0⎫
= -1-1公式1 ⎪
⎝CB⎭⎝-BCA⎛A-1⎛A0⎫
公式2 ⎪= CB⎝⎭⎝0⎛A-1⎛0A⎫
= 公式3 ⎪
⎝BC⎭⎝0⎛C
公式4
⎝B
A⎫⎛0
= -1⎪0⎭⎝A
-1-1-1
0⎫
. -1⎪B⎭
-A-1CB-1⎫⎪. -1
B⎭-A-1CB-1⎫
⎪. -1
B⎭B-1⎫
. -1-1⎪-ACB⎭
1.6.2 准对角矩阵的逆矩阵
⎛A1 ⎝
⎛A1-1⎫
⎪
⎪=
As⎪⎭⎝
-1
⎫
⎪⎪. As-1⎪⎭
1.6.3 反对角矩阵的逆矩阵
⎛
A⎝s
其中Ai可逆,i=1,2,
⎛A1⎫
⎪= ⎪⎪ A1-1⎭⎝
-1
As-1⎫
⎪⎪ ⎪⎭
,s.
1.7 一类矩阵方阵的简便解法 解AX=B(A可逆)的简便方法
行
→(I,A-1B). (A,B)−−
解XA=B的简便方法
⎛A⎫列⎛I⎫→ -1⎪. ⎪−−
⎝B⎭⎝BA⎭
⎛101⎫⎛-11⎫ ⎪ ⎪
例3 1-11⎪X= 10⎪求X.
-110⎪ 01⎪⎝⎭⎝⎭
解
⎛101-11⎫⎛101-11⎫ ⎪r2+r1⨯(-1) ⎪1-1110−−−−→0-102-1r3+r1 ⎪ ⎪ -11001⎪ 011-12⎪⎝⎭⎝⎭
⎛101-11⎫⎛100-20⎫ ⎪r1+r3⨯(-1) ⎪r3+r2
−−−→010-21−−−−→010-21r2⨯(-1) ⎪ ⎪
00111⎪ 00111⎪⎝⎭⎝⎭
所以
⎛-20⎫ ⎪X= -21⎪.
11⎪⎝⎭
2 保密通信
2.1 密码起源
当人们刚刚开始通信的时候,为了保证秘密信息不被轻易窃取,人们意识到必须寻找一种方法去保护他们的通信内容. 古代罗马的军队运用一种所谓的恺撒密码进行通信,其原理是利用26个字母的轮换.它用D表示a,用F表示c等等,也就是说密文字母相对明文字母平移3位.收信人只需要按通常的字母顺序将密文字母向相反方向平移3位即可以得到明文.当然,诸如此类的密码都是很容易破译的.
当代信息技术的发展,人们意识到加密技术的重要性.密码被政府、军队、公司、金融机构等诸多领域广泛使用.随着电子商务、电子政务等领域的迅猛发展使得海量秘密信息需要在保密状态下进行交流,而加密技术使通过诸如计算机网络等公共通信平台传递大量信息而不被窃取成为可能.自此,保密通信领域渐渐走进公众的日常生活.比如安全的网络和公共基础设施、安全的应用软件和数据库、安全测试、信息系统评估、企业安全规划以及数字取证技术等等.
在因特网上快速增长的电子数据处理和电子商务应用,以及不断出现的国际恐怖主义事件,增加了对更好地保护计算机及其存储、加工和传输的信息的需求.计算机安全、信息安全、以及信息保障等学科,是和许多专业的组织一起出现的.他们都持有共同的目标,即确保信息系统的安全和可靠.
2.2密码系统
一般的,一个密码系统由明文空间、密码空间、密钥空间、加密算法和解密算法组成.待加密的信息称为明文,明文的全体构成的集合称为明文空间.用M表示明文空间,用m表示明文.用C表示密文空间,c表示密文.用K表示密钥空间,k表示密钥.密码设计中,密钥一般是随机序列.所谓密码方案是指对加密变换的具体规则的确切描述,这种描述包括对明文进行加密时所使用的加密算法,以及对密码进行还原时所使用解密算法.
传统的保密通信的模式可表示为
密码分析
↓↑
密文Em
()明文m∈M
明文空间−−−−→加密空间−−−−→ 解密变换→明文
定义3 一个用于加密、解密的密码体制(系统)是一个五组(M,C,K,E,D),其中
(1)M称为明文空间,是所有可能的明文构成的集合; (2)C称为密文空间,是所有可能的密文构成的集合; (3)K称为密钥空间,是所有可能的密钥构成的集合;
(4)E,D分别表示加密算法集和解密算法集.
它们满足,对于每一个k∈K都存在一个加密算法ek∈E和一个解密算法dk∈D,
使得对于任意的m∈M,都有dk(ek(m))=m成立.
3 可逆矩阵在通信中的应用
3.1 加密算法
设有矩阵方程C=KM ,其中M为明文矩阵, K为加密矩阵,用加密矩阵与明文矩阵的乘积来对所发送消息实施了加密,得到密文矩阵C.如果K为可逆矩阵,则方程有唯一解M=K-1C ,其中K-1为K的逆矩阵.
例4 发送的明文是“ send money”.
解 首先可将明文用9个整数构成的矩阵来表示:
⎛52110⎫ ⎪M= 878⎪
1029⎪⎝⎭
假设进行加密的矩阵K为:
⎛121⎫ ⎪K= 253⎪
232⎪⎝⎭
则密文矩阵C为:
⎛313729⎫ ⎪C= 808369⎪
546750⎪⎝⎭
所以发送的信息为:31,80,54,37,83,67,29,69,50.
3.2 解密算法
解密时,采用下面矩阵乘法
-1
M=KC.
例5 针对上面的加密矩阵K 解 因K可逆,可得:
⎛1-11⎫
⎪K-1= 20-1⎪
-411⎪⎝⎭
故明文矩阵为:
⎛52110⎫
⎪
M=K-1C= 878⎪.
1023⎪⎝⎭
3.2 加密矩阵的生成
初等矩阵都是可逆的,而且初等矩阵的乘积仍然是可逆的.因此,通信中可以考虑利用若干个初等矩阵的乘积作为加密编码矩阵.它的生成方法如下:
从单位矩阵出发,反复运用第一类和第三类初等变换矩阵去乘它,而其中的乘数K必须取整数.这样得到矩阵将满足A=±1而A-1也将具有整数元素.
3.3 应用实例
例6 小王的朋友给小王发来一封密信,它是一个三阶方阵
⎛207210135⎫ ⎪231318135 ⎪ 244161175⎪⎝⎭
他们约定:消息的每一个英文字母用一个整数来表示:
a1,b2,
,y25,z26
约定好的加密矩阵,既密钥矩阵是
⎛437⎫ ⎪9010 ⎪ 076⎪⎝⎭
试求小王的朋友发送的密信内容.
解 试求密信的内容,先假设密信内容矩阵为X
⎛437⎫⎛207210135⎫
⎪ ⎪
9010⎪X= 231318135⎪
076⎪ 244161175⎪⎝⎭⎝⎭⎛437⎫⎛207210135⎫ ⎪ ⎪
或 X 9010⎪= 231318135⎪
076⎪ 244161175⎪⎝⎭⎝⎭⎛437⎫⎛207210135⎫ ⎪ ⎪
既 X= 9010⎪ 231318135⎪
076⎪ 244161175⎪⎝⎭⎝⎭⎛207210135⎫⎛437⎫ ⎪⎪
或 X= 231318135⎪9010⎪
244161175⎪076⎪⎝⎭⎝⎭
-1
-1
用MATLAB来求解,易得
⎛91215⎫ ⎪
X= 9010⎪
076⎪⎝⎭
由英文字母与整数之间的对应关系即得密信内容为“I LOVE YOU”.
3.4 明文矩阵的选择
如果明文矩阵M为方阵,则当M为可逆矩阵时有K=M-1C或K=CM-1 , 其中M-1为M的逆矩阵.因此,如果窃密者以某种方式窃取到一对明文和相应的密文,碰巧其中的明文矩阵可逆,那么窃密者可以轻而易举地破解密文.因此, 在实际应用时, 明文矩阵不要采用方阵.另外,在实际应用中,明文并不能总是恰好可以分成整数矩阵,出现这种情况时需要补充一些数据,补充的数据可以是有意义的,也可以是无意义的.有时,我们可以利用这些附加数据来达到某种特殊的效果,比如数据的完整性检验等.
3.5 加密矩阵的选择
设C=KM,根据矩阵乘法的定义, 乘积矩阵C中第i行第j列的元素Cij等于矩阵K中第i行的所有元素与矩阵M中第j列的对应元素之积的累加和.因此, 利用可逆矩阵来实现保密通信的另一个问题是, 如果加密矩阵选择得不好, 密文矩阵的元素长度会急剧膨胀.为了避免出现这种情况,加密矩阵K最好满足以下条件:
对任意的明文矩阵M,密文矩阵C中的每一个元素的长度都不超过明文矩阵M中对应位置上的元素的长度,或者退而求其次;
对任意的明文矩阵M,密文矩阵C中所有元素的总长度不超过明文矩阵M中所有元素的总长度.
如果能找到一个加密矩阵,使得对任意的明文矩阵,密文矩阵中所有元素的总长度在一个比较理想的程度上小于明文矩阵中所有元素的总长度,那么这时的加密算法同时也是一种较好的压缩算法.
3.6算法优化
设加密矩阵K为n阶矩阵,明文矩阵M为n行m列矩阵, 利用向量的有关知识, 密文矩阵C的第i行Ci(i=1,2,
,n)可以表示为 +KinMn
Ci=Ki1M1+Ki2M2+
其中Kij(j=1,2,
M的第n行.
,n)为矩阵K的第i行第j列位置上的元素,而Mn则为矩阵
显然, 密文矩阵的每一个行向量都是明文矩阵的所有行向量的一种线性组合, 其组合系数正好是加密矩阵的相应行上的所有元素.根据矩阵乘法的定义直接计算密文矩阵时, 计算密文矩阵的每行元素需要做mn次乘法和m(n-1)次加法,计算密文矩阵的每个元素需要做n次乘法和n-1次加法,因此计算整个密文矩阵总共需要mn2次乘法和mn(n-1)次加法.
4 总结
可逆矩阵作为矩阵乘法的逆运算,是矩阵的一种重要运算,在解决矩阵问题起着重要的作用.因而掌握可逆矩阵的求法,在解决实际问题时选择适当的方法,往往可以起到事半功倍的效果.本文首先从可逆矩阵入手给出了可逆矩阵的概念,并讨论了可逆矩阵的性质,其次对可逆矩阵的性质进行了讨论并得出了一些定理,并且举出了相应的例题.最后给出了可逆矩阵在通信中的应用,使的学习的人对可逆矩阵有了更进一步的认识.对于其它方面的应用,未进一步进行做讨论,有待进一步探讨.
致谢 在此谨向任天胜老师致以诚挚的谢意.
参 考 文 献
[1] 刘剑平, 施劲松主编. 线性代数[M]. 上海:华东理工大学出版社,2011.
[2] 熊小兵. 可逆矩阵在保密通信中的应用[J]. 大学数学, 2007,23(3).
[3] 徐仲主编. 高等代数(北大第三版)导教·导练·导考[M]. 西安:西北工业大学出版社,2006.
[4] 北京大学数学系几何与代数教研室前代数小组主编. 高等代数[M]. 北京:高等教育出版社,2003.9(2012.3重印).
[5] 华中科技大学数学系. 线性代数(第2版)[M]. 北京: 高等教育出版社,2003.
[6] 蓝以中. 高等代数简明教程(上册)[M]. 北京: 北京大学出版社,2002.
[7] 张新发. 初等矩阵的关系及可逆矩阵的分解[J]. 大学数学,2003,19(2).
可逆矩阵及其在保密通信中的应用
摘 要 本文在可逆矩阵的定义、性质及求法的基础上,讨论了判断可逆矩阵的方法、分块可逆矩阵的求法以及可逆矩阵的一类求法,并通过实例给出了具体应用.介绍了保密通信及可逆矩阵在其中的应用.
关键词 矩阵理论;可逆矩阵;保密通信;伴随矩阵;性质
0 引言
随着科学技术的不断进步,矩阵理论已成为众多高科技邻域不可或缺的组成部分.而逆矩阵是其非常重要并且是较难理解的一部分内容,但在许多线性代数教科书中逆矩阵相关知识点却零零散散,而且忽略了其重要实际应用,以至于让很多人错误地认为逆矩阵没有多大用处.为了能具体地、形象地认识逆矩阵,将抽象的知识具体的表现出来,掌握其本质,更能简单的运用到实际当中.在我们学过的高等代数教材中对可逆矩阵给出了明确的定义,但未对可逆矩阵的求解方法详细的介绍,本文主要讨论可逆矩阵的求解方法及其在保密通信中的应用.
1 可逆矩阵
定义1 在线性代数中,对于任意一个n阶方阵A,如果有n阶方阵B,使得AB=BA=E,其中E为n阶单位矩阵,则称A是可逆的,且B是A的逆矩阵,记作A.
若方阵A的逆矩阵存在,则称A为非奇异方阵或可逆矩阵. 1.2 可逆矩阵的性质
-1
性质1 若A是可逆的,则A也可逆,且A-1
()A
-1
-1
=A.
-1
-1-1
性质2 若A、B是两个同阶可逆矩阵,则AB也可逆,且(AB)=BA.
性质3 若可逆矩阵A的转置矩阵为A,则A
T
()
T-1
=(A
-1T
)
.
性质4 若A是可逆矩阵,则有A-1=A. 1.3 可逆矩阵的判定
-1
定理1 初等变换不改变矩阵的可逆性.
证明 设A经过一次初等行变换得到B,那么存在一个初等矩阵E,使得
EA=B.由于初等矩阵可逆,当A可逆时,EA也可逆,即B可逆。另一方面,
A=E-1B,当B可逆时,E-1B可逆,即A可逆.对列变换的情形可类似的证明.
1.4 几个充要条件 定理2 A可逆⇔A≅In. 定理3 A可逆⇔A=P1
Ps,Pi是初等矩阵.
证明 设A可逆,则A的等价标准形为In,即 存在初等矩阵P1,P2,
-1-1
于是A=P1P2
-1-1
=P1P2
,Ps,Q1,,Q2,,Qt使得PsP2PAQ11,Q2Qt=In,
-1-1
PIQsnt-1-1PsQt
Q2-1Q1-1 Q2-1Q1-1
故A可表示成一些初等矩阵的乘积.
定理4 A可逆⇔只经过行初等变化为In. 证明 因为A可逆⇔存在 初等矩阵P1,P2,等变换化成E.
定理5 设A,B是两个n阶矩阵,则AB=AB. 推论1 设A1,A2,
-1
Ps⇔Ps
-1-1
s次初P2P1A=E⇔A经过
,P12s使得A=PP
,As都是n阶矩阵,则
A1,A2,,As=A1A2
定理6 A可逆⇔A≠0.
As.
证明 必要性 设A可逆,则存在A-1使得AA-1=E由定理5得
AA-1=A-1A=E=1所以A≠0.
充分性 若A≠0,由定理2,存在P1,P2,
使得Ps
,Ps,Q1,,Q2,,Qt
P2PAQ11,Q2Qt=In
-1-1
于是A=P1P2
-1-1
=P1P2
-1-1
PIQsnt-1-1PsQt
Q2-1Q1-1 Q2-1Q1-1
故A可逆.
1.5逆矩阵的求法 1.5.1初等变换法 原理 设 ps
则ps
p1A=E,ps
p1A,ps
p1E=A-1
p1E)=(E,A-1).
p1(A,E)=(ps
⎛223⎫ ⎪-1
例1 设A= 1-10⎪,判定A是否可逆,若可逆,求A.
-121⎪⎝⎭
解 因为A≠0所以A可逆
⎛223100⎫ ⎪r1-2r2
→ (AE)= 1-10010⎪−−−r3-r2
-121001⎪⎝⎭
⎛0431-20⎫r+r ⎪r12-43r3
→ r1r2 1-10010⎪−−−
011011⎪r2r3⎝⎭⎛101021⎫ ⎪r1+r3011011→ r2+r3 ⎪−−− 00-11-6-4⎪r3⨯(-1)⎝⎭⎛1001-4-3⎫ ⎪-101015-3=EA() ⎪ 001-164⎪⎝⎭
故
⎛1-4-3⎫
⎪A-1= 15-3 ⎪.
-164⎪⎝⎭
1.5.2伴随矩阵法
定义2 设Aij是矩阵
⎛a11 A=
a⎝n1
中元素aij的代数余子式,矩阵
a1n⎫⎪⎪ ann⎪⎭
⎛A11
A*=
A⎝m1
称为A的伴随矩阵.
1.5.3求逆矩阵的公式
-1A=
A1n⎫
⎪⎪ Amn⎪⎭
1*
A(牢记AA*=A*A=AE). A
⎛123⎫ ⎪-1
例2 设A= 221⎪ 判定A是否可逆,若可逆,求A.
343⎪⎝⎭
解 因为A=2,所以
A可逆。又A11=2,A12=-3,A13=2,
-2⎫
5⎪⎪ -3
2⎪1-1⎪⎭3
A21=6,A22=-6,A23=2,A31=-4,A32=5,A33=-2 所以
⎛1
26-4⎛⎫
1*1 3⎪A-1=A= -3-65⎪= -
A2 2⎪
⎝22-2⎭ 1
⎝
⎛1 3-1
所以 A= -
2 1⎝
-2⎫5⎪⎪ . -3
2⎪1-1⎪⎭3
1.6可逆分块矩阵的逆矩阵
1.6.1缺角阵的逆矩阵
设A,B分别是m,n阶可逆矩阵,则有Laplace定理知m+n阶分块矩阵
⎛A0⎫D= ⎪
0B⎝⎭
⎛X11
是可逆矩阵,得到D进行相同的分块,令D=
⎝X21
-1
-1
X12⎫
⎪由于 X22⎭
⎛A0⎫⎛X11
DD= ⎪ X0B⎝⎭⎝21
-1X12⎫⎛Em
⎪= 0X22⎭⎝
(1)(2) (3)(4)
0⎫ ⎪En⎭
根据分块矩阵的乘法计算出左端,并比较等式两边,得
⎧AX11=Em
⎪AX12=0⎪⎨
⎪CX11+BX21=0⎪⎩CX12+BX22=En
有(1)、(2)式得X11=A-1,X12=A-10=0 代入(4)式得X22=B-1
代入(3)式得BX21=-CX11=-CA-1,所以X21=-B-1CA-1
-1
⎛A-1
所以 D= -1-1
⎝-BCA
0⎫
. -1⎪B⎭
1.6.2利用分块矩阵的知识可得下列公式 设A,B可逆.
-1
⎛A-1⎛A0⎫
= -1-1公式1 ⎪
⎝CB⎭⎝-BCA⎛A-1⎛A0⎫
公式2 ⎪= CB⎝⎭⎝0⎛A-1⎛0A⎫
= 公式3 ⎪
⎝BC⎭⎝0⎛C
公式4
⎝B
A⎫⎛0
= -1⎪0⎭⎝A
-1-1-1
0⎫
. -1⎪B⎭
-A-1CB-1⎫⎪. -1
B⎭-A-1CB-1⎫
⎪. -1
B⎭B-1⎫
. -1-1⎪-ACB⎭
1.6.2 准对角矩阵的逆矩阵
⎛A1 ⎝
⎛A1-1⎫
⎪
⎪=
As⎪⎭⎝
-1
⎫
⎪⎪. As-1⎪⎭
1.6.3 反对角矩阵的逆矩阵
⎛
A⎝s
其中Ai可逆,i=1,2,
⎛A1⎫
⎪= ⎪⎪ A1-1⎭⎝
-1
As-1⎫
⎪⎪ ⎪⎭
,s.
1.7 一类矩阵方阵的简便解法 解AX=B(A可逆)的简便方法
行
→(I,A-1B). (A,B)−−
解XA=B的简便方法
⎛A⎫列⎛I⎫→ -1⎪. ⎪−−
⎝B⎭⎝BA⎭
⎛101⎫⎛-11⎫ ⎪ ⎪
例3 1-11⎪X= 10⎪求X.
-110⎪ 01⎪⎝⎭⎝⎭
解
⎛101-11⎫⎛101-11⎫ ⎪r2+r1⨯(-1) ⎪1-1110−−−−→0-102-1r3+r1 ⎪ ⎪ -11001⎪ 011-12⎪⎝⎭⎝⎭
⎛101-11⎫⎛100-20⎫ ⎪r1+r3⨯(-1) ⎪r3+r2
−−−→010-21−−−−→010-21r2⨯(-1) ⎪ ⎪
00111⎪ 00111⎪⎝⎭⎝⎭
所以
⎛-20⎫ ⎪X= -21⎪.
11⎪⎝⎭
2 保密通信
2.1 密码起源
当人们刚刚开始通信的时候,为了保证秘密信息不被轻易窃取,人们意识到必须寻找一种方法去保护他们的通信内容. 古代罗马的军队运用一种所谓的恺撒密码进行通信,其原理是利用26个字母的轮换.它用D表示a,用F表示c等等,也就是说密文字母相对明文字母平移3位.收信人只需要按通常的字母顺序将密文字母向相反方向平移3位即可以得到明文.当然,诸如此类的密码都是很容易破译的.
当代信息技术的发展,人们意识到加密技术的重要性.密码被政府、军队、公司、金融机构等诸多领域广泛使用.随着电子商务、电子政务等领域的迅猛发展使得海量秘密信息需要在保密状态下进行交流,而加密技术使通过诸如计算机网络等公共通信平台传递大量信息而不被窃取成为可能.自此,保密通信领域渐渐走进公众的日常生活.比如安全的网络和公共基础设施、安全的应用软件和数据库、安全测试、信息系统评估、企业安全规划以及数字取证技术等等.
在因特网上快速增长的电子数据处理和电子商务应用,以及不断出现的国际恐怖主义事件,增加了对更好地保护计算机及其存储、加工和传输的信息的需求.计算机安全、信息安全、以及信息保障等学科,是和许多专业的组织一起出现的.他们都持有共同的目标,即确保信息系统的安全和可靠.
2.2密码系统
一般的,一个密码系统由明文空间、密码空间、密钥空间、加密算法和解密算法组成.待加密的信息称为明文,明文的全体构成的集合称为明文空间.用M表示明文空间,用m表示明文.用C表示密文空间,c表示密文.用K表示密钥空间,k表示密钥.密码设计中,密钥一般是随机序列.所谓密码方案是指对加密变换的具体规则的确切描述,这种描述包括对明文进行加密时所使用的加密算法,以及对密码进行还原时所使用解密算法.
传统的保密通信的模式可表示为
密码分析
↓↑
密文Em
()明文m∈M
明文空间−−−−→加密空间−−−−→ 解密变换→明文
定义3 一个用于加密、解密的密码体制(系统)是一个五组(M,C,K,E,D),其中
(1)M称为明文空间,是所有可能的明文构成的集合; (2)C称为密文空间,是所有可能的密文构成的集合; (3)K称为密钥空间,是所有可能的密钥构成的集合;
(4)E,D分别表示加密算法集和解密算法集.
它们满足,对于每一个k∈K都存在一个加密算法ek∈E和一个解密算法dk∈D,
使得对于任意的m∈M,都有dk(ek(m))=m成立.
3 可逆矩阵在通信中的应用
3.1 加密算法
设有矩阵方程C=KM ,其中M为明文矩阵, K为加密矩阵,用加密矩阵与明文矩阵的乘积来对所发送消息实施了加密,得到密文矩阵C.如果K为可逆矩阵,则方程有唯一解M=K-1C ,其中K-1为K的逆矩阵.
例4 发送的明文是“ send money”.
解 首先可将明文用9个整数构成的矩阵来表示:
⎛52110⎫ ⎪M= 878⎪
1029⎪⎝⎭
假设进行加密的矩阵K为:
⎛121⎫ ⎪K= 253⎪
232⎪⎝⎭
则密文矩阵C为:
⎛313729⎫ ⎪C= 808369⎪
546750⎪⎝⎭
所以发送的信息为:31,80,54,37,83,67,29,69,50.
3.2 解密算法
解密时,采用下面矩阵乘法
-1
M=KC.
例5 针对上面的加密矩阵K 解 因K可逆,可得:
⎛1-11⎫
⎪K-1= 20-1⎪
-411⎪⎝⎭
故明文矩阵为:
⎛52110⎫
⎪
M=K-1C= 878⎪.
1023⎪⎝⎭
3.2 加密矩阵的生成
初等矩阵都是可逆的,而且初等矩阵的乘积仍然是可逆的.因此,通信中可以考虑利用若干个初等矩阵的乘积作为加密编码矩阵.它的生成方法如下:
从单位矩阵出发,反复运用第一类和第三类初等变换矩阵去乘它,而其中的乘数K必须取整数.这样得到矩阵将满足A=±1而A-1也将具有整数元素.
3.3 应用实例
例6 小王的朋友给小王发来一封密信,它是一个三阶方阵
⎛207210135⎫ ⎪231318135 ⎪ 244161175⎪⎝⎭
他们约定:消息的每一个英文字母用一个整数来表示:
a1,b2,
,y25,z26
约定好的加密矩阵,既密钥矩阵是
⎛437⎫ ⎪9010 ⎪ 076⎪⎝⎭
试求小王的朋友发送的密信内容.
解 试求密信的内容,先假设密信内容矩阵为X
⎛437⎫⎛207210135⎫
⎪ ⎪
9010⎪X= 231318135⎪
076⎪ 244161175⎪⎝⎭⎝⎭⎛437⎫⎛207210135⎫ ⎪ ⎪
或 X 9010⎪= 231318135⎪
076⎪ 244161175⎪⎝⎭⎝⎭⎛437⎫⎛207210135⎫ ⎪ ⎪
既 X= 9010⎪ 231318135⎪
076⎪ 244161175⎪⎝⎭⎝⎭⎛207210135⎫⎛437⎫ ⎪⎪
或 X= 231318135⎪9010⎪
244161175⎪076⎪⎝⎭⎝⎭
-1
-1
用MATLAB来求解,易得
⎛91215⎫ ⎪
X= 9010⎪
076⎪⎝⎭
由英文字母与整数之间的对应关系即得密信内容为“I LOVE YOU”.
3.4 明文矩阵的选择
如果明文矩阵M为方阵,则当M为可逆矩阵时有K=M-1C或K=CM-1 , 其中M-1为M的逆矩阵.因此,如果窃密者以某种方式窃取到一对明文和相应的密文,碰巧其中的明文矩阵可逆,那么窃密者可以轻而易举地破解密文.因此, 在实际应用时, 明文矩阵不要采用方阵.另外,在实际应用中,明文并不能总是恰好可以分成整数矩阵,出现这种情况时需要补充一些数据,补充的数据可以是有意义的,也可以是无意义的.有时,我们可以利用这些附加数据来达到某种特殊的效果,比如数据的完整性检验等.
3.5 加密矩阵的选择
设C=KM,根据矩阵乘法的定义, 乘积矩阵C中第i行第j列的元素Cij等于矩阵K中第i行的所有元素与矩阵M中第j列的对应元素之积的累加和.因此, 利用可逆矩阵来实现保密通信的另一个问题是, 如果加密矩阵选择得不好, 密文矩阵的元素长度会急剧膨胀.为了避免出现这种情况,加密矩阵K最好满足以下条件:
对任意的明文矩阵M,密文矩阵C中的每一个元素的长度都不超过明文矩阵M中对应位置上的元素的长度,或者退而求其次;
对任意的明文矩阵M,密文矩阵C中所有元素的总长度不超过明文矩阵M中所有元素的总长度.
如果能找到一个加密矩阵,使得对任意的明文矩阵,密文矩阵中所有元素的总长度在一个比较理想的程度上小于明文矩阵中所有元素的总长度,那么这时的加密算法同时也是一种较好的压缩算法.
3.6算法优化
设加密矩阵K为n阶矩阵,明文矩阵M为n行m列矩阵, 利用向量的有关知识, 密文矩阵C的第i行Ci(i=1,2,
,n)可以表示为 +KinMn
Ci=Ki1M1+Ki2M2+
其中Kij(j=1,2,
M的第n行.
,n)为矩阵K的第i行第j列位置上的元素,而Mn则为矩阵
显然, 密文矩阵的每一个行向量都是明文矩阵的所有行向量的一种线性组合, 其组合系数正好是加密矩阵的相应行上的所有元素.根据矩阵乘法的定义直接计算密文矩阵时, 计算密文矩阵的每行元素需要做mn次乘法和m(n-1)次加法,计算密文矩阵的每个元素需要做n次乘法和n-1次加法,因此计算整个密文矩阵总共需要mn2次乘法和mn(n-1)次加法.
4 总结
可逆矩阵作为矩阵乘法的逆运算,是矩阵的一种重要运算,在解决矩阵问题起着重要的作用.因而掌握可逆矩阵的求法,在解决实际问题时选择适当的方法,往往可以起到事半功倍的效果.本文首先从可逆矩阵入手给出了可逆矩阵的概念,并讨论了可逆矩阵的性质,其次对可逆矩阵的性质进行了讨论并得出了一些定理,并且举出了相应的例题.最后给出了可逆矩阵在通信中的应用,使的学习的人对可逆矩阵有了更进一步的认识.对于其它方面的应用,未进一步进行做讨论,有待进一步探讨.
致谢 在此谨向任天胜老师致以诚挚的谢意.
参 考 文 献
[1] 刘剑平, 施劲松主编. 线性代数[M]. 上海:华东理工大学出版社,2011.
[2] 熊小兵. 可逆矩阵在保密通信中的应用[J]. 大学数学, 2007,23(3).
[3] 徐仲主编. 高等代数(北大第三版)导教·导练·导考[M]. 西安:西北工业大学出版社,2006.
[4] 北京大学数学系几何与代数教研室前代数小组主编. 高等代数[M]. 北京:高等教育出版社,2003.9(2012.3重印).
[5] 华中科技大学数学系. 线性代数(第2版)[M]. 北京: 高等教育出版社,2003.
[6] 蓝以中. 高等代数简明教程(上册)[M]. 北京: 北京大学出版社,2002.
[7] 张新发. 初等矩阵的关系及可逆矩阵的分解[J]. 大学数学,2003,19(2).