# Elementary applications of linear algebra over finite fields

I'm teaching axiomatic linear algebra again this semester. Although the textbooks I'm using do everything over the real or complex numbers, for various reasons I prefer to work over an arbitrary field when possible. I always introduce at least $\mathbb{F}_2$ as an example of a finite field. To help motivate this level of generality, I'd like to cover some application of linear algebra over finite fields. Ideally it shouldn't make explicit reference to linear algebra or finite fields in its setup, and should require as little background as possible (the students have taken calculus, but not necessarily any other advanced math — in particular applications to group theory are out). I've looked around a little, but haven't found anything so far that requires little enough overhead to fit into a single 50-minute lecture and wouldn't seem either too abstract or too arbitrary to motivate such students. Any suggestions?

Alternatively, I'd be interested in elementary applications of linear algebra over any other field which isn't a subfield of $\mathbb{C}$.

-
If you have $n+1$ positive integers, all of whose prime factors belong come from a set of size at most $n$, then some nonempty subproduct of your positive integers is a perfect square. (Look at the exponents on the primes as giving you a vector over $\mathbb{F}_2$, and note that there must be a linear dependence relation.) This is important in (e.g.) the quadratic sieve factoring algorithm. –  Anonymous Jan 14 '13 at 17:16
The book "Thirty-three miniatures" is full of delightful applications of linear algebra, and a preliminary version is available at the author's web page kam.mff.cuni.cz/~matousek . In particular, finite fields are used in "miniature 27" to explain the fastest known algorithm for checking the associativity of an arbitrary binary operation on a finite set. –  boumol Jan 14 '13 at 17:48
@buomol: I have that book, and the sections I'd looked at seemed either too abstract or to have too much overhead for this class. I hadn't noticed that Miniature 27 involves finite fields, though -- I'll have to think about whether that one fits. –  Mark Meckes Jan 14 '13 at 18:14
To clarify my last comment, I don't mind abstraction per se in this class -- I do after all give the definition of a field on the first day. But since many of the students are encountering this level of abstraction for the first time, I want applications that will feel more concrete to the students in order to motivate the abstraction. Also, I will definitely cover one or two of the sections of Matousek's beautiful book which deal with real scalars; I just wasn't sure I wanted to use any of his miniatures involving finite fields. –  Mark Meckes Jan 14 '13 at 18:31
No elementary applications of linear algebra over a field of functions? Not that I expected any, but it would have been interesting to see. –  Mark Meckes Jan 15 '13 at 15:44

How about binary linear codes? You can "see" the Hamming distance between codewords, and use linear transformations to encode/decode

-
I now feel foolish given my comments above, because Matousek has a nice section on error correcting codes near the very beginning of his book, which I somehow missed entirely. –  Mark Meckes Jan 14 '13 at 18:34
A neat application of linear codes also arises in network coding: en.wikipedia.org/wiki/… –  Tobias Fritz Jan 14 '13 at 23:48
How about $q$-ary linear codes? –  Steve Huntsman Jan 15 '13 at 0:09
BTW, a very concrete/friendly way to handle $q$-ary codes is facilitated by the approach here: mathdl.maa.org/images/cms_upload/Wardlaw47052.pdf –  Steve Huntsman Jan 15 '13 at 0:15
It's perhaps silly to bother accepting an answer to a CW question, but I've decided I will definitely discuss binary linear codes, so I'm going ahead and accepting this. (I may or may not discuss some of the other applications suggested here, but of course there's only so much time in a semester.) –  Mark Meckes Jan 16 '13 at 21:07

You can use linear algebra over $\mathbb{F}_2$ to solve the game "Lights Out": http://en.wikipedia.org/wiki/Lights_Out_%28game%29

-
This at least used to be the canonical answer to this question (when Lights Out was better known). –  Allen Knutson Jan 14 '13 at 20:24
Can be played online here: addictinggames.com/puzzle-games/lightsout.jsp –  Qiaochu Yuan Jan 15 '13 at 0:34
The linear algebra behind the game is explained here: math.ksu.edu/~dmaldona/math551/lights_out.pdf –  Martin Brandenburg Jan 15 '13 at 9:29

I suggest Linear Feedback Shift Register (LFSR) as an easy example. They can be used as pseudo random number generators and have a wide practical use in communication and cryptography, GPS, GSM, CRC, WIFI, .. (non-math) applications which are usually accepted as usefull.

