Talk:Inverse of Vandermonde Matrix

From ProofWiki
Jump to navigation Jump to search

March and May 2015

The matrix $V_n$ is $n \times n$ and the matrix $W_n$ is $(n+1) \times (n+1)$... You can't write $V_n = diag(x_i) W_n$ with $i = 1, ..., n $. --Ostrogradsky (talk) 14:16, 12 March 2015 (UTC)

Good call. I'll put a maintenance tag on it as that needs to be addressed. Thanks. --prime mover (talk) 17:04, 12 March 2015 (UTC)

I would be very grateful if someone could check for mistakes in the changes that I've made although I've looked really carefully and checked results with MATLAB. One can never be too certain--Riddler (talk) 21:55, 11 May 2015 (UTC)

Okay, thx -- I'll go over it in due course and give it a rewrite so as to put it back into its original form (as found in Knuth). --prime mover (talk) 22:03, 11 May 2015 (UTC)

Proposed new proof 2017

The current proof is hard to read, so I wrote up a simpler one. Haven't contributed to proofwiki before, so I decided to go easy and just put it here on the talk page. If nobody objects or otherwise instructed, then I'll replace the old proof after some time. An admin could do naturally do it right away if all's good. -- User:Tbackstr 4.1.2017

PLEASE NOTE: We never replace proofs with new ones unless the old proof is defective. We add new proofs, so that a given theorem may have more than one proof assigned to it.
Please feel free to browse $\mathsf{Pr} \infty \mathsf{fWiki}$ -- you will, sooner or later, find one or two theorems with multiple proofs. Then you will see how it is arranged. --prime mover (talk) 15:26, 4 January 2017 (EST)

Theorem

Let $V$ be the Vandermonde matrix of order $n$ given by:

$V = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_n \\ x_1^2 & x_2^2 & \cdots & x_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1} \end{bmatrix}$

Then its inverse $V^{-1} = B$ can be specified as:

$\ds B_{k, h} = \paren {-1}^{h - 1} \frac {\ds \sum_{\substack {1 \le m_1 < m_2 < \cdots < m_{N + 1 - h} \le N \\ m_i \ne k} } x_{m_1} x_{m_2} \cdots x_{N + 1 - h} } {\ds \prod_{\substack {i \mathop = 1 \\ i \ne h} }^N \paren {x_i - x_h} }$

The inverse exists if $x_k\neq x_h$ for all $k\neq h$.

Proof

We will proceed in two steps, 1. create a matrix which diagonalizes $V$ when multiplied from the left and 2. scale the diagonal matrix to unity.

Define matrices $A_k(z)$ with coefficients $a_{k,l}$ such that they have the zeros $x_h$, for all $h$ except $h=k$:

$\ds A_k(z) := \sum_{h=1}^N a_{k,h} z^{h-1} := \prod_{\substack{h=1\\h\neq k}}^N (x_h - z).$

where the coefficients are defined as

$\ds a_{k, h} := \paren {-1}^{h - 1} \sum_{\substack {1\le m_1 < m_2 < \cdots < m_{N + 1 - h} \le N \\ m_i \ne k} } x_{m_1} x_{m_2} \cdots x_{N + 1 - h}$

It follows the $\map {A_k} {x_h} = 0$ for all $h \ne k$ and if $A$ is the matrix with coefficients $a_{k, l}$, then

$A V = \begin {bmatrix} \map {A_1} {x_1} & 0 & \cdots & 0 \\ 0 & \map {A_2} {x_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \map {A_n} {x_n} \end {bmatrix}$

By defining a diagonal matrix $D$ as:

$D = \begin {bmatrix} \map {A_1^{-1} } {x_1} & 0 & \cdots & 0 \\ 0 & \map {A_2^{-1} } {x_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \map {A_n^{-1} } {x_n} \end{bmatrix}$

we can define the inverse as

$B := D A$

Note that the scalar inverses in $D$ exist if $\map {A_k} {x_k} \ne 0$, that is, if $x_k \ne x_h$ for all $k \ne h$.

Since the determinant of $V$ is

$\map \det V = \prod_{1 \le i < j \le n} \paren {x_j - x_i}$

then $D$ is well-defined and the inverse exists only if $\map \det V \ne 0$.

Sources

  • Klinger, Allen. "The vandermonde matrix." The American Mathematical Monthly 74.5 (1967): 571-574.
  • Macon, Nathaniel, and Abraham Spitzbart. "Inverses of Vandermonde matrices." The American Mathematical Monthly 65.2 (1958): 95-100.
  • Tou, J. "Determination of the inverse Vandermonde matrix." IEEE Transactions on Automatic Control 9.3 (1964): 314-314.

October-November 2019

The statement of the theorem is missing the hypothesis of distinct values. The proof finds the inverse of $W_n$, then finds the inverse of $V_n$ by matrix multiply. The Theorem could contain the inverse identities for both $W_n$ and $V_n$. --Gbgustafson (talk) 06:00, 28 October 2019 (EDT)

Below is a Corollary statement that collects the results actually proved and uses the elementary symmetric functions. The original proof applies and there is no need to edit anything. The symbol $b_{ij}$ matches use in the original proof. Overloading of the symbol in the original proof is a reader's toil, avoided in the Corollary by adding a separate symbol.--Gbgustafson (talk) 07:10, 1 November 2019 (EDT)

My plan: insert the corollary as Inverse of Vandermonde Matrix/Corollary 1 and edit Inverse of Vandermonde Matrix with an include. No proof details to be added. The last two references above by User:Tbackstr 4.1.2017 will be added to Inverse of Vandermonde Matrix.--Gbgustafson (talk) 07:14, 1 November 2019 (EDT)

Corollary 1, Nov 2019

Define for variables $\set {y_1, \ldots, y_k}$ elementary symmetric functions:

\(\ds \map {e_m} {\set {y_1, \ldots, y_k} }\) \(=\) \(\ds \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le k} y_{j_1} y_{j_2} \cdots y_{j_m}\) for $m = 0, 1, \ldots, k$

Let $\set {x_1, \ldots, x_n}$ be a set of distinct values.

Let $W_n$ and $V_n$ be Vandermonde matrices of order $n$:

$W_n = \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},\quad V_n = \begin{bmatrix} x_1 & x_2 & \cdots & x_n \\ x_1^2 & x_2^2 & \cdots & x_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_1^n & x_2^n & \cdots & x_n^n \\ \end{bmatrix}$

