Number Theory: Matrix Exponential

[Dollydaggerxo]

Homework Statement

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

Homework Equations

I have so far worked out M ^{2} 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

 

[micromass]

Have you tried diagonalizing the matrix? This makes it easier to calculate exponents...

 

[Dollydaggerxo]

is that just finding the inverse?

 

[micromass]

No... Did you ever take a linear algebra course?? It's impossible that they didn't spoke of diagonalization in that course...

 

[Dollydaggerxo]

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

 

[Hurkyl]

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.

 

[micromass]

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 \mathbb{F}_{101}. Since the characteristic polynomial is irreducible. So you would have to go to a field extension of \mathbb{F}_{101}, 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 \mathbb{R}, 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 \mathbb{F}_{101}.

 

[Dick]

You are right Hurkyl, but I've checked, and the matrix is not diagonaizable over \mathbb{F}_{101}. Since the characteristic polynomial is irreducible. So you would have to go to a field extension of \mathbb{F}_{101}, 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 \mathbb{R}, 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 \mathbb{F}_{101}.

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.

 

[micromass]

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...

 

[Dollydaggerxo]

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

 

[micromass]

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 -> M² -> M⁴ -> M⁸ -> M¹⁶ -> M¹⁷

 

[Dollydaggerxo]

thanks again.
when multiplying matrices to say get M¹⁷ what order would i do the matrices in?

For example does

M¹⁷ = M x (M¹⁶)

or

M¹⁷ = (M¹⁶) x M

 

[Hurkyl]

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 \mathbb{F}_{101}.

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 F₁₀₁.

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

M¹⁷ = M x (M¹⁶)

or

M¹⁷ = (M¹⁶) 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 M¹⁷ give the same value.