13
$\begingroup$

The $n\times n$ Hilbert matrix $H$ is defined as follows

$$H_{ij} = \frac{1}{i+j-1}, \qquad 1\leq i,j\leq n$$

What is known about the singular values $\sigma_1 \geq \cdots \geq \sigma_n$ of $H$?

For example, it is known that the matrix is very ill-conditioned, i.e., [1]

$$\dfrac{\sigma_1}{\sigma_n} = \mathcal O \left( \frac{1+\sqrt{2})^{4n}}{\sqrt{n}} \right)$$

But are there estimates for $\sigma_k$ for $2\leq k\leq n-1$? Or is there a bound on $1\leq k\leq n$ such that $\sigma_k > \epsilon$ for some $\epsilon>0$? I am interested in this problem because I would like to know the numerical rank of $H$.


[1] J. Todd, "The condition of the finite segments of the Hilbert matrix." Contributions to the solution of systems of linear equations and the determination of eigenvalues, 39 (1954), pp. 109-116.

$\endgroup$
  • $\begingroup$ You probably meant $\sigma_k > \epsilon$, no? (also, note that since the Hilbert matrix is symmetric positive definite, its singular values are the same as its eigenvalues. $\endgroup$ – Suvrit Jul 18 '13 at 17:45
  • $\begingroup$ Thanks, corrected. Yes, I agree that the singular values of H are the same as the eigenvalues of H (after ordering). $\endgroup$ – alext87 Jul 18 '13 at 17:54
6
$\begingroup$

While not a full characterization, the following result on $\sigma_n$ shows that $\sigma_k > \epsilon_n$, since $\sigma_n \ge \epsilon_n$.

Following my answer on this MO question here, we see that

\begin{equation*} \sigma_n \ge \frac{\det(H)}{\left[m + s/\sqrt{n-1}\right]^{n-1}} =: \epsilon_n, \end{equation*} where \begin{eqnarray*} m &=& \tfrac{\text{trace} H}{n} = \tfrac{1}{n}\left(\tfrac{H_{n-1/2}}{2} + \log 2\right),\\ s &=& \sqrt{\tfrac{\text{trace}H^2}{n} - m^2}, \end{eqnarray*} where $H_n$ is the nth Harmonic number).

Since it is known that $\det(H) = \frac{c_n^4}{c_{2n}}$, where $c_n := \prod_{i=1}^{n-1}i!$, the above bound on $\sigma_n$ is fully determined (I'm leaving an analytic / "closed-form" evaluation of $\text{trace}H^2$ as an exercise).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Notice that $tr(H^2) = \sum_{ij} h_{ij}^2$, and curiously a week or so ago, other aspects of the matrix $[h_{ij}^2]$ were discussed at mathoverflow.net/questions/136306/… $\endgroup$ – Suvrit Jul 19 '13 at 0:20
  • $\begingroup$ This is a nice lower bound on the smallest singular value, and I enjoyed the post on $H^2$. Thank you very much! Your answer shows when $H$ is numerically rank deficient, but not the numerical rank of H. Still this is a good step in that direction. $\endgroup$ – alext87 Jul 25 '13 at 8:22
6
$\begingroup$

I came back to this a few months ago and I can now answer my own question. I hope it is appropriate to answer my own question given the length of time.

Bernhard Beckermann and I just submitted a paper [1] that shows that if $AX-XB = F$ with $A$ and $B$ normal matrices, then the singular values of $X$ can be bounded as $$ \sigma_{1+\nu k}(X) \leq Z_k(\sigma(A),\sigma(B))\|X\|_2, \qquad \nu = {\rm rank}(F), $$ where $\sigma(A)$ and $\sigma(B)$ are the spectra of $A$ and $B$, respectively, and $Z_k(E,F)$ is the so-called Zolotarev number. More precisely, $$ Z_k(E,F) = \inf_{r\in\mathcal{R}_{k,k}} \frac{\sup_{z\in E}|r(z)|}{\inf_{z\in F}|r(z)|}, $$ where $\mathcal{R}_{k,k}$ is the space of degree $(k,k)$ rational functions. This is called the third Zolotarev problem.

In the case of the Hilbert matrix, let $A = {\rm diag}(1/2,3/2,\ldots,n-1/2)$ and $B = -A$ then $$ AH - HB = \begin{bmatrix}1\\\vdots\\1 \end{bmatrix}\begin{bmatrix}1&\cdots&1 \end{bmatrix}. $$ Hence, $\nu=1$ and $$ \sigma_{1+k}(H) \leq Z_k([-n+1/2,-1/2],[1/2,n-1/2])\|H\|_2. $$ Fortunately, bounds on the Zolotarev numbers are well-studied (in [1] we give asymptotically tight bounds) and we conclude that $$ \sigma_{1+k}(H) \leq 4\left[{\rm exp}\left(\frac{\pi^2}{2\log(8n-4)}\right)\right]^{-2k}\|H\|_2. $$ If we seek the numerical rank of $H$ for some $0<\epsilon<1$, i.e., $k = {\rm rank}_\epsilon(H)$ if $k$ is the smallest integer such that $\sigma_{k+1}(H)\leq \epsilon\|H\|_2$, then from the bound on the singular values of $H$ we conclude that $$ {\rm rank}_\epsilon(H) \leq \Bigg\lceil \frac{\log(8n-4)\log(4/\epsilon)}{\pi^2} \Bigg\rceil. $$

This shows that Hilbert matrices are not only exponentially ill-conditioned with $n$, but its singular values decay geometrically to zero too. This methodology extends to any matrix with displacement structure such as Pick, Cauchy, Loewner, real Vandermonde, and positive definite Hankel matrices. For more details, see [1].

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting! Though these are upper bounds, not lower bounds as you asked in the original question, no? $\endgroup$ – Suvrit Oct 1 '16 at 20:07
  • $\begingroup$ It was stated a little backwards by my younger self: it's still about the numerical rank given by ${\rm rank}_\epsilon(H)$. The answer above gives an upper bound on ${\rm rank}_\epsilon(H)$ and hence $k$ (in my original question). Suppose that $k$ is an integer such that $\sigma_{k}(H)>\epsilon$ for some $0<\epsilon <1$, then from above and $\|H\|_2\leq \pi$ we know that $k \leq \lceil \log(8n-4)\log(4\pi/\epsilon)/\pi^2\rceil+1$. $\endgroup$ – alext87 Oct 1 '16 at 20:40
  • $\begingroup$ I do not know how to get lower bounds on the singular values. This may involve developing lower bounds for so-called discrete Zolotarev numbers (if one goes for the above methodology). I am not sure if this is possible at the moment. For more details on discrete Zolotarev numbers, see: link.springer.com/article/10.1007/s00365-010-9087-6 $\endgroup$ – alext87 Oct 1 '16 at 20:42

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.