# Condition number growth with “column add” operation

This problem concerns how when you add a column to a matrix, its two-norm condition number grows. I ran across this as Problem 5.3.2 in Golub and van Loan, stated in the line below.

Let $$A \in \mathbb{R}^{m \times n}$$ with $$m > n$$. Let $$y \in \mathbb{R}^{m}$$ and $$\bar{A}=[A$$ $$|$$ $$y] \in \mathbb{R}^{m \times (n+1)}$$. Then $$\sigma_1(\bar{A}) \geq \sigma_1(A)$$ and $$\sigma_{n+1}(\bar{A}) \leq \sigma_n(A)$$.

Here's how I've proceeded.

Let $$x =\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \in \mathbb{R}^{n+1}$$

with $$x_1 \in \mathbb{R}^{n}$$ and $$x_2 \in \mathbb{R}$$. Then $$\bar{A}x = Ax_1 + x_2 y$$. This implies \begin{align*} \|\bar{A}x\|_{2}^{2} = \langle \bar{A}x, \bar{A}x \rangle = \|Ax_1\|_{2}^{2} + x_2^2 \|y\|_{2}^{2} + x_2 \langle Ax_1,y \rangle. \end{align*} Now simply take $$x_1 = v_1$$ and $$x_2 = 0$$ where $$v_1$$ is the first right singular vector of $$A$$. This yields $$\|x\|_2 = 1$$ and $$\|\bar{A}x\|_{2}^{2} = \sigma_{1}(A)^{2} \|u_1\|_{2}^{2} = \sigma_{1}(A)^{2}$$ where $$u_1$$ is the first left singular vector of $$A$$. Taking the supremum over all $$x$$ in the unit ball yields $$\sigma_1(\bar{A}) = \|\bar{A}\|_2 \geq \sigma_1(A)$$, as desired.

As for the second part, consider $$\bar{A}^{\dagger}$$, with $$\dagger$$ denoting the pseudoinverse. Then if we recycle the result from the previous part, we have that $$\frac{1}{\sigma_{n+1}(\bar{A})} \geq \frac{1}{\sigma_n(A)}$$, from which the result is covered.

I believe my proof for the first part works. However, for the second part, I'm not confident in whether this works and if it does, how exactly to formalize it...in other words, do I know that the $$\bar{A}^{\dagger} = [A^{\dagger}$$ $$|$$ $$z]$$ for some $$z$$ so that I can "recycle the result from the first part?" Furthermore, the dimensions get flipped, so I can't see immediately how to do what I've outlined in a rigorous way.

Certainly maximum and minimum over a smaller set gives, respectively, a not greater and not smaller result: $$\sigma_1(\bar{A})=\max_{\|x\|_2^2+|\xi|^2=1}\left\|[A,y]\begin{bmatrix}x\\\xi\end{bmatrix}\right\|_2 \geq \max_{\|x\|_2=1,\;\xi=0}\left\|[A,y]\begin{bmatrix}x\\\xi\end{bmatrix}\right\|_2 = \max_{\|x\|_2=1}\left\|Ax\right\|_2=\sigma_1(A),$$ $$\sigma_{n+1}(\bar{A})=\min_{\|x\|_2^2+|\xi|^2=1}\left\|[A,y]\begin{bmatrix}x\\\xi\end{bmatrix}\right\|_2 \leq \min_{\|x\|_2=1,\;\xi=0}\left\|[A,y]\begin{bmatrix}x\\\xi\end{bmatrix}\right\|_2 = \min_{\|x\|_2=1}\left\|Ax\right\|_2=\sigma_n(A).$$