【doc】用分块法降阶计算行列式和矩阵求秩算法的探讨

【doc】用分块法降阶计算行列式和矩阵求秩算法的探讨 用分块法降阶计算行列式和矩阵求秩算法 的探讨 ? 1989~.浙江工学院 (总第删蒯)JOURNALOFZHEJIANGINSTITUTE0TECHNOLOGY 3i989 'Sum.d4) 用分块法降阶计算行列式 和矩阵求秩算法的探讨 刘东 (基础课程部) 摘要 文献[1]提出7用分块法降阶计算高阶行列式和矩阵求秩的方法,但计算量 还很大.本文提出两个基本命,根据行列式或矩阵元素的特点,通过初等变换, 进行合理分块,利用基本命题改进算法,使计算量最少. 关键词:行列式,秩,计算方法,矩阵变换法 文献[1]中Schur定理提出了高阶行列式降阶计算的一个方法,即设n阶行列式 IMIl 是分块行列式,且A是非奇异矩阵,则 IMI=IAIID—CA'Bf(1) (1)式右端起了行列式降阶计算的作用,但需要计算r阶方阵A的逆阵,两次矩阵的 r阶行列式之乘积,计算量还是很大的. 乘法,一次减法,r阶和n— 本文对(1)式右端的计算如何最简进行探讨;并对用分块法降阶求矩阵的秩,使计算 尽量简单. 1降阶计算行列式的简化算法 如同n阶行列式的性质一样,分块行列式也具有以下性质: 性质1分块行列式{MI某一块行(列)的元素左(右)乘以非异阵K, 列式乘lMI,即 l,KIl会『 啦藕日期?1989—02—27 等于用K的行 ? 103? 文叶I涉及的矩阡运算,假都满址运算条件. 征利用分块矩阵的运算录lLaplace展开定理,【U得 = J(誉…))I = . :…K-:l 为了便于应用,将(2)式改写成 A c 性质2分块行列式的某一块行f列)左(右)乘以矩阵K,然后加到另一块行(列) 上去,行列式值不变.即 l十A十BCKADKB{=lACBDl十十:ll 证 c+A.Bl=1(:…)()l = …会:l 性质3分块行列式lMl的两块行(列)对调得IMl,则 -M?-=}三:l=c一,"nuj.13ii 其中r和n分别是lAJ和JMl的阶数. 证 (l == c——'1+2+?'+【(n—f+1'+_-?+n'l『==c——fn+ll;l 利用上述性质和Laplace展开定理很容易得到(1)式的证明: lAc:l=tA-lA.-Bl=tA-}:.一Ac-tAB一Bl= IAIlD—CA.Bl(3) 下面分情形讨论【1)式右端计算的简化问题,为方便起见,将单位阵两行(列)瓦换 得到的初等阵称为对换阵. 1.1行列式中台有r(?2)阶子阵是单位阵或对换阵 作为(1)式的直接推论,有 基本命题1 tD--CB-? ' (4)式将一个13.阶行列式的计算,转化成低阶矩阵的一次乘法,减法和一个13.一r 阶行 ? 104. 列式的求值,讣算量比(1)式明显l减少. 总可以利用行(列)调换得到新的行列式, 阶计算. 倒1计算行列式 凼而行列式r{r含有予阵魁单传阵或对换阵时, 其左上角子阵是单位阵,从而利用基本命题1降 2l01—1 32l02 D=112—15 i0—1614{ 14587—1l 取自(1)中例题(P56~I3),观察行列式中由第1,2行与第3,4列相交处元素 组成的子阵,是对换阵,将1,4列与第2,3列分别互换得 }10i12—1I 01i232- D=(一1)一12;115 16:一104 78;54—1J =一z 3 . 410f+sf1"810f=sIlIf… 与文献(1)中的计算比较,计算量明显减少. 例2计算行列式 (1) l2 0——1 l0 01 14 2l 13 31 )行列式的左下角2阶子阵是单位阵 12 0—1 1 O I4 21 013 : 13l 一 2 — 14 —— 18 — 3 — 20 — 34 10 0l 12 0—1 0 — 7 — 1O ;l3 :31 :l4 :21 )一(一;一)ff一:一J一一7 5行与第2,3列交错的元素组成的子阵是2阶对换阵. ? 1O5- ,,1 IlJ, 5n9 4舯勰 0船,,J?l?,,一 ,1lIJ/ 一a4l — l04 1l5 一 ,,,,, \ 41215 l2123 — 2151O l03n1 O2I32 一 ) 2 ( , i 第 l内 式 列 行 ) 2 012 201 — 135 331 210 19300 25310 683 12 21 14 483 14 21 12 21 35 )_/.0\《81116l\677,17—18—18j一9—16—8—3 1.2行列式中不含r(?2)阶子阵是单位阵或对换阵 (3)式表明,用分块法降阶计算高阶行列式,可不必先求A-1再作乘积AI1B,只要 对矩阵施行初等变换将A化成E,同时可使A右邻的矩阵B变成AI1B,即 行初等变换 (AiE)————(E;AI】B) 再计算lAlJD—CAI1BJ.因此,适当选择A,使A容易化成单位阵且AB表达形式简 单 (尽量取JAl=?1,避免分数运算),能使计算简单.这样的矩阵有:1.对角阵}2.三角形 阵|3.容易化成单位阵的其它矩阵.为此,可在行列式中先找出一个上述形式的子阵, 再通 过初等变换将它换至左上角,然后进行计算. 例3计算行列式 (1)D= 2—4 — 36 — 11 0 0 2 31—3 1—13 11 0—1 56 42 11 (2)D 0 C0d 解(1)易见行列式右上角是2阶三角形阵,将第1,2列分别与第4,5列对换, 并分块: 106, D=(一1) 11;02—410;0—12 56 42 11 — 1 3 1— 0—3601:03—6 )_( 11 31 1—1 56 }42 I11 013—2吼 02—41 02—4 2—11 — 331 31—1 2—1427 — 315 3—13 b0 ? ? bd 0 aC .' f2)D2= d b ? ? ???? d 一 320 1ib/a ? .:.' 1ib/a =a??…?…??…'''…'' cid . ? .i'. cid =a.(d-bc/a)=(ad—bc), 倒4计算行列式 Ml= (d—bc)/al 01 0l (d—be)/a{ 解这个行列式内没有二阶上子阵是单位阵,对换阵,对角阵和三角形阵,但可以找 出一个易化成单位阵的子阵,因为 I 将行列式分块 从而 D=…?………?………? 5 13 先对分块矩阵(A;B)进行行初等变换求A-1B ,1 I \2 ,1 ——— { \0 /3 CAB=I2 D—CA-1Bl= — e ,0 11, 8 — 2 ) 1 i 7 0 3 1 . 4 1O 一18) 18) 123 — 1O一23—41 4311 ? 1O7 盯58 ??0 — 230 5n2m 4加?73 37n75 23574 — 12321 ,, 4? 0, 23 12 BD AC lI —n? 坞73 n75 574 — 30l 42 31 37 23 51 一 O] d? 一一 一 一l1 51 一 ,\ ,l,?/ 074 ?鲫O 坞73 O『 一 11l==一52 — 1l 所以 IMl—JAl1D—CA13}=52 在高阶行列式的计算中,一般来说对于无规则的数字行列式用上面的算法都H:较方便 现将具体做法归纳如下: 1.若在行列式内可找到阶数?2的子阵是单位阵或对换阵,先通过行和列对换将它移 至左上角,再利用基本命题1计算. 2.若在行剜式内阶数?2的子阵中投有单位阵或对换阵,而有对角阵或三角形阵,尽 嚣选择行列式等于-t-1的子阵,移至左上角,用(3j式计算. 3.对于没有0元素的行列式,宜选择容易化成单位阵的子阵(最好是其行列式值魁 ?1),换至左上角,先计算(A;B)—?(E;A'B),再计算lD—CABf和fAf,求得原 行列式之值. 降阶计算矩阵秩的简单算法 同矩阵的初等变换一样,分块矩阵也可定义块初等变换. 定义分块矩阵A的块行(列)初等变换是指: 1.用一非异阵K左(右)乘A的某一块行(列)J 2.用矩阵L左(右)乘A的某一块行(列)加到另一块行(列)上去| 3A的第i块行(列)与第j块行(列)对调. 分块矩阵的块初等变换也不会改变矩阵的秩,证明见[2). 文献[1)中也提出了秩的降阶定理,即若A是非异阵,则 JAn' R(nD)=R(A)+R(D—CA一B)(5),U, 与行列式的计算一样,这里也有如何使右端计算尽量简化的问题. 2.1矩阵内含有r(?2)阶子阵是单位阵或对换阵 /R, 基本命题2设分块矩阵(=二),则 }LD/ /E.B, Re,,'一J=r+R(D—cB)(6)\D, 如果矩阵内有子阵是单位阵或对换阵,总可以通过行或列对换,将它移至左上角, 矩阵 的秩保持不变.利用(6)式,计算n阶矩阵的秩就转化成计算n—r阶矩阵的秩(尚需 计 算低阶矩阵的乘法和减法各一次),比直接用f5)式计算简便得多. 例5求下列矩阵的秩 ?108? O35 一一 4 一 (1) (2)A_ R(A);oo1;363+Rff.21一f.\\\\3277/\3277J] =3+o=3 (2)矩阵内台有二阶对换阵,将第1,3列对换 R(A)一R 10j10 01:10 11;00 ,一2 —2+Rf1 ,一1 2.2矩阵中不台r(?2 设A是非异阵,则 R ( 0, 01=2+3=5 1/ )阶子阵是单位阵或对换阵 )=R(暑AB)=R(.) =r+R(D-CA一B) 这里也不必先求A-1再计算AB,选择A的要求和做法也与1.2一样. 例6求下列矩阵的秩 - 一 4 ? 109 123 HOOO11 OOl361011O 0102【^011O1 45 12 00 01 1O 弛玎 H 36 2—0 14 " OOO OOO 2O1 ,,JlIl ,,一 ,,??,, OO1 O11 O1O ,,I【l, , ,,??L'' , R + 2 一一 OO.00l 11 1O O1 O0 ? 1O14 L2O4 O313 — 2411 一一 12O1 一 ,,,???? \ 譬 M ) 1 ( 一 妻)解(1)易见矩阵M中第1,3行与第1,3列相交处元素组成的子阵是对角阵,其 行列式之值是一1,故 M— 10 O1 23 — 13 :一4 11 1 0 ???.? 2 4 1—4 — 11 02 42 RcM,z+R((一:::;)一(二一;二一;)) =2+Rf3o1=4,8一b/ (2)矩阵中有一个元素是0,二阶三角形阵有16个,选择容易化成单位阵的一个J由 第4,5行与第1,3列相交处元素组成的子阵,其行列式等于2,但第5行有公因子2, 不会产生分数运算.将所选子阵移至左上角并分块:. 1l0 M 10;321 42:6—418 ???……?__????.?'?_??…?……?…? 一 26i一8—8—4 1—6:563 2—4;646 /10:321 I42;6—418 = (三) /o32\ \02一6—1214/ 一 (0.3一7)fiI\]一一6, .一cAB一 (一--8)一(一一--i6)(一3.一:) 00i4 一一 66402 一一 85636 — 2l214 一 r ? Jr,『JJl'l?1?t? , ,一一 M ) 2 ( 一 ,, ??, ,1632—4 = I一16—324 \一12—243 易见R(M)=2+2=4. 利用矩阵的初等变换和基本命题2计算高阶矩阵的秩,具体做法也可象行列式计 算一样 !日纳,不再列出 致谢:本文得刭浙江大学陈维新副教授的指导,特此致谢. 参考文献 El3屠伯墒.蝮性代数(方法导引).上洋-复旦大学曲艘社.1986:53~77,1O1,102 C2]欧阳梓祥.矩阵袋韧等变换丑其应用.工科数学.I987;(4):24,25 C3)北京大学教学力学熏几何与代数教簪f蜜代数小组.高兽代鼓.北京t人民教育 出板杜,1978:91~92,151, 152 "]同济大学数学教研童.线性代数.北京-高等教育出艘社.1982:16,l7 AnApproachtotheAlgorithmforCalculatingDeterminant andRankofMatrixbytheMethodofPartitioningand DescendingOrder LiuDong (DivisionofBasicCollrses) Abstract TheliteratureE1]listedbelowthisarticleisproposesanalgorithmfor calealatingahigherorderdeterminantandrankofmatrixbythemethodof partitioninganddescendingorder,butthismethodneedsalotofcalculation. 1nthisartide,twobasicpropositionsarepresented,andthealgorithmis improvedtOreducecalculationtominimtimbywayofelementarytransform— ation,reasonablepartitioninganddescendingorder. Keywords:Determinats,Rank,C0mpu协ti0na1method,Matrixtransform methods ? ll1 ,,./ 0l6 ?442 一一 ^U88 432 — 418 i 一 , ,??l L ,,一 I??J/ 436 864 — 856 一 ,,f?, l1