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.)

$\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}
$$



