Systems of linear equations: Systems of linear equations
Elementary operations on systems of linear equations
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, 1\le j\le n\) are real or complex numbers.
We have already noted that such a system has no solution, one solution, or multiple solutions. For example, it is easy to check that \(\rv{x,y,z,w}=\rv{0,-1,-1,3}\) and \(\rv{x,y,z,w}=\rv{3,1,-1,0}\) are solutions of the following system: \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ 2x&+&y&+&z&+&2w&=&4\end{array}\right.\] The question is, whether there are any more solutions, and, if so, how they can be determined in a systematic manner.
We first discuss the elimination method for solving systems of linear equations. The strategy is to apply the following elementary operations to systems of linear equations, so as to obtain a simpler system step by step:
Elementary operations on systems of linear equations In addition to expanding brackets, simplifying and regrouping subexpressions, we distinguish the following three elementary operations on systems of linear equations:
- multiplication of both sides of an equation by the same nonzero number;
- 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 obtained through elementary reduction of another system, then the two systems are equivalent and they have the same set of solutions.
\(\phantom{x}\)
We illustrate the elimination method in the example below, and then provide a description of the reduction process for systems with two equations and two unknowns.
When we add in the system \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ 2x&+&y&+&z&+&2w&=&4\end{array}\right.\] the first equation #-2# times to the second equation (in other words, we subtract twice the first equation of the second equation), we get \[\left\{\begin{array}{rrrrrrrrr}x&+&y&+&z&+&w&=&1\\ &-&y&-&z&&&=&2\end{array}\right.\] Next we add in the system just obtained the second equation to the first equation: \[\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 has been brought into a form in which we can easily read off the solutions and also immediately realise that there are infinitely many solutions: you can freely choose \(z\) and \(w\), 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}\)
You can also omit the final steps in the previous example, and stop when you 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 that \(x\) and \(y\) can be expressed in terms of these: if, in the second equation, we consider \(y\) as the unknown and consider \(z\) as a parameter, then the solution of this equation is \(y=-2-z\). Substitution of this expression for \(y\) into the first equation then gives \(x-2+w=1\) and thus \(x=3-w\).
- Make sure \(x\) occurs in the first equation. If that is not the case, then we let swap the two equations, so that \(x\) occurs in the first equation.
- Replace the second equation by the difference of this equation and a suitably selected multiple of the first equation, so that \(x\) no longer appears in the second equation.
- Replace the first equation by the difference of this equation with an appropriate multiple of the second equation, so that \(y\) no longer occurs in the first equation.
- Multiply the first and second equation each by an appropriate number, so that the left-hand sides become \(x\) and \(y\), respectively, and the solution appears.
Have a look at some examples of systems with two or three unknowns to get a taste of the elimination method. In the next section, we introduce a shorthand notation of system of linear equations using matrices and the elimination method is defined more succinctly by row reduction of matrices.
To see this, we begin with the original system of equations \[\lineqs{ 3 x+6 y&=&8\cr -3 x-4 y&=&-6 \cr}\] and we replace the second equation by the difference of the second equation and the multiple of the first equation that makes \(x\) disappear (by substracting -1 times the first equation for the second equation). In this way, the system becomes \[\lineqs{ 3 x+6 y&=&8\cr 2 y&=&2 \cr}\] It follows from the second equation that \(y=1\). Substitution of this value for \(y\) in the first equation turns that equation into a linear equation for \(x\) only, with solution \(x={{2}\over{3}}\).