Sum of Elements in Inverse of Vandermonde Matrix
This article needs to be tidied. Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code. |
Theorem
Let $V_n$ be the Vandermonde matrix of order $n$ given by:
- $V_n = \begin{pmatrix}
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{pmatrix}$
Let $V_n^{-1}$ be its inverse, from Inverse of Vandermonde Matrix:
- $b_{i j} = \begin {cases}
\paren {-1}^{j - 1} \paren {\dfrac {\ds \sum_{\substack {1 \mathop \le m_1 \mathop < \ldots \mathop < m_{n - j} \mathop \le n \\ m_1, \ldots, m_{n - j} \mathop \ne i} } x_{m_1} \cdots x_{m_{n - j} } } {x_i \ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne i} } \paren {x_m - x_i} } } & : 1 \le j < n \\ \qquad \qquad \qquad \dfrac 1 {x_i \ds \prod_{\substack {1 \mathop \le m \mathop \le n \\ m \mathop \ne i} } \paren {x_i - x_m} } & : j = n \end{cases}$
The sum of all the elements of $V_n^{-1}$ is:
- $\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = 1 - \prod_{k \mathop = 1}^n \paren {1 - \dfrac 1 {x_k} }$
Proof
From Sum of Elements of Invertible Matrix, the sum of elements in $V_n^{-1}$ is:
- $1 - \map \det {V_n^{-1} } \map \det {V_n - J_n}$
The plan is to expand $\map \det {V_n - J_n}$ and simplify.
The method is efficiently communicated in the $3 \times 3$ case:
\(\ds \map \det {V_3 - J_3}\) | \(=\) | \(\ds \map \det {\begin {matrix}
x_1 - 1 & x_2 - 1 & x_3 - 1 \\ x_1^2 - 1 & x_2^2 - 1 & x_3^2 - 1 \\ x_1^3 - 1 & x_2^3 - 1 & x_3^3 - 1 \\ \end {matrix} }\) |
where $J_3$ is the $3 \times 3$ ones matrix | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {x_1 - 1} \paren {x_2 - 1} \paren {x_3 - 1} \map \det {\begin {matrix}
1 & 1 & 1 \\ x_1+1 & x_2+1 & x_3+1 \\ x_1^2+x+1+1 & x_2^2+x_2+1 & x_3^2+x_3+1 \\ \end {matrix} }\) |
Use $a^n - b^n$ factorization.
Effect of Elementary Row Operations on Determinant collects common column factors outside the determinant. |
|||||||||||
\(\ds \) | \(=\) | \(\ds \paren {x_1 - 1} \paren {x_2 - 1} \paren {x_3 - 1}
\map \det {\begin {matrix} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ x_1^2 & x_2^2 & x_3^2 \\ \end {matrix} }\) |
Effect of Elementary Row Operations on Determinant simplifies the determinant. |
The proof is completed by induction using the lemmas below.
Lemma 1
Let:
- $A_n = \det \begin {pmatrix}
1 & \cdots & 1 \\ x_1 & \cdots & x_n \\ \vdots & \cdots & \vdots \\ x_1^{n - 1} & \cdots & x_n^{n - 1} \\ \end {pmatrix}$
Then from Effect of Elementary Row Operations on Determinant:
- $\ds \map \det {V_n} = \paren {\prod_{k \mathop = 1}^n x_k} \map \det {A_n}$
Lemma 2
- $\ds \map \det {V_n - J_n} = \prod_{k \mathop = 1}^n \paren {x_k - 1} \map \det {A_n}$
Lemma 3
By Lemmas 1 and 2:
- $\ds \map \det {V_n^{-1} } \map \det {V_n - J_n} = \dfrac {\ds \prod_{k \mathop = 1}^n \paren {x_k - 1} } {\ds \prod_{k \mathop = 1}^n x_k}$
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.3$: Sums and Products: Exercise $43$