I think it is known that given a nonsingular $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^n$, solving a linear system $Ax =b$ for $x$ can be done in $O(n^3)$ steps.
Now assume $A$ is of rank $r <n$ and suppose one is looking for any solution $x$ of $Ax=b$. How many steps does this take? A result that depends on $r,n$ or where $r$ is a function of $n$ would be most useful for me. I would appreciate it if anyone could help me out with this.
With Gaussian elimination, you get equivalent upper triangular system in $\mathcal{O}(n^2r)$ steps. Then, it takes another $O(n)$ steps to solve that system, therefore the answer is $\mathcal{O}(n^2r)$. I don't know if there are any special methods it the case $r$ and $n$ satisfie some additional conditions such as $r \ll n$ ...