System of Linear Equations

Standard Form of Linear Equation

$a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n=b$

• $a_1,...$ are constants, called coefficients
• $b$ is called the constant
• $x_1,\dots$ are called variables
• The linear equation is homogeneous if $b=0$

Linear System

This is a linear system with m equations and n variables in standard form: $\{\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 linear system is homogeneous if all $b$ are 0
• $x_1=c_1,\dots ,x_n=c_n$ is a solution to the linear system if all equations are satisfied after making the substitution
• The general solution to a linear system captures all possible solutions
• A linear system is inconsistent if it has zero solutions, it is consistent if it has at least one solution

Homogeneous Linear Systems

• A homogeneous linear system $Ax=0$ is always consistant, since the zero vector is a solution, $A0=0$ (trivial solution)
• A homogeneous linear system has infinitely many solutions if and only if it has a nontrivial solution: if $Ax=0$, then $A(xy)=y(Ax)=y0=0$ ($xy$ is also a solution for any $y\in \mathbb{R}$)
• If the trivial solution is a solution to a linear system, it must be a homogeneous system
• Let $v$ be a particular solution to $Ax=b$, and $u$ be a solution to its homogeneous counterpart $Ax=0$, then $v+u$ is also a solution to $Ax=b$
• If $v_1$ and $v_2$ are solutions to the linear system $Ax=b$ , then $v_1-v_2$ is a solution to its homogeneous counterpart $Ax=0$

Matrix Equation

\begin{gather*} {\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} ={\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}},\quad \text{or} \;{\textbf{A}}\textbf{x}={\textbf{b}} \end{gather*} Where $A$ is called the coefficient matrix, $\text{x}$ is the variable vector and $\text{b}$ is the constant vector

Vector Equation

\begin{gather*} x_1{\begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{pmatrix}} +x_2{\begin{pmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{pmatrix}}+\cdots +x_n{\begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{pmatrix}} ={\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}}, \quad x_1{\textbf{a}_1}+x_2{\textbf{a}_2}+\cdots+x_n{\textbf{a}_n}={\textbf{b}} \end{gather*} Where ${\text{a}}_i$ is called the coefficient vector for variable $x_i$

Augmented Matrix Representation

$\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array}\right)$

• Coefficient Matrix: The matrix on the left of the vertical bar
• Zero Row: a row where all entries are 0
• Leading Entry: the first nonzero entry of the row from the left

Row Echelon Form (REF)

• The leading entries are further to the right as we move down the rows
• If a zero rows exist, they are at the bottom of the matrix \left(\begin{array}{cccccccc\|c} \ast&&&&&&&&\ast\\ 0&\cdots&0&\ast&&&&&\ast\\ 0&\cdots&0&0&\cdots&0&\ast&&\ast\\ \vdots&&&&&&&\vdots&\vdots\\ 0&\cdots&&&&&\cdots&0&0\\ \end{array}\right)
• A pivot column is a column containing a leading entry, otherwise it is a non-pivot column

Reduced Row Echelon Form (RREF)

• A matrix in REF, and:
• The leading entries are all 1
• In each pivot column, all entries except the leading entry is 0 \left(\begin{array}{cccccccccc\|c} 0&\cdots&1&     &\ast & 0&&\ast&0&\ast&\ast\\ 0&\cdots&0&\cdots&0&1&&\ast&0&\ast&\ast\\ 0&\cdots&0&\cdots&0&0&\cdots&0&1&\ast&\ast\\ 0&\cdots&0&&&0&&&0&0&0\\ \vdots&&&&&\vdots&&&\vdots&\vdots&\vdots\\ 0&\cdots&0&\cdots&&0&&\cdots&0&0&0\\ \end{array}\right)

Number of solutions from REF

No solution: a row of zero in the coefficient matrix, with a non-zero number on the right (i.e. the rightmost column is a pivot column) $\left(\begin{array}{ccccc}\ast & \ast & \cdots & \ast & \ast \\ ⋮& ⋮& \ddots & ⋮& \\ 0& 0& \cdots & 0& a\ne 0\end{array}\right)$

Unique solution: all columns of the coefficient matrix are pivot columns (not possible if there are more variables than equations) $\left(\begin{array}{llllc}\ne 0& \ast & \cdots & \ast & \ast \\ 0& \ne 0& \cdots & \ast & \ast \\ ⋮& ⋮& \ddots & ⋮& \\ 0& 0& \cdots & \ne 0& \ast \\ ⋮& ⋮& \ddots & ⋮& \\ 0& 0& \cdots & 0& 0\end{array}\right)$

