Elementary operations on systems of linear equations

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.

We show that elementary operations to systems of linear equations do not change the solution set.

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\tiny.$ This means that $a_1s_1+\cdots +a_ns_n=b\tiny.$ Now let $\alpha$ be a number distinct from zero. Multiplying left- and right-hand side of the equation $v$ by $\alpha$ , we get $\alpha a_1s_1+\cdots +\alpha a_m s_m=\alpha b\tiny,$ so that $\rv{s_1,\ldots,s_n}$ is a solution of $\alpha v$ .
Any solution of the equation $v$ is also a solution of the equation $\alpha v$ .
So any solution of the equation $\alpha\cdot v$ is also a solution $\frac{1}{\alpha}\cdot \alpha\cdot v=v$ because $\alpha \neq 0$ . The equations $v$ and $\alpha v$ thus have the same solutions. 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:a_1x_1+\cdots +a_nx_n=b \quad \mathrm{and}\quad w:c_1x_1+\cdots +c_nx_n=d\tiny.$ This means that $a_1s_1+\cdots +a_ns_n=b \quad \mathrm{and}\quad c_1s_1+\cdots +c_ns_n=d\tiny.$
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\tiny.$ This means that any solution of the equations $v$ and $w$ also is a solution of the equations $v$ and $w+\beta v$ .
As a consequence, anu solution of the equations $v$ and $w+\beta v$ also is a solution of the equations $v$ and $(w+\beta v)-\beta v$ , so of $v$ and $w$ . The equations $v$ and $w$ thus have the same solutions as the equations $v$ and $w+\beta v$ . So, the set of solutions of a system of equations does not change if we add a multiple of another equation to a single equation.
Changing the order of equation.
It is immediate from the definition of a system of equations that, if we change the order of the equations in a system, for instance by swapping two equations, then the set of solutions does not change.

$\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$ .

Elimination method for systems with two equations and two unknowns The elimination method works as follows for a system of two equations and two unknowns:

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.

Solve the following system of equations via the elimination method $\left\{\begin{array}{rrr}2x+3y\!\!\!\!&=&\!\!\!\!1 \\ 5x+7y\!\!\!\!&=&\!\!\!\!3\end{array}\right.$

The unknown $x$ is already in the first equation. We do not need to swap the equations.
We subtract $\tfrac{5}{2}$ times the first equation from the second equation. As a result, the term with $x$ disappears and we get the equation $7y-\frac{5}{2}\cdot 3y = 3-\frac{5}{2}$ and thus $-\tfrac{1}{2}y=\tfrac{1}{2}$ resulting in $y=-1$ . The new equivalent system of equations is $\left\{\begin{array}{rrr}2x+3y\!\!\!\!&=&\!\!\!\!1 \\ y\!\!\!\!&=&\!\!\!\!-1\end{array}\right.$
We now subtract three times the second equation from the first one (so that the term with $y$ disappears), and get the system $\left\{\begin{array}{rrr}2x\!\!\!\!&=&\!\!\!\!4 \\ y\!\!\!\!&=&\!\!\!\!-1\end{array}\right.$
We divide the first equation by $2$ and get the system $\left\{\begin{array}{rrr}x\!\!\!\!&=&\!\!\!\!2 \\ y\!\!\!\!&=&\!\!\!\!-1\end{array}\right.$ Thus, the system has been solved.

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.

Solve the following linear system of equations with unknown $x$ and $y$ via the elimination method. $\lineqs{ x-y&=&-3\cr 3 x-2 y&=&-8 \cr}$

$x=-2\quad\land\quad y=1$

To see this, we begin with the original system of equations $\lineqs{ x-y&=&-3\cr 3 x-2 y&=&-8 \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 3 times the first equation for the second equation). In this way, the system becomes $\lineqs{ x-y&=&-3\cr y&=&1 \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$ .

New example