TITLE: The singular values of the Hilbert matrix
QUESTION [15 upvotes]: 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.

REPLY [7 votes]: 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].
{"set_name": "stack_exchange", "score": 15, "question_id": 137059}