当前位置：文档之家 › 关于循环矩阵的计算

关于循环矩阵的计算

  • 格式：doc
  • 大小：1.17 MB
  • 文档页数：15

引言循环矩阵的概念是T Muir于1885年首先提出来的，直到1950至1955年，Good等才分别对循环矩阵的逆、行列式及其特征值进行了研究[1]．从此拉开了对循环矩阵各个方面的研究的历史．近年来，循环矩阵类已成为矩阵理论和应用数学领域中的一个非常活跃和重要的研究方向[2-4]．它之所以引起广大数学研究者如此大的兴趣，主要是基于下面两个方面的原因：一方面循环矩阵是一类非常重要的特殊矩阵，在现代科技工程领域中被广泛的应用，比如在分子震动，信号处理，纠错码理论，编码理论，图像处理，结构计算，电动力学等领域．另一方面由于循环矩阵类有许多特殊而良好的性质和结构，已被广泛地应用于应用数学和计算数学的许多领域，如控制理论，最优化，求解（偏）微分方程，矩阵分解多目标决策，二次型化简及平面几何学等．本文主要利用循环矩阵的性质对其逆的求法、对角化、行列式计算等问题进行研究．1、预备知识1.1 循环矩阵的概念定义1.1 形如0121101221031230n n n n n n a a a a a a a a A a a a a a a a a ------⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦的矩阵称为循环矩阵．定义1.2 形如100001000011000D ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦的矩阵称为基本循环矩阵．定义1.3 若12-1,,,n a a a 为复数域C 上的n 个数，n 阶矩阵()ij A a =满足：,,1,2,,,j i ij n j i a j i a i j n a j i-+-≥⎧==⎨<⎩即01221101322104312310n n n n n n n n n n a a a a a a a a a a A a a a a a a a a a a ----------⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦称矩阵A 为复数域上的n 阶循环矩阵，简记为0121(,,,,)n A C a a a a -= ．当12-1,,,n a a a 为实数域R 上的n 个数时，称矩阵A 为实数域上的n 阶循环矩阵，简记为0121(,,,,)n A R a a a a -= ．1.2 循环矩阵的一些性质设基本循环矩阵为0100001000011000D ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦显然，21,,,,n n D D D D I -= （n 阶单位矩阵）都是循环矩阵且210121+n n A a I a D a D a D --=+++ ．设210121()+n n f x a a x a x a x --=+++ ，则()A f D =，此时00a a I =．性质1.1 两个循环矩阵,A B 的乘积仍为循环矩阵，且AB BA =． 证明 设210121+()n n A a I a D a D a D f D --=+++= 210121()n n B b I b D b D b D g D --=++++=因n k k D D +=（k 为非负整数，0D I =），因此，()()()()()AB f D g D g D f D h D BA =⋅=⋅==．这里()h x 是一个不高于1n -次的多项式，由此知AB 是n 阶循环矩阵，且AB BA =．性质1.2 可逆的循环矩阵的逆矩阵仍是循环矩阵． 证明 由性质1.1知，只要能找到循环矩阵10121()n n B b I b D b D b D g D --=++++=其中，0121,,n b b b b - 为待定常数．使得AB I =即可，其中A 为可逆的循环矩阵：即：210121n n A a I a D a D a D --=++++则：212101210121()()n n n n AB a I a D a D a D b I b D b D b D ----=++++⋅++++00112211100121()()+n n n n n a b a b a b a b I a b a b a b D -----=+++++++++110213201()n n n n n a b a b a b a b D -----++++ ．要使AB I =，必须且仅须下列方程组成立001122111001122110213201100n n n n n n n n n a b a b a b a b a b a b a b a b a b a ba b a b ---------++++=⎧⎪++++=⎪⎨⎪⎪++++=⎩ （1.1）以上方程组以0121,,n b b b b - 为未知数，以T A 为系数矩阵（T A 表示A 的置换矩阵）．由于A 可逆，故0T A A =≠．方程组（1.1）有且仅有唯一的解0121,,n b b b b - ，而B 就是A 的逆矩阵，且B 也是循环矩阵．性质1.3 任何一个循环矩阵A 在复数域上都与一个对角矩阵相似． 证明 由文献[5]知，n 阶循环矩阵D 的特征值为22cos sin k k k i n n ππλ=+ (0,1,2,1k n =- ) (21i =-)． 由于()k j k j λλ≠≠，由文献[6]知，D 相似于对角矩阵 011(,,)n diag λλλ-Λ= 即存在可逆矩阵P ，使得1P DP -=Λ．设210121+()n n A a I a D a D a D f D --=+++= ，是任意一个n 阶循环矩阵，则A 相似于对角矩阵011{(),(),()}n diag f f f λλλ- ．事实上，1D P P -=Λ1111011()()()n n A f D f P P a I a P P a P P -----==Λ=+Λ++Λ1011{(),()()}n P diag f f f P λλλ--=⋅⋅ ．2、循环矩阵的求逆循环矩阵的逆可以用初等变换法、伴随矩阵法、分块矩阵法等一般的方法来求解，但作为一类特殊的矩阵，如果用这些方法来求逆未免太麻烦．下面给出的方法比现有的方法简单，适用的范围更广．定理2.1[3] 设n 维向量(1,0,0,,0)T e = ,矩阵()B A e = ，对矩阵B 进行初等变换，使矩阵A 变成单位矩阵，如果e 变为12(,,,)T n M M M ，那么12311221111322341n n nn n n n n n nM MM M M MM M M M A M M M M M M MMM M -------⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦． 证明 由于循环矩阵的逆为循环矩阵，因此可以设A 的逆为12311221111322341n n n n n n n n n nx x x x x x x x x x A x x x x x x x x x x -------⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦由于1AA E -=从而12,,,n x x x 是方程组11221111221111231221321111000n n n n n n nnn n n nn nn n n n a x a x ax a xa x a x ax a x a x a x a x a x a x a x ax a x-----------++++=⎧⎪++++=⎪⎪++++=⎨⎪⎪++++=⎪⎩（21） 的解．此方程的系数矩阵就是A ，增广矩阵为()B A e = ，根据方程组的理论只要将B 进行初等变换，使矩阵A 变成单位矩阵，如果e 变为12(,,,)T n M M M ，那么方程组（2.1）的解为1122,,,n n x M x M x M === ． 从而12311221111322341n n nn n n n n n nM M M M M M M M M M A M M M M M M M M M M -------⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦． 例1 求矩阵1012210112100121A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦的逆 解 因为1012210112100121⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦12341000x x x x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦ 的解为[]123412113333TTx x x x ⎡⎤=-⎢⎥⎣⎦． 从而111123333211133331211333311213333A -⎡⎤-⎢⎥⎢⎥⎢⎥-⎢⎥=⎢⎥⎢⎥-⎢⎥⎢⎥⎢⎥-⎣⎦． 定理3.2[4] 设n 阶循环矩阵的分块矩阵为1234AA A A A ⎡⎤=⎢⎥⎣⎦，其中1A 为12n m ⎡⎤=+⎢⎥⎣⎦阶矩阵，则（1）A 可逆的充要条件是4A 和11243A A A A --为可逆矩阵． （2）如果4A 和11243A A A A --可逆且11243A A A A --的逆为111212122212m m m m mm x x x x x x x x x ⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦， 那么n 阶循环矩阵的逆为11121111211111113112131121114112131112111m k k m km m m kk k x x x x x x x x x xm xx A x x x xx x x xx x xx -------⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦． （2.2）证明 （1）由分块矩阵的理论知1240E A A E -⎡⎤-⎢⎥⎣⎦1234A A A A ⎡⎤⎢⎥⎣⎦1430EA A E -⎡⎤⎢⎥-⎣⎦=11243400A A A A A -⎡⎤-⎢⎥⎣⎦两边取行列式得1234A A A A A ==141243A A A A A -⋅-从而0A ≠的充要条件是40A ≠且112430A A A A --≠．（2）由于当4A 和11243A A A A --可逆，A 的逆为1111241111114344324R R A A A A A RA A A R A A ----------⎡⎤-=⎢⎥-+⎣⎦其中11243R A A A A -=-，又因为1A -为循环矩阵．所以1A -为（2.2）的形式．根据定理2.2的（2），求n 阶循环矩阵的逆可以进行分块，分块的原则是以12n ⎡⎤+⎢⎥⎣⎦阶顺序主子式为一块，共分成四块，这样就可以将n 阶循环矩阵的逆转化成一个12n ⎡⎤+⎢⎥⎣⎦阶循环矩阵的逆，从而给问题的解决带来很大的简便．例2 求1012331012231011231001231A ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦的逆矩阵．解 根据定理（2.2）的结论（2），将矩阵A 分块为1234AA A A A ⎡⎤=⎢⎥⎣⎦其中，12101233101223101A A ⎡⎤⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦，,341231001231A A ⎡⎤⎡⎤==⎢⎥⎢⎥⎣⎦⎣⎦， 那么11243A A A A --=81168911588⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦，从而1-11243-1640-231=-9-16407719-9-16A A A A -⎡⎤⎢⎥-⎢⎥⎢⎥⎣⎦（） 于是1164023199916402319119916402377231991640402319916A ----⎡⎤⎢⎥---⎢⎥⎢⎥=---⎢⎥---⎢⎥⎢⎥---⎣⎦．3、循环矩阵的对角化问题 3.1 循环矩阵的对角化n 阶矩阵A 关于多项式函数()f x 生成的矩阵为()f A ，A 的特征根与的()f A 特征根有下面的结论：结论3.1 设()f x 是一个1n -次多项式函数，若λ是矩阵A 的特征根，则()f λ是矩阵()f A 的特征根．结论3.2 设()f x 是一个1n -次多项式函数，若矩阵A 相似于矩阵B ，则矩阵()f A 相似于矩阵()f B ．考察n 阶基本循环矩阵D ，D 的特征多项式为：211(),(1)n j njnj E D ei πλλληη-=-=-=-==-∏如果n 阶循环矩阵A 记为210121()n A n A f D a E a D a D a D --==++++ ，不难求得D 与特征值j η相应的特征向量，记：()(1)1j j n j X ηη-⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦， 则2()()(1)11j j j j j j j n j DX X ηηηηηη-⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥===⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦由结论3.1得()()()()j j j j A A AX f D X f X η==可以验证11(1)()(1)000,1(,)1,1n n m kmkm k k k m X Xm ηηη----==≠⎧===⎨=⎩∑∑ 将这个两两正交的向量()j X 单位化，可得标准正交基(0)(1)(1)111,,n X X X n n n -⎧⎫⎨⎬⎩⎭令矩阵(0)(1)(1)1(,,,)n T X X X n-==11(1)(1)111111n n n n n ηηηη----⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦则'(0)(1)(1)1'1(,,)n T T X X X n--==． 于是有下面的结论：结论3.3[5] 任意n 阶循环矩阵()A A f D =在复数域C 上都可对角化，即101(1){(,(),,()}n A A A T AT diag f f f ηηη--= )．在一类n 阶可对角化的相似矩阵中，如果对角化的矩阵为：011(,,,)n B diag b b b -=由结论3.3，只要令()(0,1,2,,1)j A j f b j n η==- 即可得n 个关于011,,,n a a a - 的线性方程组．又由于矩阵T 及特征根η由n 阶矩阵K 确定，且0T ≠．所以，多项式函数()f x 中的系数011,,,n a a a - 是唯一确定的[6]．于是，循环矩阵()A A f D =是唯一确定的．因此，可得出在一类可对角化的相似矩阵中，一定含有且仅含有一个循环矩阵．否则，就不对角化.下面以四阶循环矩阵举例说明：例3[7]求四阶循环矩阵1234412334122341A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦的特征根，并对角化. 解 令23()1234f X X X X =+++得()A A f D =，0100001000011000D ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦由于2i nei πη==，所以，A 的特征根分别为：0123()10,()22,()2,()22A A A A f f i f f i ηηηη==--=-=-+其中，11111111111211i i T i i ⎡⎤⎢⎥--⎢⎥=⎢⎥--⎢⎥--⎣⎦，1111111111111i i T i i -⎡⎤⎢⎥--⎢⎥=⎢⎥--⎢⎥--⎣⎦可以验证1(10,22,2,22)T AT diag i i -=----+．3.2 一般矩阵对角化与循环矩阵的关系称多项式211012()n n f x a a x a x a x --=++++ 为循环矩阵A 的生成多项式． 定理 3.1[8] n 阶矩阵P 可以对角化的充要条件是P 相似于一个n 阶循环矩阵．证明 一方面，若n 阶矩阵P 与循环矩阵A 相似，由于A 可以对角化，所以P 也可以相似对角化．反过来，若n 阶矩阵P 可以对角化，总存在n 阶循环矩阵A 与之相似． 事实上，设112(,,,)n Q PQ diag λλλ-= ，若能得到A 的生成多项式则A 就被唯一确定了．为此令1(),0,1,,1k k f k n ελ+==- ．即21010*******01121112210112111n n n n n n n n n na a a a a a a a a a a a εεελεεελεεελ---------⎧++++=⎪++++=⎪⎨⎪⎪++++=⎩ 其中，0=1ε．这个非齐次线性方程组的系数行列式是Vandermonde 行列式，从而不等于0，于是该方程组有唯一解011(,,,)n a a a - ，则()f x 被唯一确定．此时1121((1),(),(),,())n T AT diag f f f f εεε--= =12(,,,)n diag λλλ即11T AT Q PQ --=所以存在循环矩阵A 与矩阵P 相似．定理3.2[9] 设P 和Q 是两个n 阶复矩阵，则它们可以同时对角化（即1C AC -和1C BC -均为对角形）的充要条件是存在可逆矩阵C 及两个多项式()f x 和()g x 使得1()P C f B C -= ，1()Q C g B C -=其中，B 为基本循环矩阵．4、循环矩阵的行列式计算及应用引理4.1[10] 设A 是以12,,,n a a a 为元素的n 阶循环矩阵，则矩阵A 的行列式12()()()n A f w f w f w = ，其中123,,,w w w 是n 次单位根．证明 取0100001000011000n J ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦因为012010000010000100nn n nn n J E J J J J E ⎡⎤⎢⎥⎢⎥⎢⎥====⎢⎥⎢⎥⎢⎥⎣⎦，，，， 所以n J 的特征值为方程10n x -=的根[11]，设为12,,,n ωωω ． 记112()n n n n n A a E a J a J f J -=+++=令112()n n f x a a x a x -=+++则由引理4.1知，A 的特征值为12(),(),,()n f f f ωωω ． 故而12()()()n A f f f ωωω= ．推论4.1 设A 是以12,,,n a a a 为元素的n 阶循环矩阵，则A 可逆的充分与必要条件是112()n n f x a a x a x -=+++ 与()1nn f x x =-互素，即1((),)1n f x x -=．证明 由12()()()n A f f f ωωω= ，A 可逆的充要条件是0A ≠，即112()n n f x a a x a x -=+++ 与()1nn f x x =-没有公共根，从而1((),)1n f x x -=．推论4.2 若112()n n f x a a x a x -=+++ 与()1nn f x x =-互素，则211121()n n n f x a a x a x a x --=++++ ，212112()n n n n f x a a x a x a x ---=++++ ， ，211231()n n n n f x a a x a x a x ---=++++ 都与()1nn f x x =-互素．证明 因为分别以121(),(),,()n f x f x f x - 的系数为元素的循环矩阵和以()f x 的系数为元素的循环矩阵的行列式最多相差一个符号，由推论4.1 便可推出此推论．例4[12] 设[1,2,3,]A n = ，，求矩阵A 的行列式． 解 因为[1,2,3,]A n = ，所以1231211122341nn n A n n n -=--=12()()()n f f f ωωω ，其中，12,,,n ωωω 是()f x =1n x -的根，而21()123n f x x x nx -=++++ ，通过计算得11(1)(1)2n n n n A --+=-．参考文献：[1] 江兆林，周章鑫．循环矩阵[M]．成都：电子科技大学出版社，1999． [2] 程云鹏．矩阵论[M]．西安：西北工业大学出版社，2005． [3] 詹颖，于宝满．循环矩阵的逆[J]．数学通报，1989（05）：29-31． [4] 北京大学数学系．高等代数[M]．北京：高等教育出版社，1999． [5] 赵继安．循环矩阵与矩阵对角化[J]．数学通报，1994，（4）：41-42．[6] 蔡剑芳，钱吉林，李桃生．高等代数综合题解[M]．武汉：湖北科学技术出版社，1986． [7] G W 斯图尔特．矩阵计算引论[M]．上海：上海科学技术出版社，1980． [8] 王萼芳．高等代数教程[M]．北京：清华大学出版社，1996． [9] 白述伟．高等代数选论[M]．哈尔滨：黑龙江教育出版社，2001．[10] 黄赐玺．循环矩阵的非异性[J]．山东师范大学学报，1991，6（2）：22-26． [11] 沈光星．关于某些循环矩阵的特征值[M]．应用数学，1991，4(3)：76-82．[12] 贾璐，姚光同．有关循环矩阵的行列式计算及其应用[J]．信阳师范学院学报（自然科学版）， 2005（2）：131-132．致谢在四年的大学学习和生活中，我得到了来自学院老师、亲人、同学对我多方面的关怀及帮助，使我得以顺利地走过了我人生道路上重要的一段旅程．我深深的感谢他们，并将以此激励我在今后的学习、工作和生活中不断进取！本文的完成离不开黄保军老师和刘凯老师的热情指导，他们在本文的内容研究和文章撰写过程中都给予我细心指导，并提出了宝贵意见．他们渊博的学识，严谨的治学态度和一丝不苟的教学精神，使我受益匪浅．同时，感谢所有给予我帮助的老师和同学，正是在他们的帮助下，我的论文才得以顺利完成．。

