方阵高次幂计算的几种典型方法

摘 要：方阵的幂运算是矩阵乘法的特殊情形，在图论中有着极为广泛的应用。在总结归纳方阵高次幂常见六种计算方法的基础上，着重分析了第六种算法：特征多项式法。用此方法计算m阶方阵A的n次幂时，至多只需计算A的min｛m-1，n｝次幂，相对于前五种算法，此算法应用范围最广。

关键词：方阵高次幂；解题基本思路；六种解法一、数学归纳法

例1．设A=1 0?姿 1，求A2，A3，A4，…，An。

解题基本思路：依次计算A2，A3，A4，根据A2，A3，A4的结果，猜想An，然后用数学归纳法证明即可。

说明：运用此方法一般都是先计算A2，A3，A4，并根据A2，A3，A4的计算结果进行猜想，而后对猜想用数学归纳法加以证明。但并不是所有矩阵的幂的元素跟幂指数都有较明显的关系，故此方法有一定的局限性。

二、利用二项展开公式

例2.设A=?姿 1 00 ?姿 10 0 ?姿，求An。

解：A=?姿 0 00 ?姿 00 0 ?姿+0 1 00 0 10 0 0=?姿E+H，其中H=0 1 00 0 10 0 0。注意到H2=0 1 00 0 00 0 0，H3=0，且（?姿E）H=H（?姿E），故二项展开公式成立，即有An=（?姿E+H）n=（?姿E）n+n（?姿E）n-1H+■（?姿E）n-2H2。

=?姿n 0 00 ?姿n 00 0 ?姿n+0 n?姿n-1 00 0 n?姿n-10 00+0 0 ■?姿n-20 000 00

=?姿n n?姿n-1 ■?姿n-20 ?姿n n?姿n-10 0?姿n 。

说明：该方法首先要把矩阵A写成两个矩阵B、C的和，并要求这两个矩阵满足（1）矩阵B，C可交换；（2）其中一个矩阵的较低次幂的结果为特殊矩阵，如：零矩阵，数量矩阵。故此方法具有很强的技巧性，适用范围有限。

三、利用矩阵乘法结合律

例3．设A=1■■2 1 ■3 ■ 1，求An。

解：取?琢=（1，2，3），?茁=（1，■，■），则有A=?琢T?茁，而?茁?琢T=（1，■，■）123=3。

利用矩阵乘法结合律：

An=（?琢T?茁）（?琢T?茁）…（?琢T?茁）（?琢T?茁）=?琢T（?茁?琢T）…（?茁?琢T）?茁=?琢T·3…3·?茁= 3n-1?琢T?茁=3n-1A=3n-1 ■×3n-1 3n-22×3n-1 3n-1 2×3n-23n ■×3n3n-1。

四、利用分块对角阵求方幂

例4.已知A=2 4 0 01 2 0 00 0 2 40 0 0 2，求An。

解：A是分块对角阵，A=B 00 C，其中B=2 41 2，C=2 40 2，

则An=Bn 00 Cn，利用方法三，得：Bn=2·4n-1 4n4n-1 2·4n-1。

利用方法二得：Cn=2n 4n·2n-10 2n，

故An=2·4n-1 4n004n-1 2·4n-1 00002n4n·2n-10002n 。

五、利用相似对角化

例5．设A=1 4 20 -3 40 4 3，求An。

解：详见［2］。说明：此方法只能用于可对角化的方阵的幂运算。

六、特征多项式法

例6．设A=3 -2-2 3，求?渍（A）=A10-5A9。

解：计算A的特征多项式f（?姿）=A-?姿E=（?姿-1）（?姿-5），设

?渍（?姿）=?姿10-5?姿9=f（?姿）g（?姿）+h（?姿），这里g（?姿），h（?姿）分别表示?渍（?姿）除以f（?姿）所得的商式和余式，h（?姿）的次数小于f（?姿）的次数，故可设h（?姿）=a1?姿+a0，有：?姿10-5?姿9=（?姿-1）（?姿-5）g（?姿）+a1?姿+a0，令?姿=1，得：a1+a0=-4，令?姿=5，得：5a1+a0=0，所以：a1=1，a0=-5。故：?渍（?姿）=f（?姿）g（?姿）+?姿-5，所以?渍（A）=A10-5A9=f（A）g（A）+h（A）=A-5E（因为f（A）=0）

?渍（A）=A10-5A9=A-5E=-2 -2-2 -2。

说明：

（1）方法六较之于方法五要简单实用，不仅计算量少，而且适用范围广，方法五仅局限于可对角化的矩阵。

（2）方法六的理论依据有二：其一是：若f（?姿）是A的特征多项式，则f（A）=0；其二是：多项式除法所得余式的次数小于除式的次数，在这里即小于特征多项式的次数。

（3）用方法六计算m阶方阵A的n次幂时，至多只需计算A 的minm-1，n次幂。

（4）方法六中余式h（?姿）是一个次数不大于minm-1，n的多项式。

参考文献：

［1］檀凤琴，何自强.离散数学.北京：科学出版社，2000.

［2］同济大学应用数学系.线性代数.北京：高等教育出版社，2003.

项目资助：北京高等学校青年英才计划（YETP1471）。

（作者单位 北京印刷学院基础部）

?誗编辑 段丽君