Let matrix inverses be written as

$W_n^{-1} = \begin {bmatrix} b_{ij} \end {bmatrix}$

and

$V_n^{-1} = \begin {bmatrix} c_{ij} \end {bmatrix}$

Then:

\(\ds b_{ij}\) \(=\) \(\ds \dfrac {\paren {-1}^{n - i} \map {e_{n - i} } {\set {x_1, \ldots, x_n} \setminus \set {x_j} } } {\prod_{m \mathop = 1, m \mathop \ne j }^n \paren {x_j - x_m} }\) for $i, j = 1, \ldots, n$
\(\ds c_{ij}\) \(=\) \(\ds \dfrac 1 {x_i} \, b_{ji}\) for $i, j = 1, \ldots, n$
Corollary inserted to Inverse of Vandermonde Matrix--Gbgustafson (talk) 10:14, 6 November 2019 (EST)

6 Nov 2019: The issue with proof hard to read might be fixed by changing the few proof displays that look like

$b_{k j} = \begin{cases} \paren {-1}^{n - k} \paren {\dfrac {\ds \sum_{\substack {1 \mathop \le m_1 \mathop < \ldots \mathop < m_{n - k} \mathop \le n \\ m_1, \ldots, m_{n - k} \mathop \ne j} } x_{m_1} \cdots x_{m_{n - k} } } {\ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \paren {x_j - x_m} } } & : 1 \le k < n \\ \qquad \qquad \qquad \dfrac 1 {\ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \paren {x_j - x_m} } & : k = n \end{cases}$

into:

$b_{kj} = \paren {-1}^{n - k} \dfrac {e_{n - k} \paren {\set {x_1, \ldots, x_n} \setminus \set {x_j} } } {\ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne j} } \paren {x_j - x_m} }$

The formulas in the above displays compared to the Theorem have an apparent sign error at first glance, however, the denominator products are different. Knuth explains his choice of signs in Problem 38. The cases in the proof arise by trying to match Knuth's formula for $b_{ij}$.--Gbgustafson (talk) 10:14, 6 November 2019 (EST)

9 Nov 2019: I propose minor proof changes to make it easier to read:--Gbgustafson (talk) 04:50, 9 November 2019 (EST)

existing: Identifying the kth order coefficient in these two polynomials yields:
change to: Match the kth order coefficient in these two polynomials:
Change the first (unreadable) display of $b_{ij}$ to:
$b_{ij} = \paren {-1}^p \map {e_p} U$ Definition:Elementary Symmetric Function and Viète's Formulas
existing: Second huge display for $b_{ij}$
change to: Lines of text, because the Theorem provides the display.

Knuth's equation for $b_{ij}$ emphasizes symmetric functions, but the formulas have problems in edge cases --Linus44 (talk) 23:20, 12 October 2012 (UTC). The 2012-2015 decision to change Knuth's text to the current Theorem appears to be correct.--Gbgustafson (talk) 04:50, 9 November 2019 (EST)

28 Nov 2019: The request Riddler (talk) 21:55, 11 May 2015 (UTC) to look for errors has unearthed one more:

Overloaded symbol $b_{ij}$ in the proof conflicts with Knuth's statement of the result (1997). Matrix $B$ is never used in the proof. Proposed minor edit of Proof 1:
1. Erase matrix symbol $B$ from Proof 1 (it is never used).
2. Replace $b_{}$ by $d_{}$, all Proof 1 occurences.
3. Replace $c_{kj}$ by $b_{kj}$ on the last line of Proof 1, to agree with Knuth (1997).

What do you think? --Gbgustafson (talk) 03:37, 28 November 2019 (EST)