合集下载

H-循环矩阵线性系统求解及其求逆的多项式快速算法

H-循环矩阵线性系统求解及其求逆的多项式快速算法

ＨＥ Ｃｈ ｅ ｎ ｇ ｙ ｕ ａｎ，ＺＨＡＮ Ｇ Ｋｕ ｎ ｐｅ ｎ ｇ水
，
ＭＡ Ｊ ｉ ａ ｎ ｇ ｍｉ ｎ ｇ
（ Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ， Ｘｉ ｈ ｕ ａ Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ，Ｃ ｈ ｅ ｎ ｇ ｄ ｕ ６ １ Ｏ ０ ３ ９， Ｃｈ ｉ ｎ ａ ）
摘要 ： 利 用 多项式理论 ， 给出 循环矩 阵线性 系统 求解及 求逆矩阵的一种快速算 法。该快速 算法有 一个显著特 点 ， 求解线性 系统 时不 需要预 先知道 循 环矩 阵是 非奇异还 是奇异 ， 得到 循 环矩 阵非奇异 、 唯一解、 逆矩 阵 ； 或得 到 循环 矩 阵奇异、 有 解、 特 解、 通 解、 自反广义逆矩 阵。同时， 其逆矩 阵及 自反 广义逆矩阵仍然是 循环矩 阵。 关键词 ： Ｈ － 循 环矩阵 ； 多项式快速 算法 ； 唯一 解 ； 通解 ； 逆矩 阵。 中 图分类号 ： ０ ２ ４ １ ． ６ 文献标志码 ： Ａ 文章编号 ： ２ ０ ９ ５— ５ ３ ８ ３ （ ２ ０ １ ５ ） ０ ２— ０ ０ ５ ４—０ ４
ｎ ｏ ｎ ｓ ｉ ｎ ｇ ｕｌ ａ ｒ ｗｉ ｔ ｈ ｔ ｈ ｅ ｒ ｅ ｓ ｕ ｌ ｔ ｏ ｆ ｕ ｎ ｉ ｑ ｕ ｅ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ａ ｎ ｄ ｔ ｈ ｅ ｉ ｎ ｖ ｅ ｒ ｓ ｅ ｍａ ｔ ｉ ｒ ｘ ｏ ｒ ｔ ｈ ｅ Ｈ－ ｃ ｉ ｒ ｃ ｕ ｌ ａ ｎ ｔ ｍａ ｔ ｉｘ ｒ ｉ ｓ ｓ ｉ ｎ ｇ ｕ ｌ ａ ｒ ｈ ａ ｖ ｉ ｎ ｇ ｓ ｏ ｌ ｕｔ ｉ ｏ ｎ ｓ ，ｓ ｐ ｅ ｃ ｉ ａ ｌ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ｓ ，ｇ ｅ ｎ ｅ ｒ ａ ｌ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ａ ｎ ｄ ｔ ｈ ｅ ｒ ｅ ｌｅ ｆ ｘ ｉ ｖ ｅ ｇ ｅ ｎ ｅ ｒ ｌｉ ａ ｚ ｅ ｄ ｉ ｎ ｖ ｅ ｓｅ ｒ ｍａ ｔ ｉｘ ｒ ．Ａｔ ｔ ｈ ｅ ｓ ａ ｍｅ ｔ ｉ ｍｅ ，ｔ ｈ ｅ ｆ ａ ｓ ｔ ｌｇ ａ ｏ ｉｔ ｒ ｈ ｍ ｇ ｉ ｖ ｅ ｓ ｈｅ ｔ ｉ ｎ ｖ ｅ ｓｅ ｒ ｍａ ｔ ｒ ｉ ｘ ｎｄ ａ ｒ ｅ ｌ ｆ ｅ ｘ ｉ ｖ ｅ ｇ ｅ ｎ ｅ ｒ ａ ｌ ｉ ｚ ｅ ｄ ｉ ｎ ｖ ｅ ｒ ｓ ｅ ｍａ ｔ ｉｘ， ｒ ａ ｎ ｄ ｔ ｈ ｅ ｉ ｎ ｖ ｅ ｓｅ ｒ ｍａ ｔ ｉｘ ｒ ａ ｎ ｄ ｒ ｅ ｌ ｆ ｅ ｘ ｉ ｖ ｅ ｇ ｅ ｎ ｅ ｒ ａ ｌ ｉ ｚ ｅ ｄ ｉ ｎ ｖ ｅ ｒ ｓ ｅ ｍａ ｔ ｒ ｉ ｘ ｒｅ ａ Ｈ－ ｃ ｉ ｒ ｃ ｕ ｌ ａ ｎ ｔ ｍａ ｔ ｉｃ ｒ ｅ ｓ ． Ｋｅ ｙ ｗｏ ｒ ｄ ｓ：Ｈ－ ｃ ｉ ｒ ｃ ｕ ｌ ａ ｎ ｔ ｍａ ｔ ｉｘ；ｐ ｒ ｏ ｌ ｙ ｎ ｏ ｍｉ ｌ ａ ｆ ａ ｓ ｔ ｌｇ ａ ｏ ｉｔ ｒ ｈ ｍ ；ｕ ｎｉ ｑｕ ｅ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ；ｇ ｅ ｎ ｅ ｒ ｌ ａ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ；ｉ ｎ ｖ ｅ ｓｅ ｒ ｍａ ｔ ｉｘ ｒ
KCF中的循环矩阵

