En el capítulo anterior sobre la Inverse Number Theoretic Transform, afirmamos que la inversa de la matriz de Vandermonde $V(\omega)$ para una raíz $k$-ésima primitiva de la unidad $\omega$ también es una matriz de Vandermonde, dada por $\frac{1}{k}V(\omega^{-1})$. Ahora demostraremos este hecho.

Los lectores con menos inclinación matemática pueden saltarse este capítulo sin perderse de nada. No es necesario entender la INTT, siempre y cuando acepten que la matriz inversa que proponemos es válida.

La matriz de Vandermonde se define como una matriz donde cada fila es una progresión geométrica.

• La primera fila es la progresión geométrica de $\omega^0$ desde $(\omega^0)^0$ hasta $(\omega)^{k-1}$.
• La segunda fila es la progresión geométrica de $\omega^1$ desde $(\omega^1)^{0}$ hasta $(\omega^1)^{k -1}$.
• Esto continúa hasta la última fila, que es la progresión geométrica de $\omega^{k-1}$ desde $(\omega^{k-1})^0$ hasta $(\omega^{k-1})^{k-1}$.

Por lo tanto, cada entrada en la fila $i$ y la columna $j$ de $V(\omega)$ está dada por

Consideremos un polinomio $f(x)$ de grado a lo sumo $k-1$, dado por

Sea $S$ el conjunto que consiste en las raíces $k$-ésimas de la unidad generadas por una raíz $k$-ésima primitiva:

El vector de evaluaciones de $f(x)$ en el conjunto $S$,

se puede obtener multiplicando el vector de coeficientes $\mathbf{a}$ por $V(\omega)$:

donde $a_0, a_1, ..., a_{k-1}$ son los coeficientes del polinomio $f(x)$.

Cada fila en el lado izquierdo es el producto interno de la $i$-ésima fila de la matriz de Vandermonde y el vector $\mathbf{a}$. Por ejemplo, el $i$-ésimo elemento $f(\omega^i)$ es

Por lo tanto, las evaluaciones se pueden escribir como

para $i\in \{0,1,2,...,k-1\}$.

Nota sobre los índices: En la ecuación anterior, tenemos dos índices. El índice $i$ indica de qué evaluación estamos tratando, y puede tomar los valores $0,1,2,\ldots, k-1$. Esto significa que la fórmula anterior no representa solo una ecuación, sino $k$ ecuaciones, una para cada valor de $i$. Por ejemplo, la notación anterior es una forma abreviada de

El índice $j$ en $\omega^{ij}$ y $a_j$ es un índice de suma y, por lo tanto, es “consumido” por la suma. Debido a que es consumido por la suma, no aparece en el lado izquierdo de la ecuación. La elección de los índices $i$ y $j$ es arbitraria; podríamos haber usado $m,n,p,q$ o cualquier otra letra. En general, para los índices de vectores, es común usar letras del medio del alfabeto.

Ahora queremos encontrar la relación inversa para obtener el vector $\mathbf{a}$ a partir del vector $\mathbf{y}$. En otras palabras, queremos calcular $\mathbf{a} = V^{-1}(\omega) \cdot \mathbf{y}$, donde $V^{-1}(\omega)$ es la inversa de $V(\omega)$.

Nuestra afirmación es que la inversa de la matriz de Vandermonde $V(\omega)$ también es una matriz de Vandermonde, dada por $\frac{1}{k}V(\omega^{-1})$.

Para ser completamente claros, nuestra afirmación es que

donde $\omega$ es una raíz $k$-ésima primitiva de la unidad.

Si la afirmación es correcta, el vector $\mathbf{a}$ se puede calcular de la siguiente manera:

La componente $a_i$ es el producto interno entre la $i$-ésima fila de $\frac{1}{k}V(\omega^{-1})$ y el vector $\mathbf{y}$:

Esta operación se puede escribir como la siguiente suma:

para $i\in\{0,1,2,...,k-1\}$.

Por razones pedagógicas, demostraremos nuestra afirmación (que la inversa de la matriz de Vandermonde $V(\omega)$ es otra matriz de Vandermonde, dada por $\frac{1}{k}V(\omega^{-1})$) de dos maneras diferentes.

Primero, mostraremos que la multiplicación de matrices de $V(\omega)$ y $\frac{1}{k}V(\omega^{-1})$ da como resultado la matriz identidad $\mathbb{I}$, es decir,

Luego, mostraremos que si primero multiplicamos $V(\omega)$ por $\mathbf{a}$ para obtener $\mathbf{y}$, y después multiplicamos $\frac{1}{k}V(\omega^{-1})$ por $V(\omega)\mathbf{a}$, recuperamos $\mathbf{a}$.

Estas dos pruebas son esencialmente la misma, solo que expresadas de dos maneras diferentes.

Prueba de que $V(\omega) \cdot \frac{1}{k}V(\omega^{-1}) = \mathbb{I}$

Demostraremos que la multiplicación de matrices de $V(\omega)$ con $\frac{1}{k} V(\omega^{-1})$ da como resultado la matriz identidad.

La prueba se basa en la propiedad de ortogonalidad de las raíces de la unidad, la cual se expresa como una sumatoria. Por lo tanto, primero escribiremos la multiplicación de matrices en forma de sumatoria para poder usar esta propiedad de ortogonalidad.

La multiplicación $V(\omega) \cdot \frac{1}{k}V(\omega^{-1})$ en notación de índices

Recordemos que la entrada de la matriz de $V(\omega)$ en la fila $i$ y la columna $m$ está dada por

Nota: La numeración de filas y columnas aquí se considera desde $0$, no desde $1$.

Por ejemplo, la entrada en la fila $1$ y la columna $2$ de $V(\omega)$ es $(\omega^1)^2,$ como se resalta a continuación en rojo:

