Title: On the optimality and sharpness of Laguerre's lower bound on the smallest eigenvalue of a symmetric positive definite matrix,
Abstract: Lower bounds on the smallest eigenvalue of a symmetric positive definite
matrices $A\in\mathbb{R}^{m\times m}$ play an important role in condition
number estimation and in iterative methods for singular value computation. In
particular, the bounds based on ${\rm Tr}(A^{-1})$ and ${\rm Tr}(A^{-2})$
attract attention recently because they can be computed in $O(m)$ work when $A$
is tridiagonal. In this paper, we focus on these bounds and investigate their
properties in detail. First, we consider the problem of finding the optimal
bound that can be computed solely from ${\rm Tr}(A^{-1})$ and ${\rm
Tr}(A^{-2})$ and show that so called Laguerre's lower bound is the optimal one
in terms of sharpness. Next, we study the gap between the Laguerre bound and
the smallest eigenvalue. We characterize the situation in which the gap becomes
largest in terms of the eigenvalue distribution of $A$ and show that the gap
becomes smallest when ${\rm Tr}(A^{-2})/\{{\rm Tr}(A^{-1})\}^2$ approaches 1 or
$\frac{1}{m}$. These results will be useful, for example, in designing
efficient shift strategies for singular value computation algorithms.