I'm looking for the proof of the following numerical algorithm. Suppose I want to solve a non-homogeneous linear equation \begin{equation} A x = b \end{equation} The matrix $A$ is non-invertible and thus has large condition number. So I change the matrix to $\bar{A} = A + \Delta A$, with rows of $\Delta A$ to be composed of the random combinations of null vectors of $A$( equivalently $\Delta A A^{T} = 0$ ). If $\bar{A}$ is invertible, the condition number will be significant reduced, then by a LU decomposition we get a solution $\bar{x} = \bar{A}^{-1} b$. This is perfect if one only needs one solution.
The problem can be reformulated to avoid those detailed numerical operations:
For any matrix $A$ that is not invertible, we can find a invertible matrix $\bar{A}$ such that $\bar{A} A^{T} = A A^{T}$, then $\forall b \in \text{Im}(A)$, $A \bar{A}^{-1}b = b$.
I have made some attempts.
If $(A \bar{A}^{-1} - I) b = 0$, then each rows of $A \bar{A}^{-1} - I$ are in $\text{Im}(A)^{\perp} = \text{ker}(A^T)$(Fredholm contraint).
So $A^T (A \bar{A}^{-1} - I )^T = 0 $ or $ A \bar{A}^{-1}A - A =0$. But I'm unable to relate it to the defining relation $\bar{A} A^{T} = A A^{T}$.(or something wrong with my reformulation of the problem?)
Please tell me the name of this algorithm so that I can perform a search, or you can just teach me how to prove it.
Thanks.
Edit: The key lies in the randomness of $\Delta A$, see my answer.
Let me answer it myself.
Let the column space of $A_{n\times n}$ to be $C(A) = \text{span}(c_1,c_2,\cdots, c_{n-m} )$, the null space to be $N(A) = \text{span}( n_1, n_2, \cdots n_{m} )$( $A n_i = 0$ ). Take a random matrix $R_{n\times m}$, by probability 1, it has a column space $C(R) = \text{span}( c_{n-m+1} \cdots c_n )$ and \begin{equation} C(A) \oplus C(R) = \mathbb{R}^n \end{equation} namely $c_1, c_2, \cdots, c_n$ form a set of basis.
Now construct $\bar{A}$ from $N_{m\times n} = [n_1, n_2, \cdots, n_m]^T$ by \begin{equation} \bar{A} = A + R N \end{equation} there is a large probability that $\bar{A}$ is invertible( if not, choose another random matrix ); then solve $\bar{A} \bar{x} = b$, so \begin{equation} A \bar{x} - b + R N\bar{x} = 0 \end{equation} If $Ax = b$ has solution, then $b \in C(A)$; thus $A\bar{x} - b \in C(A)$. While $R (N\bar{x}) \in C(R)$, so we must have, \begin{equation} A \bar{x} - b = 0\qquad \text{and} \qquad RN \bar{x} = 0 \end{equation} since the column vectors of $R$ are linearly independent, we must have, \begin{equation} N \bar{x} = 0 \end{equation} Therefore the solution we got is the one unique one that is perpendicular to $N(A)$.
I still don't know the name of the algorithm though.