KCF中的循环矩阵

KCF 中的循环矩阵在学习KCF ⽬标跟踪算法时，会⽤到⼀个数学概念：循环矩阵，其对KCF 的速度提升起到了⾮常关键的作⽤，值得了解下。

1. 傅⾥叶矩阵(DFT Matrix)　在了解循环矩阵的定义前，需要先了解下离散傅⾥叶矩阵：2. 循环矩阵定义形状如下的矩阵X 称为循环矩阵，x 为循环矩阵X 的⽣成向量，为矩阵第⼀⾏, 其他⾏都是x 向右循环位移得到。

X =C (x )=x 1x 2x 3x 4x 4x 1x 2x 3x 3x 4x 1x 2x 2x 3x 4x 1通过x ⽣成X , 可以由排列矩阵和x 相乘，连续平移x 得到，⽰例代码如下：import numpy as npx = np.array([[1, 2, 3, 4]])P = np.array([[0, 0, 0, 1],[1, 0, 0, 0],[0, 1, 0, 0],[0, 0, 1, 0]])X = np.zeros((4, 4))X[0, :] = xfor i in range(1, 4):X[i, :] = np.dot(P, X[i-1, :]).T # 排列矩阵P 每作⽤⼀次x ，x 向右移动⼀位print(X)输出：[[1. 2. 3. 4.][4. 1. 2. 3.][3. 4. 1. 2.][2. 3. 4. 1.]][]3. 循环矩阵性质循环矩阵很多优秀的性质，其中最重要的⼏个性质为如下：1. 任意循环矩阵可以被傅⾥叶变换矩阵对⾓化⼀般⽤如下⽅式表达这⼀概念：X=C(x)=F⋅diag(ˆx)⋅F H其中X是⼀个循环矩阵，x是X的⽣成向量, ˆx（读作x hat）为原向量x的傅⾥叶变换；F是傅⾥叶变换矩阵，F H表⽰共轭转置: F H=(F∗)T。

