Bernhard Beckermann
email: bernhard.beckermann@univ-lille1.fr

Alex Townsend
email: townsend@cornell.edu

Bounds on the Singular Values of Matrices with Displacement Structure \ast

Keywords: singular values, displacement structure, Zolotarev, rational AMS subject classifications. 15A18, 26C15

Matrices with displacement structure, such as Pick, Vandermonde, and Hankel matrices, appear in a diverse range of applications. In this paper, we use an extremal problem involving rational functions to derive explicit bounds on the singular values of such matrices. For example, we show that the kth singular value of a real n \times n positive definite Hankel matrix, Hn, is bounded by C\rho - k/ log n \| Hn\| 2 with explicitly given constants C > 0 and \rho > 1, where \| Hn\| 2 is the spectral norm. This means that a real n \times n positive definite Hankel matrix can be approximated, up to an accuracy of \epsilon \| Hn\| 2 with 0 < \epsilon < 1, by a rank \scrO (log n log(1/\epsilon )) matrix. Analogous results are obtained for Pick, Cauchy, real Vandermonde, L\" owner, and certain Krylov matrices.

solving systems of linear equations can be derived for many of these matrices by exploiting (1.1) [START_REF] Heinig | Algebraic Methods for Toeplitz-Like Matrices and Operators[END_REF][START_REF] Morf | Fast Algorithms for Multivariable Systems[END_REF].

In this paper, we use the displacement structure to derive explicit bounds on the singular values of matrices that satisfy (1.1) by using an extremal problem for rational functions from complex approximation theory. In particular, we prove that the following inequality holds (see Theorem 2.1):

\sigma j+\nu k (X) \leq Z k (E, F )\sigma j (X), 1 \leq j + \nu k \leq n, (1.2)
where \sigma 1 (X), . . . , \sigma n (X) denote the singular values of X and Z k (E, F ) is the Zolotarev number for complex sets E and F that depend on A and B (see (1.4)). Researchers have previously exploited the connection between the Sylvester matrix equation and Zolotarev numbers for selecting algorithmic parameters in the alternating direction implicit (ADI) method [START_REF] Beckermann | An error analysis for rational Galerkin projection applied to the Sylvester equation[END_REF][START_REF] Birkhoff | Alternating direction implicit methods[END_REF][START_REF] Lebedev | On a Zolotarev problem in the method of alternating directions[END_REF], and others have demonstrated that the singular values of matrices satisfying certain Sylvester matrix equations have rapidly decaying singular values [START_REF] Antoulas | On the decay rate of Hankel singular values and related issues[END_REF][START_REF] Baker | Fast singular value decay for Lyapunov solutions with nonnormal coefficients[END_REF][START_REF] Penzl | Eigenvalue decay bounds for solutions of Lyapunov equations: The symmetric case[END_REF]. Here, we derive explicit bounds on all the singular values of structured matrices. Table 1.1 summarizes our main singular value bounds.

Not every matrix with displacement structure is numerically of low rank. For example, the identity matrix is a full rank Toeplitz matrix and the exchange matrix1 is a full rank Hankel matrix. Moreover, we show in Example 5.1 that the inequality in (1.2) is trivial for circulant as well as Toeplitz matrices. The properties of A and B in (1.1) are crucial. If A and B are normal matrices, then one expects X to be numerically of low rank only if the eigenvalues of A and B are well separated (see Theorem 2.1). If A and B are both not normal, then descriptive bounds on the numerical rank of X are more subtle (see Corollary 2.2, [START_REF] Baker | Fast singular value decay for Lyapunov solutions with nonnormal coefficients[END_REF], and [48, Lemma 1]).

By the Eckart--Young theorem [START_REF] Golub | Matrix Computations[END_REF]Theorem 2.4.8], singular values measure the distance in the spectral norm from X to the set of matrices of a given rank, i.e., \sigma j (X) = min \bigl\{ \| X -Y \| 2 : Y \in \BbbC m\times n , rank(Y ) = j -1 \bigr\} .

For an 0 < \epsilon < 1, we say that the \epsilon -rank of a matrix X is k if k is the smallest integer such that \sigma k+1 (X) \leq \epsilon \| X\| 2 . That is,

(1.3) rank \epsilon (X) = min k\geq 0

\{ k : \sigma k+1 (X) \leq \epsilon \| X\| 2 \} .

Table 1.2 Summary of the upper bounds proved on the \epsilon -rank of matrices with displacement structure. For the bounds above to be valid for Cm,n and Ln, mild ``separation conditions"" must hold (see section 4). The number \gamma is the absolute value of the cross-ratio of a, b, c, and d; see (3.7). The first three rows show an \epsilon -rank of at most \scrO (log \gamma log(1/\epsilon )), and the last three rows show an \epsilon -rank of at most \scrO (log n log(1/\epsilon )). Thus, we may approximate X to a precision of \epsilon \| X\| 2 by a rank k = rank \epsilon (X) matrix.

Matrix class

An immediate consequence of explicit bounds on the singular values of certain matrices is a bound on the \epsilon -rank. Table 1.2 summarizes our main upper bounds on the \epsilon -rank of matrices with displacement structure. The form of the inequalities in (1.2) also allows one to use Zolotarev numbers to bound the \epsilon -rank of matrices when measured in the Frobenius norm [START_REF] Shi | On the Numerical Ranks of Tensors[END_REF]Lemma 5.1], which is a key observation to extending the bounds in this paper to tensors [START_REF] Shi | On the Numerical Ranks of Tensors[END_REF].

Zolotarev numbers have already proved useful for deriving tight bounds on the condition number of matrices with displacement structure [START_REF] Beckermann | On the Numerical Condition of Polynomial Bases: Estimates for the Condition Number of Vandermonde, Krylov and Hankel Matrices[END_REF][START_REF] Beckermann | The condition number of real Vandermonde, Krylov and positive definite Hankel matrices[END_REF], where the condition number of a rectangular m \times n matrix X is given by \kappa 2 (X) = \sigma 1 (X)/\sigma min(m,n) (X). For example, the first author proved that a real n \times n positive definite Hankel matrix, H n , with n \geq 3, is exponentially ill-conditioned [START_REF] Beckermann | The condition number of real Vandermonde, Krylov and positive definite Hankel matrices[END_REF]. That is, \kappa 2 (H n ) \geq \gamma n - 1 16n , \gamma \approx 3.210, and that this bound cannot be improved by more than a factor of n times a modest constant. The Hilbert matrix given by (H n ) jk = 1/(j + k -1), for 1 \leq j, k \leq n, is the classic example of an exponentially ill-conditioned positive definite Hankel matrix [65, eqn. (3.35)]. Similar exponential ill-conditioning has been shown for certain Krylov matrices and real Vandermonde matrices [START_REF] Beckermann | The condition number of real Vandermonde, Krylov and positive definite Hankel matrices[END_REF]. This paper extends the application of Zolotarev numbers to deriving bounds on the singular values of matrices with displacement structure---not just the condition number. The bounds we derive are particularly tight for \sigma j (X), where j is small with respect to n. Improved bounds on \sigma j (X) when j/n \rightar c \in (0, 1) may be possible with the ideas found in [START_REF] Beckermann | Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method[END_REF]. Nevertheless, our interest here is to justify the application of low rank techniques on matrices with displacement structure by proving that such matrices are often well approximated by low rank matrices. The bounds that we derive are sufficient for this purpose.

For an integer k, let \scrR k,k denote the set of irreducible rational functions of the form p(x)/q(x), where p and q are polynomials of degree at most k. Given two closed disjoint sets E, F \subset \BbbC , the corresponding Zolotarev number, Z k (E, F ), is defined by

Z k (E, F ) := inf r\in \scrR k,k sup z\in E | r(z)| inf z\in F | r(z)| , (1.4)
where the infimum is attained for some extremal rational function. As a general rule, the number Z k (E, F ) decreases rapidly to zero with k if E and F are sets that are disjoint and well separated. Zolotarev numbers satisfy several immediate properties: for any sets E and F and integers k, k 1 , and k 2 , one has

Z 0 (E, F ) = 1, Z k (E, F ) = Z k (F, E), Z k+1 (E, F ) \leq Z k (E, F ), and Z k1+k2 (E, F ) \leq Z k1 (E, F )Z k2 (E, F ). They also satisfy Z k (E 1 , F 1 ) \leq Z k (E 2 , F 2 ) if E 1 \subsete E 2 and F 1 \subsete F 2 as well as Z k (E, F ) = Z k (T (E), T (F ))
, where T is any M\" obius transformation [START_REF] Akhieser | Elements of the Theory of Elliptic Functions[END_REF]. As k \rightar \infty the value for Z k (E, F ) is known asymptotically to be lim k\rightar\infty

(Z k (E, F )) 1/k = exp \biggl( - 1 cap(E, F ) \biggr)
,

where cap(E, F ) is the logarithmic capacity of a condenser with plates E and F ; see [START_REF] Gon\v Car | Zolotarev problems connected with rational functions[END_REF] or [START_REF] Saff | Logarithmic Potentials with External Fields[END_REF]Theorem VIII.3.5]. A lower bound is also known [50, Theorem VIII.3.1]:

Z k (E, F ) \geq exp \biggl( - k cap(E, F ) \biggr) , k \geq 0. (1.5)
To readers who are not familiar with Zolotarev numbers, it may seem that (1.2) trades a difficult task of directly bounding the singular values of a matrix X with a more abstract task of understanding the behavior of Z k (E, F ). However, Zolotarev numbers have been extensively studied in the literature [START_REF] Akhieser | Elements of the Theory of Elliptic Functions[END_REF][START_REF] Gon\v Car | Zolotarev problems connected with rational functions[END_REF][START_REF] Zolotarev | Application of elliptic functions to questions of functions deviating least and most from zero[END_REF], and for certain sets E and F the extremal rational function is known explicitly [1, section 50] and [START_REF] Starke | Near-circularity for the rational Zolotarev problem in the complex plane[END_REF] (see section 3). Our major challenge for bounding singular values is to carefully select sets E and F so that one can use complex analysis and M\" obius transformations to convert the associated extremal rational approximation problem in (1.4) into one that has an explicitly known bound.

The paper is structured as follows. In section 2 we prove (1.2), giving us a bound on the singular values of matrices with displacement structure in terms of Zolotarev numbers. In section 3 we derive new sharper bounds on Z k ([ - b, - a], [a, b]) when 0 < a < b < \infty by correcting an infinite product formula from Lebedev (see Theorem 3.1 and Corollary 3.2). In section 4 we derive explicit bounds on the singular values of Pick, Cauchy, and L\" owner matrices. In section 5 we tackle the challenging task of showing that all real Vandermonde and positive definite Hankel matrices have rapidly decaying singular values and can be approximated, up to an accuracy of 0 < \epsilon < 1, by a rank \scrO (log n log(1/\epsilon )) matrix. While no additional novel results are included in this updated version of [START_REF] Beckermann | On the singular values of matrices with displacement structure[END_REF], we have added extra commentary on the related literature and reference recent applications.

The Singular Values of Matrices with Displacement

