Hilbert matrix

From Wikipedia, the free encyclopedia

In linear algebra, a Hilbert matrix is a matrix with the unit fraction elements

H_{ij} = \frac{1}{i+j-1}.

For example, this is the 5 × 5 Hilbert matrix:

H = \begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5} \\[4pt] \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \frac{1}{6} \\[4pt] \frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \frac{1}{6} & \frac{1}{7} \\[4pt] \frac{1}{4} & \frac{1}{5} & \frac{1}{6} & \frac{1}{7} & \frac{1}{8} \\[4pt] \frac{1}{5} & \frac{1}{6} & \frac{1}{7} & \frac{1}{8} & \frac{1}{9} \end{bmatrix}.

The Hilbert matrix can be regarded as derived from the integral

H_{ij} = \int_{0}^{1} x^{i+j-2} \, dx,

that is, as a Gramian matrix for powers of x. It is a Hankel matrix.

The Hilbert matrices are canonical examples of ill-conditioned matrices, making them notoriously difficult to use in numerical computation. For example, the 2-norm condition number of the matrix above is about 4.8 · 105.

[edit] Historical note

In Hilbert's oeuvre, the Hilbert matrix figures in his article Ein Beitrag zur Theorie des Legendreschen Polynoms (published in the journal Acta Mathematica, vol. 18, 155-159, 1894).

That article addresses the following question in approximation theory: "Assume that I = [a, b] is a real interval. Is it then possible to find a non-zero polynomial P with integral coefficients, such that the integral

\int_{a}^b P(x)^2 dx

is smaller than any given bound \varepsilon>0, taken arbitrarily small?" Using the asymptotics of the determinant of the Hilbert matrix he proves that this is possible if the length b − a of the interval is smaller than 4.

He derives the exact formula

\det(H)={{c_n^{\;4}}\over {c_{2n}}}

for the determinant of the n × n Hilbert matrix. Here cn is

\prod_{i=1}^{n-1} i^{n-i}=\prod_{i=1}^{n-1} i!.\,

Hilbert also mentions the curious fact that the determinant of the Hilbert matrix is the reciprocal of an integer (see sequence A005249) which he expresses as the discriminant of a certain hypergeometric polynomial related to the Legendre polynomial. This fact also follows from the identity

{1 \over \det (H)}={{c_{2n}}\over {c_n^{\;4}}}=n!\cdot \prod_{i=1}^{2n-1} {i \choose [i/2]}

Using Euler–MacLaurin summation on the logarithm of the cn he obtains the raw asymptotic result

\det(H)=4^{-n^2+r_n}

where the error term rn is o(n2). A more precise asymptotic result (which can be established using Stirling's approximation of the factorial) is

\det(H)=a_n\, n^{-1/4}(2\pi)^n \,4^{-n^2}

where an converges to some constant a_\infty=0.6450... as n\rightarrow\infty.

[edit] Properties

The Hilbert matrix is symmetric and positive definite.

The determinant can be expressed in closed form, as a special case of the Cauchy determinant. The Hilbert matrix is also totally positive (meaning the determinant of every submatrix is positive). The inverse can also be expressed in closed form; its entries are

(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

where n is the order of the matrix. It follows that the entries of the inverse matrix are all integer.

The condition number grows as O(e^{3.5255n}/\sqrt{n}).

[edit] References

  • David Hilbert, Collected papers, vol. II, article 21.
  • Beckermann, Bernhard. "The condition number of real Vandermonde, Krylov and positive definite Hankel matrices" in Numerische Mathematik. 85(4), 553--577, 2000.
  • Choi, M.-D. "Tricks or Treats with the Hilbert Matrix" in American Mathematical Monthly. 90, 301–312, 1983.
  • Todd, John. "The Condition Number of the Finite Segment of the Hilbert Matrix" in National Bureau of Standards, Applied Mathematics Series. 39, 109–116, 1954.
  • Wilf, H.S. Finite Sections of Some Classical Inequalities. Heidelberg: Springer, 1970.