Usually they work over $\mathbb{F}_2$, but other fields are possible. Basically you have to work with polynomials (including long division) over $\mathbb{F}_2$. The need for primitive polynomials may motivate some more advanced considerations. A brief summary for mathematicians is Nayuki's blog.

I would explicitly pick the CRC algorithm. A description is located for example in this lecture(pdf) from D.Culler. This also relates to linear codes, which is also a good idea.

More easy is an application as fancy counter. If you ever wondered how the shuffle mode of your media player works.

-

Suppose you want to compute the period of the Fibonacci sequence $\bmod p$. This reduces to examining the powers of the matrix $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$ over $\mathbb{F}_p$, which requires either diagonalizing it over $\mathbb{F}\_p$ or over $\mathbb{F}\_{p^2}$ (or, when $p = 5$, using a nontrivial Jordan block). From here you can write down a nice number that is divisible by the period, depending on the value of $p \bmod 5$ (this uses a little quadratic reciprocity).

Edit: I suppose this requires some number-theoretic background to do properly. Never mind.

-

Possibly the simplest application is Berlekamp's Oddtown theorem. One reference is Section 12.2 of http://math.mit.edu/~rstan/algcomb.pdf.

-

The game of Projective Set is tantamount to finding a linear dependence on $7$ (distinct, nonzero) vectors in $\mathbb{F}_2^6$. Linear algebra over $\mathbb{F}_2$ shows that there's always a solution, and moreover that the number of solutions is always $2^k-1$ for some positive integer $k$. How large can this $k$ get, and how many of the ${63 \choose 7} = 553270671$ possible deals attain this maximal $k$? [Thanks to Zach Abel for introducing me to this game.]

-
This is similar to the card game SET!, see mathoverflow.net/questions/13638/… –  Stephan Müller Jan 15 '13 at 14:24
Yes, it's something like SET, where one must find affine lines in a subset of $\mathbb{F}_3^4$; that's probably why the game is called "Projective Set". The $\mathbb{F}_2^6$ game is less familiar, but has the advantage for teaching that one can use ideas from an intro linear-algebra course not just to describe the game but also to obtain results such as it takes $7$ cards to guarantee a valid subset (and with $6$ cards the probability of success is $1 - \prod_{n=0}^5 (64-2^n)/(63-n) = 61363/104371 \doteq 58.8\%$). –  Noam D. Elkies Jan 15 '13 at 16:09

(1) you can use $\mathbb{F}_2$ to prove that every group $G$ with $Aut(G)\cong 0$ is either $0$ or $\mathbb{Z}/2\mathbb{Z}$.

This is done by noting that the group is abelian, since all conjugation-automorphisms are the identity.

Then for abelian groups one has the automorphism $g\mapsto -g$ so all elements are self inverse.

At this point one gets that $G$ is a $\mathbb{F}_2$-vector space. Since any vector space of dimension $≥2$ admits nontrivial automorphisms, the result follows.

(2) also you might want to take a look at this: http://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/

-
I've given (1) as an exam problem in a more advanced course, but these students have never heard of groups. –  Mark Meckes Jan 14 '13 at 20:08

(1) An obvious but a very conceptual application is the basic fact that the cardinality of every finite field $F$ is a power of a prime, as $F$ can be considered as a vector space over $\mathbb{F}_p$ for $p=char F$.

(2) Another application is the construction of finite projective planes. Consider a vector space $V$ of dimension $3$ over a finite field $F$. Then consider the projective geometry $PG(V)$ whose points are the $1$-dimensional subspaces of $V$ and whose lines are the $2$-dimensional subspaces of $V$. In particular, the Fano projective place can be obtained by this method over $\mathbb{F}_2$.

-
There is a purely group-theoretic group for (1): Use Cauchy's Theorem and $p = \mathrm{exp}(F,+)$. –  Martin Brandenburg Jan 15 '13 at 1:18

Sometimes math problems crop up in high school competitions that are secretly linear algebra problems in disguise. For instance, #6 of USAMO 2008 (http://amc.maa.org/a-activities/a7-problems/USAMO-IMO/q-usamo/-pdf/usamo2008.pdf) can be approached via linear algebra over $\mathbb{F}_2$.

