Archived

This topic is now archived and is closed to further replies.

matrix maths A^n puzzling me, puzzle you?

This topic is 5575 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

is there an easy way, in a 3x3 matrix to do this: question 1 ) C=AxB^n other than the computationally slow: C=A x [BxBxBxB...] question 2 ) again for 3x3 matrices if D=B^n D and B are known. is there a good quick way to find n? ...... please 'elp. [edited by - kindfluffysteve on September 8, 2002 3:19:43 PM]

Share this post


Link to post
Share on other sites
You could check out "Nineteen dubious ways to compute the exponential of a matrix" by Moler and Charles van Loan in SIAM Review 20 801-836 (1978) .

As the title suggests it isn't an easy problem. In the special case where the matrix is diagonalisable you can work with the eigenvalues. ie if M = E-1*D*E where D is a diagonal matrix D = diag{d1, ..., dt} you can use Mn = E-1 Dn E, and Dn = diag{d1n, ..., dtn}

The same method would work for finding n in A = Bn.



[edited by - sQuid on September 8, 2002 11:28:19 PM]

Share this post


Link to post
Share on other sites
Matrix power(const Matrix &M, int n){
if(n==1)
return M;
if(n%2)
return M*power(M,n-1);
else
return power(M*M,n/2);
}

It can be implemented much more efficiently, but this should give you the right idea. In order to compute M^17, you do the following:
M * M = M^2
M^2 * M^2 = M^4
M^4 * M^4 = M^8
M^8 * M^8 = M^16
M * M^16 = M^17

If you google for "fast modular exponentiation algorithm", you will get a similar algorithm. The only difference is that they compute powers of modular numbers instead of matrices, but the exponentiation part is the same.

Share this post


Link to post
Share on other sites
thanks, that does give me an idea or two.

The reason i ask is to see if there is a way to approach for games rotation around an arbitary vector. as in an angular velocity vector.

I was daydreaming in a physics lecture and was awoken by a game relevent thing - u know how order of rotation is important in rotating a body. well if u only rotate by a tiny bit, it doesnt matter what order you rotate in.

so i figured maybe i can rotate a 3x3 alignment axis somewhat like this if V is rotation velocity vector.

rotateMatrix(AlignmentMatrix,Vx*dt,Vy*dt,Vz*dt);

well normally that wouldnt work very well cause dt might in a game be too big to keep it honest. But maybe if within the function i devided dt by 256. and then from an identity matrix did the exponential thingy Alvaro suggested:

M * M = M^2
M^2 * M^2 = M^4
M^4 * M^4 = M^8
M^8 * M^8 = M^16
... = M^256

then i might gain a fairly accurate rotation matrix that fairly accurately rotates around the axis V without using quarterions or some other approach.

just an idea, I was just seeing how computationally expensive the dt approach is.

Share this post


Link to post
Share on other sites
My memory is fuzzy right now, but if you can factor B such that C^-1*d*C=B then B^2=C^-1*d*C*C^-1*d*C=C^-1*d^2*C. I think that d is an eigen value for the matrix. Also some matrices have the property that A^n=A so if n is 2 then A^2m where m is any integer is A. I assume you are in your first linear algebra class so you should just work it out the hard way, recognize the pattern and use it. They will teach you the eigen value way latter as well as how to recognize when a matrix has the property that A^n=A and what that property is called.

Share this post


Link to post
Share on other sites
As I said me memory was fuzzy. If you have a matrix A and it is diagonizable then P^-1*A*P=D where D is a diagonal matrix and P is a matrix formed by the eigen vectors for the matrix. Now (p^-1*A*P)^n=P^-1*A^n*P=D^n which solved for A gives A^n=P^n*D^n*P^-1. The powers of a diagonal matrix are simple to find since you simply raise the non-zero entries to whatever power.

So given the matrix A=[[0,0,-2],[1,2,1],[1,0,3]] the eigen values are 1, 2, and 2 with the eigen vectors being [[0,1,0],[-sqrt(2)/2,0,sqrt(2)/2],[-sqrt(6)/3,sqrt(6)/6,sqrt(6)/6]]. If you calculate P^-1*A*P you get [[2,0,0],[0,2,0],[0,0,1]]. So A^5 would be P*D^5*P^-1 where D^5=[[2^5,0,0],[0,2^5,0],[0,0,1]] which gives [[-30,0,-62],[31,32,31],[31,0,63]] which is what you get if you calculate A^5 directly.

As I said if you are in a linear algebra class just wait until they get to better ways of doing it. If you are doing this on your own then get a linear algebra book, read the section on eigen values/vectors and then the section on diagonalization.

Share this post


Link to post
Share on other sites