We now discuss a general system of \(m\) linear equations with \(n\) unknowns \(x_1, \ldots, x_n\) in the following form \[\left\{\;\begin{array}{lllllllll} 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 &&\vdots &&&& \vdots&&\!\!\!\!\vdots\\ a_{m1}x_1 \!\!\!\!&+&\!\!\!\! a_{m2}x_2 \!\!\!\!&+&\!\!\!\! \cdots \!\!\!\!&+&\!\!\!\! a_{mn}x_n \!\!\!\! &=&\!\!\!\!b_m\end{array}\right.\] Here, all \(a_{ij}\) and \(b_i\) with \(1\le i\le m\) and \(1\le j\le n\) are real or complex numbers. We discuss the sweep method for solving such a system. The strategy is to apply the following elementary operations to systems of linear equations, so as to obtain a simpler system step by step:
In addition to expanding brackets, simplifying and regrouping subexpressions, we distinguish the following three elementary operations on systems of linear equations:
- Multiplication of an equation (that is to say, both sides of the equation) by a number distinct from zero.
- Addition of a multiple of one equation to one of the other equations.
- Interchange of two equations.
We speak of an elementary reduction if all steps in the reduction are elementary operations (we always allow for the expansion of brackets, simplification and regrouping of subexpressions in each equation).
If a system of linear equations is an elementary reduction of another system, then the two systems are equivalent.
We show that elementary operations on systems of linear equations do not change the solution.
- Multiplying an equation by a scalar #\neq 0#
Let #\rv{s_1,\ldots ,s_n}# be a solution of the equation \[v:\quad a_1x_1+\cdots +a_nx_n=b\] This means that \[a_1s_1+\cdots +a_ns_n=b\] Now let #\alpha# be a number distinct from zero. Multiplying #v# left and right by #\alpha#, we find \[\alpha a_1s_1+\cdots +\alpha a_n s_n=\alpha b\] so #\rv{s_1,\ldots,s_n}# is a solution of the equation #\alpha \cdot v#.
Each solution of the equation #v# is also a solution of the equation #\alpha\cdot v#.
So each solution of the equation #\alpha\cdot v# is also a solution of #\frac{1}{\alpha}\cdot \alpha\cdot v=v#. We have used here that #\alpha \neq 0#. The equations #v# and #\alpha\cdot v# thus have the same solution. (This fact was also stated in the theorem of Reduction to base form.) Therefore, in a system of equations, we can replace any one of the equations by a multiple of it by a number #\alpha\neq 0# without changing the solution set.
- Replacing equations #v# and #w# by #v# and #w+\beta v# for some scalar #\beta#
Let #\rv{s_1,\ldots ,s_n}# be a solution of the equations \[ v:\quad a_1x_1+\cdots +a_nx_n=b \quad \mathrm{and}\quad w:\quad c_1x_1+\cdots +c_nx_n=d\] This means \[a_1s_1+\cdots +a_ns_n=b \quad \mathrm{and}\quad c_1s_1+\cdots +c_ns_n=d \]
From this it follows that, for an arbitrary number #\beta#, that \[(c_1+\beta\cdot a_1)s_1+\cdots +(c_n+\beta\cdot a_n)s_n=d+\beta\cdot b\] Thus, each solution of the equations #v# and #w# is also a solution of the equations #v# and #w+\beta \cdot v#.
As a consequence, each solution of the equations #v# and #w+\beta \cdot v# is also a solution of the equations #v# and #(w+\beta \cdot v)-\beta \cdot v#, so of #v# and #w#. The equations #v# and #w# thus have the same solutions as the equations #v# and #w+\beta \cdot v#. Thus, the set of solutions of a system of equations does not change if we add a multiple of another equation to another equation.
- Interchange of two equations
It is immediate from the definition of a system of equations that, if we change the order of the equations in a system, the set of solutions does not change.
Later we will see that if two systems have the same linear equation with unknowns equivalent, they can also be reduced to each other by use of elementary operations.
The statement below explains why elementary reduction works.
The following method can be employed to obtain a parametric representation of the general solution of the linear system of equations described above:
- By selecting an equation, say #i_1#, in which #x_1# occurs (that is, the coefficient #a_{i_1,1}# is distinct from #0#), and next subtracting appropriate multiples of this equation from the other equations, we can ensure that #x_1# disappears from all of the other equations of the system.
- By selecting another comparison, say #i_2#, in which #x_2# occurs (so #a_{i_2,2}\ne0#), we can similarly achieve that #x_2# will no longer be found in any other equation. If #x_2# does not appear in an equation distinct from #i_1#, we go straight to #x_3#. We continue this way until all unknown have been treated.
- The general solution of the system of equations in parameter form will appear in parameter form as follows: The equations #i_1# , #i_2,\ldots# (if any) are used to express #x_1#, #x_2,\ldots# (if any) in the other unknowns. These other unknowns can be chosen freely. In the general solution, they (or variables not used before) can act as free parameters.
Consider the system \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ 2x&+&y&+&z&+&2w&=&4\end{array}\right.\] We see that #x# occurs in the first equation. We add #-2# times the first equation to the second equation (in other words, we subtract twice the first equation from the second). Then we get \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ &-&y&-&z&&&=&2\end{array}\right.\] Next we eliminate #y# from all equations except the second: in the newly obtained system, we add the second equation to the first: \[\left\{\begin{array}{rrrrrrrrr}x&&&&&+&w&=&3\\ &-&y&-&z&&&=&2\end{array}\right.\] Finally we multiply the second equation by #-1#: \[\left\{\begin{array}{rrrrrrrrr}x&&&&&+&w&=&3\\&&y&+&z&&&=&-2\end{array}\right.\] Now the system is in a form where we can easily read off the solutions and immediately conclude that there are an infinite number of solutions: we can choose the values of the unknown \(z\) and \(w\) freely, say \(z=r\) and \(w=s\) for certain \(r\) and \(s\) and express \(x\) and \(y\) in terms of these: \[\lineqs{x&=&\phantom{-}3-s\cr y&=&-2-r\cr}\] In this case, \(r\) and \(s\) are the free parameters; we also say that there are two degrees of freedom.
\(\phantom{x}\)
We can also omit the final steps in the previous example, and stop when we have arrived at \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ &-&y&-&z&&&=&2\end{array}\right.\] Here it is already clear that \(z\) and \(w\) can be freely chosen and \(x\) and \(y\) can be expressed in terms of these: if, in the second equation we view \(y\) as the single unknown and consider \(z\) as a parameter, then the solution of this equation is \(y=-2-z\). Substituting of this expression for #y# into the first equation then gives \(x-2+w=1\), or \(x=3-w\).
The operations that we use in this method are limited to the first two types of elementary operations:
- The real elimination, that is, the reduction of the number of occurrences of #x_1# , #x_2,\ldots# is based on the second elementary operation.
- The rewriting of the equation with #x_1# in the form #x_1=\cdots# is based on the first elementary operation.
In the next section, we will introduce a shorthand notation of a system of linear equations using matrices and the elimination method will be defined more succinctly by row reduction of matrices.
Here are a few examples of systems with two or three unknowns.
Solve the following system of linear equations with unknown \(x\) and \(y\). \[\lineqs{ x-y&=&1\cr -2 x+3 y&=&-4 \cr}\]
- If there is no solution, write #none#
- If there is one solution, write #x=a\land y=b# for appropriate numbers #a# and #b#. You can find the #\land# on the mathematical input editor on the "function" tab.
- If there are multiple solutions, express one of the variables in terms of the other
- If all values of #x# and #y# are solutions, write #all#
\( x=-1\land y=-2 \)
To see this, we begin with the original system of equations \[\lineqs{ x-y&=&1\cr -2 x+3 y&=&-4 \cr}\] and we replace the second equation by the difference of the current and the multiple of the first equation that makes \(x\) disappear (add #2# times the first equation to the second). This way the system becomes
\[\lineqs{ x-y&=&1\cr y&=&-2 \cr}\] It follows from the second equation that \(y=-2\). Substitution of this value for \(y\) in the first equation turns that equation into a linear equation for \(x\) only, with solution \(x=-1\).
Elementary operations on systems of linear equations
