ADS Systems of Linear Equations

Section 12.1 Systems of Linear Equations

Subsection 12.1.1 Solutions

The method of solving systems of equations by matrices that we will look at is based on procedures involving equations that we are familiar with from previous mathematics courses. The main idea is to reduce a given system of equations to another simpler system that has the same solutions.

🔗

Definition 12.1.1. Solution Set.

🔗

Given a system of equations involving real variables

x_{1},

x_{2}, \dots,

x_{n},

the solution set of the system is the set of

n

-tuples in

R^{n},

(a_{1}, a_{2}, \dots, a_{n})

such that the substitutions

x_{1} = a_{1},

x_{2} = a_{2}, \dots,

x_{n} = a_{n}

make all the equations true.

🔗

In terms of logic, a solution set is a truth set of a system of equations, which is a proposition over

n

-tuples of real numbers.

🔗

In general, if the variables are from a set

S,

then the solution set will be a subset of

S^{n} .

For example, in number theory mathematicians study Diophantine equations, where the variables can only take on integer values instead of real values.

🔗

Definition 12.1.2. Equivalent Systems of Equations.

🔗

Two systems of linear equations are called equivalent if they have the same set of solutions.

🔗

Example 12.1.3. Two equivalent systems.

The previous definition tells us that if we know that the system

\begin{array}{l} 4 x_{1} + 2 x_{2} + x_{3} = 1 \\ 2 x_{1} + x_{2} + x_{3} = 4 \\ 2 x_{1} + 2 x_{2} + x_{3} = 3 \end{array}

is equivalent to the system

\begin{array}{l} x_{1} + 0 x_{2} + 0 x_{3} = - 1 \\ 0 x_{1} + x_{2} + 0 x_{3} = - 1 \\ 0 x_{1} + 0 x_{2} + x_{3} = 7 \end{array}

then both systems have the solution set

{(- 1, - 1, 7)} .

In other words, the simultaneous values

x_{1} = - 1,

x_{2} = - 1,

and

x_{3} = 7

are the only values of the variables that make all three equations in either system true.

🔗

Subsection 12.1.2 Elementary Operations on Equations

🔗

Theorem 12.1.4. Elementary Operations on Equations.

🔗

If any sequence of the following operations is performed on a system of equations, the resulting system is equivalent to the original system:

🔗
Interchange any two equations in the system.
🔗
Multiply both sides of any equation by a nonzero constant.
🔗
Multiply both sides of any equation by a nonzero constant and add the result to a second equation in the system, with the sum replacing the latter equation.

🔗

Let us now use the above theorem to work out the details of Example 12.1.3 and see how we can arrive at the simpler system.

🔗

The original system:

\begin{matrix} (12.1.1) & \begin{matrix} 4 x_{1} + 2 x_{2} + x_{3} = 1 \\ 2 x_{1} + x_{2} + x_{3} = 4 \\ 2 x_{1} + 2 x_{2} + x_{3} = 3 \end{matrix} \end{matrix}

🔗

Step 1. We will first change the coefficient of

x_{1}

in the first equation to one and then use it as a pivot to obtain 0’s for the coefficients of

x_{1}

in Equations 2 and 3.

🔗

Multiply Equation 1 by $\frac{1}{4}$ to obtain

$\begin{matrix} (12.1.2) & \begin{matrix} x_{1} + \frac{x_{2}}{2} + \frac{x_{3}}{4} = \frac{1}{4} \\ 2 x_{1} + x_{2} + x_{3} = 4 \\ 2 x_{1} + 2 x_{2} + x_{3} = 3 \end{matrix} \end{matrix}$
🔗

Multiply Equation 1 by $- 2$ and add the result to Equation 2 to obtain

$\begin{matrix} (12.1.3) & \begin{matrix} x_{1} + \frac{x_{2}}{2} + \frac{x_{3}}{4} = \frac{1}{4} \\ 0 x_{1} + 0 x_{2} + \frac{x_{3}}{2} = \frac{7}{2} \\ 2 x_{1} + 2 x_{2} + x_{3} = 3 \end{matrix} \end{matrix}$
🔗

Multiply Equation 1 by $- 2$ and add the result to Equation 3 to obtain

