Vandermonde Matrices

Last updated on Nov 12, 2025

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_{1} x + a_{2} x^{2} + \dots + a_{k - 1} x^{k - 1}$ with its coefficient representation:

𝐚 = [\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ ⋮ \\ a_{k - 1} \end{matrix}]

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{matrix} f (x_{0}) \end{matrix}] = [\begin{matrix} 1 & x_{0}^{1} & x_{0}^{2} & x_{0}^{3} \end{matrix}] \cdot [\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{matrix}]

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{matrix} f (x_{0}) \\ f (x_{1}) \end{matrix}] = [\begin{matrix} 1 & x_{0}^{1} & x_{0}^{2} & x_{0}^{3} \\ 1 & x_{1}^{1} & x_{1}^{2} & x_{1}^{3} \end{matrix}] \cdot [\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{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:

[\begin{matrix} f (x_{0}) \\ f (x_{1}) \\ f (x_{2}) \\ f (x_{3}) \end{matrix}] = [\begin{matrix} 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{matrix}] \cdot [\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{matrix}]

This matrix is called a $4 \times 4$ Vandermonde matrix and is denoted by $𝐕$ .

The equation above is compactly written below as

𝐩 = 𝐕 \cdot 𝐚

where $𝐚$ is the vector of the polynomial’s coefficients and $𝐩$ 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, ${ω^{0}, ω^{1}, ω^{2}, ω^{3}}$ , instead of at arbitrary $4$ points. We get the Vandermonde matrix $𝐕$ as:

𝐕 = [\begin{matrix} 1 & 1^{1} & 1^{2} & 1^{3} \\ 1 & ω & ω^{2} & ω^{3} \\ 1 & (ω^{2}) & {(ω^{2})}^{2} & {(ω^{2})}^{3} \\ 1 & (ω^{3}) & {(ω^{3})}^{2} & {(ω^{3})}^{3} \end{matrix}]

We can simplify every term that is $ω^{\frac{k}{2}}$ or greater, by leveraging the properties that $ω^{\frac{k}{2}} = ω^{2} = - 1$ and $ω^{k} = 1$ as follows:

$ω^{2} \equiv - 1$ imply that ${(ω^{2})}^{2} \equiv {(- 1)}^{2} = 1$ and ${(ω^{2})}^{3} \equiv {(- 1)}^{3} = - 1$ .
$ω^{3} = ω^{2} \cdot ω \equiv - 1 \cdot ω = - ω$ imply that:
- ${(ω^{3})}^{2} \equiv {(- ω)}^{2} = ω^{2} \equiv - 1$ and
- ${(ω^{3})}^{3} \equiv {(- ω)}^{3} = - ω^{3} = - (- ω) = ω$ .

We now substitute these simplifications into the matrix:

𝐕 = [\begin{matrix} 1 & 1^{1} & 1^{2} & 1^{3} \\ 1 & ω & ω^{2} \equiv - 1 & ω^{3} \equiv - ω \\ 1 & (ω^{2}) \equiv - 1 & {(ω^{2})}^{2} \equiv 1 & {(ω^{2})}^{3} \equiv - 1 \\ 1 & (ω^{3}) \equiv - ω & {(ω^{3})}^{2} \equiv - 1 & {(ω^{3})}^{3} \equiv ω \end{matrix}]

Therefore, the matrix simplifies to the following pattern:

𝐕 = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & ω & - 1 & - ω \\ 1 & - 1 & 1 & - 1 \\ 1 & - ω & - 1 & ω \end{matrix}]

For a concrete example, $ω = 13$ is a primitive 4th root of unity in the finite field $𝔽_{17}$ (where arithmetic is modulo 17), and the Vandermonde matrix is:

𝐕 = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 13 & 16 & 4 \\ 1 & 16 & 1 & 16 \\ 1 & 4 & 16 & 13 \end{matrix}]

Conclusion

Evaluating a polynomial of degree $k - 1$ at $k$ points is equivalent to multiplying a $k \times k$ Vandermonde $𝐕$ matrix by the coefficient vector $𝐚$ , formalized by the equation $𝐕 \cdot 𝐚 = 𝐩$ .