Infinitely many solutions: There is a non-pivot column in the coefficient matrix $\left(\begin{array}{llllllllc}\ne 0& \cdots & \ast & \ast & & \ast & \ast & \ast & \ast \\ 0& \cdots & 0& \ne 0& & \ast & \ast & \ast & \ast \\ 0& \cdots & 0& 0& \cdots & 0& \ne 0& \ast & \ast \\ 0& & & 0& & & 0& 0& 0\\ ⋮& & & ⋮& & & ⋮& ⋮& ⋮\end{array}\right)$

Gaussian Elimination

1. Locate the leftmost column that does not consist entirely of zeros
2. Interchange the top row with another row, if necessary, to bring a nonzero entry to the top of the column found in 1
3. For each row below the top row, add a suitable multiple of the top row to it so that the entry below the leading entry of the top row becomes zero
4. Cover the top row in the augmented matrix and begin again with step 1 to the remaining rows. Repeat until the entire matrix is in REF

Gauss Jordan Elimination

Continue with these steps after gaussian elimination to obtain a matrix in RREF (to solve equation with multiple solutions) 5. Multiply a suitable constant to each row so that all the leading entries become 1 6. Beginning with the last nonzero row, and working upward, add suitable multiples of each row to the rows above to introduce zeros above the leading entries

Solving linear systems with unknowns in the coefficients and constants

Example: $\left(\begin{array}{cccc}1& a& 2& 0\\ 1& 0& 1& 1\\ 1& 0& a& 2\end{array}\right)$

1. Perform gaussian elimination
   • $\left(\begin{array}{cccc}1& a& 2& 0\\ 0& -a& -1& 1\\ 0& 0& a-1& 1\end{array}\right)$
2. To continue with gauss jordan elimination, consider the cases where the leading entries that contain unknowns are zero
   • a = 0
   • a = 1
   • otherwise
3. Substitute these cases into the system, to check if the system is consistent for each case
   • When a = 1, the rightmost column is a pivot column, and the system is inconsistent
   • When a = 0, $\left(\begin{array}{cccc}1& 0& 2& 0\\ 0& 0& -1& 1\\ 0& 0& -1& 1\end{array}\right)$ , which can be reduced to $\left(\begin{array}{cccc}1& 0& 0& 2\\ 0& 0& -1& 1\\ 0& 0& 0& 0\end{array}\right)$ , and the general solution found
   • Otherwise, the system will have a unique solution, and back substitution or gauss-jordan elimination can be performed to determine the solution

Constructing a linear system from general solution

E.g. Find a linear system with 3 equations such that $x_1=1-2s+t,x_2=s,x_3=t,x_4=0,s,t\in \mathbb{R}$ is the general solution

1. Substitute the variables for s and t into the first equation to remove them $x_1=1-2x_2+x_3$
2. Include the equation $x_4=0$ , to get a linear system with 2 equations
3. To get the 3rd equation, we don’t want to add any more information, so we can get it by taking multiples of the first 2 equations, or adding the first 2 equations

Multiple Linear Systems with Same Coefficient Matrix

$p$ linear systems with the same coefficient matrix $\mathbf{A}=(a_{ij}{)}_{m\times n}$ for $k=1,\cdots ,p$ \begin{gather*} \left\{\begin{array}{rcrcrcrcr} {a_{11}}x_1 &+& {a_{12}}x_2 &+& \cdots &+& {a_{1n}}x_n &=& {b_{1k}} \\ {a_{21}}x_1 &+& {a_{22}}x_2 &+& \cdots &+& {a_{2n}}x_n &=& {b_{2k}} \\ && && && &\vdots& \\ {a_{m1}}x_1 &+& {a_{m2}}x_2 &+& \cdots &+& {a_{mn}}x_n &=& {b_{mk}} \\ \end{array}\right. \end{gather*} Can be written as a combined augmented matrix: \begin{gather*} \left(\begin{array}{cccc|c|c|c|c} {a_{11}} & {a_{12}} & {\cdots} & {a_{1n}} & {b_{11}} & {b_{12}} & & {b_{1p}} \\ {a_{21}} & {a_{22}} & {\cdots} & {a_{2n}} & {b_{21}} & {b_{22}} & & {b_{2p}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {a_{m1}} & {a_{m2}} & {\cdots} & {a_{mn}} & {b_{m1}} & {b_{m2}} & & {b_{mp}} \end{array}\right) \end{gather*} And all systems can be solved at once, using the same methods as above