Vandermonde Matrices
A Vandermonde matrix is a matrix that converts a polynomial from its coefficient representation into its value representation at a set of points.
For a polynomial $f(x) = a_0 +a_1x + a_2x^2+\dots+a_{k-1}x^{k-1}$ with its coefficient representation:
$$ \mathbf{a} = \begin{bmatrix} a_0\\ a_1\\ a_2\\ \vdots\\ a_{k-1} \end{bmatrix}$$The Vandermonde matrix evaluates it at $k$ distinct points as a single operation.
Evaluating a polynomial as a matrix product
For simplicity, we assume $k=4$, then we have a polynomial of degree $k-1 =3$.
Evaluation at single point
The evaluation of polynomial $f(x)$ at the point $x_0$ is:
$$ f(x_0) = a_0 +a_1\cdot x_0 + a_2\cdot x_0^2+a_{3}\cdot x_0^{3}$$This can be written as matrix product: multiplying a $1\times 4$ matrix containing the successive powers of $x_0$ by the vector of polynomial coefficients, as follows:
$$ \begin{bmatrix} f(x_0) \end{bmatrix} = \begin{bmatrix} 1 & x_0^1 & x_0^2 & x_0^{3} \end{bmatrix} \cdot \begin{bmatrix} a_0\\ a_1\\ a_2\\ a_{3} \end{bmatrix}$$Evaluation at two points
To evaluate at two points, $x_0$ and $x_1$, we could express these as two separate matrix products. Instead, we stack these row vectors into a $2 \times 4$ matrix:
$$ \begin{bmatrix} f(x_0) \\ f(x_1) \end{bmatrix} = \begin{bmatrix} 1 & x_0^1 & x_0^2 & x_0^{3}\\ 1 & x_1^1 & x_1^2 & x_1^{3}\\ \end{bmatrix} \cdot \begin{bmatrix} a_0\\ a_1\\ a_2\\ a_{3} \end{bmatrix}$$Where each row contains the successive powers of $x_0$ and $x_1$, respectively.
Therefore, evaluating the polynomial at two points is equivalent to multiplying a $2 \times k = 2 \times 4$ matrix by the coefficient vector.
Evaluation at $4$ points
If we extend our points to $4$ points, then with $k=4$ (already assumed), the resulting system of equations is equivalent to multiplying a $k\times k = 4\times 4$ matrix by the vector of coefficients:
$$ \begin{bmatrix} f(x_0) \\ f(x_1)\\ f(x_2)\\ f(x_{3}) \end{bmatrix} = \begin{bmatrix} 1 & x_0 & x_0^2 & x_0^{3} \\ 1 & x_1 & x_1^2 & x_1^{3} \\ 1 & x_2 & x_2^2 & x_2^{3} \\ 1 & x_{3} & x_{3}^2 & x_{3}^{3} \end{bmatrix} \cdot \begin{bmatrix} a_0\\ a_1\\ a_2\\ a_{3} \end{bmatrix}$$This matrix is called a $4\times 4$ Vandermonde matrix and is denoted by $\mathbf{V}$.
The equation above is compactly written below as
$$ \mathbf{p} = \mathbf{V}\cdot\mathbf{a}$$where $\mathbf{a}$ is the vector of the polynomial’s coefficients and $\mathbf{p}$ is the vector of its point values.
Evaluating the polynomial at the 4th roots of unity as a matrix product
Now, consider evaluating the polynomial $f(x)$ at the 4th roots of unity, $\{\omega^0, \omega^1, \omega^{2}, \omega^{3}\}$, instead of at arbitrary $4$ points. We get the Vandermonde matrix $\mathbf{V}$ as:
$$ \mathbf{V} = \begin{bmatrix} 1 & 1^1 & 1^2 & 1^3 \\ 1 & \omega & \omega^2 & \omega^{3} \\ 1 & (\omega^2) & (\omega^2)^2 & (\omega^2)^{3} \\ 1 & (\omega^3) & (\omega^3)^2 & (\omega^3)^{3} \end{bmatrix}$$We can simplify every term that is $\omega^{\frac{k}{2}}$ or greater, by leveraging the properties that $\omega^{\frac{k}{2}} = \omega^2 = -1$ and $\omega^k=1$ as follows:
- $\omega^2 \equiv -1$ imply that $(\omega^2)^2 \equiv (-1)^2 = 1$ and $(\omega^2)^3 \equiv (-1)^3 = -1$.
- $\omega^3 = \omega^2\cdot\omega\equiv -1\cdot\omega = -\omega$ imply that:
- $(\omega^3)^2 \equiv (-\omega)^2 = \omega^2\equiv -1$ and
- $(\omega^3)^3 \equiv (-\omega)^3 = -\omega^3 =-(-\omega) =\omega$.
We now substitute these simplifications into the matrix:
$$ \mathbf{V} = \begin{bmatrix} 1 & 1^1 & 1^2 & 1^3 \\ 1 & \omega & \omega^2\equiv-1 & \omega^{3}\equiv-\omega \\ 1 & (\omega^2)\equiv-1 & (\omega^2)^2\equiv1 & (\omega^2)^{3}\equiv-1 \\ 1 & (\omega^3)\equiv-\omega & (\omega^3)^2\equiv-1 & (\omega^3)^{3}\equiv\omega \end{bmatrix}$$Therefore, the matrix simplifies to the following pattern:
$$ \mathbf{V} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & \omega & -1 & -\omega \\ 1 & -1 & 1 & -1 \\ 1 & -\omega & -1 & \omega \end{bmatrix}$$For a concrete example, $\omega=13$ is a primitive 4th root of unity in the finite field $\mathbb{F}_{17}$ (where arithmetic is modulo 17), and the Vandermonde matrix is:
$$ \mathbf{V} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 13 & 16 & 4 \\ 1 & 16 & 1 & 16 \\ 1 & 4 & 16 & 13 \end{bmatrix}$$Conclusion
Evaluating a polynomial of degree $k-1$ at $k$ points is equivalent to multiplying a $k \times k$ Vandermonde $\mathbf{V}$ matrix by the coefficient vector $\mathbf{a}$, formalized by the equation $\mathbf{V}\cdot\mathbf{a} = \mathbf{p}$.