Fun Linear Algebra Problems

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.

Solution 1:

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}$.

Solution 2:

This was an old Putnam problem, but if your students have seen determinants, I don't think it'd be beyond them.

Alice and Bob play the following game: they start with an empty 2008x2008 matrix (p.s. take a wild guess which year this was) and take turns writing numbers in each of the $2008^2$ positions. Once the matrix is filled, Alice wins if the determinant is nonzero and Bob wins if the determinant is zero. If Alice goes first, does either player have a winning strategy?

Solution 3:

You could build on this problem to show that linear algebra can be applied to things that might not look like linear algebra at first sight. You could choose initial and final states with simple prime factorizations such that it's easy to find the solution once you've transformed to the eigensystem. I guess you might need to give a hint pointing towards how to think about this in terms of linear algebra.

Solution 4:

I like question 17 from http://www.dpmms.cam.ac.uk/study/IB/LinearAlgebra/2010-2011/lin_alg-10-4.pdf :

Let $a_1, a_2, \ldots, a_n$ be real numbers such that $a_1 + \cdots + a_n = 0$ and $a_1^2 + \cdots a_n^2 = 1$. What is the maximum value of $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$?

Solution 5:

You have 13 coins with real numbers on them, such that given any coin, the other 12 can be split into two groups of 6 each, such that the sum of numbers of one group is same as the sum of numbers as the other.

Show that all the coins have the same numbers.

This is in scope I believe.

One proof of this involves constructing a matrix and showing that its rank is 12, by using Derangements! (There are other ways to prove that the rank is 12, though).