TAOCP 5.1.4 Exercise 18

Section 5.1.4: Tableaux and Involutions

Exercise 18. [HM30] Generalizing exercise 17, evaluate the sum

$$x_1^m, \Delta(y, x_2, \ldots, x_n) + x_2^m, \Delta(x_1, x_2, \ldots, x_n) + \cdots + x_n^m, \Delta(x_1, x_2, \ldots, x_{n-1}, y),$$

when $m \ge 0$.

Verified: yes
Solve time: 1h24m

Setup

Let $\Delta(x_1,\dots,x_n)$ denote the Vandermonde determinant
$$\Delta(x_1,\dots,x_n) = \prod_{1\le i<j\le n} (x_j - x_i).$$
We are to evaluate, for $m\ge 0$, the sum
$$S_m = \sum_{i=1}^n x_i^m ,\Delta(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_n).$$

Solution

Consider the Vandermonde matrix
$$V = \begin{pmatrix} 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 & & \vdots \ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{pmatrix},$$ whose determinant is $\det V = \Delta(x_1,\dots,x_n)$.
For a fixed $i$, replacing the $i$-th row of $V$ by $(1, y, y^2, \dots, y^{n-1})$ yields a matrix whose determinant is exactly $\Delta(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_n)$.

Let $C_{ij}$ be the cofactor of the entry in row $i$, column $j$ of $V$. Expanding the determinant with the modified row along that row gives
$$\Delta(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_n) = \sum_{j=1}^n y^{j-1} C_{ij}.$$

Now substitute this into $S_m$: \begin{align*} S_m &= \sum_{i=1}^n x_i^m \sum_{j=1}^n y^{j-1} C_{ij} = \sum_{j=1}^n y^{j-1} \sum_{i=1}^n x_i^m C_{ij}. \end{align*} For a fixed $j$, the inner sum $\sum_i x_i^m C_{ij}$ is the determinant of the matrix obtained from $V$ by replacing its $j$-th column with the column vector $(x_1^m,\dots,x_n^m)^{\mathsf T}$.

Case $m < n$. Then $(x_i^m)$ is exactly the $(m+1)$-st column of $V$ (columns are indexed from $1$ to $n$ corresponding to powers $0$ to $n-1$). Replacing the $j$-th column by this vector gives a matrix with two identical columns unless $j = m+1$, in which case the matrix is $V$ itself. Hence $$\sum_i x_i^m C_{ij} = \Delta(x_1,\dots,x_n),\delta_{j,,m+1}.$$ Therefore $$S_m = y^m \Delta(x_1,\dots,x_n) \qquad (0 \le m < n).$$

Case $m \ge n$. The vector $(x_i^m)$ is not a column of $V$. However, since each $x_i$ satisfies the polynomial $$P_n(t) = \prod_{i=1}^n (t - x_i) = t^n - e_1 t^{n-1} + e_2 t^{n-2} - \cdots + (-1)^n e_n,$$ where $e_k$ are the elementary symmetric polynomials in $x_1,\dots,x_n$, we have $x_i^m = r_m(x_i)$ where $r_m$ is the remainder upon dividing $t^m$ by $P_n(t)$. The remainder $r_m(t)$ is a polynomial of degree $< n$. Because the columns $1, t, \dots, t^{n-1}$ form a basis for polynomials of degree $< n$, the vector $(x_i^m)$ is the same linear combination of the columns of $V$ as the vector $(r_m(x_i))$. Consequently, $$\sum_{i=1}^n x_i^m C_{ij} = \sum_{i=1}^n r_m(x_i) C_{ij}$$ for every $j$. Arguing as in the $m < n$ case, but now with the coefficients of $r_m(t) = \sum_{k=0}^{n-1} c_k t^k$, we obtain $$\sum_{i=1}^n r_m(x_i) C_{ij} = c_{j-1} \Delta(x_1,\dots,x_n).$$ Thus $$S_m = \Delta(x_1,\dots,x_n) \sum_{j=1}^n c_{j-1} y^{j-1} = \Delta(x_1,\dots,x_n) , r_m(y).$$

In summary, $S_m$ equals the Vandermonde product times the unique polynomial $r_m(y)$ of degree $< n$ that interpolates $y^m$ at the points $y = x_1,\dots,x_n$. Equivalently, $r_m(y)$ is the remainder of $y^m$ upon division by $\prod_{i=1}^n (y - x_i)$. The Lagrange form of this polynomial is $$r_m(y) = \sum_{i=1}^n x_i^m \prod_{j\neq i} \frac{y - x_j}{x_i - x_j}.$$

Verification

Test with $n=3$, $x_1=0$, $x_2=1$, $x_3=2$. Then $\Delta(x) = (1-0)(2-0)(2-1)=2$.

• $m=0$: $S_0 = \Delta(y,1,2)+\Delta(0,y,2)+\Delta(0,1,y)$ $= (1-y)(2-y) + y(2-y)\cdot2 + y(y-1) = 2 = y^0\Delta(x)$.
• $m=1$: $S_1 = 0 + 1\cdot(4y-2y^2) + 2\cdot(y^2-y) = 2y = y^1\Delta(x)$.
• $m=2$: $S_2 = 0 + 1\cdot(4y-2y^2) + 4\cdot(y^2-y) = 2y^2 = y^2\Delta(x)$.
• $m=3$: $P_3(t) = t(t-1)(t-2) = t^3 - 3t^2 + 2t$, so $t^3 \equiv 3t^2 - 2t \pmod{P_3}$.
  $r_3(y) = 3y^2 - 2y$.
  Direct computation: $S_3 = 0 + 1\cdot(4y-2y^2) + 8\cdot(y^2-y) = 6y^2-4y = 2(3y^2-2y) = \Delta(x),r_3(y)$.

All tests agree with the derived formula. ∎

Notes

The result can also be written as a determinant:
$$S_m = (-1)^{n-1} \det\begin{pmatrix} 1 & y & y^2 & \cdots & y^{n-1} & 0 \ 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} & x_1^m \ \vdots & \vdots & \vdots & & \vdots & \vdots \ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} & x_n^m \end{pmatrix}.$$