If you find any mistakes, please make a comment! Thank you.

## Special Matrix (8) Vandermonde Matrix

Vandermonde matrices have the following form:
$$A_n=\begin{bmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{bmatrix},$$ where $A_n=[a_{ij}]_{i,j=1}^n$ is an $n\times n$ matrices and the element $a_{ij}=x_i^{j-1}$. The transpose $A_n^T$ is also called a Vandermonde matrix.

Let us compute the determinant of Vandermonde matrix. We start with the simplest case where $n=2$:
$$\det A_2=\begin{vmatrix} 1&x_1\\ 1&x_2 \end{vmatrix}=x_2-x_1.$$Then we consider the case $n=3$. Subtracting the second and third columns by the first column and then expanding the determinant with respect to the first column, we obtain that
\begin{aligned} \det A_3&=\begin{vmatrix} 1&x_1&x_1^2\\ 1&x_2&x_2^2\\ 1&x_3&x_3^2 \end{vmatrix}\\ &=\begin{vmatrix} 1&x_1&x_1^2\\ 0&x_2-x_1&x_2^2-x_1^2\\ 0&x_3-x_1&x_3^2-x_1^2 \end{vmatrix}\\ &=\begin{vmatrix} x_2-x_1&x_2^2-x_1^2\\ x_3-x_1&x_3^2-x_1^2 \end{vmatrix}\\ &=(x_2-x_1)(x_3-x_2)(x_3-x_1).\end{aligned}Now we may guess the determinant of an $n\times n$ Vandermonde matrix is given by the formula:
\begin{equation}\label{eq:1}\det A_n=\displaystyle\prod_{1\le j<i\le n}(x_i-x_j).\end{equation}

We shall prove it by induction. Suppose the $k$-th Vandermonde determinant is given by
$$\det A_k=\displaystyle\prod_{1\le j<i\le k}(x_i-x_j),$$ we would like to show that the $(k+1)$-th Vandermonde determinant has the same form. We replace the last row $[1, x_{k+1}, x_{k+1}^2,\ldots,x_{k+1}^k]^T$ of $A_{k+1}$ with $[1, x, x^2,\ldots, x^{k}]^T$ and denote the determinant of this new matrix by
$$f(x)=\begin{vmatrix} 1&x_1&x_1^2&\cdots&x_1^{k}\\ 1&x_2&x_2^2&\cdots&x_2^{k}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_k&x_k^2&\cdots&x_k^{k}\\ 1&x&x^2&\cdots&x^{k} \end{vmatrix}.$$ Expanding $f(x)$ by the last row, we see that $f(x)$ is a polynomial in $x$ of degree at most $k$.

If a matrix has two rows coincide, then the determinant is zero. Therefore, we conclude that $$f(x_1)=f(x_2)=\cdots=f(x_k)=0.$$In other words, $x_1, x_2,\ldots,x_k$ are the $k$ roots of the polynomial $f(x)$. Therefore, we have
$$f(x)=\alpha(x-x_1)(x-x_2)\cdots(x-x_k).$$Now we only need to determine the constant number $\alpha$, which is also the leading coefficient of $f(x)$. But it also clear that the coefficient of $x^k$ is given by
$$\alpha=\begin{vmatrix} 1&x_1&x_1^2&\cdots&x_1^{k-1}\\ 1&x_2&x_2^2&\cdots&x_2^{k-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_k&x_k^2&\cdots&x_k^{k-1} \end{vmatrix}.$$Note that this determinant expressing $\alpha$ is exactly $\mathrm{det}A_k$. By induction hypothesis, we have
$$\alpha=\displaystyle\prod_{1\le j<i\le k}(x_i-x_j),$$ and hence
$$f(x)=\displaystyle\left[\prod_{1\le j<i\le k}(x_i-x_j)\right](x-x_1)(x-x_2)\cdots(x-x_k)$$Note that $f(x_{k+1})=\mathrm{det}A_{k+1}$, hence we obtain that
$$\det A_{k+1}=f(x_{k+1})=\displaystyle\left[\prod_{1\le j<i\le k}(x_i-x_j)\right](x_{k+1}-x_1)(x_{k+1}-x_2)\cdots(x_{k+1}-x_k).$$Rewriting this equation, we obtain
$$\det A_{k+1}=\displaystyle\prod_{1\le j<i\le k+1}(x_i-x_j),$$completing the proof.

Vandermonde matrix has many important application. Here we give a typical one to the interpolation problem of numerical analysis.

Given $n$ points $(x_i,y_i)，i=1,2,\ldots,n$ with distinct $x$-coordinates, find a polynomial of degree $n-1$
$$p(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_1x+a_0,$$ such that
\begin{aligned} p(x_1)&=a_0+a_1x_1+\cdots+a_{n-1}x_1^{n-1}=y_1\\ p(x_2)&=a_0+a_1x_2+\cdots+a_{n-1}x_2^{n-1}=y_2\\ &\vdots\\ p(x_n)&=a_0+a_1x_n+\cdots+a_{n-1}x_n^{n-1}=y_n.\end{aligned} Rewrite the above system of linear equations in the matrix form $A\mathbf{a}=\mathbf{y}$, where $A$ is the coefficient matrix. It is clear that $A$ is an $n\times n$ Vandermonde matrix. To solve the interpolation problem, it sufficents to solve for the coefficient vector
$$\mathbf{a}=\begin{bmatrix} a_0&a_1&\cdots&a_{n-1}\end{bmatrix}^T.$$
Since all $n$ parameters $x_1,x_2,\ldots,x_n$ are distinct, it follows from \eqref{eq:1} that $\mathrm{det}A_n\neq 0$. This implies that $A$ is invertible, therefore the linear system has a unique solution.

In general, we don't solve for $a_i$ explicitly, we express the polynomial $p(x)$ as a linear combinator of special polynomials, called Lagrange interpolation polynomials, as follows:
$$L_i(x)=\displaystyle\frac{\prod_{j=1,j\neq i}^n(x-x_j)}{\prod_{j=1,j\neq i}^n(x_i-x_j)},~~i=1,2,\ldots,n.$$ Every polynomial $L_i(x)$ is of degree $(n-1)$. Moreover, if $j\neq i$, $L_i(x_j)=0$ but $L_i(x_i)=1$. Use these conditions, we conclude the Lagrange interpolation formula,
$$p(x)=y_1L_1(x)+y_2L_2(x)+\cdots+y_nL_n(x).$$ Clearly, this polynomial $p(x)$ has degree $(n-1)$ and satisfies the given $n$ interpolation conditions, $p(x_i)=y_i$, $i=1,2,\ldots,n$.