Inverse of Vandermonde Matrix

From ProofWiki
Jump to: navigation, search

Theorem

Let $V_n$ be the Vandermonde matrix of order $n$ given by:

$V_n = \begin{bmatrix} x_1 & x_2 & \cdots & x_n \\ x_1^2 & x_2^2 & \cdots & x_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_1^n & x_2^n & \cdots & x_n^n \end{bmatrix}$


Then its inverse $V_n^{-1} = \left[{b}\right]_n$ can be specified as:

$b_{i j} = \begin{cases} \left({-1}\right)^{j-1} \left({\dfrac{\displaystyle \sum_{\substack{1 \mathop \le m_1 \mathop < \ldots \mathop < m_{n-j} \mathop \le n \\ m_1, \ldots, m_{n-j} \mathop \ne i} } x_{m_1} \cdots x_{m_{n-j}} } {x_i \displaystyle \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne i} } \left({x_m - x_i}\right)}}\right) & : 1 \le j < n \\ \qquad \qquad \qquad \dfrac 1 {x_i \displaystyle \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne i} } \left({x_i - x_m}\right)} & : j = n \end{cases}$


Proof

First consider the classical form of the Vandermonde matrix:

$W_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 & \ddots & \vdots \\ 1& x_n & x_n^2 & \cdots & x_n^{n-1} \\ \end{bmatrix}$

By Vandermonde Determinant, the determinant of $W_n$ is:

$\displaystyle \det \left({W_n}\right) = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_i - x_j}\right) \ne 0$

Since this is non-zero, by Matrix is Invertible iff Determinant has Multiplicative Inverse, the inverse matrix, denoted $B = \left[{b_{ij}}\right]$, is guaranteed to exist.

Using the definition of the matrix product and the inverse:

$\displaystyle \sum_{k \mathop = 1}^n b_{kj} x_i^{k-1} = \delta_{ij}$

That is, if $P_j \left({x}\right)$ is the polynomial:

$\displaystyle P_j \left({x}\right) := \sum_{k \mathop = 1}^n b_{kj}x^{k-1}$

then:

$P_j \left({x_1}\right) = 0, \ldots, P_j \left({x_{j-1}}\right) = 0, P_j \left({x_j}\right) = 1, P_j \left({x_{j+1}}\right) = 0, \ldots, P_j \left({x_n}\right) = 0$


By the Lagrange Interpolation Formula, the $j$th row of $B$ is composed of the coefficients of the $j$th Lagrange basis polynomial:

$\displaystyle P_j \left({x}\right) = \sum_{k \mathop = 1}^n b_{kj} x^{k-1} = \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j}} \frac {x - x_m} {x_j - x_m}$


Identifying the $k$th order coefficient in these two polynomials yields:

$b_{k j} = \begin{cases} \left({-1}\right)^{n - k} \left({\dfrac{\displaystyle \sum_{\substack{1 \mathop \le m_1 \mathop < \ldots \mathop < m_{n-k} \mathop \le n \\ m_1, \ldots, m_{n-k} \mathop \ne j} } x_{m_1} \cdots x_{m_{n-k}} } {\displaystyle \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \left({x_j - x_m}\right)}}\right) & : 1 \le k < n \\ \qquad \qquad \qquad \dfrac 1 {\displaystyle \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \left({x_j - x_m}\right)} & : k = n \end{cases}$

which gives:

$b_{kj} = \begin{cases} \left({-1}\right)^{k - 1} \left({\dfrac{\displaystyle \sum_{\substack{1 \mathop \le m_1 \mathop < \ldots \mathop < m_{n-k} \mathop \le n \\ m_1, \ldots, m_{n-k} \mathop \ne j} } x_{m_1} \cdots x_{m_{n-k}} } {\displaystyle \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \left({x_m - x_j}\right)}}\right) & : 1 \le k < n \\ \qquad \qquad \qquad \dfrac 1 {\displaystyle \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \left({x_j - x_m}\right)} & : k = n \end{cases}$


For the general case, we observe that by simple multiplication:

$\displaystyle V_n = \begin{pmatrix} \begin{bmatrix} x_1 & 0 & \cdots & 0 \\ 0 & x_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & x_n \end{bmatrix} \cdot W_n \end{pmatrix}^\intercal$

So by Inverse of Matrix Product and Inverse of Diagonal Matrix:

$\displaystyle V_n^{-1} = \begin{bmatrix} x_1^{-1} & 0 & \cdots & 0 \\ 0 & x_2^{-1} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & x_n^{-1} \end{bmatrix} \cdot \left({W_n^{-1} }\right)^\intercal$


Let $c_{k j}$ denote the $\left({k, j}\right)$th coefficient of $V_n^{-1}$.

Since the first matrix in the product expression for $V_n^{-1}$ above is diagonal:

$c_{kj} = \dfrac 1 {x_k} b_{j k}$

which establishes the result.

$\blacksquare$


Sources