Given a matrix $A$ of size $n\times m$ with $m<<n$ linearly independent columns and hence of full rank. Now a column $a$ is added to $A$. How can we determine the new matrix $A$ of size $n\times (m+1)$ is still invertible?
I know one way is to check if the value $[a^Ta-(A^Ta)^T(A^TA)^{\dagger}(A^Ta)]$ is non-zero. But I don't want to compute the pseudo-inverse $(A^TA)^{\dagger}$. Nor do I want to compute the determinant which takes $O(n^3)$ complexity.
Is there any computationally efficient way to do this?
@ Vinayak Abrol , do you understand that you write ?
EDIT. 2. The calculation of the rank of a matrix $(n\times m+1)$ is in $O(n(m+1)^2)$ by Gaussian elimination; moreover, there is a randomized algorithm in $O((m+1)n+(m+1)^3)$, that is much better than your $O(n^3)$.
The calculation of $(A^TA)^{-1}$ is the calculation of $A^TA$ (with complexity $nm^2$) and the calculation of its inverse (with complexity $m^3$). Finally the total complexity is $nm^2$ and absolutely not $n^3$.
Consequently, to verify that the condition $||a||^2-a^TA(A^TA)^{-1}A^Ta\not= 0$ is satisfied has complexity $O(nm^2)$, that is essentially $O(n)$; how to do better ?