Inverse of Vandermonde Matrix/Eisinberg Formula

From ProofWiki
Jump to navigation Jump to search

Theorem

Let:

\(\ds \prod_{k \mathop = 1}^n \paren {x - x_k}\) \(=\) \(\ds a_nx^n + \sum_{m \mathop = 0}^{n-1} a_m x^m\) Polynomial expansion in powers of $x$
\(\ds \) \(=\) \(\ds x^n + \sum_{m \mathop = 0}^{n - 1} \paren {-1}^{n - m} \map {e_{n-m} } {x_1, \ldots, x_n} \, x^m\) Viete's Formulas and Definition of Elementary Symmetric Function
\(\ds W_n\) \(=\) \(\ds \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}\) Definition of Vandermonde Matrix of Order $n$

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

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

Then:

\(\text {(1)}: \quad\) \(\ds d_{ij}\) \(=\) \(\ds \dfrac {\ds \sum_{k \mathop = 0}^{n - i} a_{i + k} \, x_j^k} {\ds \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }\) for $i, j = 1, \ldots, n$
\(\ds \) \(=\) \(\ds \dfrac {\ds \sum_{k \mathop = 0}^{n - i} \paren {-1}^{n - i - k} \map {e_{n - i - k} } {x_1, \ldots, x_n} \, x_j^k} {\ds \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 \le m \le p$, then:

\(\text {(2)}: \quad\) \(\ds \ds \map {e_m} {z_1, \ldots, z_p, z_{p + 1} }\) \(=\) \(\ds 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:

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

Proof of Lemma 2:

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

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

Then:

\(\ds S\) \(=\) \(\ds \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\) splitting off the term for $k = n - i$
\(\ds \) \(=\) \(\ds \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$
\(\ds \) \(=\) \(\ds \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\) reassembling summations
\(\ds \) \(=\) \(\ds \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\) reindexing the first sum
\(\ds \) \(=\) \(\ds \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\) splitting off the term for $k = 0$ and collecting under one summation
\(\ds \) \(=\) \(\ds \map {e_{n-i} } U\)

$\Box$


Proof of the Theorem

\(\ds d_{ij}\) \(=\) \(\ds \dfrac {\ds \paren {-1}^{n - i} \map { e_{n - i} } {X \setminus \set {x_j} } } {\ds \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }\) transposing $W_n$, then applying corollary to Inverse of Vandermonde Matrix
\(\ds \) \(=\) \(\ds \dfrac {\ds \sum_{k \mathop = 0}^{n - i} \paren {-1}^k \, \map {e_{n - i - k} } X \, x_j^k} {\ds \prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }\) $(3)$ in Lemma 2
\(\ds \) \(=\) \(\ds \dfrac {\ds \sum_{k \mathop = 0}^{n - i} a_{i + k} \, x_j^k} {\ds \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=513528"