linear systems of equations

Linear System of Equations

$$\underset{\text{known }}{A}\underset{\text{ solve}}{x}=\underset{\text{known}}{b}$$

where $A\in {\mathbb{R}}^{m\times n}$ is a matrix, $x\in {\mathbb{R}}^{n\times 1}$ is a column vector, and $b\in {\mathbb{R}}^{m\times 1}$ is a column vector.
If $A$ is a square matrix, we have exactly as many knowns as unknowns, and if $A$ is invertible , we can solve for $x$: $x=A^{-1}b$.

What if $A$ is not square?

Consider $Ax=b$ where $A\in {\mathbb{R}}^{m\times n}$, there are two cases:

For overdetermined systems, $m>n$ (tall skinny $A$):

• Too many equations, no exact solution typically exists
• Least squares finds $x$ that minimizes $\Vert Ax-b{\Vert }_2$ (error minimization)

For underdetermined systems $m<n$ (short fat $A$):

• Infinite solutions exist that satisfy $Ax=b$ exactly
• Minimum norm finds the $x$ with smallest $\Vert x{\Vert }_2$ among these solutions (energy minimization)

These solutions can be found with the help of the Moore-Penrose pseudo inverse $A^{+}$.

A solution of $Ax=b$ only exists if $b$ is in the column space of $A$.

$\ker (A^T)$ – the null space of $A^T$ – is the orthogonal complement to the column space, so if the vector $b$ was in $\ker (A^T)$, there would be no linear combintation $x$ of the columns of $A$ that yields $b$, i.e. no solution to the system of equations.

EXAMPLE

The vector $b$ can be represented as a linear combination of columns of $A$:

$$\begin{array}{r}\left[\begin{array}{cc}1& 2\\ 2& 3\\ 3& 4\end{array}\right]\cdot {\left[\begin{array}{c}0\\ 1\end{array}\right]}^T=\left[\begin{array}{c}2\\ 3\\ 4\end{array}\right]\end{array}$$

There is no $x$ that can solve the below system of equations, as the column space of $A$ does not contain $b$:

$$\begin{array}{r}\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\end{array}\right]\cdot x=\left[\begin{array}{c}1\\ 2\end{array}\right]\end{array}$$

Link to original

If $\dim (\ker (A))\ne 0$, then there are infinitely many solutions ($A(x+x_{\text{null}})=b$).