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$ to get the unique solution $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 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\in L(A,b)$, i.e. satisfying $A{x}_p=b$
2] Find the null space $L(A,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)$.

If the null space is trivial, $L(A,0)=\{0\}$, then $L(A,b)=x_p+\{0\}=\{x_p\}$, i.e. the solution is unique.
If the the null space is non-trivial, $L(A,0)⊋\{0\}$, then there are infinitely many solutions.
The above holds if at least one solution exists; if no solution exists, then $L(A,b)=\varnothing$.

Why does this work?

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

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)$ into row echelon form $(C|b^{\prime })$ (gaussian elimination).

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

Existence and uniqueness of solutions

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

Existence (is there at least one solution?):
If $\text{rank}(A)=m$ (full row rank), every row has a pivot, so a solution exists for every $b_{\ell }^{\prime }=0$.
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?):
If $\text{rank}(A)=n$ (full column rank), 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).
In other words: $\text{rank}(A)=n⟺L(A,0)=\{0\}$ (trivial null space).

---

Overdetermined ($m>n$, tall skinny $A$): more equations/constraints than unknowns.
At best rank $=n$, so if a solution exists it’s unique.
But the rank is $<m$, so most $b$ have no exact solution, i.e. $L(A,b)=\varnothing$.
We can approximate with Least squares, finding $x$ that minimize $\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

$\text{rank}(A)$ … constraints
$n-\text{rank}(A)$ … degrees of freedom (free variables)

Three equivalent forms / notations for solution sets

After back-substitution, each pivot variable is expressed in terms of free variables. Three ways to write the result:

Implicit: restate the constraints as set membership conditions. Doesn’t “solve” anything, just a different notation for the same set.

Parametric: substitute the free variables with parameters $t_1,\dots ,t_{n-k}$ and write out the solution tuple directly. Each element of the tuple is either a parameter or an expression in the parameters.

Vector: write as $x_p+t_1{v}_1+\cdots +t_{n-k}{v}_{n-k}$ where $x_p$ is a particular solution and $v_i\in L(A,0)$ are null space vectors. Shows the structure: particular solution + linear combination of null space directions.

---

Example: $x+y=2$ (rank 1, 2 variables, 1 free variable)

$\{(x,y)\in {\mathbb{R}}^2:x+y=2\}$ … implicit
$\{(2-t,t):t\in \mathbb{R}\}$ … parametric
$(2,0)+t\cdot (-1,1)$ … vector

Verify: pick $t=3$.
Parametric gives $(2-3,3)=(-1,3)$. Check: $-1+3=2$ ✓
Vector gives $(2,0)+3\cdot (-1,1)=(2-3,0+3)=(-1,3)$. Check: $-1+3=2$ ✓

The vector $(-1,1)$ is a null space vector ($Av=0$), so adding any multiple of it to a particular solution stays on the solution set.

---

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