Aplicaciones elementales del álgebra lineal sobre campos finitos

Question

Este semestre vuelvo a enseñar álgebra lineal axiomática. Aunque los libros de texto que estoy utilizando lo hacen todo sobre los números reales o complejos, por diversas razones prefiero trabajar sobre un campo arbitrario cuando es posible. Siempre introduzco al menos $\mathbb{F}_2$ como ejemplo de campo finito. Para ayudar a motivar este nivel de generalidad, me gustaría cubrir alguna aplicación del álgebra lineal sobre campos finitos. Lo ideal sería que no se hiciera referencia explícita al álgebra lineal o a los campos finitos en su configuración, y que se requiriera la menor cantidad de conocimientos previos posibles (los estudiantes han cursado cálculo, pero no necesariamente otras matemáticas avanzadas; en particular, las aplicaciones a la teoría de grupos están descartadas). He buscado un poco, pero hasta ahora no he encontrado nada que requiera poca carga de trabajo para que quepa en una sola clase de 50 minutos y que no parezca demasiado abstracto o demasiado arbitrario para motivar a esos estudiantes. ¿Alguna sugerencia?

Alternativamente, estaría interesado en aplicaciones elementales del álgebra lineal sobre cualquier otro campo que no sea un subcampo de $\mathbb{C}$ .

Answer 1

¿Y los códigos lineales binarios? Se puede "ver" la distancia de Hamming entre las palabras del código, y utilizar transformaciones lineales para codificar/decodificar

Answer 2

Se puede utilizar el álgebra lineal sobre $\mathbb{F}_2$ para resolver el juego "Lights Out": http://en.wikipedia.org/wiki/Lights_Out_%28game%29

Answer 3

Sugiero Registro de desplazamiento de retroalimentación lineal (LFSR) como un ejemplo fácil. Pueden utilizarse como generadores de números pseudoaleatorios y tienen un amplio uso práctico en aplicaciones de comunicación y criptografía, GPS, GSM, CRC, WIFI, .. (no matemáticas) que suelen ser aceptadas como útiles.

Por lo general, trabajan sobre $\mathbb{F}_2$ pero son posibles otros campos. Básicamente hay que trabajar con polinomios (incluyendo la división larga) sobre $\mathbb{F}_2$ . La necesidad de polinomios primitivos puede motivar algunas consideraciones más avanzadas. Un breve resumen para los matemáticos es Blog de Nayuki .

Yo elegiría explícitamente el algoritmo CRC. Una descripción se encuentra por ejemplo en esto conferencia(pdf) de D.Culler. Esto también se relaciona con los códigos lineales, que también es una buena idea.

Más fácil es una aplicación como contador de lujo. Si alguna vez te has preguntado cómo funciona el modo aleatorio de tu reproductor multimedia.

Answer 4

Posiblemente la aplicación más sencilla sea el teorema de Berlekamp sobre Oddtown. Una referencia es la sección 12.2 de http://math.mit.edu/~rstan/algcomb.pdf .

Answer 5

Supongamos que quieres calcular el periodo de la secuencia de Fibonacci $\bmod p$ . Esto se reduce a examinar las potencias de la matriz $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$ en $\mathbb{F}_p$ lo que requiere diagonalizarlo sobre $\mathbb{F}_p$ o sobre $\mathbb{F}_{p^2}$ (o, cuando $p = 5$ utilizando un bloque de Jordan no trivial). A partir de aquí se puede escribir un buen número que sea divisible por el periodo, dependiendo del valor de $p \bmod 5$ (esto utiliza un poco de reciprocidad cuadrática).

Editar: Supongo que esto requiere cierta formación en teoría de los números para hacerlo correctamente. No importa.