Sum of Elements in Inverse of Vandermonde Matrix

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$