A few of you have asked me recently about the topic of my PhD thesis. I am always happy to oblige!
The title was “On the Complexity of Matrix Multiplication” and it was concerned with properties of objects called Matrices (singular: matrix).
A matrix is an array of numbers, with a number of rows and columns. Below is an example of a 2 x 3 matrix:
Predictably, a matrix is called square if the number of rows is the same as the number of columns.
Matrices are pretty important objects: they are used in all manner of disciplines such as quantum physics (states of particles are defined by a matrix), computing, probability, statistics, relativity and predicting the outcomes of games of Snakes and Ladders.
One important property is that they can be multiplied together. Multiplying two geometric transformations will result in the two things being done at the same time, fot example a reflection and a rotation.
Unfortunately for large matrices, the standard method for doing this is rather cumbersome, so a quicker method is necessary.
The measurement for the amount of time it takes computer to do a multiplication is called the exponent and for the standard method this has value 3, and lower is better. Due to the number of entries in a matrix, the lowest value it can be is 2.
Reducing it became a possibility when Volker Strassen found that you could turn the matrices into squares and chop them up into other squares- he showed that you could reduce the exponent to 2.81- and further advances were made until 1990 when the exponent stood at 2.375.
That’s where I came in- what I did was utilise the previous method and essentially do it again to show that you could make a shortcut and do the necessary calculations even quicker.
That didn’t work- but I had a hunch that it might work if I did it again- and it did, yielding the following result- a minor improvement but, at the time, a record.
It has since been beaten by Virginia Williams at Stanford University using similar methods, but not before a delayed write-up (I wasn’t well) meant that the result wasn’t made public until it had been Williams beat it (she only found my result by chance) resulting in one professor writing a long diatribe against me (which he subsequently withdrew when he found out the cause of the delay) and comments such as the below appearing in his blog:
The above comment is now immortalised in a pub quiz team name.
Alas, my algorithm is not useful at present because of technology limitations, but I am hopeful it can be used some time. But really, when has practical use ever concerned a mathematician? I was only ever in it for the pub quiz team name.