Sum of Elements in Inverse of Cauchy Matrix

From ProofWiki
Jump to navigation Jump to search



Theorem

Let $C_n$ be the Cauchy matrix of order $n$ given by:

$C_n = \begin{bmatrix} \dfrac 1 {x_1 + y_1} & \dfrac 1 {x_1 + y_2 } & \cdots & \dfrac 1 {x_1 + y_n} \\ \dfrac 1 {x_2 + y_1} & \dfrac 1 {x_2 + y_2 } & \cdots & \dfrac 1 {x_2 + y_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac 1 {x_m + y_1} & \dfrac 1 {x_m + y_2 } & \cdots & \dfrac 1 {x_m + y_n} \\ \end{bmatrix}$


Let $C_n^{-1}$ be its inverse, from Inverse of Cauchy Matrix:

$b_{i j} = \dfrac {\ds \prod_{k \mathop = 1}^n \paren {x_j + y_k} \paren {x_k + y_i} } {\ds \paren {x_j + y_i} \paren {\prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } \paren {\prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne i} } \paren {y_i - x_k} } }$


The sum of all the elements of $C_n^{-1}$ is:

$\ds \sum_{1 \mathop \le i, \ j \mathop \le n} b_{i j} = \sum_{k \mathop = 1}^n x_k + \sum_{k \mathop = 1}^n y_k$


Proof

It suffices to prove the Theorem for Cauchy matrix:

