TAOCP 1.2.3 Exercise 43
Let $V = (v_{ij})$ be the $n \times n$ Vandermonde matrix with entries $v_{ij} = x_i^{j-1}$ for $1 \le i, j \le n$, and let $B = (b_{ij})$ denote its inverse.
Section 1.2.3: Sums and Products
Exercise 43. [M24] What is the sum of all $n^2$ elements in the inverse of Vandermonde’s matrix? [Hint: Use exercise 33.]
Verified: yes
Solve time: 39s
Solution
Let $V = (v_{ij})$ be the $n \times n$ Vandermonde matrix with entries $v_{ij} = x_i^{j-1}$ for $1 \le i, j \le n$, and let $B = (b_{ij})$ denote its inverse. By Exercise 40, each element of $B$ is given by
$$ b_{ij} = \frac{\displaystyle \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} \cdots x_{k_{n-j}}}{x_i \prod_{\substack{1 \le k \le n \ k \ne i}} (x_i - x_k)}. $$
We are asked to compute
$$ S := \sum_{i=1}^n \sum_{j=1}^n b_{ij}. $$
Let us denote the $i$th Lagrange interpolation polynomial associated with nodes $x_1, \dots, x_n$ by
$$ \ell_i(x) := \prod_{\substack{1 \le k \le n \ k \ne i}} \frac{x - x_k}{x_i - x_k}. $$
By the standard formula for the inverse of a Vandermonde matrix, the $j$th coefficient of $\ell_i(x)$ in the monomial basis is exactly $b_{ij}$; that is,
$$ \ell_i(x) = \sum_{j=1}^n b_{ij} x^{j-1}. $$
Hence, summing over $j$ yields
$$ \sum_{j=1}^n b_{ij} = \ell_i(1). $$
Consequently, the total sum is
$$ S = \sum_{i=1}^n \sum_{j=1}^n b_{ij} = \sum_{i=1}^n \ell_i(1). $$
Now consider the Lagrange interpolation property for the constant function $f(x) = 1$. By definition of $\ell_i(x)$, we have
$$ f(x) = 1 = \sum_{i=1}^n f(x_i) \ell_i(x) = \sum_{i=1}^n 1 \cdot \ell_i(x) = \sum_{i=1}^n \ell_i(x), $$
which holds for all $x$. In particular, evaluating at $x = 1$, we obtain
$$ \sum_{i=1}^n \ell_i(1) = 1. $$
Thus the sum of all elements of $B$ is
$$ S = 1. $$
This completes the proof.
∎