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:

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:

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:

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:

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:

This matrix is called a $4\times 4$ Vandermonde matrix and is denoted by $\mathbf{V}$.

The equation above is compactly written below as

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:

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:

Therefore, the matrix simplifies to the following pattern:

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:

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}$.