TAOCP 1.2.3 Exercise 41

Exercise 41. [M26] Show that the inverse of Cauchy’s matrix is given by

$$b_{ij} = \left( \prod_{1 \le k \le n} (x_j + y_k)(x_k + y_i) \right) \bigg/ (x_j + y_i) \left( \prod_{\substack{1 \le k \le n \ k \ne j}} (x_j - x_k) \right) \left( \prod_{\substack{1 \le k \le n \ k \ne i}} (y_i - y_k) \right).$$

Verified: yes
Solve time: 3m24s

Setup

Let $A=(a_{ij})_{1\le i,j\le n}$ be Cauchy’s matrix, where

$a_{ij}=\frac1{x_i+y_j}.$

Let $B=(b_{ij})$ be the matrix whose entries are

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

We shall prove that $AB=I$. Since $A$ is nonsingular by Exercise 38, this will show that $B=A^{-1}$.

The $(i,j)$ entry of $AB$ is

$$ \sum_{k=1}^n a_{ik}b_{kj} = \sum_{k=1}^n \frac1{x_i+y_k},b_{kj}. $$

Therefore it suffices to prove that

$$ \sum_{k=1}^n \frac1{x_i+y_k},b_{kj} = \delta_{ij}. \eqno(1) $$

Solution

Substituting the formula for $b_{kj}$ into (1), we obtain

$$ \sum_{k=1}^n \frac1{x_i+y_k} \cdot \frac{ \prod_{1\le r\le n}(x_j+y_r)(x_r+y_k) }{ (x_j+y_k) \left(\prod_{\substack{1\le r\le n\r\ne j}}(x_j-x_r)\right) \left(\prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r)\right) }. $$

The factors independent of $k$ may be taken outside the sum, by rule (a):

$$= \frac{ \prod_{1\le r\le n}(x_j+y_r) }{ \prod_{\substack{1\le r\le n\r\ne j}}(x_j-x_r) } \sum_{k=1}^n \frac{ \prod_{1\le r\le n}(x_r+y_k) }{ (x_i+y_k)(x_j+y_k) \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. \eqno(2)$$

Define

$$ P(t)=\prod_{1\le r\le n}(x_r+t). $$

Then the summand in (2) becomes

$$ \frac{P(y_k)} {(x_i+y_k)(x_j+y_k) \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r)}. $$

First suppose that $i\ne j$. Since

$$ \frac1{(x_i+y_k)(x_j+y_k)} = \frac1{x_j-x_i} \left( \frac1{x_i+y_k}-\frac1{x_j+y_k} \right), $$

equation (2) becomes

$$ \frac{ \prod_{1\le r\le n}(x_j+y_r) }{ (x_j-x_i) \prod_{\substack{1\le r\le n\r\ne j}}(x_j-x_r) } (S_i-S_j), \eqno(3) $$

where

$$ S_m= \sum_{k=1}^n \frac{ P(y_k) }{ (x_m+y_k) \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. $$

Since $P(y_k)=(x_m+y_k)Q_m(y_k)$, where

$$ Q_m(t)=\prod_{\substack{1\le r\le n\r\ne m}}(x_r+t), $$

we have

$$ S_m= \sum_{k=1}^n \frac{ Q_m(y_k) }{ \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. \eqno(4) $$

Now $Q_m(t)$ is a polynomial of degree $n-1$. By the Lagrange interpolation formula,

$$ Q_m(t)= \sum_{k=1}^n Q_m(y_k) \frac{ \prod_{\substack{1\le r\le n\r\ne k}}(t-y_r) }{ \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. $$

The coefficient of $t^{,n-1}$ on the left side is $1$. The coefficient of $t^{,n-1}$ in each term on the right side is

$$ \frac{ Q_m(y_k) }{ \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. $$

Hence, by equating coefficients of $t^{,n-1}$,

$$ S_m=1. \eqno(5) $$

Equation (3) therefore yields

$$ \sum_{k=1}^n a_{ik}b_{kj}=0 \qquad(i\ne j). \eqno(6) $$

Now suppose that $i=j$. Equation (2) becomes

$$ \frac{ \prod_{1\le r\le n}(x_i+y_r) }{ \prod_{\substack{1\le r\le n\r\ne i}}(x_i-x_r) } \sum_{k=1}^n \frac{ P(y_k) }{ (x_i+y_k)^2 \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. \eqno(7) $$

Since $P(y_k)=(x_i+y_k)Q_i(y_k)$,

$$ (7)= \frac{ \prod_{1\le r\le n}(x_i+y_r) }{ \prod_{\substack{1\le r\le n\r\ne i}}(x_i-x_r) } \sum_{k=1}^n \frac{ Q_i(y_k) }{ (x_i+y_k) \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. \eqno(8) $$

Define

$$ R_i(t)= \prod_{\substack{1\le r\le n\r\ne i}}(x_r+t). $$

Again applying the Lagrange interpolation formula to the polynomial $R_i(t)$ of degree $n-1$,

$$ R_i(t)= \sum_{k=1}^n R_i(y_k) \frac{ \prod_{\substack{1\le r\le n\r\ne k}}(t-y_r) }{ \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. $$

Set $t=-x_i$. Since

$$ R_i(-x_i)= \prod_{\substack{1\le r\le n\r\ne i}}(x_r-x_i), $$

we obtain

$$ \prod_{\substack{1\le r\le n\r\ne i}}(x_r-x_i) = \sum_{k=1}^n R_i(y_k) \frac{ \prod_{\substack{1\le r\le n\r\ne k}}(-x_i-y_r) }{ \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. $$

Since

$$ \prod_{\substack{1\le r\le n\r\ne k}}(-x_i-y_r) = (-1)^{n-1} \frac{ \prod_{1\le r\le n}(x_i+y_r) }{ x_i+y_k }, $$

and since

$$ \prod_{\substack{1\le r\le n\r\ne i}}(x_r-x_i) = (-1)^{n-1} \prod_{\substack{1\le r\le n\r\ne i}}(x_i-x_r), $$

the preceding equation becomes

$$ \prod_{\substack{1\le r\le n\r\ne i}}(x_i-x_r) = \prod_{1\le r\le n}(x_i+y_r) \sum_{k=1}^n \frac{ R_i(y_k) }{ (x_i+y_k) \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) }. $$

Comparing with (8), we obtain

$$ \sum_{k=1}^n a_{ik}b_{ki}=1. \eqno(9) $$

Equations (6) and (9) establish (1). Therefore $AB=I$, so $B=A^{-1}$.

This completes the proof.

∎

Verification

For $n=1$,

$$ A=\left(\frac1{x_1+y_1}\right). $$

The proposed formula gives

$$ b_{11}= \frac{(x_1+y_1)^2}{x_1+y_1} = x_1+y_1. $$

Hence

$$ a_{11}b_{11} = \frac1{x_1+y_1}(x_1+y_1) = 1. $$

Therefore the formula is correct in the $1\times1$ case.

Notes

The proof is essentially an application of Lagrange interpolation. The factors

$$ \prod_{\substack{1\le r\le n\r\ne k}}(y_k-y_r) $$

are the standard denominators appearing in interpolation formulas. The inverse matrix entries therefore have the same structure as the coefficients of interpolation polynomials.