# Inverse of Vandermonde Matrix/Eisinberg Formula

## Theorem

Let:

 $\displaystyle \prod_{k = 1}^n \paren { x - x_k }$ $=$ $\displaystyle a_nx^n + \sum_{m=0}^{n-1} a_mx^m$ Polynomial expansion in powers of $x$. $\displaystyle$ $=$ $\displaystyle x^n + \sum_{m=0}^{n-1} \paren {-1}^{n-m} \map {e_{n-m} } { x_1,\ldots,x_n } \, x^m$ Viete's Formulas and Definition:Elementary Symmetric Function $\displaystyle W_n$ $=$ $\displaystyle \begin{bmatrix} 1 & x_1 & \cdots & x_1^{n-1} \\ 1 & x_2 & \cdots & x_2^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_1^{n-1} & \cdots & x_n^{n-1} \\ \end{bmatrix}$ Vandermonde matrix of order $n$

Assume $W_n$ has a matrix inverse $W_n^{-1} = \begin{bmatrix} d_{ij} \end{bmatrix}$.

Assume $a_n=\map {e_0} {x_1,\ldots,x_n} = 1$.

Then:

 $(1):\quad$ $\displaystyle d_{ij}$ $=$ $\displaystyle \dfrac {\displaystyle \sum_{k \mathop = 0}^{n-i} a_{i+k} \, x_j^k } { \displaystyle \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }$ for $i,j=1,\ldots,n$ $\displaystyle$ $=$ $\displaystyle \dfrac{\displaystyle \sum_{k \mathop = 0}^{n-i} \paren {-1}^{n-i-k} \map { e_{n-i-k} } { x_1,\ldots,x_n } \, x_j^k } {\displaystyle \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }$ for $i,j=1,\ldots,n$

## Proof

### Lemma 1

Given values $z_1,\ldots,z_{p+1}$ and $1 \leq m \leq p$, then:

 $(2):\quad$ $\displaystyle \displaystyle \map {e_m} { z_1,\ldots,z_p,z_{p+1} }$ $=$ $\displaystyle z_{p+1} \map { e_{m-1} } { z_1,\ldots,z_p } + \map { e_m } { z_1,\ldots,z_p }$ Elementary Symmetric Function/Examples/Recursion

$\Box$

### Lemma 2

Let $X = \set { x_1,\ldots,x_n }$ and ${\mathbf u} = x_j$ for some $j=1,\ldots,n$.

Then:

 $(3):\quad$ $\displaystyle \displaystyle \sum_{k \mathop = 0}^{n-i} \paren {-1}^k \, \map { e_{n-i-k} } { X } \, {\mathbf u}^k$ $=$ $\displaystyle \map {e_{n-i} } {X \setminus \paren { {\mathbf u} } }$ Eisinberg (1981)

Proof of Lemma 2:

Let $S$ denote the left side of (3).

Let $U = X \setminus \set { {\mathbf u} }$.

Then:

 $\displaystyle S$ $=$ $\displaystyle \displaystyle \paren { -1 }^{n-i} {\mathbf u} ^{n-i} + \sum_{k \mathop = 0}^{n-i-1} \paren {-1}^k \map { e_{n-i-k} } { X } {\mathbf u} ^k$ Split off the term for $k = n-i$. $\displaystyle$ $=$ $\displaystyle \displaystyle \paren { -1 }^{n-i} \, {\mathbf u}^{n-i} + \sum_{k \mathop = 0}^{n-i-1} \paren {-1}^k \, \paren { {\mathbf u} \map { e_{n-i-k-1} } { U } + \map { e_{n-i-k} } { U } } \, {\mathbf u} ^k$ by (2) in Lemma 1 with $p=n-1$ and $m=n-i-k$ $\displaystyle$ $=$ $\displaystyle \displaystyle \sum_{k \mathop = 0}^{n-i-1} \paren {-1}^k \, \map { e_{n-i-k-1} } { U } {\mathbf u} ^{k+1} + \sum_{k \mathop = 0}^{n-i} \paren {-1}^k \map { e_{n-i-k} } { U } \, {\mathbf u} ^k$ Reassemble summations. $\displaystyle$ $=$ $\displaystyle \displaystyle \sum_{k \mathop = 1}^{n-i} \paren {-1}^{k-1} \, \map { e_{n-i-k} } { U } {\mathbf u} ^{k} + \sum_{k \mathop = 0}^{n-i} \paren {-1}^k \map { e_{n-i-k} } { U } \, {\mathbf u} ^k$ Reindex the first sum. $\displaystyle$ $=$ $\displaystyle \displaystyle \sum_{k \mathop = 1}^{n-i} \paren {-1}^{k} \paren { -\map { e_{n-i-k} } { U } + \map { e_{n-i-k} } { U } } {\mathbf u} ^k + \paren {-1}^0 \map { e_{n-i} } { U } {\mathbf u} ^0$ Split off the term for $k=0$, then collect under one summation. $\displaystyle$ $=$ $\displaystyle \displaystyle \map { e_{n-i} } { U }$ Summation equals zero. Equation (3) holds.

$\Box$

Proof of the Theorem

 $\displaystyle d_{ij}$ $=$ $\displaystyle \dfrac{\displaystyle \paren {-1}^{n-i} \map { e_{n-i} } { X \setminus \set {x_j} } } {\displaystyle \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }$ transpose $W_n$, then apply Knuth's 1997 Vandermonde inverse formula $\displaystyle$ $=$ $\displaystyle \dfrac {\displaystyle \sum_{k \mathop = 0}^{n-i} \paren {-1}^k \, \map { e_{n-i-k} } { X } \, x_j^k } { \displaystyle \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }$ (3) in Lemma 2 $\displaystyle$ $=$ $\displaystyle \dfrac {\displaystyle \sum_{k \mathop = 0}^{n-i} a_{i+k} \, x_j^k } { \displaystyle \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }$ Viete's Formulas

$\blacksquare$

## Historical Note

The Knuth Vandermonde inverse formula requires $n^2$ symmetric functions $\map {e_m} { \set {x_1,\ldots,x_n} \setminus \set {x_j} }$. Eisinberg and Picardi (1981) Vandermonde inverse formula (1) above is perhaps the first to use just $n$ elementary symmetric functions. The formula was revisited in Eisinberg and Fedele (2005), providing a concise proof without IBM Selectric typewriter fonts. Key identity (3) in Lemma 2 above is used in both references, isolated in Eisinberg, Franz and Pugliese (1998) as identity (8).