Matrix logarithms

PhantomBeaker

Hi all,

I'm puzzling out a little problem that I'm working with, and while I remember a lot of stuff about matrices and the like from college, a lot of it's slipped away, and also I think I'm looking at some stuff I didn't study in college.

What I'm looking at is: I have a square transformation matrix, T. T is real and invertable. Now, I'm facing a situation where T^n = A. Thing is, I'm trying to figure out what n is.

(That is, I know that if I take a vector, v, and pass it through T n times (each time using the output of vT as my new v), there is an equivalent matrix A that I might as well have used)

So, using a bit of guesswork, what I *think* I need is to learn about Matrix Logarithms, but when I search for pages in that area, all of them are concerned with natural logarithms (as in, to the base e), which I don't think I'm looking for.

Basically, I need to figure out how many times I've applied this matrix to itself to get the result I have. And I'm looking to solve this for the general case for my matrix.

The best result is if anyone has any links that are pitched at folks who know something of matrices, but are rusty on things like getting eigenvectors or a diagonalisation matrix (I remember realising that I wasn't on enough drugs when I was studying that particular bit in college)... and are very rusty on what they mean. Basically, a site pitched at those who don't read/write/speak algebra as a first language, but can follow what's going on if someone takes time to explain it.

And... yes... the thought has crossed my mind that I'm probably way out of my league here

Aoife

Fremen

Could you clarify what exactly the nature of the problem is?
Is it the case that you're given T and A, and you *know* A is some fixed power of T?
Is n assumed to be an integer? If not, you might need to learn about matrix exponentials (I've never even heard of matrix logs, but I suppose it makes sense that if you can exponentiate, there is an inverse operation).

If the problem is as I've described above, there are two ways to go: You could do it the naive way and just keep multiplying T by itself until you reach A, or you could take determinants of both sides.
Since Det(T)Det(T) = Det(T^2), the determniant of your A will be some power of the determinant of your T, and this is the n you're looking for.

If you want to check that A is a power of T without knowing it a priori, the problem is harder, and I'd need to think about it a bit more. But I'm going drinking now, so let's call it a day.

PhantomBeaker

Yeah, I know A and I know T, and n is an integer. I also know that T^n WILL eventually resolve to A (I can't prove it yet, but I know it will).

This is based on a real problem, so it means that I have most of the factors, I just really want to find a shortcut to the problem. I happened to draw up the transformation matrix for the problem, to see if I could make any sense of the behaviour. The big problem is, I'm trying to do this for transformations on vectors of arbitrary length, so I can't brute force it. (Plus that's what the program I've written does anyway but the algorithmic complexity is dire (somewhere in the region of O(|v|^3), where v is the vector I'm transforming), so I wanna see if I can do anything mathematically to see if I can find any shortcuts)

Hmmm, that determinant trick would be really handy were it not for the fact that all the determinants involved tend to be 1 or -1. (T has one entry per row/column, with that entry being 1) Actually, that trick might be more handy than I originally though, I might actually be able to use that somewhat, but approaching my problem from a different way.

See! This is the basic stuff I've forgotten, thank you! And sorry if there isn't a completely coherent train of thought in this post right now, I'm hitting Friday Brain-mush time.

Enjoy drinking,
Aoife

Fremen

T has one entry per row/column, with that entry being 1

Hm, what'd you mean by that? if T is an n*n matrix, T only has n nonzero entries?
There are bags of computational tricks you can use for sparse matrices which don't otherwise apply. So this is a computer science problem where you're trying to optimise performance then?

ZorbaTehZ

Can you use the fact that an nxn matrix with n eigenvectors is similiar to some diagonal matrix? Then use the fact that a diagonal matrix raised to a power is easy to determine. It might be easier if you just stated what A is.

rjt

Let me make sure I understand the problem - you have two matrices A and T. T is of size k, and has exactly k entries - one in each row and column (a so called permutation matrix). You believe that T^n is A for some n, and want a general way to find n - for arbitrary k. Is this about right?

I think a good way to look at this is to forget we're dealing with matrices at all. A matrix of the form you've described is equivalent to a permutation of k elements. As an example:

0 0 1
1 0 0
0 1 0

is equivalent to the permutation

1 2 3
3 1 2
(the permutation where 1 goes to 3, 2 goes to 1 and 3 goes to 2).

They're equivalent in the sense that if you square the matrix, and then convert it to a permutation you get the same result as converting to a permutation and then squaring that. How do we convert from a matrix to a permutation? Firstly, we write out 1,2,3 in a row as above. Then underneath the 1 we write the position of the '1' in the first row of the matrix, under the 2 we write the position of the '1' in the second row and so on.

Anyway, I'll try to get to the point: we can look at T as a permutation. We can do the same for A (any power of a permutation matrix is a permutation matrix, so A must be a permutation matrix too). So we have two permutations of k elements. Say they are:

T:
1 2 3 4
a b c d

A:
1 2 3 4
e f g h

One way to find the power is the following: firstly look at what happens to 1 every time we apply T. T(1) = a. T^2 (1) = T(T(1)) = T(a) = something else... We keep applying T until we get e. Say it takes x1 iterations, so T^(x1) (1) = e. Now we do one more thing - we keep applying T until we get 1 again, and say this takes y1 iterations (so T^(y1) (1) = 1). So we now have a pair (x1,y1).

Now the important part - what does (x1,y1) tell us about n? We know T^(n) (1) = e. So n could be x1. Say it isn't. What's the next biggest value n can be? In fact it's y1+x1. T^(y1+x1) (1) = T^(x1)[T^(y1) (1)] = T^(x1) (1) = e. The next one after this is 2*y1+x1, then 3*y1+x1 and so on. So n = m1*x1 + y1, where m1=0,1,2,... Which is to say, n = y1 mod x1.

We then do the same for 2: how many times do we have to apply T to 2 in order to get f? Call this x2. We keep applying T until we get 2 - we call this y2. So now we have another pair (x2,y2). And, like before, we know n = y2 mod x2.

We keep doing this. We have to do it k times in total, and each one takes at most k applications of T. So the above is O(k^2). We can then solve for n using the Chinese Remainder Theorem.


I think the above works - haven't tested it though! It can also be sped up a good bit - fairly sure the O(k^2) part can be easily made O(k) by keeping track of things cleverly.

equivariant

I think rjt has nailed it. The point here is that matrices that have only one 1 per row/column, with all other entries being zero are a *very* special class of matrices. So really (as rjt pointed out), this is not a problem in matrix theory, but is a problem about permutations.

PhantomBeaker

Funnily, enough, I was trying to turn a permutation problem of arbitrary length into a matrix problem. But thanks, I'll chew on that.

Fremen

So really this is a problem about the Symmetric group.
There's some technical stuff in the article. I'd advise you to stop reading at section 6 (properties) and skip the introduction, otherwise you'll just get bogged down in abstract nonsense.

Might give you a starting point though.