1、本科毕业设计（20届）对循环矩阵求逆的算法研究所在学院专业班级数学与应用数学学生姓名学号指导教师职称完成日期年月I【摘要】本文从推导循环矩阵性质入手，通过对循环矩阵性质的分析和证明，知道如何去求解一般的循环矩阵，并且也给出了循环的逆存在的充要条件，同时也列举了几个特殊的例子去运用之前推导的计算方法，效果也是非常不错，比起传统的求逆方法，计算量明显减少。于是又在此基础之上加入矩阵分块的思想，也找到了一个比较方便的算法，可以起到一个很好的降阶求逆矩阵的算法，通过举例很好的说明了问题，算法的确很大程度上减少了计算量。【关键词】循环矩阵；循环矩阵分块；逆矩阵。【ABSTRACT】THISPAPERDE
2、DUCEDTHEPROPERTYOFACYCLICMATRIX,THROUGHANALYSISOFTHECHARACTERISTICSOFCYCLICMATRIXANDPROOF,KNOWHOWTOSOLVEGENERALCIRCULATIONMATRIX,ANDALSOGIVESTHENECESSARYANDSUFFICIENTCONDITIONSOFTHEEXISTENCEOFINVERSECIRCULATION,ALSOCITEDSEVERALSPECIFICEXAMPLESTOUSETHECALCULATIONMETHODOFBEFORE,THEEFFECTISALSOVERYNICE
3、,COMPAREDTOTRADITIONALCALCULATIONMETHOD,INVERSESIGNIFICANTLYLESSANDONTHISBASISTOJOINMATRIXBLOCKTHOUGHTS,ALSOFOUNDAMORECONVENIENTALGORITHM,CANHAVEAVERYGOODORDERREDUCTIONOFINVERSEMATRIXMETHODTHROUGHEXAMPLEVERYGOODILLUSTRATESPROBLEMS,THEALGORITHMDOESLARGELYREDUCETHECOMPUTATIONTIME【KEYWORDS】CYCLICMATRIX
4、CYCLICMATRIXBLOCKINVERSEMATRIXII目录对循环矩阵求逆的算法研究错误未定义书签。摘要错误未定义书签。INVERSEOFCYCLICMATRIXALGORITHMRESEARCH错误未定义书签。ABSTRACT错误未定义书签。目录II1引言12循环矩阵的定义和基本性质221循环矩阵的定义222循环矩阵的性质2221基本循环矩阵的性质3222循环矩阵的性质及其定理33循环矩阵求逆的算法和可逆条件531一般结构的循环矩阵可逆条件及其具体算法。532一些具有特殊结构的循环矩阵求逆7321求解形如,OCIRCABBB的逆矩阵，其中0AB7322求解等差循环矩阵的逆94用矩阵分
5、块的方法对循环矩阵求逆1241用循环矩阵分块算法求逆的条件1242循环矩阵分块求逆的具体算法13参考文献17致谢（宋体，加粗，小二号字，居中）错误未定义书签。附录（宋体，加粗，小二号字，居左）错误未定义书签。11引言循环矩阵最早是在1885年，由美国学者MUIRT提出的。不过真正被人关注并开始研究是从1950年开始的。从50年代开始，随着高新技术尤其是计算机技术的迅猛发展，循环矩阵也是被广泛运用到很多众多科学和工程领域，如编码和统计，石油勘探和结构分析，以及数字图像处理等方面获得了越来越广泛的应用。循环码是一类非常重要的线性码，它具有严谨的代数结构，其性能易于分析。特别是目前已发现大部分线性码
6、与循环码有密切关系，它们之中的大部分码都可以归结于循环码。另外，循环码也有循环码的性质。由于可逆循环矩阵具有结构简单，更易于实现等优点。使得对循环矩阵的研究成为了热点。循环矩阵应用广泛，但使用初等变换的方法求逆过于麻烦，对于涉及循环矩阵求逆和一些其它运算的时候，也是希望可以寻求一些更快捷的方法，促进工程运算的效率。由于循环矩阵结构的特殊性，其应用性也是非常广泛，相信所研究的解法一定会有的其进一步应用有帮助。22循环矩阵的定义和基本性质21循环矩阵的定义首先给出循环矩阵的定义，定义1形如0121101221031230NNNNNNAAAAAAAAAAAAAAAAA的N阶矩阵，叫做N阶循环矩阵。从
7、定义上可以看出，循环矩阵中的每一行都是由前一行的元素右移一个位置，并将最右边的数挪动到左边第一个位置而组成的。因而，一个循环矩阵可以由其第一行来确定，这里用记号0121,NCIRCAAAA来表示一个循环矩阵。继续观察定义式，可以看到循环矩阵A沿平行于主对角线的每一对角线上的元素都是相等的，即循环矩阵是关次对角线对称的。其次，给出基础循环矩阵的定义，定义2设0100001000011000J，则可知J是N阶循环矩阵，称为基本循环矩阵。很明显基本循环矩阵可以表示为0,1,0,0CIRC。设0JE（N阶单位矩阵），则由定义2可知1JJ，20010000010000100J，NJE。因此我们定义1中的
8、循环矩阵都可以用0J，1J，2J，1NJ来表示。如果设210121NNFXAAXAXAX，则我们有AFJ，其中FX称为A的生成多项式。下文中很多的有关循环矩阵的性质证明都会运用到该多项式。22循环矩阵的性质这一步分主要从两个方面来描述循环矩阵的性质，首先会引入基本循环矩阵列，然后通过循环矩阵列去描述表达一般循环矩阵。并且完成对循环矩阵性质的推导。3221基本循环矩阵的性质首先，我们讨论基本循环矩阵的性质。我们把定义2中讲到的0J，1J，2J，1NJ称为循环矩阵基本列。则明显有有以下性质性质10J，1J，2J，1NJ为循环矩阵，且NIIJJ。性质2基本循环矩阵J可以与循环矩阵A交换，即AJJA。
9、性质3必存在一组数列0A，1A，2A，1NA，使得循环矩阵A可以用循环矩阵基本列来表示为0210121NNAFJAJAJAJAJ，反之利用循环矩阵基本列表示出来的矩阵一定是循环矩阵。这3个性质，非常简单，通过对定义的理解可以自己验证，这里就不做说明了。222循环矩阵的性质及其定理性质4N阶循环矩阵A、B相加，其和仍为循环矩阵。证明设循环矩阵0121,NACIRCAAAA，0121,NBCIRCBBBB。则由性质3，可知循环矩阵0210121NNAAJAJAJAJ，0210121NNBBJBJBJBJ。那么循环矩阵相加A、B相加，212101210121NNNNABAAJAJAJBBJBJBJ2
10、100112211NNNABABJABJABJ又由性质3可知A与B的和也为循环矩阵，可以表示为CIRC0B，1B，2B，1NB。性质5N阶循环矩阵A、B相乘，其乘积为循环矩阵，且有ABBA。证明设循环矩阵ACIRC0A，1A，2A，1NA，BCIRC0B，1B，2B，1NB。所以有0210121NNAAJAJAJAJ，0210121NNBBJBJBJBJ。则212101210121NNNNABAAJAJAJBBJBJBJ000112211NNNABABABABJ101102112NNABABABABJ202112013NABABABABJ101122310NNNNNABABABABJ显然我们清
11、楚的发现同阶循环矩阵的乘积仍为循环矩阵。同理我们可以得到212101210121NNNNBABBJBJBJAAJAJAJ4000112211NNNABABABABJ101102112NNABABABABJ202112013NABABABABJ101122310NNNNNABABABABJ所以可以知道循环矩阵相乘，矩阵可以交换。性质6可逆的N阶循环矩阵的逆也为N阶循环矩阵。证明设循环矩阵0121,NACIRCAAAA，设其逆矩阵存在为0121,NBCIRCBBBB。通过性质5的证明，我们知道，212101210121NNNNABAAJAJAJBBJBJBJ000112211NNNABABABAB
12、J101102112NNABABABABJ202112013NABABABABJ101122310NNNNNABABABABJ又因为，我们题设中的A、B两个矩阵是可逆的，即ABE。所以我们得到方程组，001122110110211202112013011223101000NNNNNNNNNNABABABABABABABABABABABABABABABAB即，012101012121032123011000NNNNNNNAAAABAAAABAAAABAAAAB也就是0121,1,0,0,0TTTNABBBB也就是A为可逆矩阵，则0TAA，因而由克拉默法则我们知道方程组有且仅有一组解，即0121,
13、TNBBBB是唯一确定的一组数，并且这组数确定了我们所求的逆矩阵为0121,NCIRCBBBB，是循环矩阵。至于循环矩阵可逆的条件，下一小节中将进一步讨论。53循环矩阵求逆的算法和可逆条件31一般结构的循环矩阵可逆条件及其具体算法。性质6给出了一个很好计算循环矩阵逆的思路。设可逆循环矩阵0121,NACIRCAAAA，则要求该矩阵的逆，我们可以先设它的逆为0121,NBCIRCBBBB。所以由ABE，得到方程组，001122110110211202112013011223101000NNNNNNNNNNABABABABABABABABABABABABABABABAB即，012101012121
14、032123011000NNNNNNNAAAABAAAABAAAABAAAAB也就是0121,1,0,0,0TTTNABBBB要得到0121,NBCIRCBBBB。只需要计算0B、1B、2B、1NB这组数的值即可也就是解上面列出的方程组。定理1循环矩阵A可逆的充要条件为0A。这个定理可以直接从所给的算法中理解，同时性质6的证明中也给出了说明,要解得逆矩阵，必须使得所求解的方程组有解，也就必须满足该定理。这里也就不进一步证明了。推论1循环矩阵0121,NACIRCAAAA，存在可逆矩阵时一定满足100NIIA。6证明循环矩阵A的行列式为0121101221031230NNNNNNAAAAAAAA
15、AAAAAAAA对行列式作初等行变换，从第二行开始，每一行都加一次到第一行，得到11110000101221031230NNNNIIIIIIIINNNNNAAAAAAAAAAAAAAAA假设推论不成立，那么有100NIIA，这样显然上面的行列式可以写1012210312300000NNNNNAAAAAAAAAAAA显然这个行列式的值为0。即0A，根据定理1，可知循环矩阵A不可逆，显然与题设向矛盾，所以假设不成立。因而一个循环矩阵0121,NACIRCAAAA可逆，必然满足100NIIA。下面可以通过具体的例子，来体会这种算法的优越性。例1求矩阵1236612336122361A的逆矩阵。解可以
16、看到矩阵A为循环矩阵，我们知道循环矩阵的逆也为循环矩阵，不妨设所求的逆矩阵为0123,XCIRCXXXX，根据0123,1,0,0,0TTTAXXXX我们得到方程组701230123012301236321263032606320XXXXXXXXXXXXXXXX解得01231112011601120160XXXX所以，得到所求的逆矩阵为1111111206012060111111601206012011111112060120601111116012060120。如果仔细体会过这种计算方法后会发现比传统的方法明显少了不少计算量。32一些具有特殊结构的循环矩阵求逆上一章节中已经给出了循环矩阵的求
17、逆特殊算法其优越性也有一定的体现，于是我想通过两个具体的例子，特殊结构的循环矩阵，去进一步说明其意义。321求解形如,OCIRCABBB的逆矩阵，其中0AB通过分析求解普通循环矩阵的方法，设所求的逆矩阵为0121,NPCIRCXXXX根据0121,1,0,0,0TTTNOXXXX则，我们可以得到方程组01210121012101211000NNNNAXBXBXBXBXAXBXBXBXBXAXBXBXBXBXAX写成增广矩阵的形式810000ABBBBABBBBABBBBA对增广矩阵作行列式初等变换，从第二行开始每行都加到第一行得到111110000ANBANBANBANBBABBBBABBBB
18、A由推论1，我们知道循环矩阵O要有逆必须满足10ANB，所以有111111000ANBBABBBBABBBBA进一步作行列式初等变换，将第一行乘以B，分别加到第二行至第1N行中，得到111111000100010001ANBBABANBBABANBBABANB解得0121211NANBXABANBBXXXABANB所以循环矩阵为92,1111ANBBBBCIRCABANBABANBABANBABANB。例2求循环矩阵2333323333233332NNA的逆矩阵。解观察矩阵NNA，可以看到完全可以套用本节上面讲到的模型。直接套用公式就可以得该逆矩阵，0121211NANBXABANBBXXXA
19、BANB因为2A，3D，所以01213413331NNXNXXXN所以所求的逆矩阵为134333,13313131NNCIRCNNNN个。322求解等差循环矩阵的逆若,2,1DCIRCAADADAND，则我们把D称为等差循环矩阵。如果D可逆，设其可逆矩阵为0121,NXCIRCXXXX。根据根据0121,1,0,0,0TTTNDXXXX得到线性方程组01211211202301230NXAANDANDADXADAANDADXADADAADXANDANDANDA10所以其增广矩阵为1211202301230TAANDANDADADAANDADDADADAADANDANDANDA对增广矩阵作行列式
20、初等行变换，将从第二行开始的每一行都加到第一行中去，得到11111111122221202301230NANNDNANNDNANNDNANNDADAANDADADADAADANDANDANDA由推论1，我们知道要使循环矩阵可逆满足1102NANND。则进一步做行列式初等变换，第一行都去除以112NANND111111121202301230NANNDADAANDADADADAADANDANDANDA进一步做行列式初等变换，将从第二行开始每一行，第一个数化为011111111111121022121022212102221210221112NANNDDNDDDADNANNDDDDDADNANND
21、DDNDDANDNANNDDDNDNDANDNANND继续做行列式变换，从第N1行开始，做N1行乘以1加到下一行，一直做到第二行停止，得到矩阵111111111111112102212100001210000121000012NANNDDNDDDADNANNDNDDNANNDNDDNANNDNDDNANND所以得到1011121231211211211221112NXXNANNDNADXNNXNANNDDXXXNANNDN其中10112NIINANNDA，IA代表了循环矩阵第一行中第I个数。循环矩阵D的逆矩阵得解。例3求解循环矩阵1234412334122341A的逆。分析这个矩阵也是符合本小
22、节上面讲的模型。矩阵A也符合逆存在的条件。解根据上面给出的公式，由题意我们知道，4N，1A，1D。设逆矩阵为0121,NXCIRCXXXX，解得01239401140140XXXX所以循环矩阵A的逆为91111,40404040CIRC。124用矩阵分块的方法对循环矩阵求逆41用循环矩阵分块算法求逆的条件若循环矩阵0121101221031230NNNNNNAAAAAAAAAAAAAAAAA为N阶，可以分块为1234AAAA。则先给出循环矩阵分块算法的可逆条件。定理2当4A为可逆，则循环矩阵A可逆的充要条件是11243AAAA为可逆矩阵，且有关系式1111241111114344324RRAA
23、AAARAAARAA，其中11243RAAAA。证明由分块理论可以知道11121243241344340000AAEAAAAEAAAAAAEAE（1），其中E为单位矩阵。并且124143010EEAAAAEE，所以（1）式两边同时取行列式11121243241344340000AAEAAAAEAAAAAAEAE则1211243434AAAAAAAAA定理2中要求4A为可逆矩阵，所以显然40A。又由定理1，我们知道循环矩阵A可逆的充要条件为0A。所以12340AAAAA成立的充要条件为112430AAAA。即当4A可逆时，循环矩阵A可逆的充要条件是11243AAAA可逆。13由题意可以知道，要计
24、算A的逆，可以设A的逆为12134XXAXX，则1212343400AAXXEAAXXE即得到112312243143324400AXAXEAXAXAXAXAXAXE解得1111224113431111444324XRXRAAXAARXAAARAA（其中11243RAAAA）定理证毕。通过定理2，不仅知道了循环矩阵分块之后逆的存在条件，也反应了求解具体方法。42循环矩阵分块求逆的具体算法由定理2，我们知道如果循环矩阵A满足各种矩阵分块算法的可逆条件，则有1111241111114344324RRAAAAARAAARAA。这里我们看到只要求出个各个分块矩阵就可以完成对原循环矩阵的逆的求解。不过这
25、里其实我们可以不必要那么麻烦，因为所求逆的矩阵A为可逆矩阵，我们完全可以去通过考虑它所特有的一些性质，在此基础上进一步简化求解过程。通过性质6我们知道N阶循环矩阵逆也为N阶循环矩阵。那么我们可以去考虑分块的具体方法，思考简化过程的方法。首先观察2N1阶的循环矩阵的0122201212120221230NNNNNNAAAAAAAAAAAAAAAAA，对他进行分块，分成1234AAAA，其中使得1A为11NN阶矩阵，2A为1NN阶矩阵，3A为1NN阶矩阵，144A为NN阶矩阵。可以知道0122011121202120NNNNNNNNNAAAAAAAAAAAAAAAAA，那么1A中包含了原循环矩阵A
26、中的每一个数，也就是说分块1A可以唯一的确定A。两者之间有着一一对应的关系。同理，我们知道1A也是一个循环矩阵，设他的分块为1234XXXX并且由定理2，知道111243XAAAA，则1X和1A为同阶矩阵，所以我们也就知道了1X和1A也是相互确定的，也就是说只要计算出1X，则1A也就知道了。再看下2N阶的循环矩阵0122121012222210231230NNNNNNAAAAAAAAAAAAAAAAA，如果平均分成1234AAAA四块，那么1A、2A、3A、4A都为N阶矩阵，先看下1A具体内容，01212101212221031230NNNNNNNNNAAAAAAAAAAAAAAAA，可以看到
27、1A比原矩阵A中的元素少了个NA，所以也就导致无法通过1A完全知道A。如果要达到2N1阶循环矩阵中分块矩阵的求逆效果，我们可以对2N阶循环矩阵作一个重新分块，只要满足1A阶数大于2N即可。另外对于一个矩阵求解，我们总希望它的阶数会比较第一点，这会很大程度上方便我们的求解，于是我们最后可以得到一个综合上面内容的分块方案。即我们可以将N阶循环呢矩阵分块为1234AAAA，并且使得1A为12N阶矩阵，2A为1122NNN阶矩阵，3A为1122NNN阶矩阵，4A为12NN阶矩阵。在这种分块方案下求解，我们只需求解1111243XRAAAA，即可以知道所求的循环矩阵的逆。下面就通过具体的实例来运用这样的
28、算法。15例4求循环矩阵1234551234451233451223451A的逆。解设逆矩阵12134XXAXX，可以将A分块成12341234551234451233451223451AAAA，则1123312231A，2453423A，3345234A，41251A，则1111124314161757575114167575751114757575XRAAAA所以11416111757575757511416117575757575111416175757575751111416757575757516111147575757575A。例5求循环矩阵1021110221100211A的逆矩
29、阵。16解设逆矩阵12134XXAXX，可以将A分块成12341021110221100211AAAA，则1102110211A，2120A，3021A，41A，则11111243137161616513161616751161616XRAAAA所以1137516161616513716161616751316161616375116161616A。17参考文献1柳重堪、刘锦萼，分块循环矩阵的性质及其对数字图像处理的应用J,湖北师院学报，1985,（2）914。2何承源、黄廷祝，两类循环分块矩阵及其有关算法J，应用数学学报，2002,252279288。3毛纲源，分块矩阵为循环矩阵的循环分块矩
30、阵的特征根求法J,武汉工业大学学报，1992，14（4）9398。4张佳静、杨兴东、孙苏亚，循环分块矩阵方程之解及其应用J,南京信息工程大学学报（自然科学版），2010，2（1）7478。5张光辉、叶晓丽，关于R分块循环矩阵及其对角化问题的讨论J,数学理论与应用，2007，27（1）1151176蔡子华、徐玉华,关于分块反循环矩阵及其对角化的讨论J，数学杂志,2004,2444334467卢诚波，关于R,R循环分块矩阵求逆与相乘的一种快速算法J，大学数学，2008,24（4）12212688DAVISPCIRCULANTMATRICESMNEWYORKWILEY,197999BLAHUTREFASTALGORITHMFORDIGLTALSIGNALPROCESSINGADDISONWESLEYREADING,MASS,19841010HOROWITYEAFASTMETHODFORINTERPOLATIONUSINGPRECONDITIONINGINFORMATIONPROCESSINGLETTERVOL1,1972,157163
