If we give a small perturbation of matrix coefficient, can we find a corresponding solution which has small change w.r.t. the original one?

92 Views Asked by At

Assume $A$ is a $m \times n$ matrix, $m<n$, and $\operatorname{rank}(A)<m$. For $b \in \mathbb{R}^n$, assume $AX=b$ has a solution $X=(x_1, \ldots, x_n)$, then clearly there exist infinitely many solutions. By the structure of the solutions, we may assume $\sum_{i=1}^n x_i=1$. Now my question is, for any $\epsilon>0$, does there exist $m \times n$ matrix $\tilde{A}$ with $\operatorname{rank}(\tilde{A})=m$ and vector $\tilde{X}=(\tilde{x}_1, \ldots, \tilde{x}_n) \in \mathbb{R}^n$ such that $\|A-\tilde{A}\|<\epsilon, \|X-\tilde{X}\|<\epsilon$ and $\tilde{A} \tilde{X}=b$ ?

The question is a continuation of the question in the link How to find a perturbation of coefficients of a linear system to guarantee the error of solutions is small?, which deals with the case $m=n$. Actually when $m=n$, the answer is negative, since if $b=0$, then $\tilde{X}=0$, which cannot satisfy $\|X-\tilde{X}\|<\epsilon$.

However, I do believe the answer is positive for the case $m<n$, but I've no idea how to give a proof. Maybe there are still counterexamples. Can anyone give me any ideas?