¿Cuáles son algunas aplicaciones ingeniosas del álgebra lineal en combinatoria?

Llame a un conjunto de líneas que pasan por un punto común equiangular si el ángulo entre dos de ellas es el mismo.

Ahora, supongamos que desea averiguar el número máximo de líneas equiangulares * que pasan por el origen (o cualquier otro punto fijo) en [math] \ mathbb {R} ^ n [/ math]. ¿Cómo te irías?

Aquí hay una prueba de álgebra lineal basada en el hecho de que hay como máximo [matemáticas] n (n + 1) / 2 [/ matemáticas] líneas equiangulares a través del origen, por Tom H. Koornwinder:

Deje que [math] L_1, \ dots, L_m [/ math] sean líneas que pasan por el origen con un ángulo [math] arccos (\ alpha) [/ math] entre cada par de ellas. Elija vectores de unidad [matemática] u_1, \ puntos, u_m [/ matemática] en cada línea. Luego tenemos [math] \ langle u_i, u_j \ rangle ^ 2 = \ alpha ^ 2 \ delta_ {i, j} [/ math]. Defina polinomios [matemática] P_1, \ puntos, P_m [/ matemática] como [matemática] P_i (x) = \ langle u_i, x \ rangle ^ 2 – \ alpha ^ 2 \ langle x, x \ rangle [/ math]. Luego tenemos [math] P_i (u_j) = (1- \ alpha ^ 2) \ delta_ {i, j} [/ math], y por lo tanto, estos polinomios [math] m [/ math] son ​​linealmente independientes. El espacio de polinomios homogéneos variables [matemática] n [/ matemática] con grado como máximo [matemática] 2 [/ matemática] se puede demostrar fácilmente que tiene dimensión [matemática] {n + 1 \ elegir 2} [/ matemática], y por lo tanto [math] m \ leq n (n + 1) / 2 [/ math].

* las líneas equiangulares están relacionadas con dos gráficos.

Algunas referencias:

  • ¿Pruebas de álgebra lineal en combinatoria?
  • Métodos de álgebra lineal en combinatoria por Babai y Frankl

Algunos que vienen a la mente son las pruebas de la desigualdad de Fisher y el teorema de Ray-Chaudhuri – Wilson.
Estas notas pueden resultarle interesantes: ETH – Cadmo – CADMO