Let $A$ be the $n\times n$ matrix given by

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

Show that $A$ is invertible and that the inverse has integer entries.

I was able to show that $A$ is invertible. How do I show that $A^{-1}$ has integer entries?

This matrix is called the Hilbert matrix. The problem appears as exercise 12 in section 1.6 of Hoffman and Kunze's Linear Algebra (2nd edition).

  • 5
    $\begingroup$ In fact, you have a closed form for the entries of $A^{-1}$. This is a [Hilbert matrix]( en.wikipedia.org/wiki/Hilbert_matrix) $\endgroup$ – Ewan Delanoy Jun 26 '13 at 14:58
  • 2
    $\begingroup$ May I ask how you proved that $A$ is invertible? I do remember trying to find an elegant proof of that about a year ago and didn't quite manage to find it. (Just to be sure: I don't consider it elegant in this case to find the determinant) $\endgroup$ – HSN Jun 26 '13 at 15:10
  • 1
    $\begingroup$ Related question on MO: mathoverflow.net/questions/47561/… $\endgroup$ – Jason Conti Jul 29 '13 at 16:53
  • 1
    $\begingroup$ Related, perhaps dupe of math.stackexchange.com/q/46862/8271 $\endgroup$ – leo Jul 29 '13 at 18:42
  • 2
    $\begingroup$ @HSN The vectors $x^i$ in $L_2[0,1]$ are linearly independent, so their Gram matrix is invertible. $\endgroup$ – user21467 Jul 31 '13 at 16:47

Be wise, generalize (c)

I think the nicest way to answer this question is the direct computation of the inverse - however, for a more general matrix including the Hilbert matrix as a special case. The corresponding formulas have very transparent structure and nontrivial further generalizations.

The matrix $A$ is a particular case of the so-called Cauchy matrix with elements $$A_{ij}=\frac{1}{x_i-y_j},\qquad i,j=1,\ldots, N.$$ Namely, in the Hilbert case we can take $$x_i=i-\frac{1}{2},\qquad y_i=-i+\frac12.$$ The determinant of $A$ is given in the general case by $$\mathrm{det}\,A=\frac{\prod_{1\leq i<j\leq N}(x_i-x_j)(y_j-y_i)}{\prod_{1\leq i,j\leq N}(x_i-y_j)}.\tag{1}$$ Up to an easily computable constant prefactor, the structure of (1) follows from the observation that $\mathrm{det}\,A$ vanishes whenever there is a pair of coinciding $x$'s or $y$'s. (In the latter case $A$ contains a pair of coinciding raws/columns). For our $x$'s and $y$'s the determinant is clearly non-zero, hence $A$ is invertible.

One can also easily find the inverse $A^{-1}$, since the matrix obtained from a Cauchy matrix by deleting one row and one column is also of Cauchy type, with one $x$ and one $y$ less. Taking the ratio of the corresponding two determinants and using (1), most of the factors cancel out and one obtains \begin{align} A_{mn}^{-1}=\frac{1}{y_m-x_n}\frac{\prod_{1\leq i\leq N}(x_n-y_i)\cdot\prod_{1\leq i\leq N}(y_m-x_i)}{\prod_{i\neq n}(x_n-x_i)\cdot\prod_{i\neq m}(y_m-y_i)}.\tag{2} \end{align}

For our particular $x$'s and $y$'s, the formula (2) reduces to \begin{align} A_{mn}^{-1}&=\frac{(-1)^{m+n}}{m+n-1}\frac{\frac{(n+N-1)!}{(n-1)!}\cdot \frac{(m+N-1)!}{(m-1)!}}{(n-1)!(N-n)!\cdot(m-1)!(N-m)!}=\\ &=(-1)^{m+n}(m+n-1){n+N-1 \choose N-m}{m+N-1 \choose N-n}{m+n-2\choose m-1}^2. \end{align} The last expression is clearly integer. $\blacksquare$

  • 1
    $\begingroup$ Thanks for this. The only problem I have with this answer is that it is asked in Chapter 1 of Hoffman and Kunze long before the introduction of the concept of determinant. All we know really is that an invertible matrix can be row-reduced to the identity. $\endgroup$ – Gregory Grant Jun 21 '16 at 19:11
  • 1
    $\begingroup$ @GregoryGrant And did you find any solution just using the tools provided for the first exercise? I'm curious. $\endgroup$ – Bijesh K.S May 7 '17 at 18:55

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.