Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: N/A

Properties: N/A
Sufficiencies: N/A
Questions: N/A

To find the solution set for a linear system of equations, we

1. Begin with our original equation

2. Reduce the coefficient matrix $A$ into 17.3 Reduced Row Echelon Form $U=\text{RREF}(A)$ by multiplying $A$ on the left by matrix $E$ yielding

where $E=E_t\cdot E_{t-1}\cdots E_2\cdot E_1$ is a product of elementary matrices $E_1,E_2,\dots ,E_t$ and each elementary matrix $E_J$ is either a 9.8 Shear Matrix, 9.10 Transposition Matrix, or a 9.9 Dilation Matrix for $j=1,2,\dots ,t$.
3. Simultaneously multiply the same sequence of elementary matrices to the right-hand side to produce the new updated system

4. Decide if $\overrightarrow{y}\in \text{Span}\{U(:,k){\}}_{k=1}^n$. In other words, verify if $\overrightarrow{y}$ can be written as a linear combination of the columns of $U$.

• If $\overrightarrow{y}\notin \text{Span}\{U(:,k){\}}_{k=1}^n$, then no exact solution exists to our original linear-system problem $A\cdot \overrightarrow{x}=\overrightarrow{b}$.
• If $\overrightarrow{y}\in \text{Span}\{U(:,k){\}}_{k=1}^n$, then find the general structure for any solution $\overrightarrow{x}$ in the form

where ${\overrightarrow{x}}^{\ast }$ is a particular solution to $U\cdot \overrightarrow{x}=\overrightarrow{y}$ and $\overrightarrow{z}$ is a general solution to the 18.3 Homogenous Linear System $U\cdot \overrightarrow{x}=0$.

This algorithm produces every possible solution to 17.1 The General Linear-Systems Problem.