# What happens if A is not invertible in equation Ax=b?

I know that depending on whether consistency condition is satisfied or not we get infinite or no solution. My understanding is that the case for which we have infinite solution are the least squares solution solving normal equation which has inverse of transpose(A)*A, but then if A is not invertible this also won't be invertible.

So how do we get solution in this case ?

I know by hand method in which we eliminate pivotal variables in terms of non pivotal variables and then we can set arbitrary values for non pivotal variables, hence getting infinite solutions.

I want to understand it from the perspective of arriving at the solution by solving normal equation.

So my main point of concern is that (A′A)^-1 = (A^-1)(A'^-1) = (A^-1)(A^-1)' which would require A to be invertible ?

• Typically, $A$ is noninvertible but $A^\prime A$ is. When the latter is noninvertible, there are many methods, but a good keyword to use in searches is "generalized inverse." – whuber May 15 '18 at 15:39
• Isn't (A′A)^-1 = (A^-1)*(A'^-1) which would require A to be invertible ? This is my main point of concern. I have updated it in question too. – Siddharth Shakya May 15 '18 at 18:21
• No. A'A is a matrix, we can't distribute inverse into it. In fact, when we solve the linear system, we do not explicitly calculate the inverse. see here – Haitao Du May 15 '18 at 20:27
• I don't see any help in that link, and for inverse of A'A to exist inverse of A also has to exist. For computing in that case i don't see how will we get pseudo inverse without computing svd in which case eigen-vectors corresponding to 0 eigen-value will not count in the summation. – Siddharth Shakya May 16 '18 at 5:46
• Your logic is incorrect: when $A$ is invertible, then so is $A^\prime A$, but not conversely. A simplest possible counterexample is $A=\pmatrix{1\\0}$ which, not being square, is not invertible, but where $A^\prime A = (1)$ obviously is invertible. – whuber May 16 '18 at 11:36

The pseudo-inverse a.k.a. Moore–Penrose inverse generalizes the matrix inverse for non invertible matrices and even non square matrices. It can be computed using (SVD) singular value decomposition.

When the matrix is invertible, the pseudo-inversion gives the regular inverse of the matrix.

I think OP is confused by $A$ and $A'A$ as @whuber mentioned.

Let $A$ to be the design matrix (for example, if we have 100 data point / persons, and each 2 features /height and weight, $A$ is a $100 \times 2$ matrix)

1. Solving $Ax=b$ will lead to no solutions. NOTE, it is not an underdetermined system, but an overdetermined system!

2. Instead we will solve $A'Ax=A'b$. Note, if $A$ is $100 \times 2$ matrix, $A'A$ is a $2 \times 2$ matrix! There are many nice properties with $A'A$, and if it comes from real data, it is invertable. and the $x$ is the least square solution.

3. For now, let's forget the least square problem. But only consider the math problem: $Ax=b$, i.e., $A$ is not coming from a design matrix transpose times design matrix, it is possible $A$ is not invertable. If that is the case, we can put additional constrains to the system, so we can have unique solutions. Or get one solution from infinite solutions, if that satisfy the needs.