Álgebra lineal en olimpiadas: determinantes y sistemas

Determinantes y su álgebra: recordatorio olímpico

El determinante de una matriz $n \times n$ es la única función multilineal alternada normalizada por $\det(I)=1$. Sus propiedades más usadas en olimpiadas:

(1) $\det(AB) = \det(A)\det(B)$. (2) $\det(A^T) = \det(A)$. (3) Si una fila es combinación lineal de las demás, $\det=0$. (4) $\det(kA) = k^n \det(A)$. (5) Expansión de Laplace por una fila/columna.

Desigualdad de Hadamard. $|\det(A)| \leq \prod_{i=1}^n \|a_i\|$ donde $a_i$ son las columnas (o filas). Esto da una cota sobre el determinante en términos de los tamaños de las columnas, útil para demostrar que ciertos determinantes son no nulos o para acotar el número de soluciones enteras.

Fórmula de Leibniz. $\det(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}$. Cada sumando corresponde a una permutación de $n$ elementos; hay $n!$ sumandos. Para $n=3$ esto da la regla de Sarrus; para $n$ grande, la estructura de la suma es combinatorialmente rica.

Determinante y divisibilidad. Si $A$ es una matriz entera con $\det(A) = \pm 1$ (unimodular), entonces $A^{-1}$ también es entera. Esto se usa en transformaciones de bases sobre $\mathbb{Z}$ y en cambios de variables en sistemas de ecuaciones diofánticas.

Rango y sistemas lineales sobre Z y sobre Fp

**Sistemas sobre $\mathbb{Z}$.** Un sistema $Ax = b$ con $A$ entera y $\det(A) \neq 0$ tiene solución entera si y solo si $\det(A) \mid \det(A_i)$ para cada columna aumentada $A_i$ (regla de Cramer). Esta condición de divisibilidad es exactamente el contenido aritmético del sistema.

**Rango sobre $\mathbb{F}_p$.** Reduciendo $A$ módulo $p$, el rango puede caer. Si $\text{rk}_{\mathbb{F}_p}(A) < n$, el sistema $Ax \equiv b \pmod p$ tiene ya sea ninguna solución o $p^k$ soluciones, con $k = n - \text{rk}$. Esto se usa para demostrar que un sistema tiene muchas soluciones o ninguna, en función de las condiciones modulo $p$.

Truco del núcleo. Si $Av = 0$ con $v \neq 0$ (vector entero no nulo), la condición $Ax = b$ puede tener infinitas soluciones enteras o ninguna. La existencia de un vector nulo en el núcleo de $A$ sobre $\mathbb{Z}$ es una condición de divisibilidad muy fuerte.

Lema de Minkowski. (Versión olímpica) Si $A$ es una matriz entera $n \times n$ y $\det(A) \neq 0$, el número de puntos $x \in \mathbb{Z}^n$ con $Ax = b$ (para $b$ fijo) es como mucho $|\det(A)|$. Esto porque el retículo imagen $A\mathbb{Z}^n$ tiene índice $|\det(A)|$ en $\mathbb{Z}^n$.

Ejemplo. Demostrar que el sistema $\begin{cases} x+y+z=1 \\ x^2+y^2+z^2=2 \\ x^3+y^3+z^3=3 \end{cases}$ no tiene soluciones enteras. Por Newton: $e_1=1$, $p_2=2$ da $e_2=(e_1^2-p_2)/2=(1-2)/2=-1/2$, que no es entero. Luego las raíces no son enteras (aunque los datos son enteros): no hay solución entera. $\blacksquare$

Matrices con estructura: circulantes, tridiagonales, de Cauchy

Matrices circulantes. Una matriz circulante $C$ tiene la forma $C_{ij} = c_{(j-i) \bmod n}$. Sus autovalores son $\lambda_k = \sum_{j=0}^{n-1} c_j \omega^{jk}$ donde $\omega = e^{2\pi i/n}$, y su determinante es $\det(C) = \prod_{k=0}^{n-1} \lambda_k$. Esto reduce el cálculo de $\det(C)$ a evaluar un polinomio en raíces de la unidad.

Matrices tridiagonales. La matriz tridiagonal con $a$ en la diagonal, $b$ sobre la diagonal y $c$ bajo la diagonal tiene determinante satisfaciendo la recursión $D_n = a D_{n-1} - bc D_{n-2}$. Esta es exactamente la recursión de los polinomios de Chebyshev (para $a=2\cos\theta$, $bc=1$).

Matrices de Cauchy. $C_{ij} = \frac{1}{x_i + y_j}$ tiene determinante $\det(C) = \frac{\prod_{i<j}(x_j-x_i)\prod_{i<j}(y_j-y_i)}{\prod_{i,j}(x_i+y_j)}$ (fórmula de Cauchy). Este determinante aparece en la teoría de funciones simétricas y en interpolación.

