You are here

Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra

Jiří Matoušek
American Mathematical Society
Publication Date: 
Number of Pages: 
Student Mathematical Library 53
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Fernando Q. Gouvêa
, on

We always tell our students that there are many applications of linear algebra, but showing them one is sometimes difficult. Some applications take too much setting up, some require too much knowledge of other material, many are just too difficult and abstract. Finding examples of “linear algebra in action” that are both accessible and convincing is difficult. Thirty-three Miniatures is an attempt to present some usable examples.

The subtitle says that the book is about “mathematical and algorithmic” applications. I would have said “combinatorial,” since the main focus is on using matrices to encode combinatorial data that can then be analyzed with tools from linear algebra. Many of the examples come from graph theory, but the range is quite wide, from Fibonacci numbers to error-correcting codes with many stops in between.

Most of the miniatures in the book require quite a bit of linear algebra, so they are not intended for use in a first linear algebra course. Miniature 2, finding Binet’s formula for the Fibonacci numbers via a dimension count, is elementary, but already in miniature 3 we are computing ranks of matrices over the field with two elements, and in miniature 4 we prove a matrix is nonsingular by proving that the associated bilinear form is positive-definite. None of this is difficult, but it is not necessarily stuff that one would find in an introductory course.

For me, the biggest impact of the book came from noticing the tools that are used. Many linear algebra textbooks, including the one I use, delay discussion of inner products and transpose matrices till later in the course, which sometimes means they don’t get discussed at all. Seeing how often the transpose matrix shows up in Matoušek’s miniatures made me realize space must be made for it. Similarly, the theorem relating the rank of the product of two matrices to the ranks of the factors plays a big role here. Most linear algebra instructors would benefit from this kind of insight.

Thirty-three Miniatures would be an excellent book for an informal seminar offered to students after their first linear algebra course. It may also be the germ of many interesting undergraduate talks. And it’s fun as well.

Fernando Q. Gouvêa is Carter Professor of Mathematics at Colby College in Waterville, ME.

  • Fibonacci numbers, quickly
  • Fibonacci numbers, the formula
  • The clubs of Oddtown
  • Same-size intersections
  • Error-correcting codes
  • Odd distances
  • Are these distances Euclidean?
  • Packing complete bipartite graphs
  • Equiangular lines
  • Where is the triangle?
  • Checking matrix multiplication
  • Tiling a rectangle by squares
  • Three Petersens are not enough
  • Petersen, Hoffman-Singleton, and maybe 57
  • Only two distances
  • Covering a cube minus one vertex
  • Medium-size intersection is hard to avoid
  • On the difficulty of reducing the diameter
  • The end of the small coins
  • Walking in the yard
  • Counting spanning trees
  • In how many ways can a man tile a board?
  • More bricks--more walls?
  • Perfect matchings and determinants
  • Turning a ladder over a finite field
  • Counting compositions
  • Is it associative?
  • The secret agent and umbrella
  • Shannon capacity of the union: a tale of two fields
  • Equilateral sets
  • Cutting cheaply using eigenvectors
  • Rotating the cube
  • Set pairs and exterior products
  • Index