Inverse of Vandermonde Matrix/Eisinberg Formula

From ProofWiki
Jump to navigation Jump to search

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).


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Inverse_of_Vandermonde_Matrix/Eisinberg_Formula&oldid=437200"