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 


*

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

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

 A: 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.
A: 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$?
A: 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).
A: 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. 
A: 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.
A: 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. 
A: 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.
A: 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}$.
A: *

*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.
A: 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.
A: 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?
A: One of my favorites is:
Given an $n\times n$ matrix
$$\begin{pmatrix}
a & b & \cdots & b \\
b & a & \cdots & b \\
\vdots & \vdots & \vdots & \vdots \\
b & b & \cdots & a
\end{pmatrix}
$$
with $a, b \neq 0$ and $a \neq b$. Find all the eigenvalues of this matrix.
