Prove if $A$ has full column rank, then $A+E$ is also has full column rank if $\|E\|_2\leq \frac{1}{\|A^{\dagger}\|_2}$

Solution 1:

The key point of this proof is to notice that the condition on the norm restricts the maximum singular value of $E$. For the details, first apply SVD to matrix $A$: $$ A = U\left[ \begin{array} & \Sigma \\ 0 \end{array} \right]V^{H} $$ , where $U\in\mathbb{R}^{m\times m}$ and $V\in\mathbb{R}^{n\times n}$ are unitary matrices and the diagonal elements of $\Sigma\in\mathbb{R}^{n\times n}$ are positive because $A$ has full rank in columns, i.e. $\sigma_i > 0$ for $\forall i\in\{1, 2 ,\cdots, n\}$.

Easy to verify that $A^{+} = V[\Sigma^{-1}, 0]U^{H}$, and thus $\|A^{+}\|_2 = (\min_{i}{\sigma_i})^{-1}$. So the condition is equivalent to $$ \|E\|_2 = \max_{x\in\mathbb{R}^n}{\frac{\|Ex\|_2}{\|x\|_2}}\le (\|A^{+}\|_2)^{-1} = \min_{i}{\sigma_i}$$ Note that $V$ is unitary so the columns of $V$ spans the space $R^{n}$, which means that for any $x\in\mathbb{R}^{n}$ there exists $\lambda\in\mathbb{R}^{n}$ such that $x = V\lambda$. Therefore, \begin{equation} \begin{aligned} \text{$A + E$ has full column rank} & \iff \text{$(A + E)x \neq 0$ for any nonzero $x\in\mathbb{R}^n$} \\ & \iff \text{$(A + E)V\lambda \neq 0$ for any nonzero $\lambda\in\mathbb{R}^{n}$} \end{aligned} \end{equation} Suppose $(A+E)V\lambda = 0$ for some nonzero $\lambda\in\mathbb{R}^n$: $$ (A+E)V\lambda = A\left(\sum_{i = 1}^{n}\lambda_iv_i\right) + Ex = \sum_{i = 1}^{n}\lambda_i\sigma_i u_i + Ex = 0$$ where $u_i\in\mathbb{R}^{m}$ and $v_i\in\mathbb{R}^n$ are column vectors of $U$ and $V$. Now we have to find a contradiction to show that this is impossible. Consider the norm of both sides: $$ \|Ex\|_2^2 = \|\sum_{i = 1}^{n}\lambda_i\sigma_i u_i\|_2^2 = \sum_{i = 1}^{n}\lambda_i^2\sigma_i^2$$ On the other hand, $\|Ex\|_2 \le \|E\|_2\|x\|_2$ and $\|x\|_2^2 = \sum_{i = 1}^{n}{\lambda_i^2}$, so naturally we get $$ \sum_{i = 1}^{n}\lambda_i^2\sigma_i^2 = \|Ex\|_2^2 \le \|E\|_2^2\|x\|_2^2 = \left(\min_j{\sigma_j^2}\right)\left(\sum_{i = 1}^{n}{\lambda_i^2}\right) \le \sum_{i = 1}^{n}\lambda_i^2\sigma_i^2 $$ The equality is achieved if and only if $\sigma_i = \sigma, \forall i$, i.e. all the singular values of $A$ are the same, say the identity matrix. In fact, if $A = I$ and $E = -I$, which satisfies the given condition, yields $A + E = 0$ that is not full rank. As long as the singular values of $A$ is not identical, the equality in the above inequality can never be achieved, i.e. $$ \sum_{i = 1}^{n}\lambda_i^2\sigma_i^2 \le \left(\min_j{\sigma_j^2}\right)\left(\sum_{i = 1}^{n}{\lambda_i^2}\right) < \sum_{i = 1}^{n}\lambda_i^2\sigma_i^2 $$ So here we get the contradiction, and thus prove that $A+E$ has full column rank.

So in conclusion, $A+E$ has full column rank as long as singular values of $A$ are not identical. Also note that if you change your condition to $\|E\|_2 < (\|A^{+}\|_2)^{-1}$ then $A+E$ always has full column rank no matter what the singular values are.