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.

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:

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.