Matrices de incidencia y el rango sobre $\mathbb{F}_2$

Matrices de incidencia: codificar conjuntos como vectores

Dado un sistema de conjuntos $\mathcal{F} = \{A_1, \ldots, A_m\}$ sobre un universo $[n] = \{1, \ldots, n\}$, la matriz de incidencia $M \in \{0,1\}^{m \times n}$ tiene $M_{ij} = 1$ si $j \in A_i$ y $M_{ij} = 0$ si $j \notin A_i$. Cada conjunto $A_i$ se convierte en el vector indicador $\mathbf{v}_i \in \{0,1\}^n$.

El rango de $M$ sobre un campo $\mathbb{F}$ captura dependencias lineales entre los conjuntos. La clave del método es que **combinaciones lineales sobre $\mathbb{F}_2$** corresponden a diferencias simétricas: $\mathbf{v}_i + \mathbf{v}_j$ (mod 2) es el vector indicador de $A_i \triangle A_j$. Sobre $\mathbb{F}_2$, "la suma de varios conjuntos es cero" significa que la diferencia simétrica de todos ellos es vacía.

La ventaja de trabajar sobre $\mathbb{F}_2$ frente a $\mathbb{R}$ es que los cálculos son modulares y el álgebra refleja directamente la combinatoria de diferencias simétricas, paridades e incidencias. La desventaja es que el rango sobre $\mathbb{F}_2$ puede ser menor que sobre $\mathbb{R}$ (dependencias lineales mod 2 no son dependencias sobre $\mathbb{R}$).

El Lema de la Dimensión y sus cotas

El principio fundamental es: el rango de una matriz está acotado por el número de filas y el número de columnas. Esto da cotas en la cardinalidad de sistemas de conjuntos con propiedades de intersección.

Lema de la Dimensión (versión básica). Si $A_1, \ldots, A_m \subseteq [n]$ son conjuntos tales que $|A_i \cap A_j| \equiv 0 \pmod{2}$ para todo $i \ne j$, y $|A_i| \equiv 1 \pmod{2}$ para todo $i$, entonces $m \le n$.

Prueba. Consideramos los vectores $\mathbf{v}_1, \ldots, \mathbf{v}_m \in \mathbb{F}_2^n$. La matriz de Gram $G$ con $G_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j = |A_i \cap A_j| \pmod{2}$ tiene la forma $G = \text{diag}(1,1,\ldots,1) = I_m$ sobre $\mathbb{F}_2$ (pues $G_{ii} = |A_i| \equiv 1$ y $G_{ij} = 0$ para $i \ne j$). Como $G = M M^T$ tiene rango $m$ sobre $\mathbb{F}_2$ (pues $\det G = 1 \ne 0$) y el rango de $MM^T$ es a lo sumo el rango de $M$, que es a lo sumo $n$, concluimos $m \le n$.

Esta prueba de cuatro líneas establece un resultado que sin álgebra lineal requeriría argumentos combinatorios elaborados. Es el prototipo del método del rango.

El Teorema de Fisher y diseños de bloques

Teorema de Fisher. Sea $\mathcal{F} = \{A_1, \ldots, A_m\}$ una familia de subconjuntos de $[n]$, todos de tamaño $k$, tal que $|A_i \cap A_j| = \lambda$ para todo $i \ne j$ (con $\lambda$ fijo). Entonces $m \le n$.

Prueba por rango. Consideramos la matriz de incidencia $M$ sobre $\mathbb{R}$. Entonces $MM^T = (k - \lambda)I_m + \lambda J_m$, donde $J_m$ es la matriz de unos. Esta es la ecuación fundamental de los diseños de bloques. Los valores propios de $MM^T$ son $k - \lambda + \lambda m = k + \lambda(m-1)$ (con multiplicidad 1, vector propio $\mathbf{1}$) y $k - \lambda$ (con multiplicidad $m-1$). Si $k \ne \lambda$ (lo cual vale pues $k = \lambda$ implicaría que todos los conjuntos se intersecan en $k$ elementos, contradicción), entonces $MM^T$ tiene rango $m$. Como el rango de $MM^T$ es a lo sumo el rango de $M$, que es a lo sumo $n$, concluimos $m \le n$.

