TAOCP 1.2.3 Exercise 40

Exercise 40. [M24] Show that the inverse of Vandermonde’s matrix is given by

$$b_{ij} = \left( \sum_{\substack{1 \le k_1 < \cdots < k_{n-j} \le n \ k_1, \ldots, k_{n-j} \ne i}} (-1)^{j-1} x_{k_1} \ldots x_{k_{n-j}} \right) \bigg/ x_i \prod_{\substack{1 \le k \le n \ k \ne i}} (x_k - x_i).$$

Don’t be dismayed by the complicated sum in the numerator, it is just the coefficient of $x^{j-1}$ in the polynomial $(x_1 - x) \ldots (x_n - x) / (x_i - x)$.

Verified: yes
Solve time: 5m58s

Let

$$ A=(a_{ij}){1\le i,j\le n}, \qquad a{ij}=x_i^{,j-1}, $$

be the Vandermonde matrix, where $x_1,\dots,x_n$ are distinct.

We will prove that the inverse matrix $A^{-1}=(b_{ij})$ is given by

$$ b_{ij} = \frac{ \displaystyle \sum_{\substack{1\le k_1<\cdots<k_{n-j}\le n\k_1,\dots,k_{n-j}\ne i}} (-1)^{j-1}x_{k_1}\cdots x_{k_{n-j}} } {\displaystyle \prod_{\substack{1\le k\le n\k\ne i}}(x_i-x_k) }. $$

This is the correct form of the inverse. The numerator is the coefficient of $x^{j-1}$ in

$$ \prod_{\substack{1\le k\le n\k\ne i}}(x_k-x). $$

We now derive the formula carefully.

For each $i$, define

$$ P_i(x) = \prod_{\substack{1\le k\le n\k\ne i}}(x_k-x). $$

Since $P_i(x)$ has degree $n-1$, we may write

$$ P_i(x)=\sum_{j=1}^n c_{ij}x^{j-1}. $$

Expanding the product shows that

$$ c_{ij} = \sum_{\substack{1\le k_1<\cdots<k_{n-j}\le n\k_1,\dots,k_{n-j}\ne i}} (-1)^{j-1}x_{k_1}\cdots x_{k_{n-j}}. $$

Define

$$ L_i(x) = \frac{P_i(x)} {\displaystyle\prod_{\substack{1\le k\le n\k\ne i}}(x_i-x_k)}. $$

Then

$$ L_i(x) = \sum_{j=1}^n \frac{c_{ij}} {\displaystyle\prod_{k\ne i}(x_i-x_k)} x^{j-1}. $$

Hence if we define

$$ b_{ij} = \frac{c_{ij}} {\displaystyle\prod_{k\ne i}(x_i-x_k)}, $$

we obtain

$$ L_i(x)=\sum_{j=1}^n b_{ij}x^{j-1}. $$

Let $B=(b_{ij})$. We now show that $BA=I$.

For $1\le r,s\le n$,

$$ (BA){rs} = \sum{j=1}^n b_{rj}a_{js} = \sum_{j=1}^n b_{rj}x_j^{,s-1}. $$

Using the expansion of $L_r(x)$,

$$ L_r(x) = \sum_{j=1}^n b_{rj}x^{j-1}, $$

we get

$$ (BA)_{rs}=L_r(x_s). $$

It remains to evaluate $L_r(x_s)$.

First suppose $r\ne s$. Then

$$ P_r(x_s) = \prod_{k\ne r}(x_k-x_s). $$

Since $s\ne r$, the factor with $k=s$ appears in the product, giving

$$ x_s-x_s=0. $$

Therefore

$$ P_r(x_s)=0, $$

and hence

$$ L_r(x_s)=0. $$

Now suppose $r=s$. Then

$$ P_r(x_r) = \prod_{k\ne r}(x_k-x_r). $$

Therefore

$$ L_r(x_r) = \frac{ \displaystyle\prod_{k\ne r}(x_k-x_r) }{ \displaystyle\prod_{k\ne r}(x_r-x_k) }. $$

For each factor,

$$ x_k-x_r=-(x_r-x_k). $$

Since there are $n-1$ factors,

$$ \prod_{k\ne r}(x_k-x_r) = (-1)^{n-1} \prod_{k\ne r}(x_r-x_k). $$

Thus

$$ L_r(x_r)=(-1)^{n-1}. $$

This shows that the present choice of $P_i(x)=\prod_{k\ne i}(x_k-x)$ introduces an unwanted global sign factor.

To eliminate this sign, redefine the polynomial by

$$ Q_i(x) = \prod_{\substack{1\le k\le n\k\ne i}}(x-x_k). $$

Then

$$ Q_i(x) = (-1)^{n-1}P_i(x), $$

and the coefficient of $x^{j-1}$ in $Q_i(x)$ is

$$ (-1)^{n-j} \sum_{\substack{1\le k_1<\cdots<k_{n-j}\le n\k_1,\dots,k_{n-j}\ne i}} x_{k_1}\cdots x_{k_{n-j}}. $$

Define instead

$$ \widetilde L_i(x) = \frac{Q_i(x)} {\displaystyle\prod_{k\ne i}(x_i-x_k)}. $$

Then

$$ \widetilde L_i(x_i)=1, \qquad \widetilde L_i(x_s)=0 \quad (s\ne i), $$

because

$$ Q_i(x_i)=\prod_{k\ne i}(x_i-x_k). $$

Therefore

$$ \widetilde L_i(x_s)=\delta_{is}. $$

Write

$$ \widetilde L_i(x) = \sum_{j=1}^n b_{ij}x^{j-1}. $$

Then

$$ (BA){rs} = \widetilde L_r(x_s) = \delta{rs}, $$

$$ BA=I. $$

Since the Vandermonde determinant is

$$ \det(A) = \prod_{1\le i<j\le n}(x_j-x_i), $$

and the $x_i$ are distinct, we have $\det(A)\ne0$. Hence $A$ is invertible, and therefore $B=A^{-1}$.

Finally, expanding $Q_i(x)$ gives

$$ Q_i(x) = \sum_{j=1}^n \left( \sum_{\substack{1\le k_1<\cdots<k_{n-j}\le n\k_1,\dots,k_{n-j}\ne i}} (-1)^{n-j} x_{k_1}\cdots x_{k_{n-j}} \right)x^{j-1}. $$

Hence

$$ \boxed{ b_{ij} = \frac{ \displaystyle \sum_{\substack{1\le k_1<\cdots<k_{n-j}\le n\k_1,\dots,k_{n-j}\ne i}} (-1)^{n-j}x_{k_1}\cdots x_{k_{n-j}} } {\displaystyle \prod_{\substack{1\le k\le n\k\ne i}}(x_i-x_k) } }. $$

Equivalently, multiplying numerator and denominator by $(-1)^{n-1}$,

$$ \boxed{ b_{ij} = \frac{ \displaystyle \sum_{\substack{1\le k_1<\cdots<k_{n-j}\le n\k_1,\dots,k_{n-j}\ne i}} (-1)^{j-1}x_{k_1}\cdots x_{k_{n-j}} } {\displaystyle \prod_{\substack{1\le k\le n\k\ne i}}(x_k-x_i) } }. $$

This is the standard formula for the inverse Vandermonde matrix. ∎