换句话说，X 相似于对⾓阵，X的特征值是ˆx的元素。

另⼀⽅⾯，如果⼀个矩阵能够表⽰成两个傅⾥叶矩阵夹⼀个对⾓阵的乘积形式，则它是⼀个循环矩阵。

其⽣成向量是对⾓元素的傅⾥叶逆变换：F⋅diag(y)⋅F H=C(−1(y))，（−1(y)表⽰y的傅⾥叶逆变换）2. 循环矩阵乘向量等价于⽣成向量的逆序和该向量卷积数学表⽰如下：(Xy)=(C(x)y)=(¯x∗y)=∗(x)⊙(y)这⾥¯x表⽰x的逆序排列，∗表⽰卷积。

g_循环矩阵相乘的一种快速算法

g_循环矩阵相乘的一种快速算法

≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠
C=C （c 0 ，c 1 ，…，c n-1 ） =AB，c=（c 0 ，c 1 ，… ，c n-1 ） ， 则 有 c=Fn diag（Fn a）Fn b。
解 步骤 1 由 ki ≡4i（mod5） （i=0 ，4 ）， 得到： k 0 =0 ， k 1 =4 ， k2 =3，k4 =1 。 从而 a=（2 1 4 3 -1 ） 。
n-1 j T
n-1
Q g Q g Σa i R
1 2
ig2
i=0
Σb R =
j=0 j ig2
j
n-1 j
1
n-1
Q'g Σbj R Σai R =
· 证 不难验证 c=C （a0 ，an-1 ，an-2 ，...，a1 ） b， 由
-1 -1
T
例1
引理 4 得证。 引理 2 知 c=Fn diag（Fn a）Fn b， 引理 4 说明两个循环矩阵乘积只需要 3 个 DFT 即可。 2 定理 定理 若 A∈CMg ， B∈CMg ，则 C=AB∈CMg ，
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
T
T
T
T
0 7 -9 28 7 19 28 0 19 -9
19 -9 28 0 7 19 -9 28 0 =C 2 （0，7，19， - 9，28）。 7 19 -9 28
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0
7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
循环矩阵的性质及其应用