El Teorema de Fisher es la base de la teoría de diseños de bloques balanceados incompletos (BIBD). En un $(n, k, \lambda)$-BIBD, tenemos $n$ puntos, $b$ bloques (conjuntos de tamaño $k$), cada punto en $r$ bloques, con $bk = nr$ y $r(k-1) = \lambda(n-1)$. Fisher demuestra $b \ge n$, y cuando $b = n$ el diseño se llama simétrico.

En olimpiadas, el Teorema de Fisher aparece disfrazado: "Sea $\mathcal{F}$ una familia de subconjuntos de $\{1,\ldots,n\}$ con la propiedad de que cualquier dos conjuntos de $\mathcal{F}$ se intersecan en exactamente $k$ elementos. Demuestra que $|\mathcal{F}| \le n$." La prueba es siempre el argumento de rango.

El método del rango sobre $\mathbb{F}_2$: familias 2-distantes

Sobre $\mathbb{F}_2$, el método del rango es especialmente poderoso para familias de conjuntos con propiedades de paridad. Un ejemplo paradigmático:

Teorema. Sea $\mathcal{F}$ una familia de subconjuntos de $[n]$ tal que $|A| \equiv 1 \pmod 2$ para todo $A \in \mathcal{F}$ y $|A \cap B| \equiv 0 \pmod 2$ para todo $A \ne B$ en $\mathcal{F}$. Entonces $|\mathcal{F}| \le n$.

La prueba es exactamente el Lema de la Dimensión visto antes. Una generalización: si las condiciones de paridad son $|A| \in L$ para $|L|$ valores y $|A \cap B| \in K$ para $|K|$ valores, entonces $|\mathcal{F}| \le \binom{n}{\le |L|+|K|}$ (Teorema de Frankl-Wilson, que veremos en la Lección 4.3).

El Lema de Lindström-Gessel-Viennot (LGV) es otra herramienta de rango: el número de sistemas de caminos que no se intersecan en una red dirigida acíclica se expresa como un determinante de una matriz de caminos. Esto convierte problemas de conteo de trayectorias en cálculos de rango.

Técnica práctica. Cuando un problema pide acotar $|\mathcal{F}|$ para una familia con propiedades de intersección, el primer instinto debe ser: (1) definir la matriz de incidencia $M$; (2) calcular $MM^T$ usando las condiciones del problema; (3) determinar el rango de $MM^T$ (típicamente es máximo, lo que da $\operatorname{rk}(M) = |\mathcal{F}|$); (4) usar $\operatorname{rk}(M) \le n$ para concluir.

La traza como herramienta: el Teorema de los dos grafos

Un resultado elegante que combina matrices sobre $\mathbb{F}_2$ con grafos: Teorema de los dos grafos de Seidel. Dado un grafo $G$ en $n$ vértices, se puede 2-colorear con conjuntos $R$ (rojo) y $B$ (azul) tal que $|E(G[R])|, |E(G[B])|$ son ambos pares, si y solo si el espacio nulo de la matriz de adyacencia $A(G)$ sobre $\mathbb{F}_2$ tiene dimensión $\ge 1$ (es decir, el rango de $A(G)$ sobre $\mathbb{F}_2$ es $< n$).

La conexión entre paridades de subgrafos y el rango sobre $\mathbb{F}_2$ de la matriz de adyacencia es un tema profundo que aparece en la demostración del Teorema de los cuatro colores de Robertson-Sanders-Seymour-Thomas: el rango sobre $\mathbb{F}_2$ del mapa de flujos de $G$ juega un papel central.

Para olimpiadas, el resultado relevante es: si la suma de los vectores indicadores de un sistema de conjuntos es cero sobre $\mathbb{F}_2$, el sistema es linealmente dependiente, lo que da una cadena de implicaciones sobre diferencias simétricas. Este argumento aparece en varias soluciones de IMO Shortlist en problemas de coloraciones y particiones.