Sum of Elements in Inverse of Vandermonde Matrix
Jump to navigation
Jump to search
Theorem
Let $V_n$ be the Vandermonde matrix of order $n$ given by:
- $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 $V_n^{-1}$ be its inverse, from Inverse of Vandermonde Matrix:
- $b_{i j} = \begin{cases} \paren {-1}^{j - 1} \paren {\dfrac{\displaystyle \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 \displaystyle \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 \displaystyle \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:
- $\displaystyle \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
Sum of Elements of Invertible Matrix implies the sum of elements in $V_n^{-1}$ is:
- $ 1 - \det \paren { V_n^{-1} } \det \paren { V_n - J_n } $.
The plan is to expand $\det \paren { V_n - J_n } $ and simplify.
The method is efficiently communicated in the $3\times 3$ case:
\(\ds \det \paren { V_3 - J_3 } =\) | \(=\) | \(\ds \det \paren { \begin{smallmatrix} 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{smallmatrix} }\) | $J_3$ is the $3\times 3$ ones matrix. | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {x_1 - 1} \paren {x_2 - 1} \paren {x_3 - 1} \det \paren { \begin{smallmatrix} 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{smallmatrix} }\) | 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} \det \paren { \begin{smallmatrix} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ x_1^2 & x_2^2 & x_3^2 \\ \end{smallmatrix} }\) | Effect of Elementary Row Operations on Determinant simplifies the determinant. |
The proof is completed by induction using the lemmas below.
Lemma 1
Let:
- $\displaystyle A_n = \det \paren { \begin{smallmatrix} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \\ \vdots & \cdots & \vdots \\ x_1^{n-1} & \cdots & x_n^{n-1} \\ \end{smallmatrix} }$
Then:
- $\displaystyle \det \paren { V_n } = \paren { \prod_{k \mathop = 1}^n x_k } \det \paren { A_n }$ Effect of Elementary Row Operations on Determinant
Lemma 2
- $\displaystyle \det(V_n - J_n) = \prod_{k \mathop = 1}^n \paren { x_k - 1 } \det \paren { A_n }$
Lemma 3
- $\displaystyle \det \paren { V_n^{-1} } \det(V_n - J_n) = \dfrac { \prod_{k \mathop = 1}^n \paren { x_k - 1 } } { \prod_{k \mathop = 1}^n { x_k } }$ by Lemmas 1 and 2.
$\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$