$\begin{matrix} (12.1.4) & \begin{matrix} x_{1} + \frac{x_{2}}{2} + \frac{x_{3}}{4} = \frac{1}{4} \\ 0 x_{1} + 0 x_{2} + \frac{x_{3}}{2} = \frac{7}{2} \\ 0 x_{1} + x_{2} + \frac{x_{3}}{2} = \frac{5}{2} \end{matrix} \end{matrix}$

🔗

We’ve explicitly written terms with zero coefficients such as

0 x_{1}

to make a point that all variables can be thought of as being involved in all equations. After this example is complete, we will discontinue this practice in favor of the normal practice of making these terms “disappear.”

🔗

Step 2. We would now like to proceed in a fashion analogous to Step 1; namely, multiply the coefficient of

x_{2}

in the second equation by a suitable number so that the result is 1. Then use it as a pivot to obtain 0’s as coefficients for

x_{2}

in the first and third equations. This is clearly impossible (Why?), so we will first interchange Equations 2 and 3 and proceed as outlined above.

🔗

Exchange Equations 2 and 3 to obtain

$\begin{matrix} (12.1.5) & \begin{matrix} x_{1} + \frac{x_{2}}{2} + \frac{x_{3}}{4} = \frac{1}{4} \\ 0 x_{1} + x_{2} + \frac{x_{3}}{2} = \frac{5}{2} \\ 0 x_{1} + 0 x_{2} + \frac{x_{3}}{2} = \frac{7}{2} \end{matrix} \end{matrix}$
🔗

Multiply Equation 2 by $\frac{1}{2}$ and subtract the result from Equation 1 to obtain

$\begin{matrix} (12.1.6) & \begin{matrix} x_{1} + 0 x_{2} + 0 x_{3} = - 1 \\ 0 x_{1} + x_{2} + \frac{x_{3}}{2} = \frac{5}{2} \\ 0 x_{1} + 0 x_{2} + \frac{x_{3}}{2} = \frac{7}{2} \end{matrix} \end{matrix}$

🔗

Step 3. Next, we will change the coefficient of

x_{3}

in the third equation to one and then use it as a pivot to obtain 0’s for the coefficients of

x_{3}

in Equations 1 and 2. Notice that the coefficient of

x_{3}

is already zero in Equation 1, so we have been saved some work!

🔗

Multiply Equation 3 by $2$ to obtain

$\begin{matrix} x_{1} + 0 x_{2} + 0 x_{3} = - 1 \\ 0 x_{1} + x_{2} + \frac{x_{3}}{2} = \frac{5}{2} \\ 0 x_{1} + 0 x_{2} + x_{3} = 7 \end{matrix}$
🔗

Multiply Equation 3 by $- 1 / 2$ and add the result to Equation 2 to obtain

$\begin{matrix} (12.1.7) & \begin{matrix} x_{1} + 0 x_{2} + 0 x_{3} = - 1 \\ 0 x_{1} + x_{2} + 0 x_{3} = - 1 \\ 0 x_{1} + 0 x_{2} + x_{3} = 7 \end{matrix} \end{matrix}$

🔗

From the system of equations at the end of Step 3, we see that the solution to the original system is

x_{1} = - 1,

x_{2} = - 1,

and

x_{3} = 7 .

🔗

Subsection 12.1.3 Transition to Matrices

🔗

In the above sequence of steps, we note that the variables serve the sole purpose of keeping the coefficients in the appropriate location. This we can effect by using matrices. The matrix of the original system in our example is

(\begin{array}{cccc} 4 & 2 & 1 & 1 \\ 2 & 1 & 1 & 4 \\ 2 & 2 & 1 & 3 \end{array})

🔗

where the matrix of the first three columns is called the coefficient matrix and the complete matrix is referred to as the augmented matrix. Since we are now using matrices to solve the system, we will translate Theorem 12.1.4 into matrix language.

🔗

Subsection 12.1.4 Elementary Row Operations

🔗

Theorem 12.1.5. Elementary Row Operations.

🔗

If any sequence of the following operations is performed on the augmented matrix of a system of equations, the resulting matrix is a system that is equivalent to the original system. The following operations on a matrix are called elementary row operations:

🔗
Exchange any two rows of the matrix.
🔗
Multiply any row of the matrix by a nonzero constant.
🔗
Multiply any row of the matrix by a nonzero constant and add the result to a second row, with the sum replacing that second row.