Structure and Zolotarev Numbers. Let X be an m \times n matrix with m \geq n that satisfies (1.1). We show that the singular values of X can be bounded from above in terms of Zolotarev numbers. First, we assume that A and B in (1.1) are normal matrices and later remove this assumption in Corollary 2.2. In Theorem 2.1 the spectrum (set of eigenvalues) of A and B is denoted by \sigma (A) and \sigma (B), respectively. 2Theorem 2.1. Let A \in \BbbC m\times m and B \in \BbbC n\times n be normal matrices with m \geq n, and let E and F be complex sets such that \sigma (A) \subsete E and \sigma (B) \subsete F . Suppose that the matrix X \in \BbbC m\times n satisfies AX -XB = M N \ast , M \in \BbbC m\times \nu , N \in \BbbC n\times \nu , where 1 \leq \nu \leq n is an integer. Then, for j \geq 1, the singular values of X satisfy

\sigma j+\nu k (X) \leq Z k (E, F ) \sigma j (X), 1 \leq j + \nu k \leq n,
where Z k (E, F ) is the Zolotarev number in (1.4).

Proof. Let p(z) and q(z) be polynomials of degree at most k. First, we show that (2.1) rank(p(A)Xq(B) -q(A)Xp(B)) \leq \nu k, \nu = rank(AX -XB).

Suppose that p(z) = z s and q(z) = z t , where k \geq s \geq t. Then

p(A)Xq(B) -q(A)Xp(B) = A t \bigl( A s - t X -XB s - t \bigr) B t = s - t - 1 \sum j=0 A t+j (AX -XB)B s - 1 - j = s - t - 1 \sum j=0 \bigl( A t+j M \bigr) \bigl( N \ast B s - 1 - j \bigr) .
In the last sum we have terms of the form (A \ell M )(N \ast B \wp ), with 0 \leq \ell , \wp \leq k -1. By adding together the terms occurring in p(A)Xq(B) -q(A)Xp(B) for general degree k polynomials p and q, we conclude that there exist coefficients c \ell ,\wp \in \BbbC such that

p(A)Xq(B) -q(A)Xp(B) = k - 1 \sum \ell ,\wp =0 c \ell ,\wp \bigl( A \ell M \bigr) (N \ast B \wp ) .
This shows that the rank of p(A)Xq(B) -q(A)Xp(B) is bounded above by k times the number of columns of M , proving (2.1). Now, let r(z) = p(z)/q(z), where p and q are polynomials of degree k so that r(z) is the extremal rational function for the Zolotarev number in (1.4). This means that p(z) and q(z) are not zero on F and E, respectively, so that p(B) and q(A) are invertible matrices. From (2.1) we know that \Delta = p(A)Xq(B) -q(A)Xp(B) has rank at most \nu k, and hence the matrix

Y = - q(A) - 1 \Delta p(B) - 1 = X -r(A)Xr(B) - 1
is of rank at most \nu k. Let X j be the best rank j -1 approximation to X in \| \cdot \| 2 , and let

Y j - 1 = r(A)X j - 1 r(B) - 1 . Since Y j - 1 is of rank at most j -1, Y + Y j - 1 is of rank at most j + \nu k -1. This implies that \sigma j+\nu k (X) \leq \| X -Y -Y j - 1 \| 2 = \bigm\| \bigm\| r(A)(X -X j - 1 )r(B) - 1 \bigm\| \bigm\| 2 \leq \| r(A)\| 2 \bigm\| \bigm\| r(B) - 1 \bigm\| \bigm\| 2 \sigma j (X)
, where in the last inequality we used the relation \sigma j (X) = \| X -X j - 1 \| 2 . Finally, since A and B are normal we have \| r(A)\| 2 = sup z\in \sigma (A) | r(z)| and \| r(B) - 1 \| 2 = sup z\in \sigma (B) | r(z) - 1 | . We conclude by the definition of r(z) that (2.2)

\sigma j+\nu k (X) \sigma j (X) \leq sup z\in \sigma (A) | r(z)| sup z\in \sigma (B) 1 | r(z)| = Z k (\sigma (A), \sigma (B)) \leq Z k (E, F ),
as required.

Theorem 2.1 shows that if A and B are normal matrices in (1.1), then the singular values decay at least as quickly as Z k (\sigma (A), \sigma (B)) in (1.4). In particular, when \sigma (A) and \sigma (B) are disjoint and well separated we expect Z k (\sigma (A), \sigma (B)) to decay rapidly to zero, and hence so do the singular values of X. The singular value bound in Theorem 2.1 is most useful when \nu \leq 5 as it tends to not be tight for large \nu . An extension of Theorem 2.1 has derived useful bounds when \nu is large, provided that M N \ast has rapidly decaying singular values [START_REF] Townsend | On the singular values of matrices with high displacement rank[END_REF]. It is also known that X can have off-diagonal low rank structure if M N \ast does [START_REF] Massei | Solving rank-structured Sylvester and Lyapunov equations[END_REF].

For those readers who are familiar with the ADI method [START_REF] Birkhoff | Alternating direction implicit methods[END_REF], an analogous proof of Theorem 2.1 is to run the ADI method for k steps with shift parameters given by the zeros and poles of the extremal rational function for Z k (E, F ). By doing this, one constructs a rank \nu k approximant X \nu k for X, which shows that \sigma 1+\nu k (X) \leq \| X -X \nu k \| 2 \leq Z k (E, F )\sigma 1 (X). The so-called factored ADI method is a modification of the ADI method that computes X \nu k in low rank form [START_REF] Benner | On the ADI method for Sylvester equations[END_REF][START_REF] Wachspress | Trail to a Lyapunov equation solver[END_REF] and means that it is computationally possible (and usually efficient) to construct low rank approximants that attain all our singular value bounds in this paper. The connection between Zolotarev numbers and the optimal parameter selection for the ADI method has been previously exploited [START_REF] Lebedev | On a Zolotarev problem in the method of alternating directions[END_REF].

For matrices A and B that are not normal, Theorem 2.1 can be extended by using K-spectral sets [START_REF] Badea | Spectral sets[END_REF]. Given a matrix A, a complex set E is said to be a K-spectral set for A if the spectrum \sigma (A) of A is contained in E and the inequality \| r(A)\| 2 \leq K\| r\| E holds for every bounded rational function on E, where \| r\| E = sup z\in E | r(z)| . Similar extensions have been noted when B = A \ast in (1.1) and the sets E and F are taken to be the fields of values 3 for A and B, respectively [START_REF] Baker | Fast singular value decay for Lyapunov solutions with nonnormal coefficients[END_REF].

We have the following extension of Theorem 2.1.

Corollary 2.2. Suppose that the assumptions of Theorem 2.1 hold, except that the matrices A and B are not necessarily normal. Also suppose that E and F are K-spectral sets for A and B for fixed constants K A , K B > 0, respectively. Then we have \sigma j+\nu k (X) \leq

K A K B Z k (E, F ) \sigma j (X).
Proof. It is only the first inequality in (2.2) of the proof of Theorem 2.1 that requires A and B to be normal matrices. When A is not a normal matrix, the equality \| r(A)\| 2 = sup z\in \sigma (A) | r(z)| may not hold. Instead, we replace it by the K-spectral set bounds given by \| r(A)\| 2 \leq K A \| r\| E and \| r(B)\| 2 \leq K B \| r\| F . Note that since p(z) and q(x) are not zero on F and E, respectively, one can show via the Schur decomposition that p(B) and q(A) are invertible matrices.

It is worth noting that the bound in Corollary 2.2 is not always descriptive when A and B are nonnormal matrices [START_REF] Baker | Fast singular value decay for Lyapunov solutions with nonnormal coefficients[END_REF]. There is also the remarkable result in [48, Lemma 1] that shows that for any prescribed eigenvalue distribution and monotonically decaying sequence s 1 \geq \cdot \cdot \cdot \geq s n \geq 0, there exists a (typically nonnormal) matrix A with the prescribed eigenvalues and a vector b such that the singular values of X satisfying AX + XA \ast = - b b \ast are \sigma j (X) = s j .

Theorem 2.1 and Corollary 2.2 provide bounds on the singular values of X in terms of Zolotarev numbers. Therefore, to derive analytic bounds on the singular values of matrices with displacement structure, we must now calculate explicit bounds on Zolotarev numbers---a topic that fortunately is extensively studied. 3 Crouzeix and Palencia have shown that there exists a universal constant 2 \leq K \leq 1 + \surd 2 such that the field of values E of A is a K-spectral set [START_REF] Crouzeix | Bounds for analytic functions of matrices[END_REF][START_REF] Crouzeix | The numerical range is a (1 + \surd 2)-spectral set[END_REF].

Zolotarev Numbers.

In this section, we give explicit lower and upper bounds for Zolotarev numbers for real intervals and disks. Explicit bounds on Z k (E, F ) are known for more general sets E and F , but the bounds tend to not to be tight [START_REF] Ganelius | Rational functions, capacities and approximation[END_REF]. 3)] for the upper bound. 4 There are also bounds obtained directly from an infinite product formula for \surd Z k [38, (1.11)]; unfortunately, the original product formula in [38, (1.11)] contains typos and one must be careful, as the typo has been copied elsewhere.

The value of \rho in (3.1) is related to the logarithmic capacity of a condenser with plates [ - b, - a] and [a, b]:

(3.2) \rho 2 = exp \biggl( 1 cap([ - b, - a], [a, b]) \biggr) , \rho = exp \biggl( \pi 2 2\mu (a/b) \biggr) > 1,
where \mu (\lambda

) = \pi 2 K( \surd 1 -\lambda 2 )/K(\lambda )
is the Gr\" otzsch ring function, and K is the complete elliptic integral of the first kind [44, (19.2.8)]:

K(\lambda ) = \int 1 0 1 \sqrt{} (1 -t 2 )(1 -\lambda 2 t 2 ) dt, 0 \leq \lambda \leq 1.
The bounds in (3.1) are not asymptotically sharp, and in Corollary 3.2 we show that the constant of 16 in the upper bound can be replaced by 4. For a proof of this sharper upper bound, we first return to the work of Lebedev [START_REF] Lebedev | On a Zolotarev problem in the method of alternating directions[END_REF] and derive a corrected infinite product formula for Z k .

Theorem 3.1. Let k \geq 1 be an integer and 0 < a < b < \infty . Then for

Z k := Z k ([ - b, - a], [a, b]) we have Z k = 4\rho - 2k \infty \prod \tau =1 (1 + \rho - 8\tau k ) 4 (1 + \rho 4k \rho - 8\tau k ) 4 , \rho = exp \biggl( \pi 2 2\mu (a/b) \biggr)
,

where \mu (\cdot ) is the Gr\" otzsch ring function.

Proof. We start by establishing a product formula for the inverse of \mu that is apparently not widely known. For \kappa \in (0, 1) set q = exp( - 2\mu (\kappa )). Since \mu (\kappa

) = \pi 2 K \bigl( \surd 1 -\kappa 2 \bigr) /K(\kappa ), we have that q = exp( - \pi K \bigl( \surd 1 -\kappa 2 \bigr) /K(\kappa ))
, and from [44, (22.2.2)] we obtain

