The Hilbert matrix is the square matrix given by


$$H\_{ij}=\frac{1}{i+j-1}$$


Wikipedia states that its inverse is given by


$$(H^{-1})\_{ij} = (-1)^{i+j}(i+j-1) {{n+i-1}\choose{n-j}}{{n+j-1}\choose{n-i}}{{i+j-2}\choose{i-1}}^2$$


It follows that the entries in the inverse matrix are all integers.


I was wondering if there is a way to prove that its inverse is an integer matrix without using the formula above.


Also, how would one go about proving the explicit formula for the inverse? Wikipedia refers me to a paper by Choi, but it only includes a brief sketch of the proof.



Deriving inverse of Hilbert matrix
(Note: The matrix elements are indexed from $0$. To avoid confusion, I will not index into a matrix without brackets)


Here is a naive approach to this problem, without hindsight of the already-derived formula.



> 
> Lemma:
>  If $M \in \mathbb F^{n \times n}$ is an invertible matrix and $(\alpha\_i),(\beta\_i)$ are non-zero elements of $\mathbb F$, then the matrix formed by $$N := \left[(M)\_{i,j}\alpha\_i\beta\_j\right]$$
>  is invertible, with its inverse given by
>  $$N^{-1} = \left[(M^{-1})\_{i,j}\beta\_i^{-1}\alpha\_j^{-1}\right]$$
> 
> 
> 




---



> 
> Let $H\_n$ be the $n$-th Hilbert matrix, given by
>  $$ H\_n = \left[\frac1{i+j+1}\right]\_{i,j}
> $$
>  Then $H\_n$ is invertible and every element of $H\_n^{-1}$ is an integer.
> 
> 
> 


*Proof:* The $H\_n$s are nested within each other:
$$ H\_{n+1} = \begin{bmatrix} H\_n & u \\ u^\intercal & 1/(2n+1)\end{bmatrix}
$$
Define $V\_n := H\_n - (2n+1)uu^\intercal$. Then
$$\begin{align\*}
V\_n &= \left[\frac1{i+j+1} - \frac{2n+1}{(n+1+i)(n+1+j)}\right] \\
&= \left[\frac{(n-i)(n-j)}{(i+j+1)(n+1+i)(n+1+j)}\right] \\
&= \left[(H\_n)\_{i,j} \frac{n -i}{n+1+i} \frac{n-j}{n+1+j}\right]
\end{align\*}$$
It is well-known that if $V\_n$ is invertible, then so is $H\_{n+1}$, but the invertibility of $V\_n$ is intrinsically linked to $H\_n$, so an inductive argument gives that $H\_n$ is invertible.


The inverse of $H\_{n+1}$ is given by Blockwise inversion formula:
$$ H\_{n+1}^{-1} = \begin{bmatrix}
V\_n^{-1} & -(2n+1)V\_n^{-1}u \\ -(2n+1)u^\intercal V\_n^{-1} & (2n+1) + (2n+1)^2u^\intercal V\_n^{-1} u\end{bmatrix}
$$
By the Lemma above, the inverse of $V\_n$ is given by
$$ V\_n^{-1} = \left[(H\_n^{-1}) \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \right]
$$
Since $V\_n^{-1}$ is a constituent of $H\_{n+1}$, this can be used to telescope the entries of $H\_n^{-1}$.


By the symmetry of $H\_n,V\_n,H\_n^{-1}$, it suffices to consider the upper triangular portion of $H\_n$. We can see that eventually a "interior" element of $H\_n^{-1}$ "lands" on an edge element of some $H\_n^{-1}$: Let $i,j<n$ with $i \leq j$. Then
$$\begin{align\*}
(H\_{n+1}^{-1})\_{i,j} &= (V\_n^{-1})\_{i,j}
= (H\_{j+1}^{-1})\_{i,j} \frac{(2j+2)(i+j+2)}{1(j+1-i)} \cdots \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \\
&= (H\_{j+1}^{-1})\_{i,j} \frac{(n+1+i)!(n+1+j)!}{(2j+1)!(i+j+1)!} \frac{(j-i)!}{(n-i)!(n-j)!} \\
&= (H\_{j+1}^{-1})\_{i,j} \frac{(j-i)!}{(2j+1)!(i+j+1)!} \frac{(n+1+i)!(n+1+j)!}{(n-i)!(n-j)!(2i+1)!(2j+1)!} (2i+1)!(2j+1)! \\
&= (H\_{j+1}^{-1})\_{i,j} \frac{(j-i)!(2i+1)!}{(i+j+1)!} \binom{n+1+i}{n-i}\binom{n+1+j}{n-j} \\
&= (H\_{j+1}^{-1})\_{i,j} \frac{1}{\binom{i+j+1}{2i+1}} \binom{n+1+i}{n-i}\binom{n+1+j}{n-j}
\end{align\*}$$
This is a very strong hint on what the inductive hypothesis should be.


