Lower bounding the eigenvalue of a matrix Suppose I have the following symmetric matrix 
$$
A'=\begin{bmatrix}
A + b b^T & b \\
b^T & 1
\end{bmatrix}
$$
where $A$ is positive definite $n \times n$ symmetric matrix and $b$ is a $n \times 1$ vector.  
Suppose $\|b\|_2 \leq B_1$, and all eigenvalues of $A$ are between $[B_2, B_3]$. 
What is a bound in terms of $B_1$, $B_2$, and $B_3$ for the smallest eigenvalue of $A'$?
(It is straight forward to show that $A'$ is positive definite.)

Let $z=(x,x_{n+1})$, $x\in\mathbb R^n$. Then
$$
z^TA'z = x^TAx+ (b^Tx)^2 + 2 x_{n+1} (b^Tx) + x_{n+1}^2
\ge x^TAx+ (b^Tx)^2 -((b^Tx)^2+ x_{n+1}^2) + x_{n+1}^2 = x^TAx,
$$
which tells that $A'$ is positive semi-definite. The right-hand side does not depend on $x_{n+1}$, we do not get positive definiteness here. Using the positive definiteness of $A$ gives
$$z^TA'z = x^TAx+ (b^Tx)^2 + 2 x_{n+1} (b^Tx) + x_{n+1}^2\\
\ge B_2 \|x\|^2+ (b^Tx)^2 + 2 x_{n+1} (b^Tx) + x_{n+1}^2.
$$
Estimating
$$
-2 x_{n+1} (b^Tx) \le (1-\epsilon) x_{n+1}^2 + \frac1{1-\epsilon}(b^Tx)^2
$$
with some $\epsilon\in(0,1)$
gives
$$
z^TA'z 
\ge B_2 \|x\|^2 - \frac\epsilon{1-\epsilon}(b^Tx)^2  + \epsilon \,x_{n+1}^2.
$$
Estimating the term containing $\|x\|^2$ gives
$$
B_2 \|x\|^2 - \frac\epsilon{1-\epsilon}(b^Tx)^2
\ge \left(B_2 - \frac\epsilon{1-\epsilon}B_1^2\right)\|x\|^2,
$$
setting $\epsilon:=\frac{B_2}{B_2+2B_1^2}$ gives $\frac\epsilon{1-\epsilon}B_1^2=\frac12B_2$. Thus, we obtain the lower bound
$$
z^TA'z \ge \frac{B_2}2\|x\|^2 + \frac{B_2}{B_2+2B_1^2} x_{n+1}^2 \ge \frac{B_2}{\max(2,B_2+2B_1^2)} \|z\|^2
$$
and hence the smallest eigenvalue $\lambda_1$ of $A'$ is bounded below by
$$
\frac{B_2}{\max(2,B_2+2B_1^2)} \le \lambda_1,
$$
hence the smallest eigenvalue is bounded away from zero.

One can try to balance the $\epsilon$-dependent by solving with $\epsilon\in(0,1)$
$$
B_2 - \frac\epsilon{1-\epsilon}B_1^2=\epsilon.
$$
In case $\epsilon<1$ this is equivalent to
$$
f(\epsilon)=\epsilon^2-\epsilon(1+B_2+B_1^2) +B_2=0.
$$
Assume $b\ne0$ and $B_1>0$.
Since $f(0)=B_2>0$, $f(1)=-B_1^2<0$, there is a root in $(0,1)$, but no negative root, and the smallest root is given by
$$
\epsilon^*=\frac12\left( 1+B_2+B_1^2
-\sqrt{( 1+B_2+B_1^2)^2 - 4B_2}
\right),
$$
this $\epsilon^*$ constitutes another (optimal?) lower bound for the smallest eigenvalue,  $\epsilon^*\le\lambda_1$.
In the case $B_1=0$ it holds $\epsilon^*=\min(1,B_2)$, which is optimal.
