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

  • 0
    @Moro$n$: very nice, got it :).2011-05-02
9

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

5

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

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

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

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.

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

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.