15/10/2012 @19:04:02 ^20:34:33

Linear matrices

The question (scroll down to August 2012) states:

            n
      (-3 8)  = (-4n+1   8n)
      (-2 5)    (  -2n 4n+1)

    for all natural numbers n.

    Can you find other matrices, M, such that all the elements of M^n
    are linear functions of n (where n is a natural number) ?

So you want to find M when M^n = C+nD for matrices C and D which do not depend on n.

First thing I noticed, the example you are given has determinant 1. But trying a random matrix with determinant 1 didn't work.

The next thing I noticed, was the example given is the identity matrix [(1,0)|(0,1)] (first row, second row) plus another matrix [(-4,8)|(-2,4)] whose determinant is clearly 0 (you don't even need to calculate it - one row is just a scalar multiple of the other). However making up a random matrix with determinant 0 and adding the identity to it did not prove fruitful (although it had better results than the previous point)

Finally I realised this. Make up a matrix A which satisfies A^2 = 0. Then let M = (I+A).

You can then binomially expand M^n, giving I + nA + n^2/2.A^2 + ... but A^2 and higher powers of A are all zero so they vanish and you're left with just I+nA, which is what you want. Note that in general binomial expansion does not work on matrices because multiplying them does not commute, but it does in this case since the identity commutes with anything.

How to find a matrix whose square is the zero matrix

Well at this point I resorted to good old calculation

         2
    (a b)  = ( a^2+bc  b(a+d) )  =  (0 0)
    (c d)    ( c(a+d)  bc+d^2 )     (0 0)

So all of a^2+bc , b(a+d), c(a+d) and bc+d^2 have to equal zero. The issue then splits up into several two cases.

• If b is zero then a^2 and d^2 must both be zero, then c can be anything. Similarly if c is zero, a=d=0 and b can be anything.
• Otherwise suppose both b and c are nonzero. Then a+d must be zero, that is d=-a. Also, a^2=-bc, so c=-a^2/b. So we can choose a and b freely, and (c,d) = -(a/b)(a,b). Or, obviously, you can choose the other row, or one of the columns, and it fixes the first row, or the other column.
• One other restriction if a,b,c,d must be integers: the absolute values of b and c must be cofactors of a^2. (That is a^2 has to be divisible by both b and c. The previous point asserts that when you divide a^2 by one you have to get the other).

So let's choose a=2 and b=1, then c=-4 and d=-2, so we have

                                        n
   A = (2   1)    M = I+A = (3   1)    M  = (1+2n    n)
       (-4 -2),             (-4 -1),        ( -4n 1-2n)

Not Shown

This took a couple of weeks to think my way through. I haven't done any maths in years. Not shown:

• the large amounts of paper covered in long formulas involving a, b, c, and d, where I tried to work out an answer by multiplying out the matrices manually and looking for patterns (this was stupid)
• various idle moments when I suddenly remembered something from years ago - I was stuck on idempotency for a long time - A^2=A - I couldn't remember the word for A^2=0, I eventually remembered nilpotency. Looking at some matrix like [(1,2)|(0,1)] and suddenly going "oh yeah that's Jordan Normal Form, ahaha I haven't heard that phrase in years" etcetc.

Most importantly, the fact that the very first thing I did was write a program to brute force a large number of examples other than the one given in the question. One example is not enough to spot a pattern from, although looking at it now it's obvious (it is clearly of the form I+nA, with A=[(-4,8)|(-2,4)]). Whether this counts as cheating is an open question.