Deriving inverse of Hilbert matrix 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.
 A: A simple proof is in the paper "Fibonacci numbers and orthogonal polynomials"
by Christian Berg.
A: It suffices to prove Schechter's formula for Cauchy matrix cited in Wikipedia (see link in Faisal's comment). We need to check $\sum_j b_{ij}a_{jk}=\delta_{ik}$, i.e.
$$
\frac{A(y_i)}{B'(y_i)}\sum_j \frac{f(x_j)}{A'(x_j)}=-\delta_{i,k},
$$
where $f(t)=B(t)/((t-y_i)(t-y_k))$. If $i\ne k$, then $f$ is just a polynomial of degree $n-2$, and the inner sum is its coefficient in $t^{n-1}$ (this follows from Lagrange interpolation on points $x_1,\dots,x_n$). If $i\ne k$, then denote by $F$ the corresponding Lagrange polynomial $F(x)=\sum f(x_j) \frac{A(x)}{(x-x_j)A'(x_j)}$, we are searching for a coefficient of $F$ in $x^{n-1}$. We have $F(x_j)=f(x_j)$, so $F(x)(x-y_i)-\prod_{j\ne i}(x-y_i)$ vanishes for $x=x_1,x_2,\dots,x_n$. So, $F(x)(x-y_i)-\prod_{j\ne i}(x-y_i)=cA(x)$, and we find $c$ substituting $x=y_i$. 
A: It's a bit circuitous, but I'd like to point out this paper by Hitotumatu where he derives explicit expressions for the Cholesky triangle of a Hilbert matrix. From the expressions for the Cholesky triangle, you should be able to derive explicit expressions for the inverse (if $\mathbf A=\mathbf G\mathbf G^\top$, then $\mathbf A^{-1}=\mathbf G^{-\top}\mathbf G^{-1}$).

Since the paper isn't that easily accessible, I'll include the main result here. If $\mathbf A$ is the Hilbert matrix, with the decomposition $\mathbf A=\mathbf L\mathbf D\mathbf L^\top$ with $\mathbf L$ unit lower triangular and $\mathbf D$ diagonal, then
$$\begin{align*}\ell_{j,k}&=\frac{(2k-1)\binom{2k-2}{k-1}\binom{2j-1}{j-k}}{(2j-1)\binom{2j-2}{j-1}}\\d_{k,k}&=\frac1{(2k-1)\binom{2k-2}{k-1}^2}\end{align*}$$
A: Thanks everyone for the answers offered! After chasing down the various links, I came across a very similar comment by Deane Yang in 1991 (!), that offered an elegant outline of a proof. I felt it would be nice to flesh out the details of the proof. This proof doesn't use "Cholesky machinery", and it is possible to deduce that the entries of the inverse are integers without knowing the entries explicitly.
First,  we note that $$H_{ij} = \frac{1}{i+j-1}= \int_{0}^{1}x^{i+j-2}dx= \int_{0}^{1}x^{i-1}x^{j-1}dx$$
We can treat $\int_{0}^{1}p(x)q(x)dx$ as an inner product, $ \langle p, q \rangle $, on the vector space $P_{n-1}(x)$ of polynomials of degree $ < n $.
$H_n$, the $n \times n$ Hilbert matrix, corresponds to the Gramian matrix of the set of vectors $\{ 1,x,x^2,...,x^{n-1} \} $.
Next, the Shifted Legendre Polynomials are given by $$\tilde{P_n}(x) = (-1)^n \sum_{k=0}^n {n \choose k} {n+k \choose k} (-x)^k$$
We note that these are polynomials with integer coefficients. They also have the property that $$\int_{0}^{1} \tilde{P_m}(x) \tilde{P_n}(x)dx = {1 \over {2n + 1}} \delta_{mn}$$
Also, $\tilde{P_m}(x)$ is a polynomial of degree $m$, so $\{ \tilde{P_0}(x), \tilde{P_1}(x), ... \tilde{P_{n-1}}(x) \}$ form an alternative basis of $P_{n-1}(x)$.
The change of basis matrix, $P$, (from the standard basis to this new basis) can be obtained by choosing the coefficient of the appropriate power of $x$ in the above explicit formula for the Legendre polynomials. We have $$ P_{ij} = (-1)^{i+j-1} {j-1 \choose i-1} {i+j-2 \choose i-1}$$
(i.e. replace $n$ by $j-1$ and $k$ by $i-1$ in the formula for $\tilde{P_n}$).
The Gramian matrix under this change of basis is $P^T H P$. But since the $\tilde{P_i}$'s are orthogonal, we get $$ (P^T H P)_{ii} = {1 \over 2i-1}$$.
Let this diagonal matrix be $D$. Since it is diagonal, its inverse is given by 
$$(D^{-1})_{ii}  = \frac{1}{Dii} = 2i -1 $$
Then $$ P^T H P = D $$. So $$ H = (P^T)^{-1} D P^{-1} $$ and $$ H^{-1} = P D^{-1} P^T $$.
Since, $P$, $P^T$ and $D$ are all integer matrices, $H^{-1}$ is an integer matrix. $ \blacksquare $
A: I don't have any new content to add, but I did notice some context:
A "lattice" in a real vector space $V$ is the ${\mathbb Z}$-span of an
${\mathbb R}$-basis of $V$. Any ordered ${\mathbb R}$-basis whose ${\mathbb Z}$-span is the lattice $L$ is said to be an "ordered base" of $L$.
Let $L$ be a lattice in a real inner product space $V$. (The inner product being, by definition, symmetric, bilinear and positive definite.) The "dual lattice" to $L$ in $V$ consists of vectors $v\in V$ such that, for all $w\in L$, we have:
$\langle v,w\rangle\in{\mathbb Z}$. The dual of $L$ will be denoted $L^*$.
Let $B$ be an ordered basis in a real inner product space $V$. Then the "Gramian matrix" of $B$ is the matrix whose $i,j$-entry is $\langle B_i,B_j\rangle$.
A matrix is "integral" if all of its entries are integers.
Lemma: Let $B$ be an ordered base of a lattice $L$ in a real inner product space. Then: $L^*\subseteq L$ iff the inverse of the Gramian matrix of $B$ is integral.
The proof of this lemma is not hard.
Now fix a positive integer $d$ and let $V$ be the real inner product space consisting of real polynomials ${\mathbb R}\to{\mathbb R}$ of degree $<d$, with inner product given by:
$\langle P,Q\rangle=\int_0^1 PQ$.
Let $M$ be the lattice in $V$ consisting of all polynomials in $V$ that have integer coefficients.
Let ${\bf1}$ denote the constant function
${\mathbb R}\to{\mathbb R}$ with value $1$.
Let ${\bf x}:{\mathbb R}\to{\mathbb R}$ denote the identity function.
Let $B:=({\bf1},{\bf x},{\bf x}^2,...,{\bf x}^{d-1})$, an ordered base of $M$.
The Gramian matrix of $B$ is the Hilbert $d\times d$ matrix, so, by the lemma, we wish to show that $M^*\subseteq M$.
Let $A:=(\tilde P_0,...\tilde P_{d-1})$, the ordered list of the $0$th through $(d-1)$st shifted Legendre polynomials. This is an ordered basis of $V$. Let $L$ be the ${\mathbb Z}$-span of $A$. The $L$ is a lattice in $V$.
Since the shifted Legendre polynomials have integer coefficients, $L\subseteq M$. It follows that $L^*\supseteq M^*$.
The Gramian matrix of $A$ is diagonal, with each diagonal entry in the set
$\{1,1/2,1/3,1/4,\dots\}$. So, by the lemma, $L^*\subseteq L$.
Then $M^*\subseteq L^*\subseteq L\subseteq M$. QED
