A procedure for finding the k-th power of a matrix 

Branko Malesevic
Faculty of Electrical Engineering
 University of Belgrade, Serbia
malesh@EUnet.yu 

Ivana Jovovic
PhD student, Faculty of Mathematics
University of Belgrade, Serbia
ivana121@EUnet.yu 

Introduction 

This worksheet demonstrates the use of Maple in Linear Algebra. 

We give a new procedure (PowerMatrix) in Maple for finding the k-th power of n-by-n square matrix A, in a symbolic form, for any positive integer k, k>=n. The algorithm is based on an application of Cayley-Hamilton theorem. We used the fact that the entries of the matrix A^k satisfy the same recurrence relation which is determined by the characteristic polynomial of the matrix A (see [1]). The order of these recurrences is n-d, where d is the lowest degree of the characteristic polynomial of the matrix A.  

For non-singular matrices the procedure can be extended for k not only a positive integer. 

Initialization 

>	restart: with(LinearAlgebra):

 

Procedure Definition 

PowerMatrix 

Input data are a square matrix A and a parameter k. Elements of the matrix A can be numbers and/or parameters. The parameter k can take numeric value or be a symbol. The output data is the k-th power of the matrix. The procedure PowerMatrix is as powerful as the procedure rsolve. 

 

>

PowerMatrix:=proc(A::Matrix,k) local i,j,m,r,q,n,d,f,P,F,C; P:=x->CharacteristicPolynomial(A,x); n:=degree(P(x),x); d:=ldegree(P(x),x); F:=(i,j)->rsolve({sum(coeff(P(x),x,m)*f(m+q),m=0..n)=0,seq(f(r)=(A^r)[i,j],r=d+1..n)},f); C:=q->Matrix(n,n,F); if type(k,integer) then return(simplify(A^k)) elif (Determinant(A)=0 and not type(k,numeric)) then printf("The %a-th power of the matrix for %a>=%d:",k,k,n) elif (Determinant(A)=0 and type(k,numeric)) then return(simplify(A^k)) fi; return(simplify(subs(q=k,C(q)))); end:

 

Examples 

Example 1. 

 

>	A:=Matrix([[4,-2,2],[-5,7,-5],[-6,6,-4]]);

 

(3.1.1)

 

>	PowerMatrix(A,k);

 

(3.1.2)

 

>	Determinant(A);

 

(3.1.3)

 

>	B:=A^(-1);

 

(3.1.4)

 

>	PowerMatrix(B,k);

 

(3.1.5)

 

Example 2. 

 

>	A:=Matrix([[1-p,p],[p,1-p]]);

 

(3.2.1)

 

>	PowerMatrix(A,k);

 

(3.2.2)

 

The example is from [4], page 272, exercise 19. 

Example 3. 

 

>	A:=Matrix([[a,b,c],[d,e,f],[g,h,i]]);

 

(3.3.1)

 

>	PowerMatrix(A,k)[1,1];

 

(3.3.2)

 

 

       #  Warning! In this example MatrixPower and MatrixFunction procedures cannot be done in real-time. 

 

>	# MatrixPower(A,k)[1,1];

 

>	# MatrixFunction(A,v^k,v)[1,1];

 

 

Example 4. 

 

>	A:=Matrix([[0,0,1,0,1],[1,0,0,0,1],[0,0,0,1,1],[0,1,0,0,1],[1,1,1,1,0]]);

 

(3.4.1)

 

>	PowerMatrix(A,k)[1,5];

 

(3.4.2)

 

Replace ':' with ';' and see result! 

 

>	MatrixPower(A,m)[1,5]:

 

>	simplify(MatrixPower(A,m)[1,5]):

 

>	assume(m::integer); simplify(MatrixPower(A,m)[1,5]):

 

 

The example is from [3], page 101. 

 

Example 5. and Example 6. 

 

Pay attention what happens for singular matrices. 

 

Example 5.  

 

>	A:=Matrix([[0,2,1,3],[0,0,-2,4],[0,0,0,5],[0,0,0,0]]);

 

(3.5.1.1)

 

>	PowerMatrix(A,2);

 

(3.5.1.2)

 

>	PowerMatrix(A,3);

 

(3.5.1.3)

 

>	PowerMatrix(A,k);

 

The k-th power of the matrix for k>=4:

(3.5.1.4)

 

(3.5.1.4)

 

 

>	MatrixPower(A,k);

 

Error, (in LinearAlgebra:-LA_Main:-MatrixPower) power k is not defined for this Matrix

 

>	MatrixFunction(A,v^k,v);

 

Error, (in LinearAlgebra:-LA_Main:-MatrixFunction) Matrix function v^k is not defined for this Matrix

 

The example is from [2], page 151, exercise 23. 

Example 6. 

 

>	A:=Matrix([[1,1,1,0],[1,1,1,-1],[0,0,-1,1],[0,0,1,-1]]);

 

(3.5.2.1)

 

>	PowerMatrix(A,k);

 

The k-th power of the matrix for k>=4:

(3.5.2.2)

 

(3.5.2.2)

 

>	MatrixPower(A,k);

 

Error, (in LinearAlgebra:-LA_Main:-MatrixPower) power k is not defined for this Matrix

 

>	MatrixFunction(A,v^k,v);

 

Error, (in LinearAlgebra:-LA_Main:-MatrixFunction) Matrix function v^k is not defined for this Matrix

 

References 

[1] Branko Malesevic. Some combinatorial aspects of the composition of a set of functions. NSJOM., 2006 (36), 3-9.
http://www.im.ns.ac.yu/NSJOM/Papers/36_1/NSJOM_36_1_003_009.pdf  or  http://arxiv.org/abs/math.CO/0409287 .
[2] John B. Johnston, G. Baley Price, Fred S. Van Vleck. Linear Equations and Matrices. Addison-Wesley, 1966.  

[3] Carl D. Meyer. Matrix Analysis and Applied Linear Algebra . SIAM, 2001. 

[4] Robert Messer. Linear Algebra Gateway to Mathematics. New York: Harper-Collins College Publisher, 1993. 

Conclusions 

This procedure has an educational character. It is an interesting demonstration for finding the k-th power of a matrix in a symbolic form. Sometimes, it gives solutions in the better form than the existing procedure MatrixPower (see example 4.). See also example 5. and example 6., where we consider singular matrices. In these cases the procedure MatrixPower does not give a solution. The procedure PowerMatrix calculates the k-th power of any singular matrix. In some examples it is possible to get a solution in the better form with using the procedure allvalues (see example 3.). 

Acknowledgment: Research partially supported by MNTRS, Serbia, Grant No. 144020. 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.