Compute the Vandermonde determinant

Let F be a field, m \in \mathbb{N}, and \alpha : m+1 \rightarrow F be an injective map. Evaluate the determinant of the Vandermonde matrix

V(\alpha) = [\alpha_i^j]_{i,j = 0}^m =  \left[ \begin{array}{ccccc} 1 & \alpha_0 & \alpha_0^2 & \cdots & \alpha_0^m \\ 1 & \alpha_1 & \alpha_1^1 & \cdots & \alpha_1^m \\ 1 & \alpha_2 & \alpha_2^2 & \cdots & \alpha_2^m \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_m & \alpha_m^2 & \cdots & \alpha_m^m \end{array} \right].

(In this exercise, matrix entries are indexed from 0.)

First, we define a map T^\alpha : (m+1)^3 \rightarrow F recursively as follows.

T^\alpha_0(i,j) = \alpha_i^j

T^\alpha_{t+1}(i.j) = \sum_{k=0}^j \alpha_i^k T^\alpha_t(t,j-k).

Now, for each t < m+1, define a matrix V_t(\alpha) = [T^\alpha_t(i+t,j)]_{i,j = 0}^{m-t}. For example, if t = 0, then V_0(\alpha) = V(\alpha) is just the Vandermonde matrix. For each t \in [0,m], V^\alpha_t is a square matrix with dimension m-t+1.

We will now prove some facts about T that will be useful later.

Lemma 1: T^\alpha_t(i,0) = 1 for all t and i. Proof: We proceed by induction on t. For the base case t = 0, certainly T^\alpha_0(i,0) = \alpha_i^0 = 1. Suppose now the result holds for some t such that t < m and consider t+1. We have T^\alpha_{t+1}(i,0) = \sum_{k=0}^0 \alpha_i^k T^\alpha_t(i,j-k) = \alpha_i^0 T^\alpha_t(i,0) = 1 \cdot 1 = 1. So the result holds for all i and all t \in [0,m]. \square

Lemma 2: For all i,j and all t \in [0,m),

\dfrac{T^\alpha_t(i+1+t,j+1) - T^\alpha_t(t,j+1)}{\alpha_{i+1+t} - \alpha_t} = T^\alpha_{t+1}(i+t+1,j).

Proof: We will prove this directly, handling the cases t = 0 and t \neq 0 separately. For the case t = 0, we have the following.

\dfrac{T^\alpha_0(i+1,j+1) - T^\alpha_0(0,j+1)}{\alpha_{i+1} - \alpha_0}  =  \dfrac{\alpha_{i+1}^{j+1} - \alpha_0^{j+1}}{\alpha_{i+1} - \alpha_0}
 =  \displaystyle\sum_{k=0}^j \alpha_{i+1}^k \alpha_0^{j-k}
 =  \displaystyle\sum_{k=0}^j \alpha_{i+1}^k T^\alpha_0(0,j-k)
 =  T^\alpha_{1}(i+1,j).

As desired. Suppose now that t+1 \neq 0. Then we have the following.

