I know that if the X matrix when using the normal equation is dependent then the transpose(X)*X will be non invertible and as a result there will be an infinite number of solutions to the problem.
I don't know why this is an issue. Why can't the normal equation still execute and then just return the first solution that it finds, even if there are many other equally good solutions?