3.2 Elementary Row Operations and Systems of Linear Equations
The substitution and Gaussian elimination methods for solving systems of linear equations work well for systems with a small number of variables. For systems with many equations and many variables, these methods become innefficient. In this section the Gaussian elimination method will be developed to a more efficient method for solving systems of linear equations with many variables or many equations.
Definition 3.2.1. The augmented matrix of the system of linear equations \begin {align*} 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\\ \vdots \\ a_{n1}x_1+a_{n2}x_2+\cdots +a_{mn}x_n&=b_m\\ \end {align*}
is the matrix \( \begin {pmatrix} a_{11}&a_{12}&\cdots&a _{1n}&&|&b_1\\ a_{21}&a_{22}&\cdots&a _{2n}&&|&b_2\\ .&&&.&&|&.\\ .&&&.&&|&.\\ .&&&.&&|&.\\ a_{m1}&a_{m2}&\cdots&a _{mn}&&|&b_{mn}\\ \end {pmatrix} =\Big (A/b\Big )\) where \(A\) is the coefficient matrix
\( A= \begin {pmatrix} a_{11}&a_{12}&\cdots&a _{1n}\\ a_{21}&a_{22}&\cdots&a _{2n}\\ \vdots& \vdots& \ddots& \vdots \\ a_{m1}&a_{m2}&\cdots&a _{mn}\\ \end {pmatrix} \hspace {0.3cm}\) and \(\hspace {0.3cm} b= \begin {pmatrix} b_1\\b_2\\.\\.\\.\\b_m\\ \end {pmatrix} \)
Example 3.2.2. The system of linear equations. \begin {align*} x+2y+3z&=4\\2x+3y+4z&=5\\3x+4y+5y&=6\\ \end {align*}
has coefficient matrix \( \begin {pmatrix} 1&2&3\\2&3&4\\3&4&5\\ \end {pmatrix} \) and augmented matrix \( \begin {pmatrix} 1&2&3&&|&4\\2&3&4&&|&5\\3&4&5&&|&6\\ \end {pmatrix} \)
The following terminology is used for systems of linear equations
- 1.
- An \(n\)-tuple \((x_1,x_2,\dots ,x_n)\) which satisfies each of the \(m\) equations in the system \[\sum ^n_{j=1}a_{ij}x_j=b_i\qquad (i=1,2,\dots ,m)\] is called a solution of the system.
- 2.
- Two systems of linear equations are equivalent if every solution of one system is a solution of the other and vice versa — that is, if they have the same solution set.
- 3.
- A system with at least one solution is called consistent. An inconsistent system is one with no solution.
- 1.
- If \((A'|b')=(a'_{ij}|b'_i)\) is the \(m\) by \(n+1\) matrix obtained from \((A|b)\) by a single elementary row operation, then the systems \[\sum ^n_{j=1}a'_{ij}x_j=b'_i \qquad \text {and}\qquad \sum ^n_{j=1}a_{ij}x_j=b_i \qquad (i=1,2,\dots ,m)\] are equivalent.
- 2.
- If \((R|s)\) is the reduced echelon matrix of the augmented matrix \((A|b)\), then the systems \(\sum ^n_{j=1}r_{ij}x_j=s_i\) and \(\sum ^n_{j=1}a_{ij}x_j=b_i\) \((i=1,\dots ,m)\) are equivalent.
- 3.
- A system of linear equations is consistent if and only if the reduced echelon matrix of its augmented matrix has no leading element in its last column.
Proof.
- 1.
- Read each row of the augmented matrix as an equation. The three elementary row
operations then say, respectively: list two of the equations in the other order; multiply one
equation through by a non-zero constant \(k\); add \(k\) times one equation to another.
None of these changes the solution set. If \((x_1,\dots ,x_n)\) satisfies all the original equations then it satisfies each of the new ones, since each new equation is a consequence of the old ones. Conversely — and this is the part that needs the restriction \(k\neq 0\) — each operation can be undone by an operation of the same kind (Theorem 2.6.3(2)), so by the same argument every solution of the new system is a solution of the old. Hence the two solution sets contain each other and the systems are equivalent.
- 2.
- \((R|s)\) is obtained from \((A|b)\) by a finite sequence of elementary row operations. Applying part (1) once for each operation, the solution set is unchanged at every step, so the first and last systems are equivalent.
- 3.
- Suppose the reduced echelon matrix has a leading element in its last column. That leading
element is a \(1\) in some row \(i\), and being a leading element it is the first non-zero entry of its
row, so every \(r_{ij}\) is zero. Row \(i\) therefore reads
\[0\cdot x_1+0\cdot x_2+\cdots +0\cdot x_n=1,\]
which no \(n\)-tuple satisfies. By part (2) the original system has the same solution set, so it
too is inconsistent.
Conversely, suppose there is no leading element in the last column. Then every leading element sits in one of the first \(n\) columns. Call the variables belonging to those columns leading and the rest free. Assign the value \(0\) to every free variable; each equation containing a leading element then determines its leading variable outright, and any row with no leading element is the equation \(0=0\), which is satisfied. This produces a solution, so the system is consistent.
Remark. Part (3) is what makes row reduction a decision procedure rather than merely a simplification: after reducing, consistency can be read off by looking at one column, and the proof of the converse also shows how to write down a solution when one exists.
Solution. \begin {align*} & \begin {pmatrix} 3&-1&4&|&-2\\-1&1&2&|&1\\6&3&-1&|&4\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\rightarrow r_1+3r_2\\ \longrightarrow \\ r_3\rightarrow r_3+6r_2\\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 0&2&10&|&1\\-1&1&2&|&1\\0&9&11&|&10\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\leftrightarrow r_2\\ \longrightarrow \\ \end {matrix}\\\\ & \begin {pmatrix} -1&1&2&|&1\\0&2&10&|&1\\0&9&11&|&10\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_3\rightarrow r_3-r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} -1&1&2&|&1\\0&2&10&|&1\\0&7&1&|&9\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_2\rightarrow \frac {1}{2}r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} -1&1&2&|&1\\0&1&5&|&1/2\\0&7&1&|&9\\ \end {pmatrix}\\\\ & \begin {matrix} r_3\rightarrow r_3-7r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} -1&1&2&|&1\\0&1&5&|&1/2\\0&0&-34&|&11/2\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\rightarrow r_1-r_2\\ \longrightarrow \\ r_3\rightarrow -\frac {1}{34}r_3\\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} -1&0&-3&|&1/2\\0&1&5&|&1/2\\0&0&1&|&-11/68\\ \end {pmatrix}\\ \end {align*}
\[ \begin {matrix} r_1\rightarrow r_1+3r_3\\ \longrightarrow \\ r_2\rightarrow r_2-5r_3\\ \end {matrix} \hspace {0.4cm} \begin {pmatrix} -1&0&0&|&1/68\\0&1&0&|&-21/68\\0&0&1&|&-11/68 \end {pmatrix} \]
\[\text {Therefore,}\hspace {0.4cm}(x,y,z)=\Big (\frac {1}{68},-\frac {21}{68},-\frac {11}{68}\Big )\hspace {0.4cm}\text {is the solution.}\]
For some systems of linear equations there is a parameter whose value determines the nature of the solution of the system. This is illustrated in the following example.
Example 3.2.5. Find the value of \(t\) for which the system \begin {align*} x+y+tz&=1\\x+ty+z&=1\\tx+y+z&=-2 \end {align*}
has (i). no solution (ii). a unique solution (iii). infinitely many solutions.
Solution. \begin {align*} & \begin {pmatrix} 1&1&t&|&1\\1&t&1&|&1\\t&1&1&|&-2\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\leftrightarrow r_3\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t&1&1&|&-2\\1&t&1&|&1\\1&1&t&|&1\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_3\rightarrow r_3-r_1\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t&1&1&|&-2\\1&t&1&|&1\\1-t&0&t-1&|&3\\ \end {pmatrix}\\\\ & \begin {matrix} r_2\rightarrow r_2-r_1\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t&1&1&|&-2\\1-t&t-1&0&|&3\\1-t&0&t-1&|&3\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_2\rightarrow \frac {1}{1-t}r_2\\ \longrightarrow \\ r_3\rightarrow \frac {1}{1-t}r_3\\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t&1&1&|&-2\\1&-1&0&|&3/1-t\\1&0&-1&|&3/1-t\\ \end {pmatrix}\\\\ & \begin {matrix} r_3\rightarrow r_3-r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t&1&1&|&-2\\1&-1&0&|&3/1-t\\0&1&-1&|&0\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\rightarrow r_1+r_3\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t&2&0&|&-2\\1&-1&0&|&3/1-t\\0&1&-1&|&0\\ \end {pmatrix}\\\\ & \begin {matrix} r_1\rightarrow r_1+2r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} t+2&0&0&|&\frac {2t+4}{1-t}\\\\ 1&-1&0&|&\frac {3}{1-t}\\\\0&1&-1&|&0\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_1\rightarrow (1/t+2)r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&|&\frac {2t+4}{(t+2)(1-t)}\\\\1&-1&0&|&\frac {3}{1-t}\\\\ 0&1&-1&|&0\\ \end {pmatrix}\\\\ & \begin {matrix} r_2\rightarrow r_2-r_1\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&|&\frac {2}{(1-t)}\\0&-1&0&|&\frac {1}{1-t}\\0&1&-1&|&0\\ \end {pmatrix} \hspace {0.3cm} \begin {matrix} r_3\rightarrow r_3+r_2\\ \longrightarrow \\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1&0&0&|&\frac {2}{1-t}\\0&-1&0&|&\frac {1}{1-t}\\0&0&-1&|&\frac {1}{1-t}\\ \end {pmatrix}\\\\ & \begin {matrix} r_1\rightarrow (1-t)r_1\\ \longrightarrow \\ r_2\rightarrow (1-t)r_2\\ r_3\rightarrow (1-t)r_3\\ \end {matrix} \hspace {0.3cm} \begin {pmatrix} 1-t&0&0&|&2\\0&1-t&0&|&1\\0&0&t-1&|&1\\ \end {pmatrix} \end {align*}
(i). \(t-1=0,\hspace {0.4cm} t=1\hspace {1cm}\) (ii). \(t\neq 0\hspace {1cm}\) (iii). No values of \(t\) satisfy this requirement.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.