Number Theory: Matrix Exponential

  • #1

Homework Statement



If I have a matrix M, say
30 5
20 16
How do I calculate M[tex]^{1870}[/tex] mod 101 using Euler's Theorem.


Homework Equations


I have so far worked out M [tex]^{2}[/tex] mod 101 to be

91 28
11 53

and thought I could use this as 2x935=1870



The Attempt at a Solution



I can only find Euler's theorem with respect to numbers, rather than matrices. Can anybody point me in the right direction?

Thanks
 

Answers and Replies

  • #2
22,129
3,298
Have you tried diagonalizing the matrix? This makes it easier to calculate exponents...
 
  • #3
is that just finding the inverse?
 
  • #4
22,129
3,298
No... Did you ever take a linear algebra course?? It's impossible that they didn't spoke of diagonalization in that course...
 
  • #5
Okay, after researching this diagonalising I have come to the conclusion that my matrix cannot be diagonalised because all the roots of its characteristic equation are not real.

is this correct?
or could you point me in the right direction if it is not. thank you
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Okay, after researching this diagonalising I have come to the conclusion that my matrix cannot be diagonalised because all the roots of its characteristic equation are not real.

is this correct?
or could you point me in the right direction if it is not. thank you
There are two issues with your comment:

The fact a matrix cannot be diagonalized over the reals does not imply that it cannot be diagonalized over the complex numbers -- even if the answer will eventually be real, it is often more convenient to do your calculations with complex numbers.


You are not doing linear algebra over the reals or complexes -- you are doing linear algebra over the field of 101 elements (or its extensions).




While it's worth learning the above, I suspect 1870 is small enough that you're probably better off just calculating it directly with a standard square-and-multiply method of doing exponentiation.
 
  • #7
22,129
3,298
There are two issues with your comment:

The fact a matrix cannot be diagonalized over the reals does not imply that it cannot be diagonalized over the complex numbers -- even if the answer will eventually be real, it is often more convenient to do your calculations with complex numbers.


You are not doing linear algebra over the reals or complexes -- you are doing linear algebra over the field of 101 elements (or its extensions).




While it's worth learning the above, I suspect 1870 is small enough that you're probably better off just calculating it directly with a standard square-and-multiply method of doing exponentiation.

You are right Hurkyl, but I've checked, and the matrix is not diagonaizable over [tex]\mathbb{F}_{101}[/tex]. Since the characteristic polynomial is irreducible. So you would have to go to a field extension of [tex]\mathbb{F}_{101}[/tex], and I hardly think this is what the point of the exercise is...

But, the matrix IS diagonizable over the real numbers. If you calculate the eigenvalues over [tex]\mathbb{R}[/tex], then I obtain 2 different eigenvalues. So I guess that the best way to proceed is to diagonalize this matrix over the reals, do the calculations there. And only then reduce everything to [tex]\mathbb{F}_{101}[/tex].
 
  • #8
Dick
Science Advisor
Homework Helper
26,263
619
You are right Hurkyl, but I've checked, and the matrix is not diagonaizable over [tex]\mathbb{F}_{101}[/tex]. Since the characteristic polynomial is irreducible. So you would have to go to a field extension of [tex]\mathbb{F}_{101}[/tex], and I hardly think this is what the point of the exercise is...

But, the matrix IS diagonizable over the real numbers. If you calculate the eigenvalues over [tex]\mathbb{R}[/tex], then I obtain 2 different eigenvalues. So I guess that the best way to proceed is to diagonalize this matrix over the reals, do the calculations there. And only then reduce everything to [tex]\mathbb{F}_{101}[/tex].

I'm with Hurkyl. I think it's going to be lot easier to just bootstrap your way up to M^1870. If you know M^2 then you can get M^4, M^8,... I looked at this a while and I don't see any shortcuts either. Diagonalization is, like you said, impossible in Z_101 and a pain in C. You could also factorize 1870=2*5*11*17, but I don't think that simplifies it much either. Makes me wonder what the point of the exercise really is.
 
  • #9
22,129
3,298
I'm with Hurkyl. I think it's going to be lot easier to just bootstrap your way up to M^1870. If you know M^2 then you can get M^4, M^8,... I looked at this a while and I don't see any shortcuts either. Diagonalization is, like you said, impossible in Z_101 and a pain in C. You could also factorize 1870=2*5*11*17, but I don't think that simplifies it much either. Makes me wonder what the point of the exercise really is.

Yes, I agree with you two on this. Squaring your way up to M^1870 is much easier. But then again, you won't be using Euler's theorem this way... I to am wondering what the point is and what they want you to do here...
 
  • #10
thank you everybody for your replies - much appreciated.

yes i began by just squaring my way up to 1870 using the primes however i dont' really see how this uses Euler's theorem?

I could square my way up easily if it was just a number, but I have never done it with a matrix and think it will be extremely long-winded to work out the matrix to the power of 17?

Thanks again
 
  • #11
22,129
3,298
thank you everybody for your replies - much appreciated.

yes i began by just squaring my way up to 1870 using the primes however i dont' really see how this uses Euler's theorem?

I could square my way up easily if it was just a number, but I have never done it with a matrix and think it will be extremely long-winded to work out the matrix to the power of 17?

Thanks again

To calculate the matrix to the power of 17, do:
M -> M2 -> M4 -> M8 -> M16 -> M17
 
  • #12
thanks again.
when multiplying matrices to say get M17 what order would i do the matrices in?

For example does

M17 = M x (M16)

or

M17 = (M16) x M
 
  • #13
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
So I guess that the best way to proceed is to diagonalize this matrix over the reals, do the calculations there. And only then reduce everything to [tex]\mathbb{F}_{101}[/tex].
Ah! Silly me -- it hadn't crossed my mind to compute the 1870-th power of an integer lift of M by diagonalizing over the reals (or complexes as appropriate), then reducing modulo 101.

Alas, that matrix is going to have very, very large components.


yes i began by just squaring my way up to 1870 using the primes however i dont' really see how this uses Euler's theorem?
Alas, I can't see how Euler's theorem could possibly apply to this problem, except in the special case that the matrix diagonalizes over F101.

If you know your finite fields, you could show that if M is a 2x2 matrix over F101 whose characteristic polynomial is irreducible, then M10200 is the identity matrix, but that's not particularly useful for this problem.
(key proof idea -- the matrix must be diagonalizable over F1012)


M17 = M x (M16)

or

M17 = (M16) x M
Matrix multiplication is associative, so it doesn't matter where you put the parentheses in the expression
MMMMMMMMMMMMMMMMM (this is a product of 17 M's)​
so both of your methods of computing M17 give the same value.
 

Related Threads on Number Theory: Matrix Exponential

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
3
Views
652
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
15
Views
5K
Top