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 x n matrices whose entries are only zero and one. Show that the average determinant of a matrix in S is zero.

Thanks.

-

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

-
Perhaps this is out of scope of what you asked. I could not resist though :-) – Aryabhata Apr 27 '11 at 16:47
You are right that I probably couldn't ask this to my linear algebra students. It sounds like a terrific problem for an abstract algebra class though! – Ben Linowitz Apr 27 '11 at 17:02
I'm having some trouble solving this with my linear algebra knowledge, any hints? (also, just so I'm sure, what does $\mathbb{F}_{2}$ mean?) – daniel.jackson May 1 '11 at 8:19
@danile: Show that any two clubs are orthogonal. $\mathbb{F}_2$ means the field where $1+1 = 0$ (so basically even is zero and odd is one). – Aryabhata May 1 '11 at 14:10
@Moron: ok, unfortunately the only time I saw $F_2$ was to assume the exact opposite, so I have no idea how that helps. Also, I assume it's obvious but an inhabitant can be a member of several clubs? (otherwise it seems trivial) – daniel.jackson May 1 '11 at 19:34

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.

-

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).

-
Nice. But why 13? :-) – joriki Apr 27 '11 at 16:50
@joriki: That is how I saw it first :-) – Aryabhata Apr 27 '11 at 16:51
This is a very fun problem indeed. Just a small remark though : at first your coins have real numbers on them, but afterwards those become weights. – Joel Cohen Jun 10 '11 at 22:57
@Joel: So true :-) Will edit. Thanks! btw, for a general answer: math.stackexchange.com/questions/18957/… – Aryabhata Jun 10 '11 at 22:58

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?

-
You could also ask "for which m by m matrices will a winning strategy exist?" – tom Jun 11 '11 at 4:17

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$?

-
Too bad you didn't give a hint. Now this question is somewhat causing problems math.stackexchange.com/q/324748/63659 – Pranasas Mar 9 '13 at 7:29

This is perhaps a "low-brow" answer, and maybe not quite what you have in mind, but when I was an undergrad, one of the most immediately satisfying problems we did was the standard taking a diagonalizable matrix $D$ and finding, say, $D^{2011}$. This is obviously a very common problem to do in linear algebra, but I still found it satisfying since one did not have to compute $D^{2011}$ directly.

-
I like this answer very much; so much, in fact, that I think I'll give the problem to the students on Friday. – Ben Linowitz Apr 27 '11 at 18:50
A nice application of this is the derivation of the formula for Fibonacci numbers! – Aryabhata Apr 27 '11 at 19:01

Let $M_n$ be the vector space of all $n\times n$ matrices (with, say, real entries). Prove that the matrices in a basis for $M_n$ can't all commute with each other.

-

here are some books with nice problems in linear algebra: (i) thirty three miniatures by jiri matousek,

(ii) linear algebra methods in combinatorics by laszlo babai and peter frankl,

(iii) problems and theorems in linear algebra by prasolov.

-
Perhaps you can suggest specific problems from the books? – Aryabhata Apr 27 '11 at 17:43
@Moron, the Oddtown puzzle you posted is the third of the thirty-three miniatures in the Matousek book. – Gerry Myerson Apr 28 '11 at 1:24
@Gerry: I believe the linear algebra methods in combinatorics actually starts off with the odd-town puzzle! – Aryabhata Apr 28 '11 at 1:30

Does any rotation of a d-dimension sphere have a fixed point?

It's almost trivial to visualize that one can rotate a 2D sphere (cirfunference) without fixed points, but one cannot do that in 3D. And when one asks what could happen in more dimensions, the student is led to discover the connection with properties of the eigenvalues of orthogonal matrices, and the fact that a polynomial of odd degree has at least one real root.

This in mentioned in Strang, I think, and I've always loved it.

-
• In the same spirit as your example : Let $A$ be a $n$ by $n$ matrix whose entries are only $1$ and $-1$. Show that $2^n$ divides $\det(A)$ (substracting two columns and developing with respect to it, you get the result by induction on $n$).

• Denote $P$ the set of prime numbers, show that $(\ln(p))_{p \in P}$ is free over $\mathbb{Q}$, conclude that at most one of them is possibly rational.

-

My favorite is probably the derivation of the golden ratio from the Fibonacci Sequence.

Another favorite of mine, although perhaps at too high a level, is Gauss's theorem from differential geometry; see Stoker chapter 6 section 7. I really like this proof because it's basically just a long exercise in matrix multiplication.

-