Elementary Row Operation

Solving a system of linear equations is one of the cumbersome operations in mathematics. But it is very essential in mathematics. Here we consider the elimination method using matrices.

Give a system of the linear equations.

$$(I) \left\{ \begin{array}{rrrrr} 2x&-3y&+z& = 1& ... ... 3x&+2y&-z& = 5& (3) \end{array}\right.$$

We interchange the equation $(1)$ and $(2)$. Then we have

$$(II) \left\{ \begin{array}{rrrrr} x&+2y&-3z& = 4& ... ... 3x&+2y&-z& = 5& (3) \end{array}\right.$$

Note that above systems are equivalent in the sense that they give the same answer.

Next we multiply the equation $(2)$ by $-2$ and add it to $(1)$. Also multiply the equation $(2)$ by $-3$ and add to $(3)$. Then we have

$$(III) \left\{ \begin{array}{rrrrr} x&+2y&-3z& = 4& \... ...& = -7& (3^{\prime}) \end{array}\right.$$

We have tried to eliminate the leading number of the 2nd and 3rd equations. This time we multiply the equation $(2^{\prime})$ by $-\frac{1}{7}$ to make the leading element 1.

$$(IV) \left\{ \begin{array}{rrrrr} x&+2y&-3z& = 4& ... ...& = -7& (3^{\prime}) \end{array}\right.$$

Lastly, multiply the equation $(2^{\prime\prime})$ by $4$ and add it to the equation $(3^{\prime})$. Then we have

$$(V) \left\{ \begin{array}{rrrrr} x&+2y&-3z& = 4& \... ...& (3^{\prime\prime}) \end{array}\right.$$

. Now we start to look backward. Then we have

$$z = \frac{-3}{4}, y = 1+z = 1+\frac{-3}{4} = \frac{1}{4}, x = -2y+3z+4 = \frac{5}{4}.$$

This method is called Gaussian elimination,

• Interchange the $i$thequation and $j$th equation:
  
• Multiply the $i$th equation by a nonzero scalar $k$
  
• Replace the $i$th equation by $k$ times the $j$th equation plus the $i$th equation.

Now we apply elementary operations to the system of linear equations.

First of all, The matrix composed of coefficients of the system of linear equations $(I)$ is called a coefficient matrix. The matrix composed of coefficient matrix and constant terms is called an augmented matrix and denoted by

$$\left(\begin{array}{rrr} 2&-3&1\\ 1&2&-3\\ 3&2&-1 \end{array}\r... ... \left(\begin{array}{rrrr} 2&-3&1&1\\ 1&2&-3&4\\ 3&2&-1&5 \end{array}\right)$$

We apply elementary operations on this augmented matrix.

$$(I) \left(\begin{array}{rrrr} 2&-3&1&1\\ 1&2&-3&4\\ 3&2&-1&5 \... ... \left(\begin{array}{rrrr} 1&2&-3&4\\ 2&-3&1&1\\ 3&2&-1&5 \end{array}\right)$$

$$\stackrel{\begin{array}{cc} {}^{-2R_{1}+R_{2}}\\ {}^{-3R_{1}+R_{3}} \end{array}}{\rightarrow} (III) \left(\begin{array}{rrrr} 1&\!\!2&\!\!-3&\!\!4\\ 0&\!\!-7&... ...rr} 1&\!\!2&\!\!-3&4\\ 0&\!\!1&\!\!-1&1\\ 0&\!\!-4&\!\!8&7 \end{array}\right)$$

$$\stackrel{4R_{2}+R_{3}}{\rightarrow} (V) \left(\begin{array}{rrrr} 1&2&-3&4\\ 0&1&-1&1\\ 0&0&4&-3 \end{array}\right)$$

We have used the following elementray operations.

• $L\_{1}$ : Interchange the $i$th row and $j$th row: $R_{i} Leftrightarrow R_{j}$
• $L\_{2}$ : Multiply the $i$th row by a nonzero scalar $k$: $R_{i} \Longrightarrow kR_{1}, k \neq 0$
  
• $L\_{3}$ : Replace the $i$th row by $k$ times the $j$th row plus the $i$th row: $R_{i} \Longrightarrow kR_{j} + R_{i}$

Generally, those 3 operations on a metrix $A$ is called fundamental row operation.

Example 2..7  

Solve the following system of linear equations using Gaussian elimination。

$$\begin{array}{rrrrrrrr} R_{1} &:& x_{1}& - x_{2}& + 2x_{3}& -... ...R_{4} &:& x_{1}& - x_{2}& + 4x_{3}& + 3x_{4}& = & 4 \end{array}$$

Answer The augmented matrix is given by

$$\tilde{A} = \tilde{A}^{(1)} = \left(\begin{array}{rrrrrr} 1 & -1... ... 1 & 1 & 1 & 0 & \vdots & -2\\ 1 & -1 & 4 & 3 &\vdots & 4 \end{array}\right)$$

Here we apply the following elementary operations : $-2R_{2} + R_{1}, -R_{1} + R_{3}, -R_{1} + R_{4}$. Then we have

$$\tilde{A}^{(2)} = \left(\begin{array}{rrrrrr} 1 & -1 & 2 & -1 & ... ... 0 & 2 & -1 & 1 & \vdots & 6\\ 0 & 0 & 2 & 4 &\vdots & 12 \end{array}\right)$$

Now the Pivot element $a^{(2)}_{22} = 0$. So, use the elementary operation $R_{2} \leftrightarrow R_{3}$. Then

$$\tilde{A}^{(2)'} = \left(\begin{array}{rrrrrr} 1 & -1 & 2 & -1 &... ... & 0 & -1 & -1 & \vdots & -4\\ 0 & 0 & 2 & 4 &\vdots & 12 \end{array}\right)$$

Note that $x_{2}$ is already eliminated from $R_{3}$. Thus, $\tilde{A}^{(2)'} = \tilde{A}^{(3)}$. Continue elementary operation such as $2R_{3} + R_{4}$. Then

$$\tilde{A}^{(4)} = \left(\begin{array}{rrrrrr} 1 & -1 & 2 & -1 & ... ...0 & 0 & -1 & -1 & \vdots & -4\\ 0 & 0 & 0 & 2 &\vdots & 4 \end{array}\right)$$

Now we have echlon matrix which is a matrix whose nonzero entries are preceding the first nonzero entries and the first nonzero entry of a row increases row by row.

Thus, we have

$$x_{4} = 2$$

$$x_{3} = \frac{-4 - (-1)x_{4}}{-1} = 2$$

$$x_{2} = \frac{6 -x_{4} - (-1)x_{3}}{2} = 3$$

$$x_{1} = \frac{-8 - (-1)x_{4} - 2x_{3} - (-1)x_{2}}{1} = -7$$

If a matrix $B$ is created by appling finitely many elementary operation on $A$ , a matrix $B$ is said to be row equivalent and denoted by $A \sim B$. If elmentary operation $L_{1}, L_{2}$ or $L\_{3}$ is applied once to the identity matrix of the order $n$, then the matrix obtained is called a fundamental matrix. You might already have noticed that an elementary operation can be written using an elementary matrix. For example, the elementary operation from $(I)$ to $(II)$ is $R_{1} \leftrightarrow R_{2}$ and the corresponding elementary matrix can be obtained by applying the elementary operation $R_{1} \leftrightarrow R_{2}$ on $I_{3}$.

$$\underbrace{\left(\begin{array}{rrr} 1&0&0\\ 0&1&0\\ 0&0&1 \end... ...e{\left(\begin{array}{rrr} 0&1&0\\ 1&0&0\\ 0&0&1 \end{array}\right)}_{E_{1}}$$

Now multiply $E_{1}$ to $(I)$ from the left. Then we have

$$\underbrace{\left(\begin{array}{rrr} 0&1&0\\ 1&0&0\\ 0&0&1 \end... ...egin{array}{rrrr} 1&2&-3&4\\ 2&-3&1&1\\ 3&2&-1&5 \end{array}\right)}_{(II)}$$

Now take a close look at this elementary matrix. Interchange of 2nd row and 3rd row of the identity matrix. An elmentary matrix corresponds to the elementary operation $-2R_{1} + R_{2}$ is given by the following:

$$\underbrace{\left(\begin{array}{rrr} 1&0&0\\ -2&1&0\\ 0&0&1 \end{array}\right)}_{E_{2}}$$

Another elementary matrix corresponds to the elementary operation $-3R_{1} + R_{3}$ is given by the following:

$$\underbrace{\left(\begin{array}{rrr} 1&0&0\\ 0&1&0\\ -3&0&1 \end{array}\right)}_{E_{3}}$$

Similary, we can find elementary matriced corresponds to elementary operations $E_{4}, E_{5}$. Thus,

$$E_{4} = \left(\begin{array}{rrr} 1&0&0\\ 0&\frac{1}{7}&0\\ 0&0&... ...), E_{5} = \left(\begin{array}{rrr} 1&0&0\\ 0&1&0\\ 0&4&1 \end{array}\right)$$

Now we multiply $E$'s to the matrix $A$ from the left. Then

$$E_{6}E_{5}E_{4}E_{3}E_{2}E_{1}A = B$$

Thus, the matrix $B$ and $A$ are row equivalent..

When you apply elementary operations on a matrix $A$. we are able to obatin a matrix so that all entries below the diagonal are zero. We say this matrix as upper triangular matrix.

$$A = \left(\begin{array}{clclccclc} 0&\hskip -.2cm \vline&1&&2&&3&... ...&&0&&0&&0&\hskip -.2cm \vline&4\ \cline{8-9} 0&&0&&0&&0&&0 \end{array}\right)$$

is an echlon matrix. Furthermore, the first nonzero element is $1$, it is called arow reduced echelon matrix and denoted by $A_{R}$. We show next that every matrix is row equivalent to a row reduced echlon matrix.

Theorem 2..3  

Any matrix can be reduced to a row reduced echlon matrix by taking suitable elementary row operation.

Proof It is up to you..

Example 2..8  

Find the row equivalent row reduced matrix.

$$\left(\begin{array}{rrrrr} 0&0&0&0&0\\ 0&0&2&0&0\\ 0&1&0&1&1\\ 0&4&3&4&0 \end{array}\right)$$

Answer

$$\left(\begin{array}{rrrrr} 0&0&0&0&0\\ 0&0&2&0&0\\ 0&1&0&1&1\ ... ...ay}{rrrrr} 0&0&0&0&0\\ 0&0&2&0&0\\ 0&1&0&1&1\\ 0&0&3&0&-4 \end{array}\right)$$

$$\stackrel{R_{1} \leftrightarrow R_{2}}{\rightarrow} \left(\begin{array}{rrrrr} 0&1&0&1&1\\ 0&0&2&0&0\\ 0&0&0&0&0\ ... ...ay}{rrrrr} 0&1&0&1&1\\ 0&0&1&0&0\\ 0&0&0&0&0\\ 0&0&0&0&-4 \end{array}\right)$$

$$\stackrel{\begin{array}{cc} {}^{\frac{-R_{4}}{4}}\\ {}^{R_{3} \leftrightarrow R_{4}} \end{array}}{\rightarrow} \left(\begin{array}{rrrrr} 0&1&0&1&1\\ 0&0&1&0&0\\ 0&0&0&0&1\ ... ...&0&&0&&0&\hskip -.2cm \vline&1\ \cline{8-9} 0&&0&&0&&0&&0 \end{array}\right) .$$

$\blacksquare$

In this example, the order of the row operation is not important.

Theorem 2..4  

If the matrix $B$ and $C$ are row reduced echlon matrix and row equivalent to $A$, then $B = C$.

Proof It is up to you.

It is important to know that the matrix row equivalent to $A$ is unique.

$\spadesuit$Rank of matrix $\spadesuit$

The number of steps of the row reduced echlon form is important for application. This number is called the rank of a matrix and denoted by ${\rm rank}(A)$. For example, the rank of 2.2 is $3$.

Theorem 2..5  

Let $A$ be a square matrix of the order $n$. Then the followings are equivalent.
$(1) {\rm rank}(A) = n$
$(2) A_{R} = I_{n}$

Proof If $A_{R} = I_{n}$ , then the rank of $A_{R}$ is $n$. Thus, ${\rm rank}(A) = n$.

Conversely, if ${\rm rank}(A) = n$, then the number of steps of the row reduced matrix of $A$ is $n$. By the definition of the row reduced echlon matrix, the first nonzero entry is $1$. Then every diagonal element is $1$. Thus, $A_{R} = I_{n}$. $\blacksquare$

The rank of a matrix can be defined by the concept of a vector space.

$$A = \left(\begin{array}{rrrr} 1&-1&4&2\\ 0&1&3&2\\ 3&-2&15&8 \end{array}\right)$$

Then the row vectors $(1,-1,4,2), (0,1,3,2), (3,-2,15,8)$ are elements of ${\mathcal R}^{4}$. Then a linear combination of these vectors is defined as follows:

$$V = \langle(1,-1,4,2), (0,1,3,2), (3,-2,15,8)\rangle$$

$V$ is then a subspace of ${\mathcal R}^{4}$ (Example1.4). This vector space is called a row space or row spanned subspace of $V$. Now let ${\bf v} \in V$. Then

$${\bf v} = c_{1}(1,-1,4,2) + c_{2}(0,1,3,2) + c_{3}(3,-2,15,8)$$

$$= c_{1}(1,-1,4,2) + c_{2}(0,1,3,2) + 3c_{3}(1,-1,4,2) + c_{3}(0,1,3,2)$$

$$= (c_{1}+c_{3})(1,-1,4,2) + (c_{2} + c_{3})(0,1,3,2).$$

Then every vector in this row space is representable using $(1,-1,4,2), (0,1,3,2)$. Furthermore, $(1,-1,4,2)$ and $(0,1,3,2)$ are linearly independent. Thus, these two vectors a basis of this row space. This shows that the dimension of the row space of $A$ is $2$. We now find the row reduced echlon matrix of $A$. Then

$$A_{R} = \left(\begin{array}{rrrr} 1&0&7&4\\ 0&1&3&2\\ 0&0&0&0 \end{array}\right).$$

Therefore, ${\rm rank}(A) = 2$. Thus in this example,

$${\rm rank}(A) = the dimension of the row space$$

We can do the same thing for the column space.

Theorem 2..6  

The rank of a matrix is the same sa the dimension of the rwo space the matrix.

Proof Let $A$ be a matrix of $m \times n$. Let the row vectors of $A = (a_{ij})$ be ${\bf a}_{1},{\bf a}_{2},\ldots,{\bf a}_{m}$. A row space is alinear combination of

$${\bf a}_{1},{\bf a}_{2},\ldots,{\bf a}_{m}$$

Then elementary row operations $L_{1},L_{3}$ has no effect on the linear combination. Thus, it will not have any effect on the dimension of the row space.

Next, we use $L\_{2}$ to find the row reduced echlon matrix. Suppose that ${\bf a}_{n}$ is a linear combination of ${\bf a}_{1},{\bf a}_{2},\ldots,{\bf a}_{n-1}$, then $\langle{\bf a}_{1},{\bf a}_{2},\ldots,{\bf a}_{n}\rangle$ and $\langle{\bf a}_{1},{\bf a}_{2}, \ldots, c_{1}{\bf a}_{1} + \cdots + c_{n-1}{\bf a}_{n-1}\rangle$ are the same. This corresponds to zeor row vector in the row echlon matrix and removing the row vector ${\bf a}_{n}$. Repeating this process, we can find the row vector ${\bf a}_{i}$ corresponding to the row reducing. The row vectors are linealy independent. Thus the dimension of the row vectors is the same as the rank of row reduced matrix. $\blacksquare$

The rank of a matrix plays an important role on solving the system of linear equations. Befor moving to the next section, try to solve the system of linear equations.

Example 2..9  

Find the rank of the matrix $A$.

$$A = \left(\begin{array}{rrrr} 1&-2&5&3\\ 2&3&1&-1\\ 3&8&-3&-5 \end{array}\right)$$

Answer

$$A = \left(\begin{array}{rrrr} 1&-2&5&3\\ 2&3&1&-1\\ 3&8&-3&-5 \end{... ...left(\begin{array}{rrrr} 1&-2&5&3\\ 0&7&-9&-7\\ 0&14&-18&4 \end{array}\right)$$

$$\stackrel{\begin{array}{cc} {}^{\frac{1}{7} \times R_{2}}\\ {}^{-2R_{2} + R_{3}} \end{array}}{\longrightarrow} \left(\begin{array}{rrrr} 1&-2&5&3\\ 0&1&\frac{-9}{7}&-1\\ 0&0&... ...rrrr} 1&0&\frac{17}{7}&1\\ 0&1&\frac{-9}{7}&-1\\ 0&0&0&0 \end{array}\right) .$$

Then the number of steps of the matrix $A_{R}$ is $2$. Thus ${\rm rank}(A) = 2$. We note that the row vectors $${(1,0,\frac{17}{7},1)}$$ and $${(0,1,\frac{-9}{7},-1)}$$ of the matrix $A_{R}$ forms a basis of the row space of $A$. Thus the dimension of the row space is $2$.. $\blacksquare$

Exercise2-4

1. Find the row reduced matrix which is row equivalent to $A = \left(\begin{array}{rrrr} 1&-2&3&-1\\ 2&-1&2&2\\ 3&0&2&3 \end{array}\right)$.

2. Find the rank of the following matrices.

(a) $\left(\begin{array}{rrrr} 2&4&1&-2\\ -3&-6&2&-4 \end{array}\right)$

(b) $\left(\begin{array}{rrr} 2&-1&3\\ 1&2&-3\\ 3&-4&9 \end{array}\right)$

(c) $\left(\begin{array}{rrrr} 1&-2&3&-1\\ 2&-1&2&2\\ 3&0&2&3 \end{array}\right)$

3. Given $A = \left(\begin{array}{cc} 2&3\\ 3&4 \end{array}\right)$. Apply elmentary operations $(I),(II),(III),(IV)$.

$$A = \!\! \left(\begin{array}{cc} \!\!2&\!\!3\\ \!\!3&\!\!4 \end{... ...el{IV}{\rightarrow} \!\! \left(\begin{array}{cc} 1&0\\ 0&1 \end{array}\right)$$

Find the elementary matrices of $(I),(II),(III),(IV)$. Show the matrix $I_{2}$ as a product of the matrix $A$ and elementary matrices.

4. $A = \left(\begin{array}{rrr} 2&-3&1\\ 1&2&-3\\ 3&2&-1 \end{array}\right)$ can be reduced to the identiry matrix by using the elementary row operation. Find the product of matrices $P$ so that $PA = I$.

5. Find the dimension of the subspace spanned by the following vectors.

$${\bf v}_{1} = (2,-1,1,3), {\bf v}_{2} = (-1,1,0,1), {\bf v}_{3} = (4,-1,3,11), {\bf v}_{4} = (-2,3,1,1)$$