3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.