Lower bounding the eigenvalue of a matrix

Question

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

Answer 1

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.

Answer 2

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

---