\dfrac{T^\alpha_{t+1}(i+1+t+1,j+1) - T^\alpha_{t+1}(t+1,j+1)}{\alpha_{i+1} - \alpha_{t+1}}
 =  \dfrac{\displaystyle\sum_{k=0}^{j+1} \alpha_{i+1+t+1} T^\alpha_t(t,j+1-k) - \displaystyle\sum_{k=0}^{j+1} \alpha_{t+1}^k T^\alpha_t(t,j+1-k)}{\alpha_{i+1+t+1} - \alpha_{t+1}}
 =  \dfrac{\displaystyle\sum_{k=0}^{j+1} (\alpha_{i+1+t+1}^k - \alpha^k_{t+1}) T^\alpha_t(t,j+1-k)}{\alpha_{i+1+t+1} - \alpha_{t+1}}
 =  \dfrac{\displaystyle\sum_{k=1}^{j+1} (\alpha_{i+1+t+1}^k - \alpha^k_{t+1}) T^\alpha_t(t,j+1-k)}{\alpha_{i+1+t+1} - \alpha_{t+1}}
 =  \displaystyle\sum_{k=1}^{j+1} \left( \dfrac{\alpha_{i+1+t+1}^k - \alpha^k_{t+1}}{\alpha_{i+1+t+1} - \alpha_{t+1}} \right) T^\alpha_t(t,j+1-k)
 =  \displaystyle\sum_{k=0}^{j} \left( \dfrac{\alpha_{i+1+t+1}^{k+1} - \alpha^{k+1}_{t+1}}{\alpha_{i+1+t+1} - \alpha_{t+1}} \right) T^\alpha_t(t,j-k)
 =  \displaystyle\sum_{k=0}^j \displaystyle\sum_{\ell=0}^k \alpha_{i+1+t+1}^\ell \alpha_{t+1}^{k-\ell} T_t^\alpha(t,j-k)
 =  \displaystyle\sum_{\ell=0}^j \displaystyle\sum_{k=\ell}^j \alpha_{i+1+t+1}^\ell \alpha_{t+1}^{k-\ell} T_t^\alpha(t,j-k)
 =  \displaystyle\sum_{\ell=0}^j \alpha_{i+1+t+1}^\ell \displaystyle\sum_{k=\ell}^j \alpha_{t+1}^{k-\ell} T_t^\alpha(t,j-k)
 =  \displaystyle\sum_{\ell=0}^j \alpha_{i+1+t+1}^\ell \displaystyle\sum_{k=0}^{j-\ell} \alpha_{t+1}^{k} T_t^\alpha(t,j-\ell-k)
 =  \displaystyle\sum_{\ell=0}^j \alpha_{i+1+t+1}^\ell T^\alpha_{t+1}(t+1,j-\ell)
 =  T^\alpha_{t+2}(i+t+2,j),

again as desired. So the lemma is proved. \square

Now we claim that, for all t \in [0,m), the matrix V_t(\alpha) is row and column equivalent to \left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & V_{t+1}(\alpha) \end{array} \right]. Moreover, we claim that \mathsf{det}(V_t(\alpha)) = \prod_{i=t+1}^{m}(\alpha_i - \alpha_t) \cdot \mathsf{det}(V_{t+1}(\alpha)). To see this, we will perform row and column operations on V_t(\alpha), keeping track of their effect on the determinant.

By Lemma 1, the first column of V_t(\alpha) consists of all 1s. So for each row i \in [1,m-t), we subtract row 0 from row i. This operation does not affect the determinant. Now the entry in row i+1 and column j+1 is T^\alpha_t(i+1+t,j+1) - T^\alpha_0(t,j+1). Column 0 has a 1 in row 0 and 0 elsewhere, so we may add an appropriate multiple of column 0 to the remaining columns so that row 0 has all 0s except in column 1. Finally, from each row i in [1,m-t] (that is, except the 0th), we divide \alpha_{i+t} - \alpha_t. This has the effect of dividing the determinant by \prod_{i=1}^{m-t} (\alpha_{i+t} - \alpha_t) = \prod_{i=t+1}^m (\alpha_i - \alpha_t). By Lemma 2, the (0,0)-minor matrix is now precisely V_{t+1}(\alpha).

So the determinant of V_t(\alpha) is \prod_{i=t+1}^m (\alpha_i - \alpha_t) times the determinant of \left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & V_{t+1}(\alpha) \end{array} \right], which is precisely the determinant of V_{t+1}(\alpha). Note that V_m(\alpha) = [1], which certainly has determinant 1. By induction, then, \mathsf{det}(V(\alpha)) = \prod_{t=0}^m \prod_{i=t+1}^m (\alpha_i - \alpha_t) = \prod_{0 \leq i < j \leq m} (\alpha_j - \alpha_i).

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: