The Vandermonde Matrix

Proposition 2   Given a set of elements $\{x_1,x_2,...,x_n\}$, a Vandermonde matrix $V_n$ is an $n\times n$ matrix where the $jth$ column is the vector $\left(x^{j-1}_1,x^{j-1}_2,...,x^{j-1}_n\right)^T$ for $j=1,2,...,n$. A formula for the determinant of $V_n$ follows:

$$\textnormal{det}\left(\begin{array}{ccccc} 1&x_1&x^2_1&...&x^n_1\... ...n&...&x^n_n\\ \end{array}\right)=\displaystyle \prod_{1\le i<j\le n}(x_j-x_i)$$

In particular, if $x_1,x_2,...,x_n$ are pairwise disjoint, the determinant is nonzero.

Before exploring the proof, which is due to Cauchy in 1812, we will need the following definitions. (An alternate proof is provided in Appendix 2)

Definition 8   A symmetric polynomial in the variables $x_1,x_2,...,x_n$ is a polynomial that is unchanged by any permutation of these variables.

For example,

$$f(x,y,z)=x^2y+x^2y^2+x^2yz+x^2z+x^2z^2+xy^2+xy^2z+xyz^2+xz^2+ y^2z+y^2z^2+yz^2$$

is a symmetric polynomial in $x$, $y$, and $z$:

$$f(x,y,z)=f(x,z,y)=f(y,z,x)=f(y,x,z)=f(z,x,y)=f(z,y,x)$$

Definition 9   An alternating function is a function that changes sign when we transpose any two of the variables.

For example, take a Vandermonde matrix $V_n$ with the variables $x_1,x_2,...,x_n$.

$$\left(\begin{array}{ccccc} 1&x_1&x^2_1&...&x^n_1\\ 1&x_2&x^2_2&... ...ts&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x^2_n&...&x^n_n\\ \end{array}\right)$$

We can define a function $f(x_1,x_2,...,x_n)=$det$(V_n)$.


Now if we transpose any two variables $x_i$ and $x_j$ we have simply switched two rows of the matrix.

$$\left(\begin{array}{ccccc} 1&x_1&x^2_1&...&x^n_1\\ \vdots&\vdot... ... 1&x_i&x^2_i&...&x^n_i\\ \vdots&\vdots&\vdots&&\vdots\\ \end{array}\right)$$

It follows that $f$ is an alternating function.

The proof of Proposition 1 is a direct consequence of the following lemma.

Lemma 3   If $f(x_1,x_2,...,x_n)$ is an alternating polynomial of degree $d$, then

$$\displaystyle \frac{f(x_1,x_2,...,x_n)}{\prod_{1\le i<j\le n}(x_j-x_i)}$$

is a symmetric polynomial of degree $d-\displaystyle \frac{n(n-1)}{2}$.

Proof. Assume that $i < j$ and transpose the two variables $x_i$ and $x_j$ in the product $\prod_{1\le i<j\le n}(x_j-x_i)$. For all $k$ such that $i<k<j$, the factors $(x_k-x_i)$ and $(x_j-x_k)$ will change sign. Because there are $2(j-i)$ of these terms, the product of all of the new terms will leave the original product unchanged. However, the factor $(x_j-x_i)$ must also change sign and thus the entire new product will change sign. It follows that this product is an alternating function.

Also, since there are $n\choose 2$ ways to group any variable $x_i$ in a factor $(x_i-x_k)$, the product of the factors $(x_j-x_i)$ is a polynomial of degree $n(n-1)/2$.

Next, the quotient of two alternating functions in the same variables is a symmetric function. Therefore,

$$\displaystyle \frac{f(x_1,x_2,...,x_n)}{\prod_{1\le i<j\le n}(x_j-x_i)}$$

is a symmetric function. If we can show that it is a polynomial the proof will be complete.

Consider $f$ as a function in $x_1$. Whenever $x_1=x_k$ we can interchange those two variables and get

$$f(x_k,...,x_k,...,x_n)=-f(x_k,...,x_k,...,x_n)$$

which means that the function $f$ is zero at $x_k$. This gives us $n-1$ distinct roots. Therefore,

$$f(x_1,x_2,...,x_n)=g(x_1,x_2,...,x_n)\displaystyle \prod^{n}_{j=2}(x_1-x_j)$$

where $g$ is a polynomial in $x_1,x_2,...,x_n$. If $n=2$, then

$$g(x_1,x_2)=\displaystyle \frac{f(x_1,x_2)}{x_1-x_2}$$

will be a symmetric polynomial in $x_1$ and $x_2$. Proceeding by induction on the number of variables we consider $g(x_1,x_2,...,x_n)$ as a polynomial in $x_2,...,x_n$ with coefficients expressed in terms of $x_1$. The induction hypothesis gaurantees that $g(x_1,x_2,...,x_n)/\prod_{2\le i<j\le n}(x_1-x_j)$ is a symmetric polynomial in $x_2,...,x_n$. Because the denominator does not involve $x_1$, it is still a polynomial in $x_1$. Therefore we have that

$$\displaystyle \frac{f(x_1,x_2,...,x_n)}{\prod_{1\le i<j\le n}(x_i-x_j)}= \displaystyle \frac{g(x_1,x_2,...,x_n)}{\prod_{2\le i<j\le n}(x_i-x_j)}$$

is a polynomial in $x_1,x_2,...,x_n$.
$\qedsymbol$

Understanding that $f(x_1,x_2,...,x_n)=$det$(V_n)$ is an alternating function, the previous lemma implies that det$(V_n)=C\prod_{1\le i<j\le n}(x_i-x_j)$. To prove Proposition 1, we now must show that $C=1$. This follows after comparing the coefficients on each side of the equality and seeing that for both sides of the equality the coefficient on $x^k_1x^j_2...x^s_n$ is always one. This proves the result of Proposition 1.

Lets look at an easy example. Given the Vandermonde matrix $V_3$ in terms of $a,b,c$, Proposition 1 states that

$$\textnormal{det}\left(\begin{array}{ccc} 1&a&a^2\\ 1&b&b^2\\ ... ...ray}\right)=\displaystyle \prod_{x\in S=\{a<b<c\}}(x_s-x_{s_1})=(c-b)(c-a)(b-a)$$

Using basic properties of determinants we have the following

$$\left(\begin{array}{ccc} 1&a&a^2\\ 1&b&b^2\\ 1&c&c^2\\ \end{array}\right) = \left(\begin{array}{ccc} 1&a&a^2\\ 0&b-a&b^2-a^2\\ 0&c-a&c^2-a^2\\ \end{array}\right)$$

$$= (c-a)(b-a)\; \left(\begin{array}{ccc} 1&a&a^2\\ 0&1&b+a\\ 0&1&c+a\\ \end{array}\right)$$

$$= (c-a)(b-a)\; \left(\begin{array}{ccc} 1&a&a^2\\ 0&1&b+a\\ 0&&c-b\\ \end{array}\right)$$

$$= (c-b)(c-a)(b-a)$$

From the proposition we get the important corollary.

Corollary 2   Given a set of distinct elements $x_1,x_2,...,x_n$, and the Vandermonde matrix $V_n$ with second column equal to $(x_1,x_2,...,x_n)^T$, the determinant det $(V_n)\ne 0$.

The Vandermonde matrix plays an important role when proving certain bounds on the distances of cyclic codes. We will use the result of corollary 2 in the following theorem.