Identidad de Sylvester. Para submatrices de una matriz mayor: $\det(A_{ij}) \det(A) = \det(A_{ik})\det(A_{kj}) - \det(A_{il})\det(A_{lj})$ (en versión adecuada). Este tipo de identidades de determinantes (Plücker, Dodgson condensation) aparece en problemas de combinatoria algebraica avanzada.

Aplicación olímpica directa. Sea $f(x) = \sum_{k=0}^{n-1} a_k x^k$ un polinomio con $a_0, \ldots, a_{n-1}$ reales. Si $f(x_i) = 0$ para $n$ valores distintos $x_1, \ldots, x_n$, entonces $Va = 0$ (sistema homogéneo con $V$ la matriz de Vandermonde), y como $\det(V) \neq 0$, se concluye $a = 0$, es decir $f \equiv 0$. Este principio — si un polinomio de grado $< n$ tiene $n$ raíces, es el polinomio cero — es omnipresente en olimpiadas.

Sistemas sobredeterminados y el principio de pigeonhole algebraico

Un sistema de $m$ ecuaciones en $n$ incógnitas con $m > n$ es sobredeterminado: en general no tiene solución. Si se sabe que tiene solución, esto impone condiciones de compatibilidad que se explotan en olimpiadas.

Condición de compatibilidad. Si $Ax = b$ (con $A$ de tamaño $m \times n$, $m > n$) tiene solución, entonces $b$ está en el espacio imagen de $A$, lo que equivale a que $\text{rk}(A) = \text{rk}(A|b)$ (Rouché–Frobenius). Para matrices con estructura, esto da relaciones algebraicas entre los coeficientes.

Ejemplo (IMO 1990, P3 adaptado). Si $f:\mathbb{R}\to\mathbb{R}$ es un polinomio de grado $d$ y $f(x_i) = y_i$ para $d+2$ puntos distintos $(x_i, y_i)$, entonces la condición de compatibilidad del sistema $d+2\times(d+1)$ nos dice que ciertos determinantes son cero. Esto se traduce en relaciones entre los $y_i$.

Combinatoria de sistemas. El número de soluciones enteras de un sistema lineal en $\mathbb{Z}/m\mathbb{Z}$ es $m^{n-\text{rk}(A)}$ si el sistema es compatible, y 0 en caso contrario. Este conteo exacto aparece en problemas de aritmética modular donde se pide el número de soluciones.

**Método de eliminación de Gauss sobre $\mathbb{Z}$.** Se puede hacer eliminación gaussiana sobre $\mathbb{Z}$ usando el algoritmo de Hermite (forma normal de Hermite). La forma normal de Hermite de una matriz entera es triangular superior con entradas no negativas y condiciones de divisibilidad, y determina completamente la estructura del conjunto de soluciones enteras.

Problema IMO resuelto: sistema y determinante

Problema (IMO 2007, Problema 6). Sea $a$ y $b$ reales positivos. Para cada entero $n\geq 1$, sea $s_n$ el número de pares de enteros $(x,y)$ con $x,y\geq 0$ y $ax+by\leq n$. Demostrar que $|2s_n - n^2/(ab)| \leq \max(a/b, b/a) + 1$.

Solución (esquema usando álgebra lineal). El número $s_n$ de puntos enteros en el triángulo $\{ax+by\leq n, x\geq 0, y\geq 0\}$ es aproximado por el área $n^2/(2ab)$; en realidad el enunciado pide cotar $|2s_n - n^2/(ab)|$. La diferencia entre $2s_n$ y el área del paralelogramo (doble del triángulo) es un error de conteo de frontera.

Los puntos en la frontera $ax+by=n$ son $O(n/\min(a,b))$ puntos. El error de Ehrhart-Macdonald para un poliedro racional con denominadores $a$ y $b$ es $O(n)$, pero con la constante correcta depende de $a$ y $b$.

La cota exacta se obtiene observando que $2s_n = n^2/(ab) + \sum_{k=0}^{\lfloor n/a\rfloor} (\lfloor (n-ak)/b\rfloor + 1) - n^2/(2ab)$... la estimación cuidadosa del error usa $|\lfloor t\rfloor - t|<1$ y la estructura del denominador: el error total acumulado es a lo más $n/b + n/a$ pasos de frontera, cada uno con error $<1$, dando la cota $\max(a/b, b/a)+1$ tras dividir apropiadamente. El argumento completo usa propiedades del determinante del retículo generado por $(a,0)$ y $(0,b)$, que tiene área $ab$ y determina la densidad de puntos enteros. $\blacksquare$