Elementary Operations: The following operations 1, 2 and 3 are called elementary operation.
- interchange of two equations, say “interchange the ith and jth equations”:(compare the system (2.2.2) with the original system.)
- multiply a non-zero constant throughout an equation, say “multiply the kth equation by c≠ 0
(compare the system (2.2.5) and the system (2.2.4).)
- replace an equation by itself plus a constant multiple of another equation, say “replace the kth equation
by kth equation plus c times the jth equation”.
(compare the system (2.2.3) with (2.2.2) or the system (2.2.4) with (2.2.3).)
- In the above example, observe that the elementary operations helped us in getting a linear system(2.2.5),
which was easily solvable.
- Note that at Step 1, if we interchange the first and the second equation, we get back to the linearsystem from which we had started. This means the operation at Step 1, has an inverse operation.
In other words, inverse operation sends us back to the step where we had precisely started. It will be a useful exercise for the reader to identify the inverse operations at each step in
So, in Example 2.2.4, the application of a finite number of elementary operations helped us to obtaina simpler system whose solution can be obtained directly. That is, after applying a finite number ofelementary operations, a simpler linear system is obtained which can be easily solved. Note that thethree elementary operations defined above, have corresponding inverse operations, namely,
- “interchange the ith and jth equations”,
- “divide the kth equation by c ≠ 0”;
3.“replace the kth equation by kth equation minus c times the jth equation”.
It will be a useful exercise for the reader to identify the inverse operations at each step in Example
Equivalent Linear Systems: Two linear systems are said to be equivalent if one can be obtained from the other by a finite number of elementary operations.
The linear systems at each step in Example 2.2.4 are equivalent to each other and also to the original linear system.
Lemma 2.3.3 Let Cx = d be the linear system obtained from the linear system Ax = b by a single elementary operation. Then the linear systems Ax = b and Cx = d have the same set of solutions.
Proof. We prove the result for the elementary operation “the kth equation is replaced by kth equation plus c times the jth equation.” The reader is advised to prove the result for other elementary operations. In this case, the systems Ax = b and Cx = d vary only in the kth equation. Let (α1, α2, . . . , αn) be a solution of the linear system Ax = b. Then substituting for αi’s in place of xi’s in the kth and jth equations, we get
ak1α1 + ak2α2 + · · · aknαn = bk, and aj1α1 + aj2α2 + · · · ajnαn = bj.
(ak1 + caj1)α1 + (ak2 + caj2)α2 + · · · + (akn + cajn)αn = bk + cbj . (2.3.1)
But then the kth equation of the linear system Cx = d is
(ak1 + caj1)x1 + (ak2 + caj2)x2 + · · · + (akn + cajn)xn = bk + cbj. (2.3.2)
ROW OPERATIONS AND EQUIVALENT SYSTEMS
Therefore, using Equation (2.3.1), (α1, α2, . . . , αn) is also a solution for the kth Equation (2.3.2).
Use a similar argument to show that if (β1, β2, . . . , βn) is a solution of the linear system Cx = d then it is also a solution of the linear system Ax = b.
Hence, we have the proof in this case.
Lemma 2.3.3 is now used as an induction step to prove the main result of this section
Theorem Two equivalent systems have the same set of solutions.
Proof. Let n be the number of elementary operations performed on Ax = b to get Cx = d. We prove the theorem by induction on n.
If n = 1, Lemma 2.3.3 answers the question. If n > 1, assume that the theorem is true for n = m. Now, suppose n = m+1. Apply the Lemma 2.3.3 again at the “last step” (that is, at the (m+1)th step from the mth step) to get the required result using induction.
Let us formalise the above section which led to Theorem 2.3.4. For solving a linear system of equations, we applied elementary operations to equations. It is observed that in performing the elementary operations, the calculations were made on the coefficients (numbers). The variables x1, x2, . . . , xn and the sign of equality (that is, “ = ”) are not disturbed. Therefore, in place of looking at the system of equations as a whole, we just need to work with the coefficients. These coefficients when arranged in a rectangular array gives us the augmented matrix [A b].
Elementary Row Operations The elementary row operations are defined as:
- interchange of two rows, say “interchange the ith and jth rows”, denoted Rij ;
- multiply a non-zero constant throughout a row, say “multiply the kth row by c ≠0”, denoted Rk(c);
- replace a row by itself plus a constant multiple of another row, say “replace the kth row by kth row plus c times the jth row”, denoted Rkj(c).
Exercise :Find the inverse row operations corresponding to the elementary row operations that have been defined just above.
Row Equivalent Matrices Two matrices are said to be row-equivalent if one can be obtained from the other by a finite number of elementary row operations.
Example : The three matrices given below are row equivalent.