What happens when $A$ has linearly dependent columns and $A^T A$ is thus not invertible?

Question

Suppose $A$ is a matrix with linearly dependent columns. I want to find the solution to $Ax=b$ where $b$ does not belong to column space of $A$. So, I find the solution to a new equation $Ax'=p$ where $p$ is the projection of $b$ onto column space of $A$.

Thus, $x' = (A^T A)^{-1}A^Tb$

But since $A$ has linearly dependent columns, $A^TA$ cannot be invertible.

So, how can I find the $x'$? Or am I wrong in my understanding somewhere?

Answer 1

Suppose $A$ is an $l\times n$ matrix

You can pick a basis $a_{n_1},\ldots, a_{n_m}$ for the column space of $A$ where the $a_i$ are columns of $A$ and clearly $m<n$.

Then consider the matrix $B=[a_{n_1},\ldots,a_{n_m}]$ and look at the matrix equation $By=b$. Use the pseudo-inverse to find $y'=(B^TB)^{-1}B^Tb$.

Then you need to lift the solution $y' \in \mathbb{R}^m$ to an $x' \in \mathbb{R}^n$ you can do this by setting the corresponding components in $y'$ to their counterparts in $x'$ and set the other components equal to zero.

I'm editing to provide more info on the correspondence:

$y_1 \leftrightarrow x_{n_1}\\ y_2 \leftrightarrow x_{n_2}\\ \vdots\\ y_m \leftrightarrow x_{n_m}$

Obviously, there's more than one solution here so it's not really the same sort o thing.

Answer 2

The least squares solution, $x^{'}$, is the vector of coordinates of the closest vector in $col(A)$ to vector $b$ (its projection, say vector $p$) when the column vectors of matrix A are used to span $col(A)$.

When A has linearly independent columns, then the columns form a basis for $col(A)$. As such, $x^{'}$ is unique, since $p$ is uniquely represented in terms of the columns.

When $A$ has linearly dependent columns, however, $p$ can be represented in infinitely many ways as a linear combination of the column vectors of A. In this case, the minimum least square solution is usually desired. That is, the vector of coordinates, $x^{'}$, that has the smallest or shortest length. This vector is unique and can be found by computing the pseudoinverse of A. Gilbert Strang in Appendix A of his third edition of linear algebra and its applications shows how to compute this pseudoinverse using the SVD of A.