(3.3) \kappa = \biggl( \theta 2 (0, q) \theta 3 (0, q) \biggr) 2 = 4 \surd q \infty \prod \tau =1 (1 + q 2\tau ) 4 (1 + q 2\tau - 1 ) 4 , q = q(\kappa ) = exp( - 2\mu (\kappa )) .
Here, \theta 2 (z, q) and \theta 3 (z, q) are the classical theta functions [44, (20.2.2) and (20.2.3)], and the second equality for \kappa in (3.3) is derived from the infinite product formula in [44, (20.4.3) and (20.4.4)].

In order to deduce an explicit product formula for Z k , we first note that the value of 2 \surd Z k /(1 + Z k ) is extensively reviewed by Akhiezer;5 see [1, section 51], [1, Tables 1 and2, p. 150, no. 7 and 8], and [START_REF] Akhieser | Elements of the Theory of Elliptic Functions[END_REF]Table XXIII]. This value is equal to

2 \surd Z k 1 + Z k = 1 -\lambda k 1 + \lambda k , k\mu (\lambda k ) = \mu (a/b),
for some \lambda k \in (0, 1) [1, p. 149]. Here, there is a unique \lambda k \in (0, 1) since the Gr\" otzsch ring function \mu : [0, 1] \rightar [0, \infty ] is a strictly decreasing bijection. Next, we recall that Gauss's transformation [1, Table XXI] and Landen's transformation [1, Table XX] are given by

(3.4) \mu \Biggl( 2 \surd \lambda 1 + \lambda \Biggr) = \mu (\lambda ) 2 , \mu \biggl( 1 -\lambda 1 + \lambda \biggr) = 2\mu \Bigl( \sqrt{} 1 -\lambda 2 \Bigr)
, \lambda \in (0, 1), from which we conclude that

(3.5) \mu (Z k ) = 2\mu \biggl( 2 \surd Z k 1 + Z k \biggr) = 4\mu \biggl( \sqrt{} 1 -\lambda 2 k \biggr) = \pi 2 \mu (\lambda k ) = \pi 2 k \mu (a/b) .
Therefore, from (3.5) we have

q = q(Z k ) = e - 2\mu (Z k ) = exp \biggl( - 2k \pi 2 \mu (a/b) \biggr) = \rho - 4k ,
where \rho is given in (3.2). The infinite product formula for Z k follows by setting \kappa = Z k and q = \rho - 4k in (3.3).

The infinite product in Theorem 3.1 can be estimated by observing that (1 + \rho - 4k \rho - 8\tau k ) 2 \leq (1 + \rho - 8\tau k ) 2 \leq (1 + \rho - 4k \rho - 8\tau k )(1 + \rho 4k \rho - 8\tau k ) for all \tau \geq 1. This leads to the following simple upper and lower bounds which are sufficient for the purpose of our paper.

Corollary 3.2. Let k \geq 1 be an integer and 0 < a < b < \infty . Then for

Z k := Z k ([ - b, - a], [a, b]) we have 4\rho - 2k (1 + \rho - 4k ) 4 \leq Z k \leq 4\rho - 2k (1 + \rho - 4k ) 2 \leq 4\rho - 2k , \rho = exp \biggl( \pi 2 2\mu (a/b) \biggr)
,

where \mu (\cdot ) is the Gr\" otzsch ring function.

Corollary 3.2 shows that Z k \leq 4\rho - 2k is an asymptotically sharp upper bound in the sense that the geometric decay rate and the constant 4 cannot be improved if one hopes for the bound to hold for all k. However, this does not necessarily imply that our derived singular value inequalities are asymptotically sharp. On the contrary, they are usually not. For asymptotically sharp singular value bounds, we expect that one must consider discrete Zolotarev numbers, i.e., Z k (\sigma (A), \sigma (B)) in Theorem 2.1, which are more subtle to bound and are outside the scope of this paper.

We often prefer the following slightly weaker bound that does not contain the Gr\" otzsch ring function: which is obtained by using the bound \mu (\lambda ) \leq log(2(1 + \surd 1 -\lambda 2 )/\lambda ) \leq log(4/\lambda ); see [44, (19.9.5)]. This makes our final bounds on the singular values and the \epsilonrank of matrices with displacement rank more intuitive to those readers who are less familiar with the Gr\" otzsch ring function.

Z k ([ - b, - a], [a, b]) \leq 4 \biggl[ exp \biggl( \pi 2 2 log(4b/a) \biggr) \biggr] - 2k , 0 < a < b < \infty ,
Figure 3.1 (left) shows the error between the sign function on [ - 10, - 1] \cup [1, 10] and its best \scrR 8,8 rational approximation, which equioscillates 9 times on [ - 10, - 1] and [START_REF] Akhieser | Elements of the Theory of Elliptic Functions[END_REF][START_REF] Beckermann | Error estimates and evaluation of matrix functions via the Faber transform[END_REF] to confirm its optimality.

Properties of Extremal Rational

