[Math] Fun Linear Algebra Problems

big-listlinear algebra

I'm teaching a linear algebra course this term (using Lay's book) and would like some fun "challenge problems" to give the students. The problems that I am looking for should be be easy to state and have a solution that

  1. Requires only knowledge that an average matrix algebra student would be expected to have (i.e. calculus and linear algebra, but not necessarily abstract algebra).

  2. Has a solution that requires cleverness, but not so much cleverness that only students with contest math backgrounds will be able to solve the problem.

An example of the type of problem that I have in mind is:

Fix an integer $n>1$. Let $S$ be the set of all $n \times n$ matrices whose entries are only zero and one. Show that the average determinant of a matrix in $S$ is zero.

Best Answer

One of my favourites is the odd-town puzzle.

A town with $n$ inhabitants has $m$ clubs such that

  • Each club has an odd number of members
  • Any two clubs have an even number of common members (zero included)

Show that $m \le n$.

It becomes easy once you treat each club as a vector. The conditions imply that the vectors are linearly independent over $\mathbb{F}_{2}$.

Related Question