22
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Have you looked at en.wikipedia.org/wiki/Cauchy_matrix (and in particular the reference to Schechter's paper)? I just glanced over Schechter's paper, and it seems that it answers your second question. I doubt that there's an easy answer to your first question. $\endgroup$ – Faisal Nov 28 '10 at 6:38
  • 4
    $\begingroup$ You might be interested in watching this video where Prof. Zeilberger talks about evaluating the determinant of this matrix in an awesome way. It isn't the simplest proof, but you'll it involves selberg integral and that totally makes my day. <a \href="tube.sfu-kras.ru/video/407?playlist=397"> Determinant evaluations using Integral representations<\a> . Look around the 25 minute mark $\endgroup$ – Vasu vineet Nov 28 '10 at 8:35
  • $\begingroup$ Vasu vineet: That was really great! Thanks for pointing it out. $\endgroup$ – Faisal Nov 28 '10 at 9:46
  • $\begingroup$ You're welcome! The other videos are well worth a watch too. $\endgroup$ – Vasu vineet Nov 28 '10 at 12:05
  • $\begingroup$ The explicit formula for the inverse of Cauchy's matrix is listed as an (easy) exercise (rating 26), as Exercise 1.2.3-46 in The Art of Computer Programming. $\endgroup$ – Suvrit Nov 28 '10 at 17:20
2
$\begingroup$

(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.)

  1. 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 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.

  2. 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.

$\endgroup$
16
$\begingroup$

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 $

$\endgroup$
  • $\begingroup$ Wow. It's amazing what you can dig up on the internet. I've never worked out the details, but I always had the impression that the Cholesky decomposition was related to Gram-Schmidt. It's not? But I do want to emphasize that everything I described I learned from Takahiro Shiota. $\endgroup$ – Deane Yang Dec 3 '10 at 13:53
  • 3
    $\begingroup$ Of course, I have to upvote this answer. $\endgroup$ – Deane Yang Dec 3 '10 at 13:54
8
$\begingroup$

A simple proof is in the paper "Fibonacci numbers and orthogonal polynomials" by Christian Berg.

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
6
$\begingroup$

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*}$$

$\endgroup$
  • 2
    $\begingroup$ I don't consider this a circuitous proof at all. I first saw this question as a starred problem in a textbook (Hoffman-Kunze?) but could not solve it even after asking both professors and, after I entered graduate school, other graduate students. Finally, Takahiro Shiota showed me the calculation done in this paper. $\endgroup$ – Deane Yang Nov 28 '10 at 16:31
  • $\begingroup$ @Deane: I remember seeing a proof that didn't use Cholesky machinery, but sadly I can't find the reference now. The only reason I remember Hitotumatu's paper is that I was once stress-testing a Cholesky decomposition routine I wrote for a certain obscure language, and was looking for matrices with recognizable Cholesky triangles. $\endgroup$ – J. M. is not a mathematician Nov 28 '10 at 16:44
  • $\begingroup$ I don't have access to the Hitotumato-paper; but the cholesky-decomposition on its own gives triangular matrices with fractional, if not irrational, entries. A slightly different triangular decomposition seem to allow integer arithmetic. If you decompose $ Hilb = M * D * M^t$ having D diagonal and M lower triangular with unit diagonal, then the inverses of M and D are (empirically) integer matrices. I think that should be waterproof-derivable more easily than an argument via cholesky. $\endgroup$ – Gottfried Helms Nov 28 '10 at 22:18
  • $\begingroup$ @Gottfried: Yes, the paper also gives explicit expressions for the $\mathbf L\mathbf D\mathbf L^T$ decomposition of the Hilbert matrix. I any event, If you have a Cholesky decomposition, you can easily obtain the $\mathbf L\mathbf D\mathbf L^T$ decomposition, and vice versa. ($\mathbf G=\mathbf L\sqrt{\mathbf D}$) $\endgroup$ – J. M. is not a mathematician Nov 28 '10 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.