循环矩阵的性质及其应用

循环矩阵的性质及其应⽤\S 1循环矩阵的定义及多项式表⽰设\mathbb{K}为数域. 任取\mathbb{K}中n个数a_1,a_2,\cdots,a_n,下列矩阵称为\mathbb{K}上的n阶循环矩阵:A=\begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_n \\ a_n & a_1 & a_2 & \cdots & a_{n-1} \\ a_{n-1} & a_n & a_1 & \cdots & a_{n-2} \\ \vdots & \vdots & \vdots & & \vdots \\ a_2 & a_3 & a_4 & \cdots & a_1 \\ \end{pmatrix}.\quad(1)取a_2=1, a_1=a_3=\cdots=a_n=0, 则可得到如下基础循环矩阵:J=\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ 1 & 0 & 0 & \cdots & 0 \\ \end{pmatrix}.\quad(2)由复旦⾼代⽩⽪书的例 2.1 可知, J^k=\begin{pmatrix} 0 & I_{n-k} \\ I_k & 0 \\ \end{pmatrix}\,(1\leq k\leq n), 从⽽A=a_1I_n+a_2J+a_3J^2+\cdots+a_nJ^{n-1}.\quad(3)令g(x)=a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1}, 则g(x)是\mathbb{K}上次数不超过n-1的多项式, 使得A=g(J), 这就是循环矩阵关于基础循环矩阵的多项式表⽰.记C_n(\mathbb{K})为\mathbb{K}上所有n阶循环矩阵构成的集合, 容易验证: 在矩阵的加法和数乘下, C_n(\mathbb{K})是⼀个n维线性空间, 它的⼀组基为\{I_n,J,\cdots,J^{n-1}\}. 再任取循环矩阵B=h(J), 其中h(x)是\mathbb{K}上次数不超过n-1的多项式, 则利⽤多项式乘法和J^n=I_n可知AB=g(J)h(J)仍然是⼀个循环矩阵 (参考⾼代⽩⽪书的例 2.12). 因此, C_n(\mathbb{K})是\mathbb{K}上的n维交换代数, 同构于\mathbb{K}[x]/(x^n-1).\S 2循环矩阵的性质下⾯将依次研究循环矩阵的特征值、特征向量和可对⾓化等性质, 由此可得循环矩阵的⾏列式、秩和⾮异性等信息. 这些内容包含在⾼代⽩⽪书的例 2.52, 例 6.9, 例 6.32 和例 6.39 的推论中.容易计算出基础循环矩阵J的特征多项式|\lambda I_n-J|=\lambda^n-1, 从⽽J在复数域中有n个不同的特征值, 即n次单位根\omega_k=\cos\dfrac{2k\pi}{n}+i\sin\dfrac{2k\pi}{n}\,(0\leq k\leq n-1), 因此J在复数域上可对⾓化. 经计算可知, 特征值\omega_k的特征向量是\alpha_k=(1,\omega_k,\omega_k^2,\cdots,\omega_k^{n-1})'. 将这些特征向量按列分块拼成⼀个矩阵: P=\begin{pmatrix} 1 & 1 & 1 &\cdots & 1 \\ 1 & \omega_1 & \omega_2 & \cdots & \omega_{n-1} \\ 1 & \omega_1^2 & \omega_2^2 & \cdots & \omega_{n-1}^2 \\ \vdots &\vdots & \vdots & & \vdots \\ 1 & \omega_1^{n-1} & \omega_2^{n-1} & \cdots & \omega_{n-1}^{n-1} \\ \end{pmatrix},\quad(4)则由Vandermonde ⾏列式或特征值特征向量的性质可知, P是⾮异阵, 并且满⾜P^{-1}JP=\mathrm{diag}\{1,\omega_1,\omega_2,\cdots,\omega_{n-1}\},\quad(5)从⽽P^{-1}AP=P^{-1}g(J)P=g(P^{-1}JP)=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}.\quad(6)由 (6) 式可知循环矩阵A=g(J)具有如下基本性质:(P1) A的特征值为g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1}), 对应的特征向量是\alpha_0,\alpha_1,\alpha_2,\cdots,\alpha_{n-1};(P2) |A|=g(1)g(\omega_1)g(\omega_2)\cdots g(\omega_{n-1});(P3) 循环矩阵A可对⾓化;(P4) r(A)=\sharp\{0\leq k\leq n-1\mid g(\omega_k)\neq 0\};(P5) A⾮异当且仅当g(\omega_k)\neq 0\,(0\leq k\leq n-1), 也即当且仅当(\lambda^n-1,g(\lambda))=1.定理 1 n阶复循环矩阵全体C_n(\mathbb{C})与n阶复对⾓矩阵全体D_n(\mathbb{C})之间存在⼀个⾃然的代数同构\xi.证明n阶复对⾓矩阵全体在矩阵的加法、数乘和乘法下成为复数域上的代数. 我们通过 (6) 式来定义映射\xi, 即\xi: C_n(\mathbb{C})\toD_n(\mathbb{C})定义为\xi(A)=P^{-1}AP=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}. 容易验证\xi保持矩阵的加法、数乘和乘法, 从⽽是⼀个代数同态. 对任⼀\Lambda=\mathrm{diag}\{\lambda_0,\lambda_1,\cdots,\lambda_{n-1}\}, 利⽤ Lagrange 插值公式可知, 存在次数不超过n-1的复系数多项式h(\lambda), 使得h(\omega_k)=\lambda_k(0\leq k\leq n-1). 令B=h(J), 则\xi(B)=\Lambda, 即\xi是满射. ⼜\dim C_n(\mathbb{C})=\dim D_n(\mathbb{C})=n, 从⽽\xi是⼀个线性同构, 从⽽是代数同构. \Box推论 2 n阶复矩阵B可对⾓化的充要条件是B相似于某个循环矩阵.证明由定理 1 中的代数同构\xi是通过相似变换实现的即得结论. \Box推论 3 设A\in C_n(\mathbb{K}), 则A^*也是循环矩阵.证法 1 由 (6) 式可知P^*A^*(P^*)^{-1}=(P^{-1}AP)^*=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}^*仍为对⾓阵. 注意到P^*=|P|P^{-1}, 故上述等式可化为P^{-1}A^*P=(P^{-1}AP)^*=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}^*.因此由定理 1 可知, A^*=\xi^{-1}\bigg(\xi(A)^*\bigg)也是循环矩阵.证法 2 由⾼代⽩⽪书的例 6.62 可知, 存在多项式h(\lambda)\in\mathbb{K}[\lambda], 使得A^*=h(A). 设A=g(J), 则A^*=h(A)=h(g(J))仍为J的多项式, 从⽽是循环矩阵.证法 3 设A=(a_{ij})的代数余⼦式为A_{ij}\,(1\leq i,j\leq n), 要证A^*是循环矩阵, 根据定义只要证明: 对任意的1\leq i,j\leq n,A_{ij}=A_{i+1,j+1}成⽴即可, 其中若i+1>n或j+1>n, 则需要把i+1或j+1换成i+1-n或j+1-n. 证明A_{ij}=A_{i+1,j+1}只需要简单的⾏列式计算即可. ⽐如先把A_{ij}的最后⼀列经过n-2次相邻对换换⾄第⼀列, 再把得到⾏列式的最后⼀⾏经过n-2次相邻对换换⾄第⼀⾏, 最后就能得到A_{i+1,j+1}. 我们把验证的细节留给读者完成. \Box推论 4 若A\in C_n(\mathbb{K})是⾮异阵, 则A^{-1}也是循环矩阵.证法 1 由定理 1 可知, A^{-1}=\xi^{-1}\bigg(\xi(A)^{-1}\bigg)也是循环矩阵.证法 2 由 Cayley-Hamilton 定理可知, 存在多项式h(\lambda)\in\mathbb{K}[\lambda], 使得A^{-1}=h(A) (参考⾼代⽩⽪书的例 6.61). 设A=g(J), 则A^{-1}=h(A)=h(g(J))仍为J的多项式, 从⽽是循环矩阵.证法 3 设A=g(J), 则由A⾮异可知(\lambda^n-1,g(\lambda))=1. 由互素多项式的性质可知, 存在u(\lambda),v(\lambda)\in\mathbb{K}[\lambda], 使得(\lambda^n-1)u(\lambda)+g(\lambda)v(\lambda)=1. 令\lambda=J, 代⼊上式可得g(J)v(J)=I_n, 从⽽A^{-1}=v(J)也是循环矩阵.证法 4 由A^{-1}=\dfrac{1}{|A|}A^*以及推论 3 即得结论. \Box推论 5 \mathbb{K}上的n阶⾮异循环矩阵全体GC_n(\mathbb{K})在矩阵乘法下成为⼀个 Abel 群.推论 6 设A为n阶复循环矩阵, f(z)是收敛半径等于+\infty的复幂级数, 则f(A)也是循环矩阵.证法 1 注意到f(P^{-1}AP)=P^{-1}f(A)P, 从⽽f(A)=\xi^{-1}\bigg(f(\xi(A))\bigg)也是循环矩阵.证法 2 由可知, 存在多项式h(z), 使得f(A)=h(A)也是循环矩阵.证法 3 设f(z)=\sum\limits_{i=0}^\infty a_iz^i, f_p(z)=\sum\limits_{i=0}^p a_iz^i为f(z)的部分和多项式. 设A=a_1I_n+a_2J+a_3J^2+\cdots+a_nJ^{n-1}, 则f_p(A)=b^{(p)}_1I_n+b^{(p)}_2J+b^{(p)}_3J^2+\cdots+b^{(p)}_nJ^{n-1}. 由于矩阵序列\lim\limits_{p\to\infty}f_p(A)收敛到f(A), 故每个数列\lim\limits_{p\to\infty}b^{(p)}_i都收敛. 若设\lim\limits_{p\to\infty}b^{(p)}_i=b_i\,(1\leq i\leq n), 则f(A)=\lim\limits_{p\to\infty}f_p(A)=b_1I_n+b_2J+b_3J^2+\cdots+b_nJ^{n-1}仍为循环矩阵. \Box\S 3循环矩阵的应⽤下⾯我们给出循环矩阵的⼀个应⽤.命题 7 设有\mathbb{K}中n^2\,(n\geq 2)个不同的数, 则存在⼀个全排列, 记为a_1,\cdots,a_{n^2}, 使得\begin{vmatrix} a_1 & a_2 & \cdots & a_n \\ a_{n+1} & a_{n+2} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n^2-n+1} & a_{n^2-n+2} & \cdots & a_{n^2} \\\end{vmatrix}\neq 0.证明对n进⾏归纳. n=2时, 先取到a_1,a_2, 使得a_1+a_2\neq 0, 从⽽\begin{vmatrix} a_1 & a_2 \\ a_2 & a_1 \\ \end{vmatrix}=(a_1-a_2) (a_1+a_2)\neq 0, 于是B=\{(a_1,a_2),(a_2,a_1)\}是\mathbb{K}^2的⼀组基. 注意到(a_3,a_4)\neq 0, 故由基扩张定理, 必可从基B中选取⼀个基向量, 不妨设为(a_1,a_2), 使得\{(a_1,a_2),(a_3,a_4)\}成为\mathbb{K}^2的⼀组新基, 因此\begin{vmatrix} a_1 & a_2 \\ a_3 & a_4 \\\end{vmatrix}\neq 0. 设n-1时结论成⽴, 现证n的情形.证法 1 先取到a_1,a_2,\cdots,a_n, 使得a_1+a_2\omega_k+\cdots+a_n\omega_k^{n-1}\neq 0对0\leq k\leq n-1都成⽴. 这⼀定能做到, ⽐如先选定a_2,\cdots,a_n, 则不满⾜上述条件的a_1最多只有n个, 从⽽可取到满⾜上述条件的a_1. 由循环矩阵的性质可知, (1) 式中的循环矩阵A是⾮异阵, 特别地, A的n个⾏向量\{\beta_1,\beta_2,\cdots,\beta_n\}是\mathbb{K}^n的⼀组基. 由归纳假设, 可从剩下n^2-n个数中选出(n-1)^2个数的全排列, 使得\begin{vmatrix} a_{n+2} & \cdots & a_{2n} \\ \vdots & & \vdots \\ a_{n^2-n+2} & \cdots & a_{n^2} \\\end{vmatrix}\neq 0,后⾯随便选取a_{n+1},\cdots,a_{n^2-n+1}, 均可使n-1个⾏向量(a_{n+1},a_{n+2},\cdots,a_{2n}), \cdots, (a_{n^2-n+1},a_{n^2-n+2},\cdots,a_{n^2})线性⽆关 (参考复旦⾼代教材的习题 3.4.9). 因此由基扩张定理, 必可从基\{\beta_1,\beta_2,\cdots,\beta_n\}中选出⼀个基向量, 不妨设为\beta_1, 使得\{(a_1,a_2,\cdots,a_n), (a_{n+1},a_{n+2},\cdots,a_{2n}), \cdots, (a_{n^2-n+1},a_{n^2-n+2},\cdots,a_{n^2})\}构成\mathbb{K}^n的⼀组新基, 从⽽结论得证.证法 2 ⽤反证法, 设对n^2个数的所有全排列, 对应的⾏列式都等于零, 我们来推出⽭盾. 先取到a_1,a_2,\cdots,a_n, 使得a_1+a_2+\cdots+a_n\neq 0, 再由归纳假设, 不妨设取到的⾏列式中, a_1的代数余⼦式A_1\neq 0. 设其余元素a_i的代数余⼦式为A_i\,(2\leq i\leq n), 因此a_1A_1+a_2A_2+\cdots+a_nA_n=0. 在取到的⾏列式中, 对换第⼀⾏的a_1与a_i\,(2\leq i\leq n), 其余n^2-2个元素保持不变, 则有a_iA_1+\cdots+a_1A_i+\cdots+a_nA_n=0. 由此可得(a_1-a_i)(A_1-A_i)=0, 但a_1\neq a_i, 从⽽A_1=A_i\,(2\leq i\leq n). 最后,0=a_1A_1+a_2A_2+\cdots+a_nA_n=(a_1+a_2+\cdots+a_n)A_1\neq 0, ⽭盾. \Box注 1 命题 7 的证法 1 是构造性的, 利⽤这⼀证法可以给出满⾜条件的全排列的总个数的⼀个粗略估计. 命题 7 的证法 2 由复旦数学学院 16 级本科⽣朱民哲提供.注 2 本⽂的主要结论还可以推⼴到特征零的域或者特征p>0的域 (要求p\nmid n) 及其分裂域或代数闭包上. 另外, ⾼代⽩⽪书第⼆章的解答题 13 还给出了b-循环矩阵的推⼴. 有兴趣的读者可以⾃⾏学习和验证这些结论.参考⽂献[1] ⾼代教材: 姚慕⽣, 吴泉⽔, 谢启鸿编著, ⾼等代数学 (第三版), 复旦⼤学出版社, 2014.[2] ⾼代⽩⽪书: 姚慕⽣, 谢启鸿编著, 学习⽅法指导书: ⾼等代数 (第三版), 复旦⼤学出版社, 2015.Processing math: 0%。