| sgn(z) -r(z)| = 2 \surd Z k 1 + Z k , sgn(z) = \Biggl\{ 1, z \in [a, b], - 1, z \in [ - b, - a],
where the infimum is attained by the rational function [1, section 51, Table 2, no. 7 and 8]

(3.6) \r(z) = M z \prod \lfloor (k - 1)/2\rfloor j=1 z 2 + c 2j \prod \lfloor k/2\rfloor j=1 z 2 + c 2j - 1 , c j = a 2 sn 2 (jK(\kappa )/k; \kappa ) 1 -sn 2 (jK(\kappa )/k; \kappa ) .
Here, M is a real constant selected so that sgn(z) -\r(z) equioscillates on [ - b, - a] \cup [a, b], \kappa = \sqrt{} 1 -(a/b) 2 , and sn(\cdot ) is the first Jacobian elliptic function. In order to construct an extremal function for Z k with the required properties, we observe from (3.6) that M and c 1 , . . . , c k - 1 are real, and thus \bullet \r(z) is real-valued for z \in \BbbR , \bullet \r(iz) is purely imaginary for z \in \BbbR , and \bullet \r(z) is an odd function on \BbbR , i.e., \r(z) = - \r( - z) for z \in \BbbR . As a consequence, the rational function given by

R(z) = 1 + 1+Z k 1 - Z k \r(z) 1 -1+Z k 1 - Z k \r(z) \in \scrR k,k
is real-valued for z \in \BbbR with R( - z) = 1/R(z), and of modulus 1 on the imaginary axis. Finally, as \r(z) takes values in the interval

\biggl[ - 1 - 2 \surd Z k 1 + Z k , - 1 + 2 \surd Z k 1 + Z k \biggr] = \biggl[ - (1 + \surd Z k ) 2 1 + Z k , - (1 - \surd Z k ) 2 1 + Z k \biggr] for z \in [ - b, - a], we have for such z that 1 + Z k 1 -Z k \r(z) \in \biggl[ - 1 + \surd Z k 1 - \surd Z k , - 1 - \surd Z k 1 + \surd Z k \biggr] , implying that - \surd Z k \leq R(z) \leq \surd Z k for z \in [ - b, - a]. Hence, using R( - z) = 1/R(z) we have sup z\in [ - b, - a] | R(z)| inf z\in [a,b] | R(z)| \leq Z k = inf r\in \scrR k,k sup z\in [ - b, - a] | r(z)| inf z\in [a,b] | r(z)| , showing that R is extremal for Z k ([ - b, - a], [a, b]
), as required. Therefore, by solving the quadratic and noting that \alpha > 1 we find that

Zolotarev Numbers for General Real Intervals. Consider the Zolotarev number

Z k ([a, b], [c, d]), where either b < c or d < a so that [a, b] \cap [c, d] = \emptyse . Since Z k (E, F ) = Z k (T (E), T (F )) for any M\" obius transformation T (z) = (a 1 z + a 2 )/(a 3 z + a 4 ), we can find bounds on Z k ([a, b], [c, d]) by transplanting [a, b] \cup [c, d] onto sym- metric real intervals [ - \alpha , - 1] \cup [1, \alpha ] for some \alpha > 1. If b < c, then the M\" obius transformation satisfies T (a) = - \alpha , T (b) = - 1, T (c) = 1, T (d) = \alpha . Since T is a M\" obius
(3.7) \alpha = - 1 + 2\gamma + 2 \sqrt{} \gamma 2 -\gamma , \gamma = | c -a| | d -b| | c -b| | d -a| .
We conclude from Corollary 3.2 that

(3.8) Z k ([a, b], [c, d]) \leq 4 \biggl[ exp \biggl( \pi 2 2\mu (1/\alpha ) \biggr) \biggr] - 2k \leq 4 \biggl[ exp \biggl( \pi 2 2 log(16\gamma ) \biggr) \biggr] - 2k
.

Here, the last inequality comes from Gauss's transformation in (3.4) as we have \mu (1/\alpha ) = 2\mu (1/ \surd \gamma ) \leq 2 log(4 \surd \gamma ) = log(16\gamma ).

Zolotarev Numbers for Disks.

For two disjoint closed disks E, F \in \BbbC , it is known from a so-called near-circularity characterization of the extremal rational function that [53, p. 123]

Z k (E, F ) = exp \biggl( - k cap(E, F ) \biggr) = Z 1 (E, F ) k ,
where an explicit but technical expression for cap(E, F ) is given in Example VIII.4.2 of [START_REF] Saff | Logarithmic Potentials with External Fields[END_REF]. By invariance under M\" obius transformations, we see that the same formula holds if one of the sets E or F is either a half plane or the exterior of a disk of the form \{ z \in \BbbC : | z -c| \geq r\} . We give two examples where we can be a bit more explicit. Provided that c \in \BbbC and 0 < r 1 < r 2 , we have

Z 1 (\{ | z -c| \leq r 1 \} , \{ | z -c| \geq r 2 \} ) = r 1 r 2 ,
which easily follows by applying [53, p. 123] to the (extremal) rational function R(z) = z. Also, provided that 0 < a < b, we find that

Z 1 ( - E, E) = \Biggl( 1

The Decay of the Singular Values of Pick, Cauchy, and L öwner Matrices.

In this section we bound the singular values of Pick (see section 4.1), Cauchy (see section 4.2), and L\" owner (see section 4.3) matrices. In view of Theorem 2.1 and Corollary 3.2, our first idea is to construct matrices A and B so that the rank of AX -XB is small with the additional hope that \sigma (A) and \sigma (B) are contained in real and disjoint intervals. For the three classes of matrices in this section, this first idea works out under mild ``separation conditions."" In section 5 the more challenging cases of Krylov, real Vandermonde, and real positive definite Hankel matrices are considered.

Pick

Matrices. An n \times n matrix P n is called a Pick matrix if there exist a vector s = (s 1 , . . . , s n ) T \in \BbbC n\times 1 and a collection of real numbers x 1 < \cdot \cdot \cdot < x n from an interval [a, b] with 0 < a < b < \infty such that (4.1)

(P n ) jk = s j + s k x j + x k , 1 \leq j, k \leq n.
All Pick matrices satisfy the following Sylvester matrix equation: There are two important consequences of Corollary 4.1: (1) Pick matrices are ill-conditioned unless b/a is large and/or n is small, and (2) all Pick matrices can be approximated, up to an accuracy of \epsilon \| P n \| 2 with 0 < \epsilon < 1, by a rank \scrO (log(b/a) log(1/\epsilon )) matrix. More precisely, for any Pick matrix in (4.1) we have

\kappa 2 (P n ) = \sigma 1 (P n ) \sigma n (P n ) \geq 1 4 \biggl[ exp \biggl( \pi 2 2 log(4b/a) \biggr) \biggr] 2\lceil n 2 - 1\rceil , (4.3)
where for an even integer n we used \sigma 1 (P n )/\sigma n (P n ) \geq \sigma 1 (P n )/\sigma n - 1 (P n ). Moreover, by setting k to be the smallest integer so that \sigma 1+2k (P n ) \leq \epsilon \sigma 1 (P n ), we find the following bound on the \epsilon -rank of P n (see (1.3)): In both (4.3) and (4.4), the bound can be slightly improved by replacing the log(4b/a) term by \mu (a/b). Previously, bounds on the minimum and maximum singular values of Pick matrices were derived under the additional assumption that P n is a positive definite matrix [START_REF] Fasino | How bad are symmetric Pick matrices?[END_REF]. Generalized Cauchy matrices satisfy the following Sylvester matrix equation: where \gamma is the absolute value of the cross-ratio of a, b, c, and d. We expect our bounds to be quite tight when the cross-ratio \gamma \gg 1. When the cross-ratio is close to 1, then the discrete nature of the spectra of D x and D y matters more and our bound may not adequately describe the decay rate of the singular values. When m \geq n and b < c or d < a, we have the following lower bound on the condition number of C m,n :

\kappa 2 (C m,n ) = \sigma 1 (C m,n ) \sigma n (C m,n ) \geq 1 4 \biggl[ exp \biggl( \pi 2 2 log(16\gamma ) \biggr) \biggr] 2(n - 1) , \gamma = | c -a| | d -b| | c -b| | d -a| .
From the bounds in subsection 3.3, explicit singular value bounds are also possible to derive when x 1 , . . . , x m and y 1 , . . . , y n lie in two disjoint disks.

Remark 4.3. Most of the existing bounds in the literature on the numerical rank of Cauchy matrices are derived from separable approximations of the Cauchy kernel (see [START_REF] Tyrtyshnikov | Mosaic-skeleton approximations[END_REF], [23,

then rank \epsilon (C m,n ) \leq k. If R \in \scrR k,k , then the proof of Theorem 2.1 shows that 1 x -y \biggl( R(x) R(y) -1 \biggr) = k \sum j=1 f j (x)g j (y),
where f j and g j are rational functions. Thus, (4.7) holds, provided that max

x\in [a,b] | R(x)| \Big/ min y\in [ - b, - a] | R(y)| \leq \epsilon .
By sampling the functions f j and g j , one can construct a low rank approximant of C m,n . Tyrtyshnikov used this observation to construct a skeleton approximation [START_REF] Oseledets | Lower bounds for separable approximations of the Hilbert kernel[END_REF] of the Cauchy matrix [START_REF] Tyrtyshnikov | Mosaic-skeleton approximations[END_REF]; see also [START_REF] Grasedyck | Existence of a low rank or \scrH matrix approximant to the solution of a Sylvester equation[END_REF] and [55, Chapter 3] for the hierarchical low rank structure of C m,n . In [23, section 2.2] the authors first apply a M\" obius transform and then use a polynomial approximation of the Cauchy kernel. Penzl in [48, Theorem 1] obtains a sharper bound in terms of \sqrt{} b/a by constructing a particular rational function R \in \scrR k,k ; however, our bound of 4\rho 2k \leq \epsilon with \rho \in (0, 1) as in Corollary 3.2 is sharper since it is based on an optimal rational function. Another approach investigated by Braess and Hackbusch [START_REF] Braess | On the efficient computation of high-dimensional integrals and the approximation by exponential sums[END_REF] (see also [START_REF] Braess | Nonlinear Approximation Theory[END_REF][START_REF] Braess | Approximation of 1/x by exponential sums in [1, \infty )[END_REF]) is to let z = x -y \in [2a, 2b] and approximate the function 1/z by an exponential sum of the form \sum k j=1 \alpha j exp( - t j z) for suitable chosen \alpha j , t j \in \BbbR . A combination of [19, Lemma 2.1 and Theorems 3.3 and 4.1] shows that (4.7) holds with c k \rho - 2k \leq \epsilon with the same \rho as before, and a nonexplicit constant c depending on a/b but not on k. The connection to exponential sum bounds is extensively discussed in [57, section 4.3]. Corollary 4.2 also includes the important Hilbert matrix, i.e., (H n ) jk = 1/(j +k -1) for 1 \leq j, k \leq n. By setting x j = j -1/2, y j = - k + 1/2, and s = r = (1, . . . , 1) T , the matrix in (4.5) is the Hilbert matrix. In particular, Corollary 4.

2 with [a, b] = [ - n + 1/2, - 1/2] and [c, d] = [1/2, n -1/2] shows that (4.8) \sigma k+1 (H n ) \leq 4 \biggl[ exp \biggl( \pi 2 2 log(8n -4) \biggr) \biggr] - 2k \sigma 1 (H n ), 1 \leq k \leq n -1.
Therefore, the Hilbert matrix can be well approximated by a low rank matrix and has exponentially decaying singular values. 6 In particular, it has an \epsilon -rank of at most \lceil log(8n -4) log(4/\epsilon )/\pi 2 \rceil . Recall that our bounds are most useful for \sigma k (H n ), where k is relatively small with respect to n. Therefore, (4.8) with k = n -1 does not give an asymptotically sharp bound on the condition number of H n [65, eqn. (3.35)]. The Hilbert matrix is an example of a real positive definite Hankel matrix, and in section 5 we show that bounds similar to (4.8) hold for the singular values of all such matrices. Figure 4.1 (right) demonstrates the bound in Corollary 4.2 on three n \times n Cauchy matrices, where n = 100. In practice, the derived bound is relatively tight for singular values \sigma j (C m,n ) when j is small with respect to n.

L öwner Matrices.

An n \times n matrix L n is called a L\" owner matrix if there exist vectors r, s \in \BbbC n\times 1 , points x 1 < \cdot \cdot \cdot < x n in [a, b] with - \infty < a < b < \infty , and points y 1 < \cdot \cdot \cdot < y n (all different from x 1 , . . . , x n ) in [c, d] with - \infty < c < d < \infty such that (4.9)

(L n ) jk = r j -s k x j -y k , 1 \leq j, k \leq N.
In the special case when y j = - x j and s j = - r j , a L\" owner matrix is a Pick matrix (see section 4.1). L\" owner matrices satisfy the Sylvester matrix equation given by Proof. The proof follows the same argument as in the proof of Corollary 4.2, but with \nu = 2. Corollary 4.4 shows that many L\" owner matrices can be well approximated by low rank matrices with rank \epsilon (L n ) = \scrO (log \gamma log(1/\epsilon )) and are exponentially ill-conditioned.

D x L n -L n D y =

5.

The Singular Values of Krylov, Vandermonde, and Hankel Matrices. The three types of matrices considered in section 4 allowed for direct applications of Theorem 2.1 and Corollary 3.2. In this section, we consider the more challenging tasks of bounding the singular values of Krylov matrices with Hermitian arguments, real Vandermonde matrices, and real positive definite Hankel matrices.

Krylov and Real Vandermonde

Matrices. An m \times n matrix K m,n with m \geq n is said to be a Krylov matrix if there exist a matrix A \in \BbbC m\times m and a vector w \in \BbbC m\times 1 such that Krylov matrices satisfy the following Sylvester matrix equation:

(5.2) AK m,n -K m,n Q = s e T n , Q = \left[ 0 - 1 1 . . . 1 0 \right]
,

where s \in \BbbC m\times 1 and e n = (0, . . . , 0, 1)

T . Here, we will only consider K m,n where the matrix A in (5.2) is normal. When A = D x and w = (1, . . . , 1) T the Krylov matrix in (5.1) is the Vandermonde matrix (V m,n ) jk = x k - 1 j for 1 \leq j \leq m and 1 \leq k \leq n. This makes the bounds in this section also applicable to Vandermonde matrices. The vector of w in (5.1) allows for additional row scaling of V m,n . We refer the reader to [START_REF] Moitra | Super-resolution, extremal functions and the condition number of Vandermonde matrices[END_REF] for a state-of-the-art conditioning analysis of Vandermonde matrices.

We start by considering an example for which A is a unitary matrix and Theorem 2.1 is trivial.

Example 5.1. Let m = n and A = \widetil Q be the n \times n circshift matrix obtained from Q in (5.2) by replacing the - 1 entry by 1. Then, for any vector s in (5.2), the solution K n,n to the Sylvester matrix equation is a circulant matrix. Moreover, all circulant matrices satisfy (5.2) with A = \widetil Q. If s is the first or second canonical vector, then K n,n is the identity or circshift matrix, respectively. In both cases, K n,n is an orthogonal matrix and \sigma j (K n,n ) = 1 for 1 \leq j \leq n. Through the link with companion matrices, the eigenvalues of \widetil Q are the nth roots of unity, i.e., the even powers of exp( 2\pi i 2n ). These eigenvalues perfectly interlace the eigenvalues of Q, which are the odd powers of exp( 2\pi i 2n ). An application of Theorem 2.1 reveals that

1 = \sigma k+1 (I n ) \sigma 1 (I n ) \leq Z k (\sigma ( \widetil Q), \sigma (Q)) \leq 1,
where I n is the identity matrix and \sigma ( \widetil Q) and \sigma (Q) denote the spectrum of \widetil Q and Q, respectively. Hence, we find that Z k (\sigma ( \widetil Q), \sigma (Q)) = 1 for 1 \leq k \leq n -1. As a consequence, for any circulant matrix K n,n our Theorem 2.1 gives the trivial bound that \sigma k+1 (K n,n ) \leq \sigma 1 (K n,n ) for 1 \leq k \leq n -1. On the other hand, using the discrete Fourier transform one can construct a circulant matrix with any sequence of singular values s 1 \geq s 2 \geq \cdot \cdot \cdot \geq s n \geq 0. We conclude that for circulant matrices as well as the larger class of Toeplitz matrices, Theorem 2.1 is not useful.

Similarly, from the Moitra upper bound [START_REF] Moitra | Super-resolution, extremal functions and the condition number of Vandermonde matrices[END_REF] on the condition number of a rectangular Vandermonde matrix V m,n , m \leq n, with arbitrary nodes x 1 , . . . , x m on the unit circle, we get lower bounds for the Zolotarev number Z m - 1 (\sigma (D x ), \sigma (Q)), provided that the nodes x j are distributed like n roots of unity.

We now study another class of Krylov matrices where A is Hermitian, and we attempt to use Theorem 2.1 to bound the singular values of K m,n . When A is Hermitian, Theorem 2.1 provides a nontrivial bound on the singulars of K m,n .

For the analysis that follows, we require that n be an even integer. This is not a loss of generality because of the interlacing theorem for singular values [START_REF] Thompson | Principal submatrices IX: Interlacing inequalities for singular values of submatrices[END_REF]. To see this, let K m,n - 1 be the m \times (n -1) Krylov matrix obtained from K m,n by removing its last column. If n is odd, then 7

(5.3) \sigma j+k (K m,n ) \sigma j (K m,n ) \leq \sigma j+k - 1 (K m,n - 1 ) \sigma j (K m,n - 1 ) , 2 \leq j + k \leq n,
and one can bound \sigma j+k - 1 (K m,n - 1 )/\sigma j (K m,n - 1 ) instead. From now on in this section we will assume that n is an even integer.

The Sylvester matrix equation in (5.2) contains matrices A and Q, which are both normal matrices. The eigenvalues of A are contained in \BbbR and the eigenvalues of Q are the n (shifted) roots of unity, i.e.,

\sigma (Q) = \Bigl\{ z \in \BbbC : z = e 2\pi i(j+1/2) n , 0 \leq j \leq n -1 \Bigr\} .
Since n is even, the spectrum of Q and the real line are disjoint. Using Theorem 2.1 we find that for j \geq 1 and 1 \leq j

+ k \leq n \sigma j+k (K m,n ) \leq Z k (E, F )\sigma j (K m,n ), E \subsete \BbbR , F = F + \cup F -,
where F + and F -are complex sets defined by (5.4) 5.1 shows the two sets E and F in the complex plane. As n \rightar \infty the sets F + and F -approach the real line, suggesting that our bound on the singular values must depend on n somehow. Our task is to bound the quantity Z k (E, F + \cup F -)---a Zolotarev number that is not immediately related to one of the form

F + = \{ e it : t \in [ \pi n , \pi -\pi n ]\} , F -= \{ e it : t \in [ - \pi + \pi n , -\pi n ]\} . Figure
Z k ([ - b, - a], [a, b]).
The following lemma relates the quantity Z 2k (E,

F + \cup F -) to the Zolotarev number Z k ([ - 1/\ell , - \ell ], [\ell , 1/\ell ]) with \ell = tan(\pi /(2n)). Lemma 5.2. Let k \geq 1 be an integer and E \subsete \BbbR . Then Z 2k+1 (E, F + \cup F -) \leq Z 2k (E, F + \cup F -) and Z 2k (E, F + \cup F -) \leq 2 \surd Z k 1 + Z k , Z k := Z k ([ - 1/\ell , - \ell ], [\ell , 1/\ell ]), 7
Observe that the singular values of a matrix decrease when removing a column and thus \sigma j (K m,n - 1 ) \leq \sigma j (Km,n). Let Y be a best rank j + k -2 approximation to K m,n - 1 so that \sigma j+k - 1 (K m,n - 1 ) = \| K m,n - 1 -Y \| 2 and consider X obtained from Y by concatenating (on the right) the last column of Km,n. Then the rank of X is at most j + k -1, and hence where \ell = tan(\pi /(2n)), the complex sets F + and F -are as defined in (5.4), and n is an even integer. .

\sigma j+k (Km,n) \leq \| Km,n -X\| 2 = \| K m,n - 1 -Y \| 2 = \sigma j+k - 1 (K m,n - 1 ). \sigma (A) \subset E \subsete \BbbR F + F - \sigma (Q) \subset F = F + \cup F - 0 Im Re -\rightar -\rightar
2R(z) 1 + R(z) 2 \bigm| \bigm| \bigm| \bigm| \leq 2 \surd Z k 1 + Z k . Therefore, Z 2k (E, F + \cup F -) \leq Z 2k (\BbbR , F + \cup F -) \leq 2 \surd Z k /(1 + Z k ) as required. The bound Z 2k+1 (E, F + \cup F -) \leq Z 2k (E, F + \cup F -)
If n is an even integer, then we can immediately conclude a bound on the singular values from Theorem 2.1. If n is an odd integer, then one must employ (5.3) first.

Corollary 5.3. The singular values of K m,n can be bounded as follows:

\sigma j+2k (K m,n ) \leq 4 \biggl[ exp \biggl( \pi 2 2\mu (tan(\pi /(4\lfloor n/2\rfloor )) 2 ) \biggr) \biggr] - k+[n]2 \sigma j (K m,n ), 1 \leq j + 2k \leq n, (5.5)
where \mu (\cdot ) is the Gr\" otzsch function and [n] 2 = 1 if n is odd and is 0 if n is even.

The bound above remains valid, but is slightly weakened, if 2\mu (tan(\pi /(4\lfloor n/2\rfloor )) 2 ) is replaced by 4 log(8\lfloor n/2\rfloor /\pi ).

Figure 5.2 demonstrates the bound on the singular values in (5.5) on n \times n Krylov matrices, where n = 10, 100, 1000. The step behavior of the bound is due to the fact that (5.5) only bounds \sigma 1+2k (K m,n ) when n is even, and we use the trivial inequality \sigma 2k+2 (K m,n ) \leq \sigma 2k+1 (K m,n ) otherwise. One also observes that the singular values of Krylov matrices with Hermitian arguments can decay at a supergeometric rate; however, the analysis in this paper only realizes a geometric decay. Therefore, (5.5) is only a reasonable bound on \sigma j (K m,n ) when j is a small integer with respect to n. If j/n \rightar c and c \in (0, 1), then improved bounds on \sigma j (K m,n ) may be possible by bounding discrete Zolotarev numbers [START_REF] Beckermann | Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method[END_REF]. The bound in (5.5) which allows for either an odd or an even integer n.

As mentioned before, Vandermonde matrices of size m \times n with real abscissas x \in \BbbR m\times 1 , i.e., (V m,n ) jk = x k - 1 j , are also Krylov matrices with A = D x and w = (1, . . . , 1) T . Therefore, the bounds in this section also apply to (possibly row-scaled) Vandermonde matrices with real abscissas and show that they have rapidly decaying singular values and are exponentially ill-conditioned, an observation that has been extensively investigated in the literature [START_REF] Beckermann | The condition number of real Vandermonde, Krylov and positive definite Hankel matrices[END_REF][START_REF] Gautschi | Lower bounds for the condition number of Vandermonde matrices[END_REF][START_REF] Pan | How bad are Vandermonde matrices?[END_REF].

Real Positive Definite Hankel

Matrices. An n \times n matrix H n is a Hankel matrix if the matrix is constant along each antidiagonal, i.e., (H n ) jk = h j+k for 1 \leq j, k \leq n. Clearly, not all Hankel matrices have decaying singular values. For example, the exchange matrix has repeated singular values of 1. This means that any displacement structure that is satisfied by all Hankel matrices, for example, rank \bigl( QX -XQ T \bigr) \leq 2, where Q is given in (5.2), does not result in a Zolotarev number that decays. Motivated by the Hilbert matrix in section 4.2, we show that every real and positive definite Hankel matrix has rapidly decaying singular values. Previous work has led to bounds that can be calculated by using a pivoted Cholesky algorithm [START_REF] Antoulas | On the decay rate of Hankel singular values and related issues[END_REF], bounds for very special cases [START_REF] Townsend | Fast polynomial transforms based on Toeplitz and Hankel matrices[END_REF], and incomplete attempts [START_REF] Tyrtyshnikov | More on Hankel Matrices[END_REF][START_REF] Tyrtyshnikov | How bad are Hankel matrices?[END_REF].

In order to exploit the positive definite structure we recall that the Hamburger moment problem states that a real Hankel matrix is positive semidefinite if and only if it is associated to a nonnegative Borel measure supported on the real line. x j+k - 2 d\mu H (x), 1 \leq j, k \leq n.

Proof. For a proof, see [START_REF] Peller | Hankel Operators and Their Applications[END_REF]Theorem 7.1].

Let H n be a real positive definite Hankel matrix associated to the nonnegative weight \mu H in (5.6) supported on \BbbR . Let x 1 , . . . , x n and w 2 1 , . . . , w 2 n be the Gauss quadrature nodes and weights associated to \mu H . Then, since a Gauss quadrature is exact for polynomials of degree 2n -1 or less, we have

(H n ) jk = \int \infty - \infty x j+k - 2 d\mu H (x) = n \sum s=1 w 2 s x j+k - 2 s = n \sum s=1 \bigl( w s x j - 1 s \bigr) \bigl( w s x k - 1 s \bigr) .
Therefore, every real positive definite Hankel matrix has a so-called Fiedler factorization [START_REF] Fiedler | Special Matrices and Their Applications in Numerical Mathematics[END_REF], i.e., where K n,n is a Krylov matrix with Hermitian argument and K \ast n,n is the conjugate transpose of K n,n . This means that \sigma j (H n ) = \sigma j (K n,n ) 2 for 1 \leq j \leq n. That is, a bound on the singular values of H n and the \epsilon -rank of H n directly follows from (5.5). where both bounds allow for n to be an even or odd integer.

H n = K \ast n,n K n,n , K n,n =
We conclude that all real positive definite Hankel matrices have an \epsilon -rank of at most \scrO (log n log(1/\epsilon )), explaining why low rank techniques are usually advantageous in computational mathematics on such matrices.

Since a real positive semidefinite Hankel matrix can be arbitrarily approximated by a real positive definite Hankel matrix, the results from this section immediately extend to such Hankel matrices. 8 This fact was exploited, but not proved in general, in [START_REF] Townsend | Fast polynomial transforms based on Toeplitz and Hankel matrices[END_REF] to derive quasi-optimal complexity fast transforms between orthogonal polynomial bases.

Conclusions.

Many special matrices such as Pick, Vandermonde, and Hankel matrices have a displacement structure and satisfy a Sylvester matrix equation. Zolotarev numbers can be used to derive explicit bounds on the singular values of such matrices (see Table 1.1) that help explain the abundance of low rank structures in computational mathematics.

Zolotarev numbers have received renewed attention in the field of numerical linear algebra for computing matrix functions [29, for communication-avoiding eigensolvers [START_REF] Nakatsukasa | Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev's functions[END_REF], for fast Poisson solvers [START_REF] Fortunato | Fast Poisson Solvers for Spectral Methods[END_REF][START_REF] Wilber | Computing with functions in spherical and polar geometries II. The disk[END_REF], for solving Sylvester equations [START_REF] Penzl | Eigenvalue decay bounds for solutions of Lyapunov equations: The symmetric case[END_REF][START_REF] Sabino | Solution of Large-Scale Lyapunov Equations via the Block Modified Smith Method[END_REF], for solving Riccati equations [START_REF] Kressner | Low-Rank Updates and a Divide-and-Conquer Method for Linear Matrix Equations[END_REF], for bounding exponential sums [START_REF] Braess | Approximation of 1/x by exponential sums in [1, \infty )[END_REF][START_REF] Braess | On the efficient computation of high-dimensional integrals and the approximation by exponential sums[END_REF], and for tensor compression [START_REF] Shi | On the Numerical Ranks of Tensors[END_REF]. We look forward to the future advances that this renewed interest in Zolotarev numbers will bring.

Appendix A. Infinite Product Formulas for Quantities Related to the Zolotarev Number. Here, we rederive infinite product formulas related to a formula given by Lebedev [38, (1.11)], which unfortunately contained a typo. The typo has been copied several times in the literature.

Lebedev [START_REF] Lebedev | On a Zolotarev problem in the method of alternating directions[END_REF] and his successors [START_REF] Medovikov | Variable time steps optimization of L\omega -stable Crank--Nicolson method[END_REF][START_REF] Oseledets | Lower bounds for separable approximations of the Hilbert kernel[END_REF] were not concerned with the Zolotarev problem in (1.4) but instead with the equivalent problem of minimal Blaschke products in the half plane, i.e., In [38, (1.11)], Lebedev presented an infinite product formula for E k that unfortunately contained typos and resulted in an erroneous lower bound for E k in [38, (1.12)]. More recently, other erroneous lower bounds have been claimed in [34, (4.1)] for a related problem based on [40, (3.17 Here, in the last inequality we have applied property (a). We conclude that E k ([ - b, - a]) = \surd Z k . Therefore, an infinite product formula for E k ([\eta , 1]) that corrects [38, (1.11)] is obtained by taking square roots (and setting a/b = \eta ) in Theorem 3.1. That is, for 0 < \eta < 1 we have9 (1 + \rho - 8\tau k ) 2 (1 + \rho 4k \rho - 8\tau k ) 2 , \rho = exp \biggl( \pi 2 2\mu (\eta )

\biggr)

,

where \mu (\cdot ) is the Gr\" otzsch ring function. From (A.2), one obtains upper and lower bounds for E k ([\eta , 1]) that correct [38, (1.12)], [40, (3.17)], and [45, (15)], namely, (A.3) 2\rho - k (1 + \rho - 4k ) 2 \leq E k ([\eta , 1]) \leq 2\rho - k 1 + \rho - 4k \leq 2\rho - k , \rho = exp \biggl( \pi 2 2\mu (\eta )

\biggr)

.

More refined estimates than (A.3) can be obtained by taking more terms from the infinite product in (A.2). More recently, the best rational approximation of the sign function on [ - b, - a] \cup [a, b] has become important in numerical linear algebra because of a recursive construction of spectral projectors of matrices [START_REF] G\" Uttel | Zolotarev quadrature rules and load balancing for the FEAST eigensolver[END_REF][START_REF] Nakatsukasa | Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev's functions[END_REF] Unfortunately, lower and upper bounds for E 2k,2k = E 2k - 1,2k are claimed in [34, (4.1)] based on the erroneous infinite product formula in [40, (3.17)] and for E 2k+1,2k+1 = E 2k+1,2k in [43, (3.8)] by incorrectly citing the fundamental work of Gon\v car [31, (32)].

We believe it is therefore useful to state infinite product formulas for E k,k and the resulting estimates. We recall from the proofs of Theorems 3.1 and 3.3 that we have

E k,k = E 2\lfloor (k - 1)/2\rfloor +1,2\lfloor k/2\rfloor = 2 \surd Z k 1 + Z k , \mu \biggl( 2 \surd Z k 1 + Z k \biggr) = \mu (Z k ) 2 .
Thus, in the proof of Theorem 3.1 we select q = exp( - 2\mu (E k,k )) = \rho - 2k and obtain .

Similarly, more refined estimates than (A.6) can be obtained by taking more terms from the infinite product in (A.5). In Zolotarev's original work [START_REF] Zolotarev | Application of elliptic functions to questions of functions deviating least and most from zero[END_REF], he demonstrated an equivalence between (A. It is worth noting that these are relative errors as opposed to absolute errors.

3. 1 .

 1 Zolotarev Numbers for Real Symmetric Intervals. Let 0 < a < b < \infty and consider the Zolotarev number Z k := Z k ([ - b, - a], [a, b]). The sharpest bounds that we are aware of in the literature take the form (3.1) \rho - 2k \leq Z k \leq 16 \rho - 2k ; see (1.5) or [31, Theorem 1] for the lower bound and [18, eqn. (2.

Fig. 3 . 1

 31 Fig. 3.1 Zolotarev's rational approximations. Left: The error between the sign function on [ - 10, - 1] \cup [1, 10] and its best rational \scrR 8,8 approximation on the domain [ - 10, 10]. The error equioscillates 9 times in the interval [ - 10, - 1] and [1, 10] (see red dots), verifying its optimality [1, p. 149]. Right: The upper bound (black line) on Z k ([ - b, - a], [a, b]) (colored dots) in Corollary 3.2 for 0 \leq k \leq 20, with b/a = 1.1 (blue), 10 (red), 100 (yellow).

  Functions for \bfitZ \bfitk ([ - \bfitb , - \bfita ], [\bfita , \bfitb ]). Later, in section 5 we will need to use properties of an extremal rational function for Z k = Z k ([ - b, - a], [a, b]), and we prove them now. Zolotarev [66] studied the value Z k and gave an explicit expression for the extremal function for Z k (see (1.4)) by showing an equivalence to the problem of best rational approximation of the sign function on [ - b, - a] \cup [a, b]. We now repeat this to derive the desired properties of the extremal rational function. Theorem 3.3. Let k \geq 1 be an integer and 0 < a < b < \infty . There exists an extremal function R \in \scrR k,k for Z k = Z k ([ - b, - a], [a, b]) such that (a) for z \in [ - b, - a], we have -\surd Z k \leq R(z) \leq \surd Z k , (b) for z \in \BbbC , we have R( - z) = 1/R(z), and (c) for z \in \BbbR , we have | R(iz)| = 1. Proof. We give an explicit expression for an extremal function for Z k by deriving it from the best rational approximation of the sign function on [ - b, - a]\cup [a, b]. According to [1, sections 50 and 51, p. 144, line 6] we have inf r\in \scrR k,k sup z\in [ - b, - a]\cup [a,b]

Figure 3 . 1 (

 31 Figure 3.1 (right) demonstrates the upper bound in Corollary 3.2 when b/a = 1.1, 10, 100. In section 4 we combine our upper bound on the singular values in Theorem 2.1 with our upper bound on Zolotarev numbers to derive explicit bounds on the singular values of certain Pick, Cauchy, and L\" owner matrices.

  transformation the cross-ratio of the four collinear points a, b, c, and d equals the cross-ratio of T (a), T (b), T (c), and T (d). Hence, if b < c or d < a, then we know that \alpha must satisfy | c -a| | d -b| | c -b| | d -a| = (\alpha + 1) 2 4\alpha .

  R = (z + \surd ab)/(z -\surd ab). Interesting enough, the same function allows one to show that Z 1 ([ - b, - a], [a, b]) = Z 1 ( - E, E), even though E is quite a bit larger than [a, b]. We also see that the upper bound of Z k ([ - b, - a], [a, b]) \leq Z 1 ([ - b, - a], [a, b]) k does not have an asymptotically sharp decay rate since the righthand side is Z k ( - E, E).

(4. 2 )Corollary 4 . 1 .

 241 D x P n -P n ( - D x ) = s e T + e s T , D x = diag (x 1 , . . . , x n ) , where e = (1, . . . , 1) T . Since diagonal matrices are normal matrices and in this case the spectrum of D x is contained in [a, b], we have the following bounds on the singular values of P n . Let P n be the n \times n Pick matrix in (4.1). Then, for j \geq 1, we have\sigma j+2k (P n ) \leq 4 \biggl[ exp \biggl( \pi 2 2\mu (a/b) \biggr) \biggr] - 2k \sigma j (P n ), 1 \leq j + 2k \leq n,where \mu (\lambda ) is the Gr\" otzsch ring function (see section 3). The bound remains valid, but is slightly weakened, if \mu (a/b) is replaced by log(4b/a).Proof. From (4.2), we know thatA = D x , B = - A, \nu = 2, E = [a, b], and F = [ - b, - a] in Theorem 2.1. Therefore, for j \geq 1 we have \sigma j+2k (P n ) \leq Z k (E, F )\sigma j (P n ), 1 \leq j + 2k \leq n. The result follows from the upper bound in Corollary 3.2.

(4. 4 )

 4 rank \epsilon (P n ) \leq 2 \biggl\l log(4b/a) log(4/\epsilon ) \pi 2 \biggr\r .

Figure 4 . 1 (

 41 left) demonstrates the bound in Corollary 4.1 on three 100 \times 100 Pick matrices. The black line bounding the singular values has a stepping behavior because of the inequality in Corollary 4.1, which for j = 1 only bounds the odd indexed singular values of P n . To bound \sigma 2k (P n ) we use the trivial inequality \sigma 2k (P n ) \leq \sigma 2k - 1 (P n ). At this time we can offer little insight into why the singular values of the tested Pick matrices also have a similar stepping behavior.

4. 2 .

 2 Cauchy Matrices. An m \times n matrix C m,n with m \geq n is called a (generalized) Cauchy matrix if there exist vectors s \in \BbbC m\times 1 and t \in \BbbC n\times 1 , points x 1 < \cdot \cdot \cdot < x m on an interval [a, b] with - \infty < a < b < \infty , and points y 1 < \cdot \cdot \cdot < y n (all distinct from x 1 , . . . , x m ) in an interval [c, d] with - \infty < c < d < \infty such that (4.5) (C m,n ) jk = s j t k x j -y k , 1 \leq j \leq m, 1 \leq k \leq n.

\gamma \approx 2 5 1 . 4 6 Fig. 4 . 1

 641 Fig. 4.1 Left: The scaled singular values of 100 \times 100 Pick matrices (colored dots) and the bound in Corollary 4.1 (black lines) for b/a = 1.1 (blue dots), 10 (red dots), 100 (yellow dots). In (4.1), x is a vector of equally spaced points in [a, b] and s is a random vector with independent standard Gaussian entries. Right: The scaled singular values of 100 \times 100 Cauchy matrices (colored dots) and the bound in Corollary 4.2 (black lines) for \gamma = 1.1, 10, 100. In (4.5), x is a vector of Chebyshev nodes from [ - 8.5, - 2] (blue dots), [ - 100, - 3] (red dots), and [ - 101, 2.8] (yellow dots), respectively, y is a vector of Chebyshev nodes from [3, 10] (blue dots), [3, 100] (red dots), and [3, 100] (yellow dots), respectively, and s and t are random vectors with independent standard Gaussian entries. The decay rate depends on the cross-ratio of the endpoints of the intervals.

(4. 6 )

 6 D x C m,n -C m,n D y = s t T ,where D x = diag (x 1 , . . . , x m ) and D y = diag (y 1 , . . . , y n ).If we make the further assumption that either b < c or d < a so that the intervals [a, b] and [c, d] are disjoint, then we can bound the singular values of C m,n . This `separation condition"" is an extra assumption on Cauchy matrices that simplifies the analysis. If the intervals [a, b] and [c, d] overlapped, then one would have to consider discrete Zolotarev numbers to estimate the singular values, and we want to avoid this in this paper. For implicit bounds, i.e., bounds that require computation, on the singular values of Cauchy matrices that continue to hold when the separation condition is violated, see[START_REF] Truhar | Analysis of the solution of the Sylvester equation using low-rank ADI with exact shifts[END_REF] Theorem 3] and[59, (2.34)]. Corollary 4.2. Let C m,n be an m \times n Cauchy matrix in (4.5) with m \geq n and either b < c or d < a. Then \sigma j+k (C m,n ) \leq 4 ] - 2k \sigma j (C m,n ), 1 \leq j + k \leq n, where \gamma = | (c -a)(d -b)/((c -b)(d -a))| is the absolute value of the cross-ratio of a, b, c, and d. If c = - b and d = - a, then 2\mu (1/ \surd \gamma ) = \mu (a/b). The bound remains valid, but is slightly weakened, if 4\mu (1/ \surd \gamma ) is replaced by 2 log(16\gamma ). Proof. From (4.6), we know that A = D x , B = D y , \nu = 1, E = [a, b], and F = [c, d] in Theorem 2.1. Therefore, we have \sigma j+k(C m,n ) \leq Z k (E, F )\sigma j (C m,n ) for 1 \leq j + k \leq n. From (3.8), we conclude that \sigma j+k (C m,n ) \leq 4 \biggl[ exp \biggl( \pi 2 2\mu (1/\alpha ) \biggr) \biggr] - 2k \sigma j (C m,n ), 1 \leq j + k \leq n.It is interesting to observe that our bound on the singular values of Cauchy matrices depends on the absolute value of the cross-ratio of a, b, c, and d. Hence, the `separation"" of two real intervals [a, b] and [c, d] for the purposes of our singular value estimates is measured in terms of the cross-ratio of a, b, c, and d---not the separation distance max(c -b, a -d). Corollary 4.2 shows that the Cauchy matrix in (4.5) (when b < c or d < a) has an \epsilon -rank of at most rank \epsilon (C m,n ) \leq \biggl\l 2\mu (1/ \surd \gamma ) log(4/\epsilon )

  section 2.2], and[START_REF] Penzl | Eigenvalue decay bounds for solutions of Lyapunov equations: The symmetric case[END_REF] Theorem 1]). For simplicity we only report about the case where [c, d] = [ - b, - a] with 0 < a < b. If there exist 2k functions f j and g j such that for some 0 < \epsilon < 1 y) \in [a, b] \times [ - b, - a],

Corollary 4 . 4 .

 44 r e T -e s T , where e = (1, . . . , 1) T . From Theorem 2.1 we can bound the singular values of L n , provided that [a, b] and [c, d] are disjoint, i.e., either b < c or d < a. We emphasize that the separation condition of the intervals [a, b]and [c, d] is an extra assumption on a L\" owner matrix that allows us to proceed with the methodology we have developed. Let L n be an n \times n L\" owner matrix in (4.9) with b < c or d < a. Then, for j \geq 1, we have\sigma j+2k (L n ) \leq 4 ] - 2k \sigma j (L n ), 1 \leq j + 2k \leq n,where \gamma is the absolute value of the cross-ratio of a, b, c, and d (see (3.7)). If c = - b and d = - a, then 2\mu (1/ \surd \gamma ) = \mu (a/b). The bound remains valid, but is slightly weakened, if 4\mu (1/ \surd \gamma ) is replaced by 2 log(16\gamma ).

Fig. 5 . 1

 51 Fig.5.[START_REF] Akhieser | Elements of the Theory of Elliptic Functions[END_REF] The sets E and F in the complex plane for the Zolotarev problem (1.4) used to bound the singular values of a 20 \times 20 Krylov matrix with a Hermitian argument. The sets F + and F -are a distance of only \scrO (1/n) from the real axis, where n is the size of the Krylov matrix, and this causes the log n dependence in the weaker version of (5.5). The solid black dots denote the spectrum of Q, which is contained in F + \cup F -.

Proof. 1 mapsF

 1 Let R(z) \in \scrR k,k be the extremal function for Z k := Z k ([ - 1/\ell , - \ell ], [\ell , 1/\ell ]) characterized in Theorem 3.3, where \ell = tan(\pi /(2n)). Since the M\" obius transform given by + to [\ell , 1/\ell ], F -to [ - 1/\ell , - \ell ], and \BbbR to i\BbbR , we haveZ 2k (\BbbR , F + \cup F -) = Z 2k (i\BbbR , [ - 1/\ell , - \ell ] \cup [\ell , 1/\ell ]) = inf r\in \scrR 2k,2k sup z\in \BbbR | r(iz)| inf z\in [ - 1/\ell , - \ell ]\cup [\ell ,1/\ell ] | r(z)| .Now, consider the rational functionS(z) = R(z) + 1/R(z) 2 = R(z) + R( - z) 2 \in \scrR 2k,2k ,where we used the fact that 1/R(z) = R( - z) (see Theorem 3.3(b)). Since | R(iz)| = 1 for z \in \BbbR (see Theorem 3.3(c)), we have sup - 1 \leq -\surd Z k \leq R(z) \leq \surd Z k \leq 1 for z \in [ - 1/\ell , - \ell ] (see Theorem 3.3(a)) and x \mapsto \rightar 2x/(1 + x 2 ) is a nondecreasing function on [ - 1, 1] and S( - z) = S(z), we have sup z\in [ - 1/\ell , - \ell ]\cup [\ell ,1/\ell ]

Fig. 5 . 2

 52 Fig. 5.2 Left: The singular values of the n \times n Krylov matrix (colored dots) compared to the bound in (5.5) for n = 10 (blue dots), 100 (red dots), 1000 (yellow dots). In (5.1) the matrix A is a diagonal matrix with entries taken to be equally spaced points in [ - 1, 1] and w is a random vector with independent Gaussian entries. Right: The singular values of the n \times n real positive definite Hankel matrices (colored dots) associated to the measure \mu H (x) = \bfone | - 1\leq x\leq 1 compared to the bound in (5.7) for n = 10 (blue dots), 100 (red dots), 1000 (yellow dots).

Lemma 5 . 4 .

 54 A real n \times n Hankel matrix, H n , is positive semidefinite if and only if there exists a nonnegative Borel measure \mu H supported on the real line such that (5.6) (H n ) jk = \int \infty - \infty

(A. 1 )

 1 E k ([a, b]) = min z1,...,z k \in \BbbC max z\in [a,b]

  )].To correct the situation we first show that withZ k := Z k ([ - b, - a], [a, b]) we have \sqrt{} Z k = E k ([ - b, - a]) = E k ([a, b]) = E k ([a/b, 1]),where the last two equalities are immediate from symmetry considerations and scaling. Since any z 1 , . . . , z k \in \BbbC describes a rational function for E k ([ - b, - a]) in (A.1), the solution to (A.1) describes a rational function r(z) that is a candidate for the Zolotarev problem in (1.4) and satisfies 1/r(z) = r( - z). By construction, we have maxz\in [ - b, - a] | r(z)| = E k ([ - b, - a]), max z\in [a,b] z\in [a,b] | r( - z)| = E k ([ - b, - a]),where we used the fact that [a, b] is a real interval. Therefore, \surd Z k \leq E k ([ - b, - a]). Conversely, taking R(z) as in Theorem 3.3 we know from property (c) that | R(iz)| =1. Therefore, R(z) satisfies R(z)R( - z) = 1 on the imaginary axis and by analytic continuation R(z)R( - z) = 1 holds for all z \in \BbbC . We conclude that if p 1 , . . . , p k \in \BbbC are the zeros of R(z), then the poles of R(z) are - p 1 , . . . , - p n . Thus, R(z) from Theorem 3.3 has the formR(z) = | \alpha | k \prod j=1 z -p j z + p j , | \alpha | = 1.This implies that E k ([ - b, - a]) \leq max z\in [ - b, - a] | R(z)| \leq \surd Z k .

(A. 2 )

 2 E k ([\eta , 1]) = 2\rho - k \infty \prod \tau =1

  . In this setting, if E m,n := E m,n ([ - b, - a], [a, b]), then (A.4) E m,n = min r\in \scrR m,n max z\in [ - b, - a]\cup [a,b] | r(z) -sgn(z)| , sgn(z) = \Biggl\{ 1, z \in [a, b], - 1, z \in [ - b, - a].

( 1 +

 1 \rho - 4\tau k ) 4 (1 + \rho 2k \rho - 4\tau k ) 4 , \rho = exp \biggl( \pi 2 2\mu (a/b) \biggr).Again, this infinite product in (A.5) results in asymptotically tight corrected lower and upper bounds on E k,k :(A.6) 4\rho - k (1 + \rho - 2k ) 4 \leq E k,k \leq 4\rho - k (1 + \rho - 2k ) 2 \leq 4\rho - k , \rho = exp \biggl( \pi 2 2\mu (a/b) \biggr)

  4) and the best rational approximation of 1/ \surd z and \surd z on the interval [a 2 , b 2 ]. Since the rational function given in (3.6) can be written as \r(z) = zS(z 2 ) with a rational function S, one can verify by letting x = z 2 and x = a 2 b 2 /y that [1, p. 147] E 2k,2k = min r\in \scrR k - 1,k max x\in [a 2 ,b 2 ]

  trivially holds from the definition of Zolotarev numbers. By Corollary 3.2 we have the slightly weaker upper bound for Z 2k (E, F + \cup F -):Z 2k (E, F + \cup F -) \leq 2 \sqrt{} Z k ([ - 1/\ell , - \ell ], [\ell , 1/\ell ]) \leq 4\rho - k ,where since tan x \geq x for 0 \leq x \leq \pi /2, we have

	\rho = exp \biggl(	\pi 2 2\mu (tan(\pi /(2n)) 2 )	\biggr)	\geq exp	\biggl(	\pi 2 2 log(4/ tan(\pi /(2n)) 2 )	\biggr)	\geq exp	\biggl(	4 log(4n/\pi ) \pi 2	\biggr)

  provides an upper bound on the \epsilon -rank of K m,n :rank \epsilon (K m,n ) \leq 2

	\biggl\l	4 log (8\lfloor n/2\rfloor /\pi ) log (4/\epsilon ) \pi 2	\biggr\r	+ 2,

  Corollary 5.5. Let H n be an n \times n real positive definite Hankel matrix. Then (5.7) \sigma j+2k (H n ) \leq 16

		\biggl[ exp	\biggl(	\pi 2 4 log(8\lfloor n/2\rfloor /\pi )	\biggr) \biggr] - 2k+2	\sigma j (H n ),	1 \leq j + 2k \leq n,
	and	rank \epsilon (H n ) \leq 2	\biggl\l	2 log (8\lfloor n/2\rfloor /\pi ) log (16/\epsilon ) \pi 2	\biggr\r	+ 2,

The n \times n exchange matrix X is obtained by reversing the order of the rows of the n \times n identity matrix, i.e., X n - j+1,j = 1 for 1 \leq j \leq n.

The statement of Theorem 2.1 was presented by the first author at the Cortona meeting on Structured Numerical Linear Algebra in 2004[START_REF] Beckermann | Singular Value Estimates for Matrices with Small Displacement Rank, Presentation at Structured Matrices[END_REF] as well as several other locations. Similar statements based on the presentation have appeared in[49, Theorem 2.1.1], [52, Theorem 4], and [14, Theorem 4.2].

See also[17, eqn. (A1)] and [10, proof of Theorem 6.6] for the related problem of minimal Blaschke products, and see[START_REF] Braess | Nonlinear Approximation Theory[END_REF] Theorem V.5.5] for how to deal with rational functions with different degree constraints.

There is a typo in [1, Tables1 and 2, p. 150, no. 7 and 8]. There should be no prime on \lambda 1 .

More generally, skeleton decompositions can be used to show that the Hilbert kernel of f (x, y) = 1/(x + y) on [a, b] \times [a, b] with 0 < a < b < \infty has exponentially decaying singular values[START_REF] Oseledets | Lower bounds for separable approximations of the Hilbert kernel[END_REF].

For a real positive semidefinite Hankel matrix one may improve our bounds on the singular values of Hn by replacing n by the rank of Hn.

For those readers who want to make a direct comparison to[38, (1.11)], we know from Theorem 3.1 that the q in[38, (1.11)] satisfies the relationship q = \rho - 4k .

Acknowledgments. Many of the inequalities in this paper were numerically verified using RKToolbox [13], and we thank Stefan G\" uttel for providing support. We thank Yuji Nakatsukasa for carefully reading a draft of this manuscript and pointing us toward [34] and [43]. We also thank Sheehan Olver, Gil Strang, Marcus Webb, and Heather Wilber for discussions. Finally, we thank the referees for carefully reading the paper and providing us with excellent and helpful feedback. The authors are grateful to the SIMAX and SIAM Review editors for selecting this work for a SIGEST award. It is an honor to have our work appreciated in this way.

The work of the first author was supported in part by the Labex CEMPI (ANR-11-LABX-0007-01). The work of the second author was supported by National Science Foundation grant 1818757.

\dagger Laboratoire Paul Painlev\'


Louis DELAUNAY a ; Sabrina MACE b ; Emeline COZIEN b ; Florence POSTOLLEC b ; Ivan LEGUERINEL a ; Anne-Gabrielle MATHOT a a Université de Brest, EA3882, Laboratoire Universitaire de Biodiversité et Ecologie Microbienne, UMT14.01 SPORE-RISK, IBSAM, 6 rue de l'Université, 29334, Quimper, France b ADRIA Développement, UMT14.01 SPORE-RISK, Z.A. de Creac'h Gwen, F-29196, Quimper Cedex, France Lors de la fabrication des poudres laitières, la pasteurisation est la seule étape thermique permettant de détruire les microorganismes végétatifs et potentiellement pathogènes. Cependant, les spores bactériennes présentent dans le lait cru persistent. Celles-ci peuvent germer, se développer, former des biofilms sur les surfaces en inox (spécifiquement dans les échangeurs thermiques et dans les évaporateurs). De plus, les conditions rencontrées (température, a w ) sont optimales pour la germination et la croissance des spores thermophiles. Ces bactéries sporulées pourront altérer le produit final lors de sa réhydratation ou de sa conservation. L'objectif de cette étude a été l'évaluer les prévalences des bactéries sporulées thermophiles dans les poudres laitières d'origines françaises.

Figure 1 :

 1 Figure 1 : Dénombrement des spores thermophiles après un traitement thermique à 80°C pendant 10 min (TSC) et 106°C pendant 30 min (HRTSC). Point central :médiane; boite : quartile: barre : centile; Δ : points extrêmes ou atypiques.

Figure 3 :

 3 Figure 3 : Proportion des isolats récupérés après dénombrement et identification par M13 RAPD-PCR et séquençage du gène 16S de l'ADNr. A : Totalité des 313 isolats; B : Diversité d'isolats issus de la poudre de lait entier; C : Diversité d'isolats issus de la poudre de protéines; D : Diversité d'isolats issus de la poudre de lactosérum

  licheniformis et Anoxybacillus flavithermus : en accord avec la bibliographie(Rückert et al., 2004; Postollec et al., 2012; Sadiq et al., 2018) Diversité spécifique par type de poudres: sélection du process Postollec, F., Mathot, A.G., Bernard, M., Divanac'h, M.L., Pavan, S., and Sohier, D. (2012) Tracking sporeforming bacteria in food: From natural biodiversity to selection by processes. Int J Food Microbiol 158: 1-8 Rückert, A., Ronimus, R.S., and Morgan, H.W. (2004) A RAPD-based survey of thermophilic bacilli in milk powders from different countries. Int J Food Microbiol 96: 263-272 Sadiq, F.A., Flint, S., and He, G. (2018) Microbiota of milk powders and the heat resistance and spoilage potential of aerobic spore-forming bacteria. Int Dairy J 85: 159-168 Prévalence et biodiversité d'Anoxybacillus flavithermus associé à l'industrie des poudres laitières D


Louis Delaunay

Florence Postollec

Ivan Leguerinel

Anne-Gabrielle Mathot

Screening of fast biofilm formation on stainless steel by thermophilic sporeformers originated from dairy powder and their resistance against CIP

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

  Screening of fast biofilm formation on stainless steel by thermophilic sporeformers originated from dairy powder and their resistance against CIP Louis Delaunay, Florence Postollec, Ivan Leguerinel, and Anne-Gabrielle Mathot biofilms 9 Raw milk is contaminated with few thermophilic sporeformers They grow in process and can adhere to stainless steel to form biofilm Conditions encountered in the process are optimal and biofilms can resist CIP procedures biofilms 9.1 -Biofilm control louis.delaunay@univ-brest.fr 3 species isolated from dairy powders : Anoxybacillus flavithermus, Geobacillus stearothermophilus and Bacillus licheniformis -Inoculation of UHT skimmed milk, incubation 55°C 6h in rotary shaker with submerged coupons -Washing steps with tempered water, coloration with Acridine Orange and microscopy. Screening of fast biofilm formation in 6h on stainless steel coupons (1cm x 1cm) . flavithermus strain 288; B: A. flavithermus strain 5; C: G. stearothermophilus strain 60 A. flavithermus is a fast biofilm former in tested conditions and could be the pioneer strain allowing others strains to form biofilm biofilms 9 biofilms 9.1 -Biofilm control 7 strains of A. flavithermus 3 strains of G. stearothermophilus No biofilm formation: B. licheniformis -Inoculation of UHT skimmed milk, incubation 55°C 6h in rotary shaker -CIP procedures (washing with water, NaOH or HNO3, washing with water) -Counting survivals with micro colony method (5µL) after US (10min 16kHz) Biofilm resistance against CIP procedures used in dairy powders industries A. flavithermus are more resistant than G. stearothermophilus ones against CIP Need to validate those results using flow cell biofilm protocol and with multi species biofilms

louis.delaunay@univ-brest.fr


Smail Hamlat
email: smail.hamlat@lcpc.fr

Ferhat Hammoum
email: ferhat.hammoum@lcpc.fr

Pierre-Yves Hicher

CONTACT PROBLEM BETWEEN RUBBER AND ROAD TEXTURE : DETERMINATION OF PRESSURE AND CONTACT AREA DISTRIBUTION

Keywords: area, pressure, Fuji film, road texture

In this paper we derive a method to evaluate the pressure distribution for the road/rubber contact problem The method is based on Fuji Prescale pressure-sensitive film which is currently one of the more popular methods within the biomechanics community. We propose to use it on surface road for determining both pressure and contact area distribution.

INTRODUCTION

To improve comfort and safety and increase the durability of wearing courses, thereby helping to reduce maintenance sequences, wearing courses are being made thinner and rougher, with better skidding resistance, and faster to apply. The problem of determining the pressure distribution between the tire and the road is of enormous importance to the transportation engineering. The surface characteristics of bituminous mixes depends of arrangement of the granular skeleton. For a given set of aggregates, the texture will depend of the constituent as the curve grading, nature of bitumen and of the compaction in place. The aim of this work is to propose a methodology in the setting of the laboratory to determine the pressure distribution in contact problem betwwen a piece of rubber and a sample of bituminous material. Experimental results needs a calibration of data from Fuji pressure-sensitive film. The objective of our research is to identify available laboratory techniques that would allow road laboratories to measure the impact of road texture on the pressure distribution. The pressure distribution in the contact area between a tire and a road depends of several factors that it is been well investigated by De Beer [START_REF] De Beer | Towards improved mechanistic design of thin asphalt layer surfacings based on actual tyre/pavement contact stress-in-motion (SIM) data in South Africa[END_REF]. For a well determined tire, the pressure in free rolling condition is related with the applied load and the pressure inflation.

The results obtained recently by Michelin [START_REF]Le pneu l'adhérence[END_REF] show that the effective contact area is estimated betwwen 5 and 10 % of apparent area between a tire (for an inflation pressure equal 8 bars) and a new surface road. It seems that the heavy load is non-uniformaly distributed in the effective area. The local pressure can reach 150 bars. The local pressure distribution can become the major mechanism for generating damage and evolution in surface charactristics of road.

METHODOLOGY

Pressure distribution applied to road materials, and more generally civil engineering ones, can be divided into four main steps: i) Sample preparation, ii) Digitization of pink stain by using a scanner, iii) pre-treatment by converting the grey level to pressure distribution, iv) Extraction of the pertinent characteristics on digital image. Our approach to the use of Fuji film prescale pressure-sensitive film was similar to those described by Liggins and al. [START_REF] Liggins | Recording contact areas and pressures in joint interfaces[END_REF] et [START_REF] Liggins | Calibration and Manipulation of data from Fuji pressure-sensitive film[END_REF]. The Fuji film was placed on a road texture and a piece of rubber (Shore 60°) was placed on the Fuji film with a pressure range between 0.5 -2.5 MPa. Then, a uniform load was applied on the upper surface of the rubber during 15 secondes. Fuji Prescale pressure-sensitive film (Fuji Photo Co Ltd, Japan) is a two part medium, consisting of a, A-film and a C-Film, both having an active coating on a polymer sustrate. The active surface of the A-film consists of microscopic bubbles adhered to the substrate, within is encapsulated a colourless liquid. On the application of pressure, a number of bubbles will be burst, depending on the pressure magnitude. The active surface of the Cfilm contains a medium which reacts with the liquid released from the A-film, producing a characteristic pink stain. Budapest, Hungary

In addition to pressure, the film's response is affected by load-rate, ambient temperature and relative humidity. Given these factors, the film requires calibration for the previous factors to any test protocol.

A digitized image of the characteristic pink stain can be obtained by using a scanner connected to a personnel computer.

In third step, the pre-treatment by converting the grey level distribution of digital image to pressure needs a calibration curve. This calibration was reproduced here with a circular punch following the procedure given by Liggins and al. [START_REF] Liggins | Calibration and Manipulation of data from Fuji pressure-sensitive film[END_REF]. The last step consists to extract the pertinent characteristics of digital image. The mean of level grey was calculated from Otsu method [START_REF] Otsu | A threshold selection method from grey scale histogram[END_REF]. The results presented in figure 1 were fitted from a 5° order polynomial curve.

DEPENDANCE OF CONTACT AREA UPON TEXTURE ROAD

We evaluate this method on three different road texture made with different aggregate size (D≤10mm, D≤6mm, D≤4mm). The effective contact contact area depends of road texture and the difference can raise 10 % around 7.5 bars corresponding the applied load of heavy traffic (figure2b). Increasing the size of aggregate gradation seems a more concentrated pressure on surface road.

CONCLUSION

The pressure and area contact distribution at aggregate-scale was obtained by using the Fuji Prescale pressuresensitive film. The results obtained in this study shows that for an applied load representing heavy traffic, the pressure and the contact area distribution that depends strongly of aggregate gradation size used on surface road.

Figure 1 .

 1 Figure 1. Fuji Film calibration apparatus and calibration curve

  Figure 2a. Schematic diagram of Fuji Film placed between rubber and road texture