In Chapter 1 the question whether two lines or two planes intersect or do not intersect was touched upon. In the case of two planes the question can be resolved by finding equations for the planes and checking whether there are points that simultaneously satisfy these two equations. We can write this in the form \[ \left\ < \begin
A linear equation is an equation that can be written in the form \[ a_1x_1 + a_2x_2 + \ldots + a_nx_n = k. \nonumber\] The numbers \(a_1,a_2,\ldots,a_n\) are called the coefficients and the variables \(x_1,x_2, \ldots, x_n\) the unknowns. The term \(k\) is referred to as the constant term.
The equation \[ 3x_1 + 5x_2 = 4x_3 - 2x_4 + 10 \nonumber\] is a linear equation, as it can be rewritten as \[ 3x_1 + 5x_2 - 4x_3 + 2x_4 = 10. \nonumber\] By contrast, the equation \[ x_1 + 2x_1x_2 - 3x_2 = 5 \nonumber\] is not linear because of the nonlinear term \(2x_1x_2\).
A set of one or more linear equations is called a system of linear equations (or linear system, for short). In the case of \(m\) linear equations in the variables \(x_1,x_2,\ldots, x_n\) we speak of a system of \(m\) equations in \(n\) unknowns. The most general system then looks as follows: \[ \left\ a_x_1\! & \!+\!&\!a_x_2\! & \!+\!&\! \ldots\! & \!+\!&\!a_x_n \! & \!=\!&\! b_1 \\ a_x_1 \quad \! & \!+\!&\!a_x_2\! & \!+\!&\!\ldots\! & \!+\!&\!a_x_n \! & \!=\!&\! b_2 \\ \vdots \! & \! \!&\! \vdots\! & \! \!&\!\cdots\! & \! \!&\! \vdots \! & \! \!&\! \vdots \\ a_x_1 \quad \! & \!+\!&\!a_x_2\! & \!+\!&\! \ldots\! & \!+\!&\!a_x_n \! & \!=\!&\! b_m \\ \end \right. \nonumber\]
Of course, if we have equations we want to solve them. Here is what we mean by that in a precise way.
A solution of a linear system is an ordered list of \(n\) values \((c_1, c_2, \ldots, c_n)\), or, depending on the context, a vector \( \left[\beginc_1 \\ c_2 \\ \vdots \\ c_n \end\right]\) such that substitution of \[ x_1 = c_1, x_2 = c_2, \ldots, x_n = c_n \nonumber\] into each of the equations yields a true identity. The solution set or general solution of a system is the set of all solutions.
Two solutions for the system of equations \[ \left\ 2x_1&+&3x_2&+& x_3&=&0\\ 3x_1&+& x_2&+& 5x_3&=&7\\ \end\right. \nonumber\] are given by \[ (1, -1, 1) \quad \text \quad (5, -3, -1) \nonumber\] or, equivalently, by \[ \left[\begin 1\\-1\\1 \end\right] \quad \text \quad \left[\begin 5\\-3\\-1 \end\right]. \nonumber\] For instance, substitution of the second proposed solution yields \[ \left\ 2\cdot 5&+&3\cdot(-3)&+& (-1)&=&0\\ 3\cdot 5&+& (-3)&+& 5\cdot(-1)&=&7.\\ \end\right. \nonumber\] which are both true identities. The solution set may be empty, as in the following example
The system \[ \left\ 2x_1&+&3x_2&+& x_3&=&5\\ 3x_1&+& x_2&+& 4x_3&=&7\\ 4x_1&+& 6x_2&+& 2x_3&=&8\\ \end\right. \nonumber\] has no solutions because the first equation conflicts with the third equation: if \((c_1,c_2,c_3)\) is a triple that satisfies \[ 2c_1 + 3c_2 + c_3 = 5 \nonumber\] then automatically \[ 4c_1 + 6c_2 + 2c_3 = 2(2c_1 + 3c_2 + c_3) = 10 \neq 8 \nonumber\] so \((c_1,c_2,c_3)\) cannot also be a solution of the third equation.
If the solution set of a system is empty, a system is said to be inconsistent. This concept and its opposite are sufficiently important to be properly defined.
A system of linear equations is consistent if it has at least one solution. Otherwise it is called inconsistent.
The simplest inconsistent system may well be the system with the one equation \[ 0x_1 + 0x_2 + \ldots + 0x_n = 1 \nonumber\] As we will see later, this conflicting equation in a way pops up in any inconsistent system.
A consistent system of one equation in \(n\) unknowns is easily solved. Any unknown with a nonzero coefficient can be expressed in the other unknowns, and the other unknowns can be chosen freely. In words this may look more complicated than it is, as the following example illustrates.
Find all solutions of the equation in the variables \(x_1,\ldots,x_5\). \[ x_1 + 4x_2 + 5x_3 - x_5 = 7 \nonumber\] One way to denote the set of solutions: \[ \left\ x_1 = 7 - 4x_2 -5x_3 + x_5 \\ x_2, x_3, x_4 \quad \text x_5 \quad \text < are free>\end \right. \nonumber\] By this we mean: if we assign arbitrary values to the variables \(x_2, x_3, x_4\) and \(x_5\), say \[ x_2 = c_1, x_3 = c_2, x_4 = c_3, x_5 = c_4, \nonumber\] and put \[ x_1 = 7 - 4c_1 -5c_2 + c_4 \nonumber\] then \[ x_1 + 4x_2 + 5x_3 - x_5 = (7 - 4c_1 -5c_2 + c_4) + 4c_1 +5c_2 - c_4 = 7 \nonumber\] so \[ (7 - 4c_1 -5c_2 + c_4, c_1, c_2, c_3, c_4) \nonumber\] is indeed a solution of the given equation. However, this is not the only way to write down the general solution: in this example almost any set of four variables can act as free variables. The descriptions \[ \left\ x_5 = -7 +x_1 +4x_2 +5x_3 \\ x_1, x_2, x_3 \quad \text x_4 \quad \text < are free>\end \right. \nonumber\] and \[ \left\ x_2 = \frac74 - \frac14x_1 -\frac54x_3+\frac14x_5 \\ x_1, x_3, x_4 \quad \text x_5 \quad \text < are free>\end \right. \nonumber\] are just as good. You might want to avoid fractions though. The only set of four variables that cannot act as free variables is the set \(\\).
The idea behind all methods to find the general solution of a linear system: rewrite the system in simpler forms, basically by eliminating variables from equations. We illustrate this by an example.
We solve the system \[ \left\ 2x_1&-&5x_2&=&-2\\ 4x_1&-&7x_2&=& 2 \end\right. \nonumber\] First method: from the first equation it follows that \[ 2x_1 = -2 + 5x_2 \quad \iff x_1 = -1 + \tfrac52 x_2 \nonumber\] Substitution of the expression for \(x_1\) into the second equation yields \[ 4(-1 + \tfrac52 x_2) - 7x_2 = 2, \nonumber\] an equation with \(x_2\) as single unknown (the jargon: \(x_1\) has been eliminated), and then \[ -4 +10x_2 - 7x_2 = 2 \quad \iff 3x_2 = 6 \quad \iff x_2 = 2, \nonumber\] and finally \[ x_1 = -1 + \tfrac52 x_2 = -1 + \tfrac52\cdot2 = 4. \nonumber\] Thus we have found that there is a unique solution: \[ \left\ x_1 = 4 \\ x_2 = 2 \end \right. \nonumber\] There is nothing wrong with this method, but with more than two equations it has the tendency to become messy. Second method: take clever combinations of the equations to eliminate variables. For the above example we may for instance subtract the first equation twice from the second. Think a moment why this is okay. It is the crucial step in the elimination method we will explain in the next subsection. \[ \left\ 2x_1&-&5x_2&=&-2\\ 4x_1&-&7x_2&=& 2 \end\right. \quad\Rightarrow\quad \left\ 2x_1&-&5x_2&=&-2\\ & &3x_2&=& 6 \end\right. \nonumber\] Again we see that \(x_2 = 2\), in fact the equation \(3x_2 = 6\) is the same equation that we arrived at with the substitution method above, and substitution of this into the first equation again yields \[ 2x_1 - 5\cdot2 = -2 \quad \quad \iff \quad x_1 = 4. \nonumber\]
\[ \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ 3x_1 &+& 7x_2 &-& 2x_3 &=& 8 \\ 2x_1 &+& 10x_2 &-& 9x_2 &=& 4 \end \right. \nonumber\] We can simplify this system by successively eliminating unknowns from equations by combining equations in a clever way. We can for instance eliminate the variable \(x_1\) from the second equation by subtracting the first equation three times from the second equation, and likewise we can subtract the first equation twice from the third equation: \[ \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ 3x_1 &+& 7x_2 &-& 2x_3 &=& 8 \\ 2x_1 &+& 10x_2 &-& 9x_2 &=& 4 \end \right. \quad \Longrightarrow \quad \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ & & -2x_2 &+& 4x_3 &=& -4 \\ & & 4x_2 &-& 5x_2 &=& -4 \end \right. \nonumber\] With the arrow we express that if we have a solution of the system on the left, this will also be a solution of the system on the right. Now, why is this okay, why is it allowed to 'subtract equations'? Let's introduce the shorthand notation \[ L_1 = x_1 +3x_2 - 2x_3, \quad L_2 = 3x_1 +7 x_2 -2x_3. \nonumber\] for the expressions on the left sides of the first two equations. Then the given equations are: \[ L_1 = 4, \quad L_2 = 8. \nonumber\] It then follows that we must have \[ L_2 - 3L_1 = 8 - 3\cdot4 = -4 \nonumber\] which yields \[ 3x_1 +7 x_2 -2x_3 - 3(x_1 +3x_2 - 2x_3) = -4 \quad \iff -2 x_2 +4x_3 = -4. \nonumber\] The last equation is exactly the second equation of the second system. The crucial thing to note is that these operations can be undone: if in the second system the first equation is added three times to the second equation, and added twice to the third equation we end up with the original system. So in fact we have \[ \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ & & -2x_2 &+& 4x_3 &=& -4 \\ & & 4x_2 &-& 5x_2 &=& -4 \end \right. \quad \Longrightarrow \quad \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ 3x_1 &+& 7x_2 &-& 2x_3 &=& 8 \\ 2x_1 &+& 10x_2 &-& 9x_2 &=& 4 \end \right. \nonumber\] The implication works two ways, which we can write as follows: \[ \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ 3x_1 &+& 7x_2 &-& 2x_3 &=& 8 \\ 2x_1 &+& 10x_2 &-& 9x_2 &=& 4 \end \right. \quad \Longleftrightarrow \quad \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ & & -2x_2 &+& 4x_3 &=& -4 \\ & & 4x_2 &-& 5x_2 &=& -4 \end \right. \nonumber\] So any triple of values \((c_1,c_2,c_3)\) that satisfies the first system satisfies the second system and vice versa. Systems that have the same set of solutions are called equivalent.
By the same line of reasoning as in the above example we can deduce that adding an arbitrary multiple of any equation to another equation does not change the solution set of the system. Of course if we multiply an equation with some nonzero constant, the solution set also remains invariant. This operation is called scaling. For the system at hand we could, as a next step, scale the second equation with a factor \(-\frac12\). The following proposition summarizes the suitable operations to adapt a system of equations.
The correctness of the first operation is illustrated in Example \(\PageIndex\). One example is by far not a proof, but the explanation given there can be generalized/formalized. The other two statements are rather obvious.
Let's take up the example at the point where we left it and work our way to its solution. Also let us introduce a notation that makes it easier for the reader to see what's going on. And also for yourself, in case you look back at your computations later, or if you want to check your computations. The '\(E\)' stands for: 'Equation'. We scale the second equation with a factor \(-\frac12\) \[ \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 & \quad[E_1]\\ & & -2x_2 &+& 4x_3 &=& -4 & \quad[-\frac12E_2]\\ & & 4x_2 &-& 5x_2 &=& -4 &\quad[E_3] \end \right. \quad \Longleftrightarrow \quad \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ & & x_2 &-& 2x_3 &=& 2 \\ & & 4x_2 &-& 5x_2 &=& -4 \end \right. \nonumber\] and then subtract the second equation four times from the third: \[ \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 & \quad[E_1]\\ & & x_2 &-& 2x_3 &=& 2 & \quad[E_2]\\ & & 4x_2 &-& 5x_2 &=& -4 & \quad[E_3-4 E_2] \end \right. \quad \Longleftrightarrow \quad \left\ x_1 &+& 3x_2 &-& 2x_3 &=& 4 \\ & & x_2 &-& 2x_3 &=& 2 \\ & & & & 3x_2 &=& -12 \end \right. \nonumber\] From the third equation it follows that \[ x_3 = \dfrac = -4, \nonumber\] and then we can work upwards to find that \[ x_2 = 2 + 2x_3 = 2+2\cdot(-4) = -6 \nonumber\] and finally from the first equation it follows that \[ x_1 = 4 - 3x_2 + 2x_3 = 4 - 3\cdot(-6) + 2\cdot(-4) = 14. \nonumber\] Conclusion: the system has the unique solution \[ (x_1,x_2,x_3) = (14,-6,-4). \nonumber\] Problem solved. The last few steps, working our way up from the last equation to successively find \(x_3\), \(x_2\), \(x_1\), is sometimes referred to as back substitution.
Consider the following system of equations \[ \left\ x_1 &+& 4x_2 &-& 5x_3 &=& 4 \\ 2x_1 &+& 7x_2 &-& 2x_3 &=& 9 \\ x_1 &+& 3x_2 &+& 3x_3 &=& 6 \end \right. \nonumber\] Making use of the notation introduced in the previous example we simplify the system: \[ \left\ x_1 &+& 4x_2 &-& 5x_3 &=& 4 &\quad [E_1]\\ 2x_1 &+& 7x_2 &-& 2x_3 &=& 9 &\quad [E_2-2E_1]\\ x_1 &+& 3x_2 &+& 3x_3 &=& 6 &\quad [E_3-E_1] \end \right. \nonumber\] \[ \iff \left\ x_1 &+& 4x_2 &-& 5x_3 &=& 4 &\quad [E_1] \\ & & -x_2 &+& 8x_3 &=& 1 &\quad [E_2]\\ & & -x_2 &+& 8x_3 &=& 2 &\quad [E_3-E_2] \end \right. \nonumber\] \[ \iff \left\ x_1 &+& 4x_2 &-& 5x_3 &=& 4 \\ & & -x_2 &+& 8x_3 &=& 1 \\ & & & & 0 &=& 1 \end \right. \nonumber\] and from the last equation it immediately follows that there are no solutions, in other words: the system is inconsistent.
Let's look at one more example. Here we will see how to find the solution that contains a free variable.
We find the general solution of the linear system \[ \left\ 4x_1&-&2x_2&-& 3x_3&+&7x_4&=&5\\ 3x_1&-&x_2&-& 2x_3&+&5x_4&=&7\\ x_1&-&x_2&-& 2x_3&+&3x_4&=&3. \end\right. \nonumber\] Using the shorthand notation just introduced the system can be simplified as follows: we first interchange the first and the third equation to have a first equation where the coefficient of \(x_1\) is equal to 1. That way we avoid fractions in at least the first elimination step. \[ \begin & \left\ 4x_1&-&2x_2&-& 3x_3&+&7x_4&=&5&\quad[E_3]\\ 3x_1&-&x_2&-& 2x_3&+&5x_4&=&7&\quad[E_2]\\ x_1&-&x_2&-& 2x_3&+&3x_4&=&3&\quad[E_1] \end\right.\\ \iff & \left\ x_1&-&x_2&-& 2x_3&+&3x_4&=&3&\quad[E_1]\\ 3x_1&-&x_2&-& 2x_3&+&5x_4&=&7&\quad[E_2-3E_1]\\ 4x_1&-&2x_2&-& 3x_3&+&7x_4&=&5&\quad[E_3-4E_1] \end\right. \\ \iff & \left\ x_1&-&x_2&-& 2x_3&+&3x_4&=&3&\quad[E_1]\\ &&2x_2&+& 4x_3&-&4x_4&=&-2&\quad[\frac12E_2]\\ &&2x_2&+& 5x_3&-&5x_4&=&-7&\quad[E_3] \end\right. \\ \iff & \left\ x_1&-&x_2&-& 2x_3&+&3x_4&=&3&\quad[E_1]\\ &&x_2&+& 2x_3&-&2x_4&=&-1&\quad[E_2]\\ &&2x_2&+& 5x_3&-&5x_4&=&-7&\quad[E_3-2E_2] \end\right. \\ \iff & \left\ x_1&-&x_2&-& 2x_3&+&3x_4&=&3\\ &&x_2&+& 2x_3&-&2x_4&=&-1\\ && && x_3&-&x_4&=&-5. \end\right. \end \nonumber\] Again we can find the solution by back-substitution: the third equation can be rewritten as \[ x_3 = -5 + x_4. \nonumber\] Via the second equation we can express \(x_2\) as a function of \(x_4\) \[ x_2 + 2(-5+x_4) -2x_4 = -1 \quad \quad \iff \quad x_2 = 9 \nonumber\] And then it follows from the first equation that \[ x_1 - 9 - 2\cdot(-5+x_4) + 3x_4 = 3 \quad \quad \iff \quad x_1 = 2 -x_4 \nonumber\] So the solution can be written as \[ \left\ x_1 = 2 -x_4 \\ x_2 = 9 \\ x_3 = -5 + x_4\\ x_4 \quad \text < is free>\end\right. \nonumber\] Note that the row swap that we used as a first step is not really necessary. However, this way we avoided having to work with non-integer multiples of rows.
Let's summarize the elimination method in a
In theory the method works for any linear system, however large, though with pen and paper it soon becomes cumbersome. In the next subsection we will use an appropriate representation of a linear system to solve it in a more efficient way. And we will also see how the procedure of back-substitution can be incorporated in the elimination process.
We will introduce a convenient shorthand notation for linear systems. This notation contains the essentials of the system in a structured way. Before that, we define the concept of one of the most basic building blocks in linear algebra: the matrix.
An \(m \times n\) matrix \(A\) is an rectangular array of numbers \(a_, 1\leq i \leq m, 1 \leq j \leq n\). \[ A = \left[\begin a_ & a_& \ldots& a_ \\ a_ & a_& \ldots& a_ \\ \vdots & \vdots& \cdots& \vdots \\ a_ & a_& \ldots& a_ \end \right]. \nonumber\] It consists of \(m\) horizontal rows of size \(n\), or, equivalently, of \(n\) vertical columns of size \(m\).
In a statement about a matrix the first index always refers to the row(s), the second index to the column(s). E.g., \(a_\) is the number in the \(i\)-th row and the \(j\)-th column, and an \(m \times n\) matrix has \(m\) rows and \(n\) columns. A matrix is usually surrounded by parentheses or (square) brackets. We opt for brackets.
The matrix \[ B = \left[\begin
Matrices play an important role in linear algebra. In this section we will use them as concise representations of linear systems, in which the computations involved to solve a system can be done quite systematically.
The augmented matrix for a system of equations \[ \left\ a_x_1\! & \!+\!&\!a_x_2\! & \!+\!&\! \ldots\! & \!+\!&\!a_x_n \! & \!=\!&\! b_1 \\ a_x_1 \quad \! & \!+\!&\!a_x_2\! & \!+\!&\!\ldots\! & \!+\!&\!a_x_n \! & \!=\!&\! b_2 \\ \vdots \! & \! \!&\! \vdots\! & \! \!&\!\cdots\! & \! \!&\! \vdots \! & \! \!&\! \vdots \\ a_x_1 \quad \! & \!+\!&\!a_x_2\! & \!+\!&\! \ldots\! & \!+\!&\!a_x_n \! & \!=\!&\! b_m \\ \end \right. \nonumber\] is the matrix \[ \left[\begin a_ & a_& \ldots& a_ & b_1 \\ a_ & a_& \ldots& a_ & b_2 \\ \vdots & \vdots& \ldots& \vdots & \vdots \\ a_ & a_& \ldots& a_ & b_m \end \right]. \nonumber\] The part before the vertical bar, i.e. \[ A = \left[\begin a_ & a_& \ldots& a_ \\ a_ & a_& \ldots& a_ \\ \vdots & \vdots& \ldots& \vdots \\ a_ & a_& \ldots& a_ \end \right] \nonumber\] is called the coefficient matrix of the system. The column behind the bar contains the constant terms.
The augmented matrix is nothing more than an abbreviation for a system of equations. With the vertical bar we want to indicate that the last column plays a special role, namely, it contains the constants on the right-hand sides of the equations. If we denote these terms by the vector \[ \vect = \left[\begin b_1\\b_2\\\vdots\\b_m \end \right] \nonumber\] the augmented matrix can be written as \[ [ A | \vect ]. \nonumber\] To conclude this subsection we will reconsider the earlier example of a system of three equations in three unknowns \[ \left\ <\begin x_1 & + & 3x_2 & -&2x_3 &=& 4 \\ 3x_1 & + & 7x_2 & -&2x_3 &=& 8 \\ 2x_1 & + &10x_2 & -&9x_3 &=& 4. \end \right. \nonumber\] We will apply the same simplifications to the system as before. Parallel to this we adapt the augmented matrix accordingly, using a notation that speaks for itself. \[ \begin \left\ <\begin x_1 & + & 3x_2 & -&2x_3 &=& 4 \\ 3x_1 & + & 7x_2 & -&2x_3 &=& 8 \\ 2x_1 & + &10x_2 & -&9x_3 &=& 4 \end \right.&\qquad& \left[\begin 1 & 3 & -2& 4 \\ 3 & 7 & -2& 8 \\ 2 & 10 & -9 & 4 \end\right] \quad \begin [R_] \\ [R_ -3R_] \\ [R_ -2R_] \end \\ & <\Big\Updownarrow>& \\ \left\ <\begin x_1 & + & 3x_2 & -&2x_3 &=& 4 \\ & - & 2x_2 & +&4x_3 &=& -4 \\ & &4x_2 & -&5x_3 &=& -4 \end \right.&\qquad& \left[\begin 1 & 3 & -2& 4 \\ 0& -2 & 4 & -4 \\ 0 & 4 & -5 & -4 \end\right]\quad \begin [R_] \\ [ -\frac12 R_] \\ [R_] \end \\ &<\Big\Updownarrow>& \\ \left\ <\begin x_1 & + & 3x_2 & -&2x_3 &=& 4 \\ & & x_2 & -&2x_3 &=& 2 \\ & &4x_2 & -&5x_2 &=& -4 \end \right.&\qquad& \left[\begin 1 & 3 & -2& 4 \\ 0& 1 & -2 & 2 \\ 0 & 4 & -5 & -4 \end\right]\quad \begin [R_] \\ [R_] \\ [R_ -4R_] \end \\ &<\Big\Updownarrow>& \\ \left\ <\begin x_1 & + & 3x_2 & -&2x_3 &=& 4 \\ & & x_2 & -&2x_3 &=& 2 \\ & & & &3x_3 &=& -12 \end \right.&\qquad& \left[\begin 1 & 3 & -2& 4 \\ 0& 1 & -2 & 2 \\ 0 & 0 & 3 & -12 \end\right] \end \nonumber\] As we have seen before, the solution can now be found by back substitution. The right moment to start this back substitution is when the augmented matrix has been simplified to so-called echelon form.
In subsection \(\PageIndex\) we have solved linear systems by eliminating variables from the equations. It would be nice to have a clear mark where we can stop rewriting the given system, to forestall ending up in a never ending loop. When we use the notation of an augmented matrix we can identify such a mark. We first need a few more definitions.
The following three matrices are meant to visualize the structure of an echelon matrix. The symbol \(\blacksquare\) denotes an arbitrary nonzero number, and \(\ast\) just any real number. \[ E_1 = \left[\begin
In a similar manner we can define the concept of a column echelon matrix. However, since we will only consider row echelon matrices we will not do this. In the sequel we will drop the epithet 'row' and simply speak of echelon form and echelon matrix.
A pivot of a row in an echelon matrix is the first nonzero element of the row. Sometimes we also refer to it as the leading entry.
The following three matrices are in echelon form: \[ \left[\begin
Here are the three echelon matrices again, with boxes around their pivots: \[ \left[\begin
In practice the pivots are the coefficients in the equations of a system that are used to eliminate variables from other equations. In the context of augmented matrices: they are the entries used to create zeros in the column below that entry. Note that from the second condition in Definition \(\PageIndex\) it follows that automatically all entries in the column below a pivot must be 0.
Now have a look again at the derivation at the end of the previous subsection. We worked our way downwards through the rows to create zeros in the first columns, while keeping in mind that we did not change the solution set of the corresponding linear system. The process is called row reduction. The end point, from which we could start building the solution by back substitution, was an augmented matrix in echelon form!
Matrices that can be transformed into each other via row operations are called row equivalent. If two matrices \(A\) and \(B\) are row equivalent we denote this by \(A \sim B\).
if two augmented matrices are row equivalent it means that the linear systems they represent are equivalent (i.e., have the same solution set).
Above we applied row operations to an augmented matrix, to work our way to the solution of a system of equations. In fact we simplified the system and the matrix along parallel paths. From now on we will simplify a system by working almost always with the corresponding augmented matrix. In the future (chapter or section . . . .) we will also apply row reduction to matrices in other contexts, i.c. for other purposes.
We will row reduce the matrix \[ M = \left[\begin
The echelon matrix to which a matrix can be reduced is in no way unique. For instance, by scaling a row in an echelon matrix the echelon form persists. We can go a bit further, namely we can create zeros in the columns above the pivots as well. The following example shows how. First we work downwards to the echelon form, and then work upwards to create the extra zeros, as mentioned.
The matrix \[ M = \left[\begin
There are three important observations regarding this example.
Apart from the second step, where two rows were scaled, in each step one pivot was used to make all elements right above and right below it equal to 0. In this way we move forward all the time to a matrix with more and more zeros in a structured way.
The third remark is the most important one, keeping in mind the goal of this section: solving linear systems.
If the matrix \(M\) were actually an augmented matrix for a system, in which we'd better have written \[ M = \left[\begin
This natural end point of the row reduction process has got his own name.
Of the matrices \[ \left[\begin
The big advantage of reduced echelon matrices, already hinted at in Remark (\(\PageIndex\)), is the following:
If the augmented matrix of a linear system is in reduced echelon from, the solution of the system is found by expressing the variables corresponding to the pivots in terms of the other variables. These other variables can be assigned arbitrary values.
In the solution as constructed according to the previous proposition the pivot variables are called the basic variables. The other variables are called free variables.
We find the solution of the linear system with the following augmented matrix, which is already in row reduced echelon: \[ \left[\begin
The row reduction of the augmented matrix to echelon form corresponds to the forward substitution as in examples (\(\PageIndex\)) and (\(\PageIndex\)). There we found the solution by back-substitution. When the augmented matrix is reduced to reduced echelon form we have in fact incorporated this back-substitution part and can write down the general solution directly.
Again we give no formal proof. In the previous section we showed, also informally, that any matrix can be reduced to a matrix in echelon form. In this echelon matrix we may divide each row by its pivot (first nonzero element). And lastly working upwards' step by step we use a pivot -- which we made equal to 1 -- to create zeros in all positions above it. (The last two simplifications may be done in reversed order: first use the pivots to create zeros in the positions above them, and then scale the rows.) This reasoning supports the validity of the first statement. The uniqueness is harder to show in an intuitive way, and it is definitely harder to prove rigorously.
We further simplify the echelon matrix \[ \left[\begin
Instead of a formal proof of the uniqueness of the row reduced echelon form of a matrix, we illustrate this uniqueness with one example.
We will find the row reduced echelon form of the matrix \[ M = \left[\begin
The following algorithm summarizes the solution method for a linear system.
The following important general statement about the solution set of linear systems has already been lurking in the background all the time.
A system of linear equations has either zero, or one, or infinitely many solutions. In the case when there is exactly one solution, we speak of a unique solution.
Skip/Read the proofThis just depends on the outcome of the elimination method. If (iii) occurs, the number of solutions is zero; if (iv) occurs and there are no free variables, there is just one solution, and if there is at least one free variable, the solution set automatically contains infinitely many solutions.
Note that to answer the question which of the three cases -- zero solutions, a unique solution or infinitely many solutions -- holds, it is suffices to reduce the augmented matrix to just any echelon form. From this echelon form it can already be decided whether the system is consistent, and if it is, whether there are free variables.
We want to find out whether the linear system \[ \left\ x_1 & + & 3x_2 & +&x_3 &=& 5 \\ 2x_1 & + & x_2 & -&x_3 &=& 4 \\ 3x_1 & - & x_2 & -&3x_2 &=& 3 \end \right. \nonumber\] has zero, exactly one, or infinitely many solutions. We row reduce the augmented matrix just as far as necessary: \[ \left[\begin 1 & 3 & 1 & 5\\ 2 & 1 & -1 & 4\\ 3 & -1 & -3 & 3 \end\right] \quad \begin [R_] \\ [R_ -2R_] \\ [R_ -3R_] \end \sim \left[\begin 1 & 3 & 1 & 5\\ 0 & -5& -3 & -6\\ 0 & -10 & -6 & -12 \end\right] \quad \begin [R_] \\ [R_] \\ [R_ -2R_] \end \sim \left[\begin 1 & 3 & 1 & 5\\ 0 & -5& -3 & -6\\ 0 & 0 & 0 & 0 \end\right] \nonumber\] As the system is clearly consistent, and there will be a free variable, we can conclude that the system has infinitely many solutions.
This example stresses that the conclusion whether a linear system has zero, one or infinitely many solutions, is basically a matter of the structure of an echelon matrix that is equivalent to the augmented matrix of the system. Suppose the augmented matrices of three linear systems can be row reduced to the following matrices \[ E_1 = \left[\begin \blacksquare & \ast & \ast & \ast \\ 0 & \blacksquare & \ast & \ast \\ 0 & 0 &\blacksquare & \ast \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end\right] , \quad E_2 = \left[\begin \blacksquare & \ast & \ast & \ast & \ast \\ 0 & \blacksquare & \ast & \ast & \ast \\ 0 & 0 & 0 &\blacksquare & \ast \\ 0 & 0 & 0 &0 & 0 \end\right], \quad E_3 = \left[\begin \blacksquare & \ast & \ast & \ast \\ 0 & \blacksquare & \ast & \ast \\ 0 & 0 & \blacksquare & \ast \\ 0 & 0 & 0 & \blacksquare \\ 0 & 0 &0 & 0 \end\right] \nonumber\] where \(\blacksquare\) denotes an arbitrary nonzero number, and \(\ast\) just any real number. Then the first system has a unique solution, the second system has infinitely many solutions, the third system is inconsistent.
A linear system of \(m\) equations in \(n\) unknowns can only have a unique solution if \(m \geq n\), i.e. if the number of unknowns is at most equal to the number of equations.
Skip/Read the proofLet \[ [A |\vect] \nonumber\] be the augmented matrix of the system, and \[ [E |\vect] \nonumber\] an equivalent echelon matrix. Here \(E\) is an \(m\times n\) echelon matrix. Since the pivots are in different rows, there are at most \(m\) pivots. If \(m < n\), there must be at least one column without a pivot. This implies that either the system is inconsistent (zero solutions) or the system has a solution with at least one free variable (infinitely many solutions). And we have shown that a unique solution is impossible for a system of \(m\) equations in \(n\) unknowns with \(m < n\).
A geometric interpretation of the last proposition: suppose \(n = 3\). The solution set of a linear equation \[ a_1x_1 + a_2x_2 + a_3x_3 = b \nonumber\] can be seen as a plane in \(\mathbb
2.1: Systems of Linear Equations is shared under a CC BY license and was authored, remixed, and/or curated by LibreTexts.