🔗

Definition 12.1.6. Row Equivalent Matrices.

🔗

Two matrices,

A

and

B,

are said to be row-equivalent if one can be obtained from the other by any sequence of zero or more elementary row operations.

🔗

If we use the notation

R_{i}

to stand for Row

i

of a matrix and

⟶

to stand for row equivalence, then

A \overset{c R_{i} + R_{j}}{⟶} B

🔗

means that the matrix

B

is obtained from the matrix

A

by multiplying the Row

i

A

c

and adding the result to Row

j .

The operation of multiplying row

i

c

is indicated by

A \overset{c R_{i}}{⟶} B

🔗

while exchanging rows

i

and

j

is denoted by

A \overset{R_{i} \leftrightarrow R_{j}}{⟶} B .

🔗

The matrix notation for the system given in our first example, with the subsequent steps, is:

\begin{aligned} (\begin{array}{cccc} 4 & 2 & 1 & 1 \\ 2 & 1 & 1 & 4 \\ 2 & 2 & 1 & 3 \end{array}) & \overset{\frac{1}{4} R_{1}}{⟶} (\begin{array}{cccc} 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ 2 & 1 & 1 & 4 \\ 2 & 2 & 1 & 3 \end{array}) \overset{- 2 R_{1} + R_{2}}{⟶} (\begin{array}{cccc} 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ 0 & 0 & \frac{1}{2} & \frac{7}{2} \\ 2 & 2 & 1 & 3 \end{array}) \\ \overset{- 2 R_{1} + R_{3}}{⟶} (\begin{array}{cccc} 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ 0 & 0 & \frac{1}{2} & \frac{7}{2} \\ 0 & 1 & \frac{1}{2} & \frac{5}{2} \end{array}) \overset{R_{2} \leftrightarrow R_{3}}{⟶} (\begin{array}{cccc} 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ 0 & 1 & \frac{1}{2} & \frac{5}{2} \\ 0 & 0 & \frac{1}{2} & \frac{7}{2} \end{array}) \\ \overset{- \frac{1}{2} R_{2} + R_{1}}{⟶} (\begin{array}{cccc} 1 & 0 & 0 & - 1 \\ 0 & 1 & \frac{1}{2} & \frac{5}{2} \\ 0 & 0 & \frac{1}{2} & \frac{7}{2} \end{array}) \overset{2 R_{3}}{⟶} (\begin{array}{cccc} 1 & 0 & 0 & - 1 \\ 0 & 1 & \frac{1}{2} & \frac{5}{2} \\ 0 & 0 & 1 & 7 \end{array}) \\ \overset{- \frac{1}{2} R_{3} + R_{2}}{⟶} (\begin{array}{cccc} 1 & 0 & 0 & - 1 \\ 0 & 1 & 0 & - 1 \\ 0 & 0 & 1 & 7 \end{array}) \end{aligned}

🔗

This again gives us the solution. This procedure is called the Gauss-Jordan elimination method.

🔗

It is important to remember when solving any system of equations via this or any similar approach that at any step in the procedure we can rewrite the matrix in “equation format” to help us to interpret the meaning of the augmented matrix.

🔗

In our first example we found a unique solution, only one triple, namely

(- 1, - 1, 7),

which satisfies all three equations. For a system involving three unknowns, are there any other possible results? To answer this question, let’s review some basic facts from analytic geometry.

🔗

The graph of a linear equation in three-dimensional space is a plane. So geometrically we can visualize the three linear equations as three planes in three-space. Certainly the three planes can intersect in a unique point, as in the first example, or two of the planes could be parallel. If two planes are parallel, there are no common points of intersection; that is, there are no triple of real numbers that will satisfy all three equations. Another possibility is that the three planes could intersect along a common axis or line. In this case, there would be an infinite number of real number triples in

R^{3} .

Yet another possibility would be if the first two planes intersect in a line, but the line is parallel to, but not on, the third plane, giving us no solution. Finally if all three equations describe the same plane, the solution set would be that plane.

🔗

We can generalize these observations. In a system of

n

linear equations,

n

unknowns, there can be

🔗
a unique solution,
🔗
no solution, or
🔗
an infinite number of solutions.

🔗

To illustrate these points, consider the following examples:

🔗

Example 12.1.7. A system with no solutions.

Find all solutions to the system

\begin{array}{l} x_{1} + 3 x_{2} + x_{3} = 2 \\ x_{1} + x_{2} + 5 x_{3} = 4 \\ 2 x_{1} + 2 x_{2} + 10 x_{3} = 6 \end{array}

The reader can verify that the augmented matrix of this system,

(\begin{array}{cccc} 1 & 3 & 1 & 2 \\ 1 & 1 & 5 & 4 \\ 2 & 2 & 10 & 6 \end{array}),

reduces to

(\begin{array}{cccc} 1 & 3 & 1 & 2 \\ 1 & 1 & 5 & 4 \\ 0 & 0 & 0 & - 2 \end{array}) .

We can attempt to row-reduce this matrix further if we wish. However, any further row-reduction will not substantially change the last row, which, in equation form, is

0 x_{1} + 0 x_{2} + 0 x_{3} = - 2,

or simply

0 = - 2 .

It is clear that we cannot find real numbers

x_{1},

x_{2},

and

x_{3}

that will satisfy this equation. Hence we cannot find real numbers that will satisfy all three original equations simultaneously. When this occurs, we say that the system has no solution, or the solution set is empty.

🔗

Example 12.1.8. A system with an infinite number of solutions.

Next, let’s attempt to find all of the solutions to:

\begin{array}{l} x_{1} + 6 x_{2} + 2 x_{3} = 1 \\ 2 x_{1} + x_{2} + 3 x_{3} = 2 \\ 4 x_{1} + 2 x_{2} + 6 x_{3} = 4 \end{array}

The augmented matrix for the system is

\begin{array}{r} (12.1.8) & (\begin{array}{cccc} 1 & 6 & 2 & 1 \\ 2 & 1 & 3 & 2 \\ 4 & 2 & 6 & 4 \end{array}) \end{array}

which reduces to

\begin{array}{r} (12.1.9) & (\begin{array}{cccc} 1 & 0 & \frac{16}{11} & 1 \\ 0 & 1 & \frac{1}{11} & 0 \\ 0 & 0 & 0 & 0 \end{array}) \end{array}

If we apply additional elementary row operations to this matrix, it will only become more complicated. In particular, we cannot get a one in the third row, third column. Since the matrix is in simplest form, we will express it in equation format to help us determine the solution set.

\begin{matrix} (12.1.10) & \begin{array}{l} x_{1} + \frac{16}{11} x_{3} = 1 \\ x_{2} + \frac{1}{11} x_{3} = 0 \\ 0 = 0 \end{array} \end{matrix}

Any real numbers will satisfy the last equation. However, the first equation can be rewritten as

x_{1} = 1 - \frac{16}{11} x_{3},

which describes the coordinate

x_{1}

in terms of

x_{3}

. Similarly, the second equation gives

x_{2}

in terms of

x_{3}

. A convenient way of listing the solutions of this system is to use set notation. If we call the solution set of the system

S,

then

S = {(1 - \frac{16}{11} x_{3}, - \frac{1}{11} x_{3}, x_{3}) ∣ x_{3} \in R} .

What this means is that if we wanted to list all solutions, we would replace

x_{3}

by all possible numbers. Clearly, there is an infinite number of solutions, two of which are

(1, 0, 0)

and

(- 15, - 1, 11),

when

x_{3}

takes on the values 0 and 11, respectively.

A Word Of Caution: Frequently we may can get “different-looking” answers to the same problem when a system has an infinite number of solutions. Assume the solutions set in this example is reported to be

A = {(1 + 16 x_{2}, x_{2}, - 11 x_{3}) ∣ x_{3} \in R} .

Certainly the result described by

S

looks different from that described by

A .

To see whether they indeed describe the same set, we wish to determine whether every solution produced in

S

can be generated in

A .

For example, the solution generated by

S

when

x_{3} = 11

(- 15, - 1, 11) .

The same triple can be produced by

A

by taking

x_{2} = - 1 .

We must prove that every solution described in

S

is described in

A

and, conversely, that every solution described in

A

is described in

S .

(See Exercise 6 of this section.)

🔗

To summarize the procedure in the Gauss-Jordan technique for solving systems of equations, we attempt to obtain 1’s along the main diagonal of the coefficient matrix with 0’s above and below the diagonal. We may find in attempting this that this objective cannot be completed, as in the last two examples we have seen. Depending on the way we interpret the results in equation form, we either recognize that no solution exists, or we identify “free variables” on which an infinite number of solutions are based. The final matrix forms that we have produced in our examples are referred to as echelon forms.

