Adding row and column to a positive definite matrix

Question

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.

Answer 1

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.