## 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)$.