3.2 Matrices and Gaussian Elimination

In Example 6 of Section 3.1 we applied the method of elimination to solve the linear system

1x+2y+1z=43x+8y+7z=202x+7y+9z=23.
(1)

There we employed elementary operations to transform this system into the equivalent system

1x+2y+1z=40x+1y+2z=40x+0y+1z=3,
(2)

which we found easy to solve by back substitution. Here we have printed in color the coefficients and constants (including the 0s and 1s that would normally be omitted) because everything else—the symbols x, y, and z for the variables and the + and = signs—is excess baggage that means only extra writing, for we can keep track of these symbols mentally. In effect, in Example 6 we used an appropriate sequence of operations to transform the array

[12143872027923]
(3)

of coefficients and constants in (1) into the array

[121401240013]
(4)

of constants and coefficients in (2).

Rectangular arrays of numbers like those in (3) and (4) are called matrices. Thus, a matrix is simply a rectangular array of numbers, which are called the entries or elements of the matrix. The size, or shape, of a matrix is specified by telling how many horizontal rows and vertical columns it has. Each matrix in (3) and (4) has three rows and four columns; therefore, each is a 3×4 (read “three by four”) matrix. We always specify first the number of rows and then the number of columns.

Example 1

The matrices

[3725][3015][203]

have sizes 2×2, 1×4, and 3×1, respectively.

Coefficient Matrices

A general system of m linear equations in the n variables x1,x2,,xn may be written in the form

a11x1+a12x2+a13x3++a1nxn=b1a21x1+a22x2+a23x3++a2nxn=b2am1x1+am2x2+am3x3++amnxn=bm.
(5)

Observe that aij denotes the (constant) coefficient in the ith equation of the jth variable xj and that bi denotes the constant on the right-hand side in the ith equation. Thus the first subscript i refers to the equation and the second subscript j to the variable. For instance, a32 denotes the coefficient of x2 in the 3rd equation. This scheme of systematic double subscripts enables us to specify readily the location of each coefficient in a system with many equations and variables. It also helps us get rid of the excess baggage in (5) by focusing our attention on the coefficients.

The coefficient matrix of the linear system in (5) is the m×n matrix

A=[a11a12a13a1na21a22a23a2nam1am2am3amn].
(6)

We will use boldface capital letters to denote matrices and lowercase letters to denote numbers. When we want to refer more briefly to the matrix A and its entries, we can write

A=[aij]=[aij](jth column)(ith row)
(7)

The first subscript i specifies the row and the second subscript j the column of A in which the element aij appears:

First subscript Second subscript
Row Column

Although double subscripts may seem tedious when first encountered, their usefulness should not be underestimated. For instance, they are consistent with the notation used in most programming languages. Many practical applications lead to linear systems with hundreds or even thousands of variables and equations. In a typical computer system, the coefficient matrix A of such a system would be represented by a two-dimensional array in which A(i, j) denotes aij. With this approach, the computer can store a 100×100 matrix in the same way that it stores a 3×3 matrix.

The matrices in (3) and (4) include not only the coefficients but also the constants on the right-hand sides in the corresponding linear systems in (1) and (2). Let us write

b=[b1b2bm]
(8)

for the column of constants in the general system in (5). An m×1 matrix—that is, one with a single column—is often called a (column) vector and is denoted by a boldface letter. When we adjoin the constant vector b to the coefficient matrix A (as a final column), we get the matrix

[Ab]=[a11a12a1nb1a21a22a2nb2am1am2amnbm].
(9)

This m×(n+1) matrix is called the augmented coefficient matrix, or simply the augmented matrix, of the m×n system in (5).

Although it takes a good deal of notation to describe the augmented matrix of a general linear system, it is a very simple matter to write the augmented matrix of a particular system. If the system is written in chalk on a blackboard with the variables in the same order in each equation, we merely erase all the xj’s and the plus and equal signs (retaining a minus sign for each negative coefficient) and insert a zero in each spot where a variable is missing in an equation.

Example 2

The augmented coefficient matrix of the system

2x1+3x27x3+4x4=6x2+3x35x4=0x1+2x29x4=17

of three equations in four variables is the 3×5 matrix

[2374601350120917].

Elementary Row Operations

In Section 3.1 we described the three elementary operations that are used in the method of elimination. To each of these corresponds an elementary row operation on the augmented matrix of the system. For instance, when we interchange two equations in the system, we interchange the corresponding two rows of its augmented coefficient matrix.

Figure 3.2.1 shows notation that we use to describe elementary row operations briefly. For instance,

[1234](3)R1+R2[12610]
(10)

shows the result of adding 3 times row 1 to row 2. Note that, when we perform the operation (c)Rp+Rq on a matrix—that is, when we add c times row p to row q—row p itself remains unchanged.

FIGURE 3.2.1.

Notation for elementary row operations.

Type Row Operation Notation
1 Multiply row p by c cRp
2 Interchange row p and row q SWAP(Rp,Rq)
3 Add c times row p to row q (c)Rp+Rq

Example 3

To solve the system

x1+2x2+x3=43x1+8x2+7x3=202x1+7x2+9x3=23,
(11)

whose augmented coefficient matrix is exhibited in (3), we carry out the following sequence of elementary row operations, corresponding to the steps in the solution of Example 6 in Section 3.1:

[12143872027923](3)R1+R2[1214024827923](2)R1+R3[1214024803715](12)R2[1214012403715](3)R2+R3[121401240013].
(12)
(13)

The final matrix here is the augmented coefficient matrix of the system

x1+2x2+x3=4x2+2x3=4.x3=3
(14)

whose unique solution (readily found by back substitution) is x1=5, x2=2, x3=3.

It is not quite self-evident that a sequence of elementary row operations produces a linear system having the same solution set as the original system. To state the pertinent result concisely, we need the following definition.

Thus the two matrices in (10) are row equivalent, as are the two matrices in (12) and (13). In Problem 29 we ask you to show that if B can be obtained from A by elementary row operations, then A can be obtained from B by elementary row operations. This follows from the observation that row operations are “reversible.” In Problem 30 we suggest a proof of the following theorem.

Thus, the linear systems in (11) and (14) have the same solution set, because their augmented matrices in (12) and (13) are row equivalent.

Echelon Matrices

Up to this point we have been somewhat informal in our description of the method of elimination. Its objective is to transform a given linear system, by elementary row operations, into one for which back substitution leads easily and routinely to a solution. The following definition tells what should be the appearance of the augmented coefficient matrix of the transformed system.

Echelon matrices are sometimes called row-echelon matrices. Property 1 says that if E has any all-zero rows, then they are grouped together at the bottom of the matrix. The first (from the left) nonzero element in each of the other rows is called its leading entry. Property 2 says that the leading entries form a “descending staircase” pattern from upper left to lower right, as in the following echelon matrix.

Here we have highlighted the leading entries and indicated the descending staircase pattern.

The following list exhibits all possibilities for the form of a 3×3 echelon matrix, with asterisks denoting the (nonzero) leading entries; a # denotes an element that may be either zero or nonzero.

[##0#00][000000000][##0#000][##00000][0#00000][##000000][0#000000][00000000]

It follows from Properties 1 and 2 that the elements beneath any leading entry in the same column are all zero. The matrices

A=[132000015]andB=[015132000]

are not echelon matrices because A does not have Property 1 and B does not have Property 2.

Suppose that a linear system is in echelon form—its augmented matrix is an echelon matrix. Then those variables that correspond to columns containing leading entries are called leading variables; all the other variables are called free variables. The following algorithm describes the process of back substitution to solve such a system.

Example 4

The augmented coefficient matrix of the system

x12x2+3x3+2x4+x5=10x3+2x5=3x44x5=7
(15)

is the echelon matrix

[1232110001023000147].
(16)

The leading entries are in the first, third, and fourth columns. Hence x1, x3, and x4 are the leading variables and x2 and x5 are the free variables. To solve the system by back substitution, we first write

x2=s,x5=t,
(17a)

where s and t are arbitrary parameters. Then the third equation in (15) gives

x4=7+4x5=7+4t;
(17b)

the second equation gives

x3=32x5=32t;
(17c)

finally, the first equation in (15) yields

x1=10+2x23x32x4x5=10+2s3(32t)2(7+4t)t.

Therefore,

x1=5+2s3t.
(17d)

Thus the system in (15) has an infinite solution set consisting of all (x1,x2,x3,x4,x5) given in terms of the two parameters s and t as follows:

x1=5+2s3tx2=sx3=32tx4=7+4tx5=t.

For instance, with s=2 and t=1 we get the solution x1=6, x2=2, x3=5, x4=11, and x5=1.

Gaussian Elimination

Because we can use back substitution to solve any linear system already in echelon form, it remains only to establish that we can transform any matrix (using elementary row operations) into an echelon matrix. The procedure that we have already illustrated in several examples is known as Gaussian elimination. The following systematic description of the procedure makes it clear that it succeeds with any given matrix A.

In brief, we work on the matrix A one column at a time, from left to right. In each column containing a leading entry (perhaps after a row interchange), we “clear out” the nonzero elements below it and then move on to the next column.

Example 5

To solve the system

x12x2+3x3+2x4+x5=102x14x2+8x3+3x4+10x5=73x16x2+10x3+6x4+5x5=27,
(18)

we reduce its augmented coefficient matrix to echelon form as follows.

[1232110248310736106527](2)R1+R2[1232110002181336106527](3)R1+R3[12321100021813001023]SWAP(R2,R3)[12321100010230021813](2)R2+R3[1232110001023000147](1)R3[1232110001023000147]

Our final result is the echelon matrix in (16), so by Eqs. (17a)(17d) in Example 4, the infinite solution set of the system in (18) is described in terms of arbitrary parameters s and t as follows:

x1=5+2s3tx2=sx3=32tx4=7+4tx5=t.
(19)

Thus, the substitution of any two specific values for s and t in (19) yields a particular solution (x1,x2,x3,x4,x5) of the system, and each of the system’s infinitely many different solutions is the result of some such substitution.

Examples 3 and 5 illustrate the ways in which Gaussian elimination can result in either a unique solution or infinitely many solutions. On the other hand, if the reduction of the augmented matrix to echelon form leads to a row of the form

0000,

where the asterisk denotes a nonzero entry in the last column, then we have an inconsistent equation,

0x1+0x2++0xn=*,

and therefore the system has no solution.

Remark

We use algorithms such as the back substitution and Gaussian elimination algorithms of this section to outline the basic computational procedures of linear algebra. In modern numerical work, these procedures often are implemented on a computer. For instance, linear systems of more than four equations are usually solved in practice by using a computer to carry out the process of Gaussian elimination.

3.2 Problems

The linear systems in Problems 1–10 are in echelon form. Solve each by back substitution.

  1. x1+x2+2x3=5x2+3x3=6x3=2

     

  2. 2x15x2+x3=23x22x3=9x3=3

     

  3. x13x2+4x3=7x25x3=2

     

  4. x15x2+2x3=10x27x3=5

     

  5. x1+x22x3+x4=9x2x3+2x4=1x33x4=5

     

  6. x12x2+5x33x4=7x23x3+2x4=3x4=4

     

  7. x1+2x2+4x35x4=17x22x3+7x4=7

     

  8. x110x2+3x313x4=5x3+3x4=10

     

  9. 2x1+x2+x3+x4=63x2x32x4=23x3+4x4=9x4=6

     

  10. x15x2+2x37x4+11x5=0x213x3+3x47x5=0x45x5=0

In Problems 11–22, use elementary row operations to transform each augmented coefficient matrix to echelon form. Then solve the system by back substitution.

  1. 2x1+8x2+3x3=2x1+3x2+2x3=52x1+7x2+4x3=8

     

  2. 3x1+x23x3=62x1+7x2+x3=92x1+5x2=5

     

  3. x1+3x2+3x3=132x1+5x2+4x3=232x1+7x2+8x3=29

     

  4. 3x16x22x3=12x14x2+x3=17x1+2x22x3=9

     

  5. 3x1+x23x3=4x1+x2+x3=15x1+6x2+8x3=8

     

  6. 2x1+5x2+12x3=63x1+x2+5x3=125x1+8x2+21x3=17

     

  7. x14x23x33x4=42x16x25x35x4=53x1x24x35x4=7

     

  8. 3x16x2+x3+13x4=153x16x2+3x3+21x4=212x14x2+5x3+26x4=23

     

  9. 3x1+x2+x3+6x4=14x12x2+5x35x4=74x1+x2+2x3+7x4=17

     

  10. 2x1+4x2x32x4+2x5=6x1+3x2+2x37x4+3x5=95x1+8x27x3+6x4+x5=4

     

  11. x1+x2+x3=62x12x25x3=133x1+x3+x4=134x12x23x3+x4=1

     

  12. 4x12x23x3+x4=32x12x25x3=104x1+x2+2x3+x4=173x1+x3+x4=12

In Problems 23–27, determine for what values of k each system has (a) a unique solution; (b) no solution; (c) infinitely many solutions.

  1. 3x+2y=16x+4y=k

     

  2. 3x+2y=06x+ky=0

     

  3. 3x+2y=116x+ky=21

     

  4. 3x+2y=17x+5y=k

     

  5. x+2y+z=32xy3z=54x+3yz=k

     

  6. Under what condition on the constants a, b, and c does the system

    2xy+3z=ax+2y+z=b7x+4y+9z=c

    have a unique solution? No solution? Infinitely many solutions?

  7. This problem deals with the reversibility of elementary row operations.

    1. If the elementary row operation cRp changes the matrix A to the matrix B, show that (1/c)Rp changes B to A.

    2. If SWAP(Rp,Rq) changes A to B, show that SWAP(Rp,Rq) also changes B to A.

    3. If cRp+Rq changes A to B, show that (c)Rp+Rq changes B to A.

    4. Conclude that if A can be transformed into B by a finite sequence of elementary row operations, then B can similarly be transformed into A.

  8. This problem outlines a proof that two linear systems LS1 and LS2 are equivalent (that is, have the same solution set) if their augmented coefficient matrices A1 and A2 are row equivalent.

    1. If a single elementary row operation transforms A1 to A2, show directly—considering separately the three cases—that every solution of LS1 is also a solution of LS2.

    2. Explain why it now follows from Problem 29 that every solution of either system is also a solution of the other system; thus the two systems have the same solution set.

3.2 Application Automated Row Reduction

Computer algebra systems are often used to ease the labor of matrix computations, including elementary row operations. The 3×4 augmented coefficient matrix of Example 3 can be entered with the Maple command

with(linalg):
A := array( [[1, 2, 1,  4],
             [3, 8, 7, 20],
             [2, 7, 9, 23]] );

or the Mathematica command


A = {{1, 2, 1,  4},
     {3, 8, 7, 20},
     {2, 7, 9, 23}}

or the Matlab command


A = [1 2 1  4
     3 8 7 20
     2 7 9 23]

The Maple linalg package has built-in elementary row operations that can be used to carry out the reduction of A exhibited in Example 3, as follows:


A := addrow(A,1,2,-3);          # (-3)R1 + R2
A := addrow(A,1,3,-2);          # (-2)R1 + R3
A := mulrow(A,2,1/2);           # (1/2)R2
A := addrow(A,2,3,-3);          # (-3)R2 + R3

The inserted remarks, which follow the notation of Fig. 3.2.1, should make clear the structure of these row operations in Maple.

In Mathematica the ith row of the matrix A is denoted by A[[i]], and we can operate directly on rows to carry out the reduction of Example 3, as follows:


A[[2]] = (-3)A[[1]] + A[[2]];   (* (-3)R1 + R2  *)
A[[3]] = (-2)A[[1]] + A[[3]];   (* (-2)R1 + R3  *)
A[[2]] = (1/2)A[[2]];           (*  (1/2)R2     *)
A[[3]] = (-3)A[[2]] + A[[3]];   (* (-3)R2 + R3  *)

In Matlab, the ith row of the matrix A is denoted by A(i,:), and we can operate similarly on rows to carry out the reduction to echelon form, as follows:


A(2,:) = (-3)*A(1,:)   + A(2,:)  %  (-3)R1  + R2
A(3,:) = (-2)*A(1,:)   + A(3,:)  %  (-2)R1  + R3
A(2,:) = (1/2)*A(2,:)            %  (1/2)R2
A(3,:) = (-3)*A(2,:)   + A(3,:)  %  (-3)R2  + R3

You should verify (by using the computer algebra system of your choice) that these operations yield the echelon matrix

[121401240013].

If you wanted to interchange the 1st and 3rd rows—and proceed to solve the corresponding system by “forward substitution” rather than back substitution—this could be done as follows:


A := swaprow(A,1,3);
A[[{1,3}]] = A[[{3,1}]];
A([1 3],:)  = A([3 1],:)

(Maple)
(Mathematica)
(MATLAB)

These “automated” elementary row operations can be used in Problems 11–22 of this section.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.220.125.100