When does it not require least square to solve $A × x=b$?

Question

Suppose I have a $n \times n$ independent matrix $A$, can I just take the inverse of $A$ directly and get $x = A^{-1}\times b$?

Is least square solution only for the matrix that is not in $N\times N$ form?

If I am wrong about the $N \times N$ part, can you give an example of such matrix $A$ that doesn't need least squares to solve?

Answer 1

Not all matrices are invertible, meaning $A^{-1}$ doesn't always exist. $A$ is invertible if and only if it is square and $\det(A)\neq 0$; in this case any equation $Ax=b$ has a solution given by $x=A^{-1}b$.

---

When $A$ is square $(n\times n)$ the following are equivalent:

• $A$ is invertible
• $A^{-1}$ exists
• $A$ is surjective, meaning $\text{Codom}(A) = \text{Im}(A)$
• $A$ is injective, meaning $\ker(A) = \{0\}$
• $A$ is bijective, meaning it is both surjective and injective

It is a consequence of the rank-nullity theorem that nonsquare $A$ are never invertible. Indeed, if $A$ is $m\times n$, then as a linear transformation it is a map $\mathbb R^n \longmapsto \mathbb R^m$. The rank-nullity theorem then says that

$$\dim \text{Im}(A) +\dim\ker(A) = n$$

If $m>n$, then $\dim \text{Im}(A) \leq n < m = \dim \text{Codom}(A)$, so $A$ fails to be surjective.
If $m<n$, then $\dim\ker(A) = n - \dim \text{Im}(A)\geq n - m > 0$, so $A$ fails to be injective.

---

Now, suppose $A$ is square and not invertible; there are two possibilities:

$\qquad (1)$: $b \in \text{Im}(A)$

In this case, there is some $x\in \text{Dom}(A)$ with $Ax=b$, so the equation has a solution.
The problem is since $A$ is not invertible, it is not injective and hence its kernel has $\dim \geq 1$. Any $u \in \ker(A)\setminus\{0\}$ — and notice this set is nonempty because of our previous observation — will therefore be such that $x+u$ is also a solution. Indeed:

$$A(x+u) = Ax + Au = b + 0 = b$$

In other words, we not only have a solution, we have infinitely many of them.

$\qquad (2)$: $b \not\in \text{Im}(A)$

In this case, of course there is no solution.

---

Least squares is a method for finding 'almost solutions' when none exist. More specifically, when the equation $Ax = b \iff Ax - b = 0$ has no solution, least squares attempts to find an $x$ which minimizes $\lVert Ax - b \rVert$. In other words, it finds some $x$ such that $Ax$ is closest (in the usual Euclidean norm sense) to $b$.

The value $u = Ax$ always exists and is unique, because $\text{Im}(A)$ is closed and $\{b\}$ is compact. However, like in case $(1)$ above, there may be infinitely many $x$ that satisfy $Ax = u$.

I find it best to think in terms of projections: if $u$ minimizes $\lVert u - b\rVert$ over $u\in \text{Im}(A)$, then $u$ is the projection of $b$ onto $\text{Im}(A)$, ie

$$ u = \text{Proj}_{\text{Im}(A)} b$$

Answer 2

Yes, you can solve $A × x=b$ directly using the inverse of $A$ if it exists.

Least squares (and pseudo-inverse of $A$) is needed, e.g. when (quoting wikipedia)

a vector $x$ that solves the system may not exist, or if one does exist, it may not be unique