Solution of $Ax=b$

Problem

Given $Ax=b$, where$A\in R^{m\times n}$, $x\in R^{n}$, $b \in R^{m}$, what is the solution?

Solution

It has a little difference from $Ax=0$. There may be no solution or unique solution and more. What we should first think about here is augmented matrix $\tilde{A} = [ A | b ]$ and to compare $rank(\tilde{A})$ and $rank(A)$.

if $rank(\tilde{A}) > rank(A)$, there'll be no solution here.
if $rank(\tilde{A}) = rank(A)$, there exists at least one solution.

So let's look about the case of existing solutions, which is much similar to the form $Ax = 0$.

if $m = n$ and $rank(A) = n$, then $A^{-1}$ exists, so $x = A^{-1}b$.

if $m = n$ and $rank(A) < n$, there exists at least one free variable, the number of which is $n - rank(A)$

if $m \neq n$ and $rank(A)$ must not be more than $min(m, n)$.

if $m < n$, then $rank(A) <= m < n$, so the equations will be undetermined, which means there exists non-trivial solutions.

if $m > n$, then $rank(A) <= n < m$. For $rank(A) = n$, the system has an unique solution. What's interesting here is that A is not really overdetermined. We could remove $m-n$ rows from $\tilde{A}$ and change the linear system to case 1. While $rank(A) < n$, it degenerates to be undetermined with non-trivial solutions.

Least Squares

What if there's no solution for $Ax = b$ in theory, namely $rank(\tilde{A}) > rank(A)$? That's what least squares does.

If $A$ is overdetermined, we could use least squares to get an approximate solution by converting $Ax = b$ to an optimization problem, which means $E(x) = |Ax - b|^{2}$. The following shows least squares figure:

Least Squares Approximation

What we should realize is that if the blue dots all lie in the same red line, that implies $rank(\tilde{A}) = rank(A)$, which is case 3.2.

Problem

Solution

Least Squares

References