Hilbert matrix

From Wikipedia, the free encyclopedia

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

B_ij = 1 / (i + j − 1).

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

$B = \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

$B_{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 · 10⁵.

[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_{ij})_{i,j}={{c_n^{\;4}}\over {c_{2n}}}$

for the determinant of the n × n Hilbert matrix. Here c_n 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 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_{ij})_{i,j}}={{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 c_n he obtains the raw asymptotic result

$\det(H_{ij})_{i,j}=4^{-n^2+r_n}$

where the error term r_n is o(n^{2^{). A more precise asymptotic result (which can be established using Stirling's approximation of the factorial) is}}

^{where a_n converges to some constant as .}

^{[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}

^{where n is the order of the matrix.}

^{The condition number grows as .}

^{[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.}