🔗

In practice, larger systems of linear equations are solved using computers. Generally, the Gauss-Jordan algorithm is the most useful; however, slight variations of this algorithm are also used. The different approaches share many of the same advantages and disadvantages. The two major concerns of all methods are:

🔗
minimizing inaccuracies due to round-off errors, and
🔗
minimizing computer time.

🔗

Subsection 12.1.5 The Gauss-Jordan Algorithm

🔗

The accuracy of the Gauss-Jordan method can be improved by always choosing the element with the largest absolute value as the pivot element, as in the following algorithm.

🔗

Algorithm 12.1.9. The Gauss-Jordan Algorithm.

🔗

Given a matrix equation

A x = b,

where A is

n \times m,

let

C

be the augmented matrix

[A | b] .

The process of row-reducing to echelon form involves performing the following algorithm where

C [i]

is the

i^{th}

row of

C .

🔗
i = 1
🔗
j = 1
🔗

while i <= n and j <= m):
1. 🔗
  maxi=i
2. 🔗
  for k = i+1 to n:
  
  🔗
  if abs(C[k,j])>abs(C[maxi,j]): then maxi=k
3. 🔗
  
  if C[maxi,j] != 0 then:
  1. 🔗
    exchange rows i and maxi
  2. 🔗
    divide each entry in row i by C[i,j]
  3. 🔗
    for u = i+1 to n:
    
    🔗
    subtract C[u,j]*C[i] from C[u]
  4. 🔗
    i = i+1
4. 🔗
  j=j+1

🔗

Note 12.1.10.

🔗

At the end of this algorithm, with the final form of

C

you can revert back to the equation form of the system and a solution should be clear. In general,

🔗
If any row of $C$ is all zeros, it can be ignored.
🔗
If any row of $C$ has all zero entries except for the entry in the $(m + 1)^{st}$ position, the system has no solution. Otherwise, if a column has no pivot, the variable corresponding to it is a free variable. Variables corresponding to pivots are basic variables and can be expressed in terms of the free variables.

🔗

Example 12.1.11.

If we apply The Gauss-Jordan Algorithm to the system

\begin{array}{l} 5 x_{1} + x_{2} + 2 x_{3} + x_{4} = 2 \\ 3 x_{1} + x_{2} - 2 x_{3} = 5 \\ x_{1} + x_{2} + 3 x_{3} - x_{4} = - 1 \end{array}

the augmented matrix is

(\begin{array}{ccccc} 5 & 1 & 2 & 1 & 2 \\ 3 & 1 & - 2 & 0 & 5 \\ 1 & 1 & 3 & - 1 & - 1 \end{array})

is reduced to

(\begin{array}{ccccc} 1 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 0 & - \frac{3}{2} & \frac{3}{2} \\ 0 & 0 & 1 & 0 & - 1 \end{array})

Therefore,

x_{4}

is a free variable in the solution and general solution of the system is

x = (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}) = (\begin{matrix} \frac{1}{2} - \frac{1}{2} x_{4} \\ \frac{3}{2} + \frac{3}{2} x_{4} \\ - 1 \\ x_{4} \end{matrix})

This conclusion is easy to see if you revert back to the equations that the final value the reduced matrix represents.

🔗

Subsection 12.1.6 SageMath Note - Matrix Reduction

🔗

Given an augmented matrix,

C,

there is a matrix method called echelon_form that can be used to row reduce

C .

Here is the result for the system in Example 12.1.11. In the assignment of a matrix value to

C,

notice that the first argument is QQ, which indicates that the entries should be rational numbers. As long as all the entries are rational, which is the case here since integers are rational, the row-reduced matrix will be all rational.


    
        
xxxxxxxxxx
 
1
C = Matrix(QQ,[[5,1,2,1,2],[3,1,-2,0,5],[1,1,3,-1,-1]])
2
C.echelon_form()

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

If we don’t specify the set from which entries are taken, it would assumed to be the integers and we do not get a fully row-reduced matrix. This is because the next step in working with the next output would involve multiplying row 2 by

\frac{1}{2}

and row 3 by