-
I'd like problems like this one better if I could understand why everyone would insist on being in a room containing an even number of one's friends. –  Mark Meckes Jan 14 '13 at 20:23
Don't you play (spontaneous with a single referee) games which need two teams, each team having the same number of players? Gerhard "Neither Do I. So There!" Paseman, 2013.01.14 –  Gerhard Paseman Jan 14 '13 at 23:57
Anyone who's ever been single knows the phenomenon whereby everyone else in the room is a couple. But I've never heard anyone say they liked that. –  Tom Leinster Jan 15 '13 at 0:38
@Gerhard, no I don't, but to apply this problem you're either talking about two games each being played by two matched teams of a priori arbitrary sizes, or one game between two teams whose sizes are even but not necessarily equal. To me this kind of problem seems like it would work better as a motivating example in a combinatorics course than in a linear algebra course. –  Mark Meckes Jan 15 '13 at 15:39
I don't see a motivation based in linear algebra, but my comment above was based on a contrived scenario from reading your comment: in MetaMagiGame (a name I just made up) a person is selected at random from a room of people, and that person must devise or choose a game which he or she must referee and must pit half of their friends against the other half, while the non-friends look on. Tom Leinster's scenario sounds more plausible to me. Gerhard "Game Parties Beat Party Games" Paseman, 2013.01.15 –  Gerhard Paseman Jan 15 '13 at 18:49

This one is pretty good. Kaplansky wanted squarefree numbers $x$ such that $$\sigma ( x^3) = y^2,$$ where $\sigma$ is the sum of divisors function. Somewhere around here I have a short note of his. He referred to this (and some very similar problems) as Ozanam's problem, from page 56 of Dickson's History, volume 1. Let's see; for each prime $p$ up to some bound, I had the computer factor $\sigma ( p^3),$ especially recording the exponents on the output primes $q.$ So, to the best of my memory (about 18 years ago), I wound up with a big matrix with entries in the field with two elements; each column meant a prime $p,$ each row was saying whether the exponent for the prime $q$ was even or odd. Then, a solution was a column vector, also of 0's and 1's, which my big matrix mapped to the zero vector. So, I did Gauss elimination over the field of two elements. And found hundreds of solutions.

I will see if I can find something written about this. For that matter, the program or programs I wrote should still be there in my MSRI account.

Note: i am having a little trouble remembering if it is the matrix i describe above or its transpose. So perhaps a little care is needed. It definitely worked, though, and quickly. I also built in some procedure where i could force some prime to be included, then see if i could find solutions with that restriction. As I recall, that needed more handholding for the computer, more attention by me.

-

There is a Martin Gardner problem, reprinted in his Unexpected Hanging collection, that goes like this:

Miranda beat Rosemary in a set of tennis, winning 6–3. There were five service breaks. Who served first?

One solution is as follows. The wins by the player who served first may be represented by a vector $\mathbb{F}_2^9$ that is the sum of (1,0,1,0,1,0,1,0,1) and another vector of weight 5. Such a vector must have even weight, so the player who served first won an even number of games. Thus Miranda served first.

In the book, Gardner writes that his original solution was long and cumbersome, and that the shortest solution he received was by Goran Ohlin: "Whoever served first, served five games, and the other player served four. Suppose the first server won $x$ of the games she served and $y$ of the other four games. The total number of games lost by the player who served them is then $5-x+y$. This equals $5$ [we were told that the non-server won five games]. Therefore $x=y$, and the first server won a total of $2x$ games. Because only Miranda won an even number of games, she must have been the first server." Though more elementary in some sense, this solution seems more ad hoc and less conceptual to me than the above argument using $\mathbb{F}_2$.

-

Rubik's Clock and Its Solution by Dénes and Mullen (Math. Mag. 68 (1995), 378–381) uses linear algebra modulo 12 to solve the Rubik's clock puzzle.

-

A trivial application: The group $(\mathbb{Z}/2\mathbb{Z})^n$ is generated by no less than $n$ elements.

[Probably this is the easiest way to prove that the free profinite group on $n$ letters cannot be topologically generated by less elements. And more abstractly, it is in general hard to find the minimal number of generators of a group, UNLESS it has a vector space quotient, and then we have dimension theory of vector spaces.]

-
Yes every dihedral group is generated by two elements of order 2, so we need to use that the group is abelian. If an abelian group is generated by $m$ elements and all of them have order $2$, then we get an epimorphism from $\mathbb{Z}/2 \oplus \dotsc \oplus \mathbb{Z}/2$, thus the group has $\leq 2^m$ elements. –  Martin Brandenburg Jan 15 '13 at 1:14
@Berlusconi see the beginning of the answer. @Martin, I agree to what you write, but the vector space approach is as simple. –  Lior Bary-Soroker Jan 17 '13 at 15:53