Una transformada de Fourier rápida para el grafo de Johnson

Abstract: La Transformada de Fourier para el grafo de Johnson es definida como la matriz cambio de base en el espacio $\mathcal{F}$ de funciones complejas en los vértices del grafo, de la base delta o canónica a la base de Gelfand-Tsetlin.

La aplicación directa de esta matriz a un vector genérico requiere $\binom{n}{k}^2$ operaciones artiméticas. Nosotros demostramos que esta matriz puede ser factorizada como producto de $n-1$ matrices ortogonales, cada una de ellas con a lo sumo dos elementos no nulos en cada columna. La factorización está basada en la construcción de bases intermedias las cuales son parametrizadas vía el algoritmo de inserción de Robinson-Schensted. La factorización nos permite aplicar la Transformada de Fourier a un vector genérico en a lo sumo $2(n-1) \binom{n}{k}$ operaciones aritméticas. También demostramos que cada una de estas matrices esparsas puede ser construída utilizando $O(\binom{n}{k})$ operaciones aritméticas.

Como consecuencia de estos hechos, podemos computar todos los pesos de las componentes isotípicas de una función $f \in \mathcal{F}$ utilizando $O(n \binom{n}{k})$ operaciones, lo que mejora los resultados conocidos cuando $k$ domina asintóticamente a $\sqrt{n}$.

La charla se basa un trabajo conjunto con Rodrigo Iglesias (https://arxiv.org/abs/1912.09243).

Spanishcombinatorics

Audience: researchers in the topic

( paper | slides | video )

---

Seminario de álgebra, combinatoria y teoría de Lie

Series comments: The talks are usually in Spanish. Las instrucciones para recibir el link de zoom están en la página web del seminario: sites.google.com/view/semact-uns/.

---