\frac{1}{9},

but these multipliers are not integers.


    
        
xxxxxxxxxx
 
1
C2 = Matrix([[5,1,2,1,2],[3,1,-2,0,5],[1,1,3,-1,-1]])
2
C2.echelon_form()

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

If we specifying real entries, the result isn’t as nice and clean as the rational output.


    
        
xxxxxxxxxx
 
1
C3 = Matrix(RR,[[5,1,2,1,2],[3,1,-2,0,5],[1,1,3,-1,-1]])
2
C3.echelon_form()

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

The default number of decimal places may vary from what you see here, but it can be controlled. The single small number in row three column four isn’t exactly zero because of round-off but we could just set it to zero.

🔗

Exercises 12.1.7 Exercises

🔗

1.

🔗

Solve the following systems by describing the solution sets completely:

🔗
$\begin{array}{l} 2 x_{1} + x_{2} = 3 \\ x_{1} - x_{2} = 1 \end{array}$
🔗
$\begin{array}{l} 2 x_{1} + x_{2} + 3 x_{3} = 5 \\ 4 x_{1} + x_{2} + 2 x_{3} = - 1 \\ 8 x_{1} + 2 x_{2} + 4 x_{3} = - 2 \end{array}$
🔗
$\begin{array}{l} x_{1} + x_{2} + 2 x_{3} = 1 \\ x_{1} + 2 x_{2} - x_{3} = - 1 \\ x_{1} + 3 x_{2} + x_{3} = 5 \end{array}$
🔗
$\begin{array}{l} x_{1} - x_{2} + 3 x_{3} = 7 \\ x_{1} + 3 x_{2} + x_{3} = 4 \end{array}$

Answer.

${(4 / 3, 1 / 3)}$
${(\frac{1}{2} x_{3} - 3, - 4 x_{3} + 11, x_{3}) ∣ x_{3} \in R}$
${(- 5, 14 / 5, 8 / 5)}$
${(6.25 - 2.5 x_{3}, - 0.75 + 0.5 x_{3}, x_{3}) ∣ x_{3} \in R}$

🔗

2.

🔗

Solve the following systems by describing the solution sets completely:

🔗
$\begin{array}{l} 2 x_{1} + 2 x_{2} + 4 x_{3} = 2 \\ 2 x_{1} + x_{2} + 4 x_{3} = 0 \\ 3 x_{1} + 5 x_{2} + x_{3} = 0 \end{array}$
🔗
$\begin{array}{l} 2 x_{1} + x_{2} + 3 x_{3} = 2 \\ 4 x_{1} + x_{2} + 2 x_{3} = - 1 \\ 8 x_{1} + 2 x_{2} + 4 x_{3} = 4 \end{array}$
🔗
$\begin{array}{l} x_{1} + x_{2} + 2 x_{3} + x_{4} = 3 \\ x_{1} - x_{2} + 3 x_{3} - x_{4} = - 2 \\ 3 x_{1} + 3 x_{2} + 6 x_{3} + 3 x_{4} = 9 \end{array}$
🔗
$\begin{array}{l} 6 x_{1} + 7 x_{2} + 2 x_{3} = 3 \\ 4 x_{1} + 2 x_{2} + x_{3} = - 2 \\ 6 x_{1} + x_{2} + x_{3} = 1 \end{array}$
🔗
$\begin{array}{l} x_{1} + x_{2} - x_{3} + 2 x_{4} = 1 \\ x_{1} + 2 x_{2} + 3 x_{3} + x_{4} = 5 \\ x_{1} + 3 x_{2} + 2 x_{3} - x_{4} = - 1 \end{array}$

🔗

3.

🔗

Given the final augmented matrices below from the Gauss-Jordan Algorithm, identify the solutions sets. Identify the basic and free variables, and describe the solution set of the original system.

🔗
$(\begin{array}{ccccc} 1 & 0 & - 5 & 0 & 1.2 \\ 0 & 1 & 4 & 0 & 2.6 \\ 0 & 0 & 0 & 1 & 4.5 \end{array})$
🔗
$(\begin{array}{cccc} 1 & 0 & 9 & 3 \\ 0 & 1 & 0 & 4 \\ 0 & 0 & 0 & 1 \end{array})$
🔗
$(\begin{array}{cccc} 1 & 0 & 6 & 5 \\ 0 & 1 & - 2 & 1 \\ 0 & 0 & 0 & 0 \end{array})$
🔗
$(\begin{array}{ccccc} 1 & 0 & 0 & - 3 & 1 \\ 0 & 1 & 0 & 2 & 2 \\ 0 & 0 & 1 & - 1 & 1 \end{array})$

