A book which changed my view of linear algebra

Aside: To comment on my recent Gresham College lectures please go to this blog entry. My most recent Gresham College lecture was on Monday 15 April at 6pm at Barnards Inn Hall, near Chancery Lane tube station, central London.  I talked about proof, by human and by computer: all readers of this blog are very welcome.  The lectures can be viewed on the Gresham College website.

*****

(Just in case any of my students are reading this: just because I didn't use to much like linear algebra doesn't mean you won't!)

When I was an undergraduate I wasn't very excited about linear algebra.  It was worthy stuff, but it wasn't as attractive as group theory and combinatorics were.  Even when I was employed to write mathematical modelling software and relied heavily on matrix methods, I felt the applications of linear algebra were useful but not really very interesting.  Even when the founders of Google have made millions by exploiting the Power Method, I still found it hard to be wildly enthusiastic about this (very important) area of mathematics.

But I have just read a wonderful book which has changed my mind completely.  It's Jiri Matousek's Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra.

The book consists of (you've guessed it!) thirty-three chapters, generally of four to six pages, each describing an entertaining problem which can be solved by linear algebra.  The applications are staggering - this isn't boring applied mathematical modelling or billionaire-making search engines, but REAL mathematics - combinatorics, geometry, coding, probabilistic algorithms.

For example: we begin by finding the formula for Fibonacci numbers.  We show that there are no four points in the plane such that the difference between any pair is an odd integer.  We learn about turning ladders around in a finite field.  We have the wonderful matrix-tree theorem which counts the spanning trees of a graph. There is the wonderful account of the information that can be transmitted by a secret agent whose only means of communication is to choose the colour of umbrella he uses each day, to be photographed by a satellite which can't tell the colours apart.   And my favourite - how do you tell whether a given binary operation on n objects is associative?  It appears you have to test n cubed cases.  Even if you only want a probabilistic answer, sampling doesn't appear to help us much: if the operation has one non-associative triple, you have to sample half the triples to have an even chance of detecting the offending triple.  But no - there is an ingenious algorithm which does very much better.

The amazing thing for me is that we are using linear algebra in all these diverse areas of pure mathematics where its relevance seems quite unexpected.  This is a sensational book!