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

## 2 Answers

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.

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

• $\mu_{n+1}=\min(1,B_2)$ in the second part – daw Jun 3 '15 at 6:26
• @daw Oh, sorry. I will recheck the answer. – PSPACEhard Jun 3 '15 at 6:27