Sum of Elements in Inverse of Vandermonde Matrix

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:

\(\displaystyle \det \paren { V_3 - J_3 } =\)

\(=\)

\(\displaystyle \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.

\(\displaystyle \)

\(=\)

\(\displaystyle \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.

\(\displaystyle \)

\(=\)

\(\displaystyle \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$