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$.

Written out explicitly:

$$\begin{array}{ccccccccc}{a}_{11}{x}_1& +& a_{12}{x}_2& +& \cdots & +& a_{1n}{x}_n& =& b_1\\ a_{21}{x}_1& +& a_{22}{x}_2& +& \cdots & +& a_{2n}{x}_n& =& b_2\\ ⋮& & ⋮& & ⋮& & ⋮& & ⋮\\ a_{m1}{x}_1& +& a_{m2}{x}_2& +& \cdots & +& a_{mn}{x}_n& =& b_m\end{array}$$

The $x_i$ are called variables or unknowns, the $a_{ij}$ are coefficients ($A=(a_{ij})$ is the coefficient matrix), and $b$ is the right-hand side. A system with no solution is called inconsistent.

Set of solutions

$$L(A,b):=\{x\in {\mathbb{R}}^n:Ax=b\}$$

Homogenous system of equations

A linear system of equations with $A\in {\mathbb{R}}^{m\times n}$ and $x\in {\mathbb{R}}^n$ is called homogenous if the right-hand side is the zero vector $0:=0_{m1}$:

$$Ax=0$$

To a given linear system of equations $Ax=b$, we call $Ax=0$ the associated homogenous system of equations.
Every homogenous system of equations has at least one solution, the trivial solution $x=0$, i.e. $L(A,0)\supseteq \{0\}$.

How to find all solutions to $Ax=b$

Goal: Find the general solution — the complete set $L(A,b)$ of all vectors satisfying $Ax=b$.

We can decompose problem into two simpler parts:
1] Find one particular solution $x_p$ satisfying $A{x}_p=b$
2] Find the null space $L(A,0)$ — all solutions to the associated homogeneous system $Ax=0$

The general solution is $L(A,b)=x_p+L(A,0)$, i.e. every solution has the form $x_p+y$ where $y\in L(A,0)$.

---

Why this works:
Adding a null space vector to $x_p$ gives another solution: $A(x_p+y)=A{x}_p+Ay=b+0=b$
Every solution is captured: if $x^{\prime }$ also solves $Ax=b$, then $A(x^{\prime }-x_p)=b-b=0$, so $x^{\prime }-x_p\in L(A,0)$, meaning $x^{\prime }=x_p+(x^{\prime }-x_p)\in x_p+L(A,0)$

---

Consequence: The null space determines uniqueness.

Null space	Solutions to $Ax=b$
$L(A,0)=\{0\}$	Unique (if exists)
$L(A,0)⊋\{0\}$	Infinitely many (if any exist)

Solve $x_1+x_2=3$

Particular solution: $x_p=(3,0)$
Null space: $L(A,0)=\{(t,-t):t\in \mathbb{R}\}$ (solutions to $x_1+x_2=0$)
General solution: $(3,0)+(t,-t)=(3+t,-t)$ for any $t\in \mathbb{R}$

When does $Ax=b$ have a solution?

Bring the augmented matrix $(A|b)$ to row echelon form $(C|b^{\prime })$.

No solution iff there’s a zero row in $C$ with non-zero entry in $b^{\prime }$:

$$\left(\begin{array}{cccccc}0& 0& \cdots & 0& |& b_{\ell }^{\prime }\end{array}\right)\text{with }{b}_{\ell }^{\prime }\ne 0$$

This row says $0\cdot x_1+\cdots +0\cdot x_n=b_{\ell }^{\prime }$, a contradiction.

Otherwise, the system is solvable. Back-substitute from bottom to top: each pivot variable is determined by the variables to its right (which are either already solved or free).

Rank determines existence and uniqueness

For $Ax=b$ with $A\in {\mathbb{R}}^{m\times n}$, the rank determines:

Existence (is there at least one solution?):
$\text{rank}(A)=m$ (full row rank) guarantees a solution exists for every $b$.
If $\text{rank}(A)<m$, some rows become zero rows after elimination — solution exists only if the corresponding $b_{\ell }^{\prime }=0$.

Uniqueness (is there at most one solution?):
$\text{rank}(A)=n$ (full column rank) means every column has a pivot, so no free variables, so at most one solution.
If $\text{rank}(A)<n$, there are $n-\text{rank}(A)$ free variables, giving infinitely many solutions (if any exist).

---

Overdetermined ($m>n$, tall skinny $A$): more equations than unknowns.
At best rank $=n$, so if a solution exists it’s unique. But rank $<m$, so most $b$ have no exact solution.
Least squares finds $x$ minimizing $\Vert Ax-b{\Vert }_2$.

Underdetermined ($m<n$, short fat $A$): more unknowns than equations.
At best rank $=m$, so a solution exists for every $b$. But rank $<n$, so always infinitely many solutions.
Minimum norm finds the $x$ with smallest $\Vert x{\Vert }_2$ among solutions.

For square matrices: $\text{rank}(A)=n$ $⟺$ $A$ is invertible $⟺$ unique solution for every $b$.

Pivot columns vs free columns

When solving Ax = b:
Pivot columns correspond to basic variables, determined by back-substitution (solving from the bottom row upward, each pivot variable in terms of the ones already solved).
Non-pivot columns correspond to free variables (can be set to any value).

In the REF example above, columns 1, 2, 4 have pivots, column 3 doesn’t. So $x_3$ is free — the solution is parameterized by it.

Number of free variables $=n-\text{rank}(A)=\dim ($null space$)$.

Link to original

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$).