34
$\begingroup$

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.

12 Answers 12

15

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

  • 1
    Perhaps this is out of scope of what you asked. I could not resist though :-)2011-04-27
  • 0
    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!2011-04-27
  • 2
    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?)2011-05-01
  • 2
    @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).2011-05-01
  • 0
    @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)2011-05-01
  • 0
    @daniel: Yes, an inhabitant can be a member of several clubs.2011-05-01
  • 0
    @daniel: btw, if you don't want to work over $\mathbb{F}_2$, you can try working over $\mathbb{Q}$ or even $\mathbb{R}$. $\mathbb{F}_2$ just makes it simpler. (The vectors need not be orthogonal over $\mathbb{Q}$ or $\mathbb{R}$, though).2011-05-01
  • 0
    @Moron: very nice, got it :).2011-05-02
8

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.

8

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?

  • 0
    You could also ask "for which m by m matrices will a winning strategy exist?"2011-06-11
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).

  • 1
    Nice. But why 13? :-)2011-04-27
  • 0
    @joriki: That is how I saw it first :-)2011-04-27
  • 1
    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.2011-06-10
  • 0
    @Joel: So true :-) Will edit. Thanks! btw, for a general answer: http://math.stackexchange.com/questions/18957/13-integers-with-each-set-of-12-integers/18962#189622011-06-10
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$?

  • 1
    Too bad you didn't give a hint. Now this question is somewhat causing problems http://math.stackexchange.com/q/324748/636592013-03-09
3

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.

  • 0
    Perhaps you can suggest specific problems from the books?2011-04-27
  • 0
    @Moron, the Oddtown puzzle you posted is the third of the thirty-three miniatures in the Matousek book.2011-04-28
  • 0
    @Gerry: I believe the linear algebra methods in combinatorics actually starts off with the odd-town puzzle!2011-04-28
3

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.

  • 0
    I like this answer very much; so much, in fact, that I think I'll give the problem to the students on Friday.2011-04-27
  • 4
    A nice application of this is the derivation of the formula for Fibonacci numbers!2011-04-27
  • 0
    Aren't you still left with the problem of calculating the 2011'th power of the diagonal elements? Or is this something that is just left symbolically?2018-10-12
3

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.

2
  • 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.

  • 0
    I think it's $2^{n-1}$.2018-08-04
2

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.

1

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.

1

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.