Adding row and column to a positive definite matrix 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.
 A: *

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

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

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

*This I believe is hopeless.