**Inductive Hypothesis** P(n):



> 
> Every element of $H\_n^{-1}$ is an integer, and $$\binom{n+i}{n-1-i}\binom{n+j}{n-1-j} \mid (H\_n^{-1})\_{i,j}$$
>  where $i,j \in \{0,\dots,n-1\}$.
> 
> 
> 


Define the matrix
$$ A\_n := \left[\frac{(H\_n^{-1})\_{i,j}}{\binom{n+i}{n-1-i} \binom{n+j}{n-1-j}}\right]\_{i,j}
$$
$P(n)$ is just the statement that $A\_n$ has integer entries. Evidently $P(1)$ holds. Suppose $P(n)$ holds for some $n$. We shall examine the validity of $P(n+1)$.


There are three cases:


1. Suppose $i,j < n$. This corresponds to a "interior" element $(H\_{n+1}^{-1})\_{i,j}$ of $H\_{n+1}^{-1}$.


We have that
$$\begin{align\*}
(H\_{n+1}^{-1})\_{i,j} &= (V\_n^{-1})\_{i,j} = (H\_n^{-1})\_{i,j} \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \\
&= (A\_n)\_{i,j} \binom{n+i}{n-1-i}\binom{n+j}{n-1-j} \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \\
&= (A\_n)\_{i,j} \binom{n+1+i}{n-i} \binom{n+1+j}{n-j}
\end{align\*}$$
Establishing the interior case. (It can also be inferred from this equation that $A\_n$'s are nested within each other.)


2. The edge case: Consider the edge $-(2n+1)V\_n^{-1}u$. Let $i \in \{0,\dots,n-1\}$ The $i$th element $(H\_{n+1}^{-1})\_{i,n}$ on the edge is given by the dot product
$$\begin{align\*}
-(2n+1)(V\_n^{-1}u)\_i
&= -(2n+1) \sum\_{j=0}^{n-1} (V\_n^{-1})\_{i,j} (u)\_j \\
&= -(2n+1) \sum\_{j=0}^{n-1} (H\_n^{-1})\_{i,j} \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \frac1{n+1+j} \\
&= -\frac{(n+1+i)(2n+1)}{n-i} \sum\_{j=0}^{n-1} (H\_n^{-1})\_{i,j} \frac1{n-j} \\
&= -\frac{(n+1+i)(2n+1)}{n-i} \sum\_{j=0}^{n-1} (A\_n)\_{i,j} \binom{n+i}{n-1-i}\binom{n+j}{n-1-j} \frac1{n-j} \\
&= -\frac{n+1+i}{n-i}\binom{n+i}{n-1-i} \sum\_{j=0}^{n-1} (A\_n)\_{i,j} \frac{2n+1}{n-j} \binom{n+j}{n-1-j}\\
\end{align\*}$$
[Here](https://math.stackexchange.com/questions/2622874/product-of-binomial-coefficient-and-fraction-is-integer) people proved that the multiplier in the sum is an integer, so it remains to show that
$$ \frac{n+1+i}{n-i}\binom{n+i}{n-1-i} = \binom{n+i+1}{n-i}
= \binom{n+i+1}{n-i}\binom{n+n+1}{n-n}
$$
is also an integer.
3. The corner element $(H\_{n+1}^{-1})\_{n,n}$ is given by the quadratic form:
$$\begin{align\*}
(H\_{n+1}^{-1})\_{n,n} - (2n+1)
&= (2n+1)^2 \sum\_{i=0}^{n-1}\sum\_{j=0}^{n-1} \frac{(H\_n^{-1})\_{i,j}}{(n-i)(n-j)} \\
&= \sum\_{i=0}^{n-1}\sum\_{j=0}^{n-1} (A\_n)\_{i,j} \frac{(2n+1)(2n+1)}{(n-i)(n-j)}\binom{n+i}{n-1-i}\binom{n+j}{n-1-j}
\end{align\*}$$
The last sum is a sum integers, and hence an integer. Trivially it holds that
$$ \binom{n+1+n}{n-n}\binom{n+1+n}{n-n} \mid (H\_{n+1}^{-1})\_{n,n}
$$
With all three cases established, the proof is complete by induction.


