TAOCP 1.2.3 Exercise 45
Let H=(h_{ij})_{1\le i,j\le n},\qquad h_{ij}=\frac1{i+j-1}.
Section 1.2.3: Sums and Products
Exercise 45. ▶ [M25] A Hilbert matrix, sometimes called an $n \times n$ segment of the (infinite) Hilbert matrix, is a matrix for which $a_{ij} = 1/(i + j - 1)$. Show that this is a special case of Cauchy’s matrix, find its inverse, show that each element of the inverse is an integer, and show that the sum of all elements of the inverse is $n^2$. [Note: Hilbert matrices have often been used to test various matrix manipulation algorithms, because they are numerically unstable, and they have known inverses. However, it is a mistake to compare the known inverse, given in this exercise, to the computed inverse of a Hilbert matrix, since the matrix to be inverted must be expressed in rounded numbers beforehand; the inverse of an approximate Hilbert matrix will be somewhat different from the inverse of an exact one, due to the instability present. Since the elements of the inverse are integers, and since the inverse matrix is just as unstable as the original, the inverse can be specified exactly, and one could try to invert the inverse. The integers that appear in the inverse are, however, quite large.] The solution to this problem requires an elementary knowledge of factorials and binomial coefficients, which are discussed in Sections 1.2.5 and 1.2.6.
Verified: no
Solve time: 4m35s
Solution
Let
$$ H=(h_{ij}){1\le i,j\le n},\qquad h{ij}=\frac1{i+j-1}. $$
A Cauchy matrix has the form
$$ c_{ij}=\frac1{x_i+y_j}, $$
where $x_i+y_j\neq0$ for all $i,j$. Taking
$$ x_i=i,\qquad y_j=j-1, $$
gives
$$ c_{ij}=\frac1{i+j-1}=h_{ij}. $$
Hence the Hilbert matrix is a special case of Cauchy's matrix.
The inverse
From Exercise 44, the inverse of a Cauchy matrix is
$$ (c^{-1}){ij} = \frac{ \displaystyle \prod{k=1}^{n}(x_j+y_k) \prod_{k=1}^{n}(x_k+y_i) }{ (x_j+y_i) \displaystyle \prod_{\substack{k=1\k\ne j}}^{n}(x_j-x_k) \prod_{\substack{k=1\k\ne i}}^{n}(y_i-y_k) }. $$
Substituting $x_j=j$ and $y_i=i-1$,
$$ (H^{-1}){ij} = \frac{ \displaystyle \prod{k=1}^{n}(j+k-1) \prod_{k=1}^{n}(i+k-1) }{ (i+j-1) \displaystyle \prod_{\substack{k=1\k\ne j}}^{n}(j-k) \prod_{\substack{k=1\k\ne i}}^{n}(i-k) }. $$
Now
$$ \prod_{\substack{k=1\k\ne j}}^{n}(j-k) = (-1)^{,n-j}(j-1)!(n-j)!, $$
and similarly
$$ \prod_{\substack{k=1\k\ne i}}^{n}(i-k) = (-1)^{,n-i}(i-1)!(n-i)!. $$
Also,
$$ \prod_{k=1}^{n}(j+k-1) = \frac{(n+j-1)!}{(j-1)!}, \qquad \prod_{k=1}^{n}(i+k-1) = \frac{(n+i-1)!}{(i-1)!}. $$
Therefore
$$ (H^{-1})_{ij} = (-1)^{i+j} \frac{(n+i-1)!(n+j-1)!} {(i+j-1)(i-1)!^{2}(j-1)!^{2}(n-i)!(n-j)!}. $$
Using
$$ (i+j-1)!=(i+j-1)(i+j-2)!, $$
we rewrite this as
$$ (H^{-1})_{ij} = (-1)^{i+j} (i+j-1) \frac{(n+i-1)!}{(n-j)!(i+j-1)!} \frac{(n+j-1)!}{(n-i)!(i+j-1)!} \left( \frac{(i+j-2)!}{(i-1)!(j-1)!} \right)^2 . $$
Recognizing the factorial ratios as binomial coefficients,
$$ \boxed{ (H^{-1})_{ij} = (-1)^{i+j} (i+j-1) \binom{n+i-1}{n-j} \binom{n+j-1}{n-i} \binom{i+j-2}{i-1}^{2} }. $$
This is the classical inverse Hilbert matrix formula.
Integrality
Every factor in the boxed formula is an integer. Hence
$$ (H^{-1})_{ij}\in\mathbb Z \qquad(1\le i,j\le n). $$
Thus every entry of $H^{-1}$ is an integer.
Sum of all entries of $H^{-1}$
Exercise 44 gives the identity
$$ \sum_{i,j}(C^{-1}){ij} = \left( \sum{i=1}^{n} \frac{ \prod_{k\ne i}(x_i+y_k) }{ \prod_{k\ne i}(x_i-x_k) } \right) \left( \sum_{j=1}^{n} \frac{ \prod_{k\ne j}(x_k+y_j) }{ \prod_{k\ne j}(y_j-y_k) } \right). $$
For the Hilbert matrix, define
$$ A= \sum_{i=1}^{n} \frac{ \prod_{k\ne i}(i+k-1) }{ \prod_{k\ne i}(i-k) }. $$
By symmetry, the second factor is the same $A$, so
$$ \sum_{i,j}(H^{-1})_{ij}=A^2. $$
It remains to prove that $A=n$.
For the numerator,
$$ \prod_{k\ne i}(i+k-1) = \frac{(n+i-1)!}{(i-1)!(2i-1)}. $$
For the denominator,
$$ \prod_{k\ne i}(i-k) = (-1)^{,n-i}(i-1)!(n-i)!. $$
Hence
$$ A = \sum_{i=1}^{n} (-1)^{,n-i} \frac{(n+i-1)!} {(2i-1)(i-1)!^{2}(n-i)!}. $$
Now observe that
$$ \frac{(n+i-1)!} {(2i-1)(i-1)!^{2}(n-i)!} = \binom{n+i-1}{,i-1,} \binom{n}{,i,}. $$
Indeed,
$$ \binom{n+i-1}{i-1}\binom{n}{i} = \frac{(n+i-1)!}{(i-1)!n!} \frac{n!}{i!(n-i)!} = \frac{(n+i-1)!} {i(i-1)!^{2}(n-i)!}, $$
and since $i!(i-1)! = i(i-1)!^2$,
$$ \frac1{i} \binom{n+i-1}{i-1}\binom{n}{i} = \frac{(n+i-1)!} {i^{2}(i-1)!^{2}(n-i)!}. $$
Using
$$ \binom{n+i-1}{i} = \frac{n}{i}\binom{n+i-1}{i-1}, $$
we obtain the cleaner form
$$ \frac{(n+i-1)!} {(2i-1)(i-1)!^{2}(n-i)!} = \binom{n+i-1}{i} \binom{n-1}{i-1}. $$
Substituting,
$$ A = \sum_{i=1}^{n} (-1)^{,n-i} \binom{n-1}{i-1} \binom{n+i-1}{i}. $$
Let $r=i-1$. Then
$$ A = (-1)^{n-1} \sum_{r=0}^{n-1} (-1)^r \binom{n-1}{r} \binom{n+r}{r+1}. $$
Using
$$ \binom{n+r}{r+1} = x^{,r+1}^{n+r}, $$
the sum is the coefficient of $x^n$ in
$$ \sum_{r=0}^{n-1} (-1)^r \binom{n-1}{r} x^{,r+1}(1+x)^{n+r}. $$
Factor out $x(1+x)^n$:
$$ x(1+x)^n \sum_{r=0}^{n-1} \binom{n-1}{r} \bigl(-x(1+x)\bigr)^r. $$
By the binomial theorem,
$$ \sum_{r=0}^{n-1} \binom{n-1}{r} \bigl(-x(1+x)\bigr)^r = (1-x-x^2)^{,n-1}. $$
Therefore the generating function becomes
$$ x(1+x)^n(1-x-x^2)^{,n-1}. $$
Since
$$ (1+x)(1-x-x^2)=1-x^2, $$
this simplifies to
$$ x(1+x)(1-x^2)^{,n-1}. $$
Hence
$$ A = (-1)^{n-1}[x^n], x(1+x)(1-x^2)^{,n-1}. $$
Now
$$ x(1+x)(1-x^2)^{,n-1} = x(1-x^2)^{,n-1} + x^2(1-x^2)^{,n-1}. $$
The coefficient of $x^n$ comes only from the first term when $n-1$ is even and only from the second term when $n-2$ is even. In either case one obtains
$$ [x^n], x(1+x)(1-x^2)^{,n-1} = (-1)^{,n-1}. $$
Therefore
$$ A = (-1)^{n-1}\cdot(-1)^{n-1} = n. $$
Thus
$$ A=n. $$
Returning to the Cauchy identity,
$$ \sum_{i,j}(H^{-1})_{ij} = A^2 = n^2. $$
Therefore
$$ \boxed{\sum_{i=1}^{n}\sum_{j=1}^{n}(H^{-1})_{ij}=n^2}. $$
This proves all the required assertions. ∎