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.)
 A: 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.
A: $\color{red}{\text{Correct me if I am wrong please.}}$
Upper Bound
Assuming you are talking about real matrices. Note that
$$
A' = C + B
$$
where
$
C =
\begin{bmatrix}
A & \textbf{0} \\
\textbf{0}^T & 0
\end{bmatrix}
$
and
$
B =
\begin{bmatrix}
bb^T & b\\
b^T & 1
\end{bmatrix} =
\begin{bmatrix}
b \\
1
\end{bmatrix}
\begin{bmatrix}
b\\
1
\end{bmatrix}^T
$.
Let $\lambda_1, \mu_1, \rho_1$ be the largest eigenvalues of $A', C, B$ respectively and $\lambda_{n+1}, \mu_{n+1}, \rho_{n+1}$ be their smallest eigenvalues accordingly. We have
$$
\lambda_{n+1} \leq \min \{\mu_1 + \rho_{n+1}, \rho_1 + \mu_{n+1}\}
$$
by the Weyl's inequality.



*

*Bound $\mu_{n+1}$ and $\mu_1$


Easy to observe that each eigenvalue of $A$ is also an eigenvalue of $C$. Morevoer, $0$ is also an eigenvalue of $C$. Thus we have
$$
\mu_{n+1} = 0 \text{ and } \mu_1 \leq B_3
$$


*

*Bound $\rho_{n+1}$ and $\rho_1$


Note that $B$ is of rank 1. Thus $B$ has only one non-zero eigenvalue, i.e.,
$\|b\|^2+1$, the trace of $B$. Thus we have
$$
\rho_{n+1} = 0 \text{ and } \rho_1 \leq B_1^2 + 1
$$


*

*Finally, we have
$$
\lambda_{n+1} \leq \min \{B_3, B_1^2 + 1\}
$$



Lower Bound
Let
$$
A' = C + B
$$
where
$
C =
\begin{bmatrix}
A & \textbf{0} \\
\textbf{0}^T & 1
\end{bmatrix}
$
and
$
B =
\begin{bmatrix}
bb^T & b\\
b^T & 0
\end{bmatrix}
$. Note these two matrices are different from the two in last part.
Let $\lambda_{n+1}, \mu_{n+1}, \rho_{n+1}$ be the smallest eigenvalues of $A'$, $C$, $B$, respectively. We have
$$
\mu_{n+1} + \rho_{n+1} \leq \lambda_{n+1}
$$



*

*Bound $\mu_{n+1}$


Easy to observe that each eigenvalue of $A$ is also an eigenvalue of $C$. Morevoer, $1$ is another eigenvalue of $C$. Thus we have
$$
\mu_{n+1} = \min\{1, B_2\}
$$


*

*Bound $\rho_{n+1}$


We apply the Gershgorin circle theorem here. According to the theorem, there exists a $1 \leq i \leq n$ such
that
$$
|b_i|(|b_i| - \sum_{j\neq i}|b_j| - 1) \leq \rho_{n+1} \tag{1}
$$
where $b_1, b_2, \cdots, b_n$ are components of $b$ OR
$$
-\sum_{j=1}^n|b_j| \leq \rho_{n+1} \tag{2}
$$.
By Cauchy–Schwarz inequality, we have
$$
\sum_{j=1}^n |b_j| \leq \sqrt{n}\|b\| \tag{3}
$$
thus
$$
|b_i|(|b_i| - \sum_{j\neq i}|b_j| - 1) \geq -|b_i|(\sum_{j=1}^n |b_j| + 1) \geq -B_1(\sqrt{n}B_1 + 1) \tag{4}
$$
By (1) - (4), we have
$$
\min\{-B_1(\sqrt{n}B_1 + 1), - \sqrt{n}B_1\} \leq \rho_{n+1}
$$


*

*Finally, we have
$$
\min\{1, B_2\} + \min\{-B_1(\sqrt{n}B_1 + 1), - \sqrt{n}B_1\} \leq \lambda_{n+1}
$$



