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

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