TAOCP 1.2.3 Exercise 44

Exercise 44. ▶ [M26] What is the sum of all $n^2$ elements in the inverse of Cauchy’s matrix?

Verified: yes
Solve time: 3m29s

Let

$$ A=(a_{ij}){1\le i,j\le n}, \qquad a{ij}=\frac1{x_i+y_j}, $$

be Cauchy's matrix, and let $B=A^{-1}=(b_{ij})$.

From Exercise 41,

$$ b_{ij} = \frac{ \displaystyle \prod_{k=1}^{n}(x_j+y_k)(x_k+y_i) }{ (x_j+y_i) \displaystyle \prod_{k\ne j}(x_j-x_k) \displaystyle \prod_{k\ne i}(y_i-y_k) }. $$

We seek

$$ S=\sum_{i=1}^n\sum_{j=1}^n b_{ij}. $$

1. Rewrite the inverse entries

Define

$$ X(z)=\prod_{k=1}^{n}(z-x_k), \qquad Y(z)=\prod_{k=1}^{n}(z-y_k). $$

Then

$$ X'(x_j)=\prod_{k\ne j}(x_j-x_k), \qquad Y'(y_i)=\prod_{k\ne i}(y_i-y_k), $$

and

$$ X(-y_i)=(-1)^n\prod_{k=1}^{n}(x_k+y_i), \qquad Y(-x_j)=(-1)^n\prod_{k=1}^{n}(x_j+y_k). $$

Since the two factors $(-1)^n$ cancel,

$$ b_{ij} = \frac{ X(-y_i),Y(-x_j) }{ (x_j+y_i),X'(x_j),Y'(y_i) }. $$

Hence

$$ S = \sum_{i=1}^{n} \frac{X(-y_i)}{Y'(y_i)} \sum_{j=1}^{n} \frac{Y(-x_j)} {(x_j+y_i)X'(x_j)}. $$

So it remains to evaluate the inner sum.

2. Evaluate the inner sum

Consider the polynomial

$$ P(z)=Y(-z). $$

Its degree is $n$, and its leading coefficient is $(-1)^n$.

Applying the Lagrange interpolation formula at the nodes

$x_1,\dots,x_n$,

$$ P(z) = (-1)^n X(z) + X(z) \sum_{j=1}^{n} \frac{P(x_j)} {X'(x_j)(z-x_j)}. $$

Since $P(x_j)=Y(-x_j)$,

$$ Y(-z) = (-1)^n X(z) + X(z) \sum_{j=1}^{n} \frac{Y(-x_j)} {X'(x_j)(z-x_j)}. $$

Now set $z=-y_i$. Because $Y(y_i)=0$,

$$ 0 = (-1)^n X(-y_i) + X(-y_i) \sum_{j=1}^{n} \frac{Y(-x_j)} {X'(x_j)(-y_i-x_j)}. $$

Since $X(-y_i)\neq0$,

$$ \sum_{j=1}^{n} \frac{Y(-x_j)} {X'(x_j)(-y_i-x_j)} = -(-1)^n. $$

Using

$$ \frac1{-y_i-x_j} = -\frac1{x_j+y_i}, $$

we obtain

$$ \sum_{j=1}^{n} \frac{Y(-x_j)} {(x_j+y_i)X'(x_j)} = (-1)^n. $$

Therefore

$$ S = (-1)^n \sum_{i=1}^{n} \frac{X(-y_i)}{Y'(y_i)}. $$

Let

$$ T=\sum_{i=1}^{n}\frac{X(-y_i)}{Y'(y_i)}. $$

Then $S=(-1)^nT$.

3. Evaluate $T$

Apply the same interpolation formula to

$$ F(z)=X(-z). $$

Again $\deg F=n$, with leading coefficient $(-1)^n$. Hence

$$ X(-z) = (-1)^nY(z) + Y(z) \sum_{i=1}^{n} \frac{X(-y_i)} {Y'(y_i)(z-y_i)}. $$

The second term has degree at most $n-1$. Its coefficient of

$z^{,n-1}$ is exactly

$$ T=\sum_{i=1}^{n}\frac{X(-y_i)}{Y'(y_i)}. $$

Now compare coefficients of $z^{,n-1}$.

For the left side,

$$ X(-z) = (-1)^n \Bigl( z^n+(\sum_{k=1}^{n}x_k)z^{n-1}+\cdots \Bigr), $$

so the coefficient of $z^{n-1}$ is

$$ (-1)^n\sum_{k=1}^{n}x_k. $$

For the first term on the right,

$$ (-1)^nY(z) = (-1)^n \Bigl( z^n-(\sum_{k=1}^{n}y_k)z^{n-1}+\cdots \Bigr), $$

whose $z^{n-1}$-coefficient is

$$ (-1)^n!\left(-\sum_{k=1}^{n}y_k\right). $$

Therefore

$$ (-1)^n\sum_{k=1}^{n}x_k = (-1)^n!\left(-\sum_{k=1}^{n}y_k\right)+T, $$

which gives

$$ T = (-1)^n \left( \sum_{k=1}^{n}x_k+\sum_{k=1}^{n}y_k \right). $$

Finally,

$$ S=(-1)^nT = \sum_{k=1}^{n}x_k+\sum_{k=1}^{n}y_k. $$

Thus the sum of all entries of $A^{-1}$ is

$$ \boxed{ \sum_{i=1}^{n}\sum_{j=1}^{n}(A^{-1}){ij} = \sum{k=1}^{n}x_k+\sum_{k=1}^{n}y_k }. $$

As a check, for $n=2$, $x=(1,2)$, $y=(3,4)$, the formula gives

$$ 1+2+3+4=10, $$

which agrees with the direct computation of the inverse matrix.