Además, la entrada de la matriz de $\frac{1}{k} V(\omega^{-1})$ en la fila $m$ y la columna $j$ está dada por

Por ejemplo, la entrada en la fila $2$ y la columna $0$ de $\frac{1}{k} V(\omega^{-1})$ es $(\omega^{-2})^0$, como se resalta a continuación:

Por lo tanto, cuando las dos matrices $V(\omega)$ y $\frac{1}{k} V(\omega^{-1})$ se multiplican, el elemento resultante en la fila $i$ y la columna $j$ se obtiene multiplicando la fila $i$ de $V(\omega)$ (rojo) con la columna $j$ de $\frac{1}{k} V(\omega^{-1})$ (azul):

Cada entrada de la matriz $V(\omega) \cdot \frac{1}{k} V(\omega^{-1})$, que denotamos por $M_{ij}$, está entonces dada por

Ahora necesitamos mostrar que las entradas $M_{ij}$ son iguales a las de la matriz identidad. Para hacer esto, usamos la ortogonalidad de las raíces de la unidad.

Recordatorio: Ortogonalidad de las raíces de la unidad

En el capítulo sobre la ortogonalidad de las raíces de la unidad, mostramos que

Para recapitular, la fórmula anterior nos da el resultado de la sumatoria en dos casos: (1) cuando $i\equiv j$ y (2) cuando $i \not\equiv j$. Usaremos ambos casos a continuación.

Caso 1: Cuando $i\equiv j$

Queremos calcular

cuando $i\equiv j$. La ortogonalidad de las raíces de la unidad dice que, cuando $i\equiv j$,

Usando este resultado para $M_{ij}$, tenemos que

Por lo tanto, para los términos de la diagonal (como $M_{00}, M_{11}, M_{22},...,M_{(k-1)(k-1)}$), tenemos

Caso 2: Cuando $i \not\equiv j$

Ahora queremos calcular

cuando $i\not\equiv j$. La ortogonalidad de las raíces de la unidad dice que, cuando $i\not\equiv j$ ,

Usando este resultado para $M_{ij}$, tenemos

Por lo tanto, para cualquier término fuera de la diagonal (como $M_{10}, M_{01}, M_{12}, \dots)$, tenemos $M_{ij} = 0$.

La matriz $M$

Teniendo en cuenta los casos (1) y (2) anteriores, tenemos que la matriz $M = (M_{ij})$ es

que es exactamente la matriz identidad $\mathbb{I}$. Por lo tanto, las matrices $V(\omega)$ y $\frac{1}{k} V(\omega^{-1})$ son inversas la una de la otra, porque

La multiplicación de matrices de $\frac{1}{k}V(\omega^{-1})$ con el vector $\mathbf{y}$ devuelve el vector $\mathbf{a}$

Otra manera de demostrar que $\frac{1}{k} V(\omega^{-1})$ es la inversa de $V(\omega)$ es mostrar que invierte a esta última.

Es decir, si primero aplicamos $V(\omega)$ a $\mathbf{a}$ para obtener $\mathbf{y}$,

y luego aplicamos $\frac{1}{k}V(\omega^{-1})$ a $\mathbf{y}$, recuperamos $\mathbf{a}$:

Eso es exactamente lo que mostraremos.

Primera transformación: $\mathbf{y} = V(\omega) \cdot \mathbf{a}$

La primera transformación lleva el vector de coeficientes $\mathbf{a}$ al vector de evaluaciones $\mathbf{y}$ mediante la siguiente operación matricial:

Como ya hemos visto, esta operación matricial se puede escribir usando índices:

Segunda transformación: $\mathbf{\tilde{a}} = \frac{1}{k}V(\omega^{-1}) \mathbf{y}$

Ahora realizamos una segunda transformación sobre el vector $\mathbf{y}$, lo que da como resultado un vector $\mathbf{\tilde{a}}$:

Si podemos demostrar que $\mathbf{a} = \mathbf{\tilde{a}}$, entonces la segunda transformación es la inversa de la primera.

La operación matricial anterior se puede escribir en forma de índices como

Ahora sustituimos la expresión de $f(\omega^i)$ . Recordemos que

donde $i$ es simplemente un índice que podemos reemplazar por $m$, o cualquier otra letra. Por lo tanto, al reemplazar $f(\omega^m)$ en el resultado para $\tilde{a}_j$, tenemos

Reescribiendo como una doble suma:

El término entre paréntesis es exactamente la relación de ortogonalidad:

Para continuar la prueba, podríamos estudiar el caso (1), donde $i=j$, y el caso (2), donde $i \neq j$, pero procederemos de manera diferente. Introduciremos un símbolo llamado la delta de Kronecker.

La delta de Kronecker, $\delta_{ij}$, es un símbolo con 2 índices, $i$ y $j$ en este caso, que es $1$ cuando $i=j$ y $0$ de lo contrario:

La delta de Kronecker se puede entender como las entradas de la matriz identidad.

Usando la delta de Kronecker, podemos escribir la propiedad de ortogonalidad como

Al usar la delta de Kronecker en la expresión de $\tilde{a}_j$, tenemos

Desarrollando la sumatoria, la expresión anterior se puede escribir como

Por la propiedad de la delta de Kronecker, solo un término en la sumatoria es distinto de cero. Por ejemplo, para $j=2$, solo $\delta_{22}$ es distinto de cero. Por lo tanto, tenemos

Esto es válido para cualquier $j$, por lo tanto tenemos que

para cualquier $j$.

Esto demuestra que la transformación $\frac{1}{k} V(\omega^{-1})$ es la inversa de la transformación $V(\omega)$.

Este artículo es parte de una serie sobre la Number Theoretic Transform en nuestro ZK Book