Elementary applications of linear algebra over finite fields

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

(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/

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 13

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