\(\ds C\) \(=\) \(\ds \begin{pmatrix} \dfrac 1 {x_1 - y_1} & \dfrac 1 {x_1 - y_2 } & \cdots & \dfrac 1 {x_1 - y_n} \\ \dfrac 1 {x_2 - y_1} & \dfrac 1 {x_2 - y_2 } & \cdots & \dfrac 1 {x_2 - y_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac 1 {x_n - y_1} & \dfrac 1 {x_n - y_2 } & \cdots & \dfrac 1 {x_n - y_n} \\ \end {pmatrix}\) Distinct values $\set {x_1, \ldots, x_n, y_1, \ldots, y_n}$ required.

The sum $S$ of elements in $C^{-1}$ will be shown to be a scalar product of two vectors $\vec A$ and $\vec B$.

The statement of the theorem is obtained by replacing $y_k \to -y_k$ in $C$ and in the sum $S$.

Let:

\(\ds \vec \bsone\) \(=\) \(\ds \begin {pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix}\) vector of all ones

The sum $S$ of elements in $C^{-1}$ is the matrix product:

\(\text {(1)}: \quad\) \(\ds S\) \(=\) \(\ds \vec \bsone^T C^{-1} \vec \bsone\)

To identify vectors $\vec A$ and $\vec B$, the tool is:

\(\ds C\) \(=\) \(\ds -P V_x^{-1} V_y Q^{-1}\) Vandermonde Matrix Identity for Cauchy Matrix

Definitions of symbols:

\(\ds V_x\) \(=\) \(\ds \begin {pmatrix} 1 & 1 & \cdots & 1 \\ x_1 & x_2 & \cdots & x_n \\ \vdots & \vdots & \ddots & \vdots \\ x_1^{n - 1} & x_2^{n - 1} & \cdots & x_n^{n - 1} \\ \end {pmatrix}, \quad V_y = \begin {pmatrix} 1 & 1 & \cdots & 1 \\ y_1 & y_2 & \cdots & y_n \\ \vdots & \vdots & \ddots & \vdots \\ y_1^{n - 1} & y_2^{n - 1} & \cdots & y_n^{n - 1} \\ \end {pmatrix}\) Definition of Vandermonde Matrix
\(\ds \map p x\) \(=\) \(\ds \prod_{i \mathop = 1}^n \paren {x - x_i}, \quad \map {p_k} x = \prod_{i \mathop = 1,i \mathop \ne k}^n \, \paren {x - x_i} ,\quad 1 \mathop \le k \mathop \le n\) Definition of Polynomial over Complex Numbers
\(\ds P\) \(=\) \(\ds \begin {pmatrix} \map {p_1} {x_1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \map {p_n} {x_n} \\ \end {pmatrix}, \quad Q = \begin {pmatrix} \map p {y_1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \map p {y_n} \\ \end {pmatrix}\) Definition of Diagonal Matrix

Compute the sum $S$:

\(\ds C^{-1}\) \(=\) \(\ds - Q V_y^{-1} V_x P^{-1}\) Inverse of Matrix Product
\(\ds S\) \(=\) \(\ds \vec \bsone^T C^{-1} \vec \bsone\) from $(1)$
\(\ds \) \(=\) \(\ds \paren {-\vec {\bsone}^T Q V_y^{-1} } \paren {V_x P^{-1} \vec \bsone}\)

Define vectors $\vec A$ and $\vec B$:

\(\text {(2)}: \quad\) \(\ds \vec A^T\) \(=\) \(\ds -\vec \bsone^T Q V_y^{-1}\)
\(\text {(3)}: \quad\) \(\ds \vec B\) \(=\) \(\ds V_x P^{-1} \vec \bsone\) Sum $S$ equals scalar product $\vec A^T \vec B$

Compute $\vec A$:

\(\ds \vec A\) \(=\) \(\ds -\paren {\vec \bsone^T Q V_y^{-1} }^T\) from $(2)$
\(\ds \) \(=\) \(\ds -\paren {V_y^T}^{-1} Q^T \vec \bsone\) Definition:Inverse Matrix and Transpose of Matrix Product

Then $\vec A$ uniquely solves the problem

\(\ds \begin{pmatrix} 1 & \cdots & y_1^{n - 1} \\ \vdots & \cdots & \vdots \\ 1 & \cdots & y_n^{n - 1} \end {pmatrix} \vec A\) \(=\) \(\ds -\begin{pmatrix} \map p {y_1} \\ \vdots \\ \map p {y_n} \\ \end {pmatrix}\) coefficient matrix $V_y^T$

The two polynomials

\(\ds \map p x\) \(=\) \(\ds \prod_{j \mathop = 1}^n \paren {x - x_j}\)
\(\ds \) \(=\) \(\ds x^n + \sum_{i \mathop = 1}^n a_i x^{i - 1}\)
\(\ds \map q y\) \(=\) \(\ds \prod_{j \mathop = 1}^n \paren {y - y_j}\)
\(\ds \) \(=\) \(\ds y^n + \sum_{i \mathop = 1}^n b_i y^{i - 1}\)

have coefficients expressed by symmetric functions:

\(\ds a_i\) \(=\) \(\ds \paren {-1}^{n + 1 - i} e_{n + 1 - i} \paren {\set {x_1, \ldots, x_n} }\) Viète's Formulas
\(\ds b_i\) \(=\) \(\ds \paren {-1}^{n + 1 - i} e_{n + 1 - i} \paren {\set {y_1, \ldots, y_n} }\) Viète's Formulas

Solve in equation $\map q {y_j} = 0$ for highest power $y_j^n$ and replace in the equation for $\map p {y_j}$:

\(\ds \map p {y_j}\) \(=\) \(\ds \sum_{i \mathop = 1}^n \paren {a_i - b_i } y_j^{i - 1}\) for $j = 1, \ldots, n$

Vector $\begin {pmatrix} \map p {y_1} \\ \vdots \\ -\map p {y_n} \\ \end {pmatrix}$ is a linear combination of the column vectors of matrix $V_y^T$ with weights (coefficients) $b_i - a_i$.

Then:

\(\ds \vec A\) \(=\) \(\ds \begin {pmatrix} b_1 - a_1 \\ \vdots \\ b_n - a_n \\ \end{pmatrix}\)
\(\ds \) \(=\) \(\ds \begin{pmatrix} \paren {-1}^n \paren {e_n \paren {\set {y_1,\dots,y_n} } - e_n \paren {\set {x_1,\dots,x_n} } } \\ \vdots \\ \paren {-1}^1 \paren {e_1 \paren {\set {y_1, \dots, y_n} } - e_1 \paren {\set {x_1, \dots, x_n} } } \\ \end {pmatrix}\) The last entry contains the sum of the elements in $C^{-1}$: $S = x_1 + \cdots + x_n - \paren {y_1 + \cdots + y_n}$

Compute $\vec B$:

\(\ds \vec B\) \(=\) \(\ds V_x P^{-1} \vec { \bsone }\) from $(3)$
\(\ds \) \(=\) \(\ds V_x \begin {pmatrix} \dfrac 1 {\map {p_1} {x_1} } \\ \vdots \\ \dfrac 1 {\map {p_n} {x_n} } \end{pmatrix}\)
\(\ds \) \(=\) \(\ds \begin {pmatrix} \ds \sum_{k \mathop = 1}^n \frac 1 {\map {p_k} {x_k} } \\ \vdots \\ \ds \sum_{k \mathop = 1}^n \frac {x_n^{n - 1} } { \map {p_n} {x_n} } \\ \end{pmatrix}\)
\(\ds \) \(=\) \(\ds \begin {pmatrix} 0 \\ 0 \\ \vdots \\ 1 \\ \end{pmatrix}\) Summation of Powers over Product of Differences

Evaluate $S$:

\(\ds S\) \(=\) \(\ds \vec A^T \vec B\)
\(\ds \) \(=\) \(\ds \begin {pmatrix} * \\ * \\ \vdots \\ x_1 + \cdots + x_n - \paren { y_1 + \cdots + y_n } \\ \end {pmatrix} ^T \begin {pmatrix} 0 \\ 0 \\ \vdots \\ 1 \\ \end {pmatrix}\) Entries $*$ contribute nothing because of matching zero in $\vec B$.
\(\ds \) \(=\) \(\ds x_1 + \cdots + x_n - \paren { y_1 + \cdots + y_n}\)

$\blacksquare$


Sources