Answer.

Basic variables: $x_{1},$ $x_{2}$ and $x_{4} .$ Free variable: $x_{3} .$ Solution set: ${(1.2 + 5 x_{3}, 2.6 - 4 x_{3}, 4.5) ∣ x_{3} \in R}$
Basic variables: $x_{1}$ and $x_{2} .$ Free variable: $x_{3} .$ The solution set is empty because the last row of the matrix converts to the inconsistent equation $0 = 1 .$
Basic variables: $x_{1}$ and $x_{2} .$ Free variable: $x_{3} .$ Solution set: ${(- 6 x_{3} + 5, 2 x_{3} + 1, x_{3}) ∣ x_{3} \in R}$
Basic variables: $x_{1},$ $x_{2}$ and $x_{3} .$ Free variable: $x_{4} .$ Solution set: ${(3 x_{4} + 1, - 2 x_{4} + 2, x_{4} + 1, x_{4}) ∣ x_{4} \in R}$

🔗

4.

🔗

🔗
Write out the details of Example 12.1.7.
🔗
Write out the details of Example 12.1.8.
🔗
Write out the details of Example 12.1.11.

🔗

5.

🔗

Solve the following systems using only mod 5 arithmetic. Your solutions should be

n - tuples

from

Z_{5} .

🔗
$\begin{array}{l} 2 x_{1} + x_{2} = 3 \\ x_{1} + 4 x_{2} = 1 \end{array}$ (compare your solution to the system in 5(a))
🔗
$\begin{array}{l} x_{1} + x_{2} + 2 x_{3} = 1 \\ x_{1} + 2 x_{2} + 4 x_{3} = 4 \\ x_{1} + 3 x_{2} + 3 x_{3} = 0 \end{array}$

Answer.

${(3, 0)}$
${(3, 0, 4)}$

🔗

6.

🔗

🔗
Use the solution set $S$ of Example 12.1.8 to list three different solutions to the given system. Then show that each of these solutions can be described by the set $A$ in the same example.
🔗
Prove that $S = A .$

🔗

7.

🔗

Given a system of

n

linear equations in

n

unknowns in matrix form

A X = b,

prove that if

b

is a matrix of all zeros, then the solution set of

A X = b

is a subgroup of

R^{n} .

Answer.

Proof: Since

b

is the

n \times 1

matrix of 0{’}s, let’s call it

0 0 .

Let S be the set of solutions to

A X = 0 0 .

X_{1}

and

X_{2}

be in

S .

Then

A (X_{1} + X_{2}) = A X_{1} + A X_{2} = 0 0 + 0 0 = 0 0

X_{1} + X_{2} \in S;

or in other words,

S

is closed under addition in

R^{n} .

The identity of

R^{n}

0 0,

which is in

S .

Finally, let

X

be in

S .

Then

A (- X) = - (A X) = - 0 0 = 0 0

and so

- X

is also in

S .

Applied Discrete Structures

Search Results:

Section 12.1 Systems of Linear Equations

Subsection 12.1.1 Solutions

Definition 12.1.1. Solution Set.

Definition 12.1.2. Equivalent Systems of Equations.

Example 12.1.3. Two equivalent systems.

Subsection 12.1.2 Elementary Operations on Equations

Theorem 12.1.4. Elementary Operations on Equations.

Subsection 12.1.3 Transition to Matrices

Subsection 12.1.4 Elementary Row Operations

Theorem 12.1.5. Elementary Row Operations.

Definition 12.1.6. Row Equivalent Matrices.

Example 12.1.7. A system with no solutions.

Example 12.1.8. A system with an infinite number of solutions.

Subsection 12.1.5 The Gauss-Jordan Algorithm

Algorithm 12.1.9. The Gauss-Jordan Algorithm.

Note 12.1.10.

Example 12.1.11.

Subsection 12.1.6 SageMath Note - Matrix Reduction

Exercises 12.1.7 Exercises

1.

2.

3.

4.

5.

6.

7.