In the previous chapter on the Inverse Number Theoretic Transform, we claimed that the inverse of the Vandermonde matrix $V(\omega)$ for a primitive $k$-th root of unity $\omega$ is also a Vandermonde matrix, given by $\frac{1}{k}V(\omega^{-1})$. We now prove this fact.

Less mathematically inclined readers can skip this chapter without any loss. It is not necessary to understand the INTT, provided they accept that our proposed inverse matrix is valid.

The Vandermonde matrix is defined as a matrix where each row is a geometric progression.

• The first row is the geometric progression of $\omega^0$ from $(\omega^0)^0$ to $(\omega)^{k-1}$.
• The second row is the geometric progression of $\omega^1$ from $(\omega^1)^{0}$ to $(\omega^1)^{k -1}$.
• This continues until the last row, which is the geometric progression of $\omega^{k-1}$ from $(\omega^{k-1})^0$ to $(\omega^{k-1})^{k-1}$.

Thus, each entry in row $i$ and column $j$ of $V(\omega)$ is given by

Consider a polynomial $f(x)$ of degree at most $k-1$, given by

Let $S$ be the set consisting of the $k$-th roots of unity generated by a primitive $k$-th root:

The vector of evaluations of $f(x)$ on the set $S$,

can be obtained by multiplying the coefficient vector $\mathbf{a}$ by $V(\omega)$:

where $a_0, a_1, ..., a_{k-1}$ are the coefficients of the polynomial $f(x)$.

Each row on the left-hand side is the inner product of the $i$-th row of the Vandermonde matrix and the vector $\mathbf{a}$. For instance, the $i$-th element $f(\omega^i)$ is

Thus, the evaluations can be written as

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

Note on indices: In the equation above, we have two indices. The index $i$ indicates which evaluation we are dealing with, and it can take the values $0,1,2,\ldots, k-1$. This means that the formula above represents not just one equation, but $k$ equations, one for each value of $i$. For instance, the notation above is a shorthand for

The index $j$ in $\omega^{ij}$ and $a_j$ is a summation index and therefore “consumed” by the sum. Because it is consumed by the sum, it does not appear on the left-hand side of the equation. The choice of the indices $i$ and $j$ is arbitrary; we could have used $m,n,p,q$ or any other letters. In general, for vector indices, it is common to use letters from the middle of the alphabet.

Now we want to find the inverse relation to obtain the vector $\mathbf{a}$ from the vector $\mathbf{y}$. In other words, we want to calculate $\mathbf{a} = V^{-1}(\omega) \cdot \mathbf{y}$, where $V^{-1}(\omega)$ is the inverse of $V(\omega)$.

Our claim is that the inverse of the Vandermonde matrix $V(\omega)$ is also a Vandermonde matrix, given by $\frac{1}{k}V(\omega^{-1})$.

To be completely clear, our claim is that

where $\omega$ is a primitive $k$-th root of unity.

If the claim is correct, the vector $\mathbf{a}$ can be calculated as follows:

The component $a_i$ is the inner product between the $i$-th row of $\frac{1}{k}V(\omega^{-1})$ and the vector $\mathbf{y}$:

This operation can be written as the following sum:

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

For pedagogical reasons, we will prove our claim - that the inverse of the Vandermonde matrix $V(\omega)$ is another Vandermonde matrix, given by $\frac{1}{k}V(\omega^{-1})$ - in two different ways.

First, we will show that the matrix multiplication of $V(\omega)$ and $\frac{1}{k}V(\omega^{-1})$ yields the identity matrix $\mathbb{I}$, that is,

Then, we will show that if we first multiply $V(\omega)$ by $\mathbf{a}$ to obtain $\mathbf{y}$, and then multiply $\frac{1}{k}V(\omega^{-1})$ by $V(\omega)\mathbf{a}$, we recover $\mathbf{a}$.

These two proofs are essentially the same, just expressed in two different ways.

Proof that $V(\omega) \cdot \frac{1}{k}V(\omega^{-1}) = \mathbb{I}$

We will prove that the matrix multiplication of $V(\omega)$ with $\frac{1}{k} V(\omega^{-1})$ yields the identity matrix.

The proof relies on the orthogonality property of the roots of unity, which is expressed as a summation. Therefore, we first write the matrix multiplication in summation form so that we can use this orthogonality property.

The multiplication $V(\omega) \cdot \frac{1}{k}V(\omega^{-1})$ in index notation

Recall that the matrix entry of $V(\omega)$ in row $i$ and column $m$ is given by

Note: The numbering of rows and columns here is considered from $0$, not $1$.

For example, the entry in row $1$ and column $2$ of $V(\omega)$ is $(\omega^1)^2,$ as highlighted below in red:

Also, the matrix entry of $\frac{1}{k} V(\omega^{-1})$ in row $m$ and column $j$ is given by

For example, the entry in row $2$ and column $0$ of $\frac{1}{k} V(\omega^{-1})$ is $(\omega^{-2})^0$, as highlighted below:

Therefore, when the two matrices $V(\omega)$ and $\frac{1}{k} V(\omega^{-1})$ are multiplied, the resulting element in row $i$ and column $j$ is obtained by multiplying row $i$ of $V(\omega)$ (red) with column $j$ of $\frac{1}{k} V(\omega^{-1})$ (blue):

Each entry of the matrix $V(\omega) \cdot \frac{1}{k} V(\omega^{-1})$, which we denote by $M_{ij}$, is then given by

Now we need to show that the entries $M_{ij}$ are equal to those of the identity matrix. To do this, we use the orthogonality of the roots of unity.

Recall: Orthogonality of roots of unity

In the chapter on the orthogonality of roots of unity, we showed that

To recap, the formula above gives us the result of the summation in two cases: (1) when $i\equiv j$ and (2) when $i \not\equiv j$. We will use both cases below.

Case 1: When $i\equiv j$

We want to calculate

when $i\equiv j$. The orthogonality of the roots of unity says that, when $i\equiv j$,

Using this result for $M_{ij}$, we have that

Thus, for the diagonal terms (such as $M_{00}, M_{11}, M_{22},...,M_{(k-1)(k-1)}$), we have

Case 2: When $i \not\equiv j$

Now we want to calculate

when $i\not\equiv j$. The orthogonality of the roots of unity says that, when $i\not\equiv j$ ,

Using this result for $M_{ij}$, we have

Therefore, for any non-diagonal terms (such as $M_{10}, M_{01}, M_{12}, \dots)$, we have $M_{ij} = 0$.

The matrix $M$

Taking into account cases (1) and (2) above, we have that the matrix $M = (M_{ij})$ is

which is exactly the identity matrix $\mathbb{I}$. Thus, the matrices $V(\omega)$ and $\frac{1}{k} V(\omega^{-1})$ are inverses of each other, because

Matrix multiplication of $\frac{1}{k}V(\omega^{-1})$ with vector $\mathbf{y}$ yields vector $\mathbf{a}$ back

Another way to show that $\frac{1}{k} V(\omega^{-1})$ is the inverse of $V(\omega)$ is to show that it inverts the latter.

That is, if we first apply $V(\omega)$ to $\mathbf{a}$ to obtain $\mathbf{y}$,

and then apply $\frac{1}{k}V(\omega^{-1})$ to $\mathbf{y}$, we recover $\mathbf{a}$:

That is exactly what we will show.

First transformation: $\mathbf{y} = V(\omega) \cdot \mathbf{a}$

The first transformation takes the vector of coefficients $\mathbf{a}$ to the vector of evaluations $\mathbf{y}$ via the following matrix operation:

As we have already seen, this matrix operation can be written using indices:

Second transformation: $\mathbf{\tilde{a}} = \frac{1}{k}V(\omega^{-1}) \mathbf{y}$

Now we perform a second transformation on the vector $\mathbf{y}$, which results in a vector $\mathbf{\tilde{a}}$:

If we can show that $\mathbf{a} = \mathbf{\tilde{a}}$, then the second transformation is the inverse of the first.

The matrix operation above can be written in index form as

Now substitute the expression for $f(\omega^i)$ . Recall that

where $i$ is just an index that we can replace for $m$, or any other letter. Thus, replacing $f(\omega^m)$ in the result for $\tilde{a}_j$, we have

Rewriting as a double sum:

The term in parentheses is exactly the orthogonality relation:

To continue the proof, we could study case (1), where $i=j$, and case (2), where $i \neq j$, but we will proceed differently. We will introduce a symbol called the Kronecker delta.

The Kronecker delta, $\delta_{ij}$, is a symbol with 2 indices, $i$ and $j$ in this case, which is $1$ when $i=j$ and $0$ otherwise:

The Kronecker delta can be understood as the entries of the identity matrix.

Using the Kronecker delta, we can write the orthogonality property as

Using the Kronecker delta in the expression for $\tilde{a}_j$, we have

Expanding the summation, the expression above can be written as

By the Kronecker delta property, only one term in the summation is nonzero. For example, for $j=2$, only $\delta_{22}$ is nonzero. Thus, we have

This holds true for any $j$, therefore we have that

for any $j$.

This shows that the transformation $\frac{1}{k} V(\omega^{-1})$ is the inverse of the transformation $V(\omega)$.

This article is part of a series on the Number Theoretic Transform in our ZK Book