Let $S\in\mathbb{R}^{n\times n}$ be a diagonal positive semidefinite matrix with exactly $k$ positive entries in its diagonal, where $k<n$. Let $\epsilon$ be any arbitrarily small positive real number. Can we find a symmetric matrix $A=A(\epsilon)\neq 0$ such that $\|A\|_{\mathrm{op}} \leq \epsilon\; \lambda_{\textrm{min}}(S+A)$ ?
Here, $\|\cdot\|_{\mathrm{op}}$ denotes the operator norm, and $\lambda_{\mathrm{min}}$ is the smallest eigenvalue.
Thank you very much.
On
As both $A,S$ are symmetric, we get $$\lambda_\text{min}(S+A) = \min_{v\in \mathbb{R}^2 : \Vert v \Vert=1} \langle v, (S+A) v \rangle.$$ As $S$ has nontrivial kernel, we can pick $w\in Ker(S)$ with $\Vert w \Vert=1$ and get $$ \lambda_\text{min}(S+A) \leq \langle w, (S+A) w\rangle = \langle w,Aw\rangle \leq \Vert A \Vert_\text{op} \Vert w \Vert^2 = \Vert A \Vert_\text{op}. $$ Then your desired inequality would imply that $$ \Vert A \Vert_\text{op} \leq \varepsilon \Vert A \Vert_\text{op}, $$ which does not work for $A\neq 0$ and $0\leq \varepsilon<1 $.
Note that the same proof works for any symmetric $S$ with nontrivial kernel. If $S$ admits a negative eigenvalue, we test on the corresponding eigenvector and reach the same contradiction. For your conclusion to hold, we need that the lowest eigenvalue of $S$ is strictly positive.
Let us look at the case when $n=2$ and $S=\begin{pmatrix}s & 0\\ 0 & 0\end{pmatrix}$ for some fixed $s>0$.
We are looking for a symmetric $A$, therefore we can write $A=U^T\begin{pmatrix}sx & 0 \\ 0 & sy \end{pmatrix}U$ for some real numbers $x,y$ and some orthogonal matrix $U$. Since conjugating a matrix doesn't change its eigenvalues, we need to find $x,y$ such that $s\max(|x|,|y|)\leq \varepsilon \lambda_{min}(B)$, where $B:=USU^T+\begin{pmatrix}sx & 0 \\ 0 & sy \end{pmatrix}$, with $x,y$ depending on $\varepsilon$.
Now orthogonal matrices in dimension two are either rotations of the form $\begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{pmatrix}$ or reflections of the form $\begin{pmatrix}\cos\theta & \sin\theta \\ \sin\theta & -\cos\theta\end{pmatrix}$.
In both cases ($U$ being either a reflection or a rotation), we get \begin{equation*} P_B(\lambda)=\begin{vmatrix} s\cos^2\theta+sx-\lambda & s\sin\theta\cos\theta\\ s\sin\theta\cos\theta & s\sin^2\theta +sy -\lambda\end{vmatrix} = \lambda^2 -s(1+x+y)\lambda+s^2(xy+x\sin^2\theta+y\cos^2\theta), \end{equation*}
so $\lambda_{min}=s\frac{1+x+y-\sqrt{(1+x+y)^2-4(x\sin^2\theta+y\cos^2\theta+xy)}}{2}$.
Therefore the inequality we want to satisfy reduces to \begin{equation*} \frac{2}{\varepsilon}\max(|x|,|y|)\leq 1+x+y-\sqrt{(1+x+y)^2-4(x\sin^2\theta+y\cos^2\theta+xy)}. \end{equation*}
By assuming without loss of generality that $|x|\geq |y|$ and dividing both sides by $|x|$, we see that $\frac{RHS}{|x|}$ should be unbounded (as a function of $x,y$) for the inequality to be satisfied (for small enough $\varepsilon$). But note that $\frac{RHS}{|x|}\leq 2+\frac{1}{|x|}$, so we can restrict our search to the case $|y|\leq|x|<1$. In fact, setting \begin{equation*} f(x,y)=1+x+y-\sqrt{(1+x+y)^2-4(x\sin^2\theta+y\cos^2\theta+xy)}, \end{equation*} the only hope for the inequality to be satisfied for an appropriate choice of $x,y$ with $|y|\leq |x|$ is that $\limsup_{x\to 0}\frac{f(x,y)}{|x|}=\infty$. Clearly, $\lim_{x\to 0}f(x,y)=0$, so using L'Hopital's rule, we need that $\lim_{x\to 0}|\frac{\partial{f}}{\partial{x}}(x,y)|=\infty$.
However, $\frac{\partial{f}}{\partial{x}}(x,y)=1-\frac{1+x-y-2\sin^2\theta}{\sqrt{(1+x+y)^2-4(x\sin^2\theta+y\cos^2\theta+xy)}}$ (assuming my computations are correct :D), and this clearly tends to $2\sin^2\theta\leq 2$ as $x\to 0$ (recall that $|y|\leq |x|$).
Therefore, for $n=2$ and for $\varepsilon$ sufficiently small, no $A$ can be found to satisfy the required inequality.