Let $A\in \mathbb{R}^{n\times n}$ be positive definite matrix with least eigenvalue $\lambda$. We create a new matrix $\widetilde{A}\in \mathbb{R}^{(n+1)\times (n+1)}$ in the following way: Pick $i\in \{1,\dots,n\}$ and add a row and a column to $A$ such that for every $j\neq i$: $ a_{n+1,j} = a_{i,j}, ~~ a_{j,n+1} = a_{j,i}$, and $~a_{n+1,n+1} = a_{i,i}, ~a_{i,n+1} = a_{n+1,i} = \frac{1}{2}$. For example, if we pick $i=n$ and denote $A = \begin{pmatrix} A' ~~ b \\ b^\top \alpha \end{pmatrix}$ where $A'\in \mathbb{R}^{(n-1)\times (n-1)},~ b\in \mathbb{R}^{n-1},~ \alpha\in \mathbb{R}$ then:

$\widetilde{A} = \begin{pmatrix} A' ~~ b ~~ b \\ b^\top~~ \alpha ~~ \frac{1}{2} \\ b^\top ~~\frac{1}{2} ~~\alpha\end{pmatrix}$

My questions are the following:

1) Assume that $\lambda$ large enough, will $\widetilde{A}$ be positive definite for every $i$ we chose?

2) will the smallest eigenvalue of $\widetilde{A}$ necessarily be smaller than the least eigenvalue of $A$?

3) Can we get a lower bound on the smallest eigenvalue of $\widetilde{A}$?

4) Is there a strategy to pick the best $i\in\{1,\dots,n\}$ so that the lower bound on the smallest eigenvalue of $\widetilde{A}$ is the largest we can find.

I think that because of the way the row and column are added, the smallest eigenvalue of $\widetilde{A}$ is smaller than the smallest eigenvalue of $A$ by at most $1$, but it might depend on the row $i$ that we pick. Also couldn't find an example of a PD matrix that you add a row and column in this manner and the smallest eigenvalue increases, so I suspect that (2) is also true.

  1. No. Consider $A=n\pmatrix{5&4\\ 4&5}$, whose eigenvalues are $9n$ and $n$, so that $\lambda_\min(A)\to\infty$ as $n\to\infty$. Then $\widetilde{A}=\pmatrix{5n&4n&4n\\ 4n&5n&\frac12\\ 4n&\frac12&5n}$ when $i=2$. Since the eigenvalues of $\lim_{n\to\infty}\left(\frac1n\widetilde{A}\right)=\pmatrix{5&4&4\\ 4&5&0\\ 4&0&5}$ are $5$ and $5\pm4\sqrt{2}$, $\widetilde{A}$ is indefinite when $n$ is large.
  2. Yes. By Cauchy's interlacing inequality, $$ \lambda_1(\widetilde{A})\le\lambda_1(A)\le\lambda_2(\widetilde{A})\le\lambda_2(A)\le\cdots\le\lambda_n(\widetilde{A})\le\lambda_n(A)\le\lambda_{n+1}(\widetilde{A}), $$ where $\lambda_i(\cdot)$ denotes the $i$-th smallest eigenvalue of a Hermitian matrix.
  3. As $\lambda_\min(\widetilde{A})$ can be negative, I'm not sure if you still want to a lower bound. Anyway, since $$ \pmatrix{A'&b&b\\ b^T&\alpha&\frac12\\ b^T&\frac12&\alpha} =\pmatrix{1&0&0\\ 0&1&0\\ 0&1&1} \pmatrix{A'&b&0\\ b^T&\alpha&0\\ 0&0&0} \pmatrix{1&0&0\\ 0&1&1\\ 0&0&1} +\pmatrix{0&0&0\\ 0&0&\frac12-\alpha\\ 0&\frac12-\alpha&0}, $$ we have $$ \|\widetilde{A}\|_2 \le\left(\frac{1+\sqrt{5}}{2}\right)^2\|A\|_2+|\alpha-\frac12| $$ and hence a rather loose lower bound of $\lambda_\min(\widetilde{A})$ is given by $$ \lambda_\min(\widetilde{A})\ge-\|\widetilde{A}\|_2\ge-\left(\frac{3+\sqrt{5}}{2}\|A\|_2+\max_k|a_{kk}-\frac12|\right). $$
  4. This I believe is hopeless.

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.