Gaussian Elimination: Matrices

Row reduction methods

The technique used to solve systems of linear equations (Gaussian elimination) can be carried out using matrices as follows. To solve the system  

we begin by writing down the augmented matrix of coefficients and right-hand sides H = [ A  b ]:

Then as in Gaussian elimination, we try to make the terms below the leading diagonal zero. Note that we do not need to write down the equations for at this stage, we can simply deal with the numerical coefficients.

1. Replace Row2 by Row2 - 2 ⨯ Row1:

2. Replace Row3 by Row3 -  Row1:

3. Replace Row3 by Row3 - 3⨯ Row2:

Now we rewrite the rows of the augemented matrix as equations for  . The 3rd row gives

The 2nd row gives

The 1st row gives

The solution as we had before.

Example

Consider the set of equations

We begin by writing down the augmented matrix of coefficients and right-hand sides H = [ A  b ]:

The solution to our original system can be obtained by carrying out elementary row operations on the augmented matrix H.

We now use back substitution to obatin the solution. This gives (starting with the bottom row):

Elementary row operations

The operations we carried out above are examples of elementary row operations (EROs). There are three types of elementary row operations:

(1)  interchange any two rows ;

This is equivalent to swapping the order of any two equations.

(2)  multiply any row by any non-zero constant ;

This is equivalent to multiplying any given equation by the constant.

(2)  add the multiple of one row to another ;

This is equivalent to adding the multiple of one equation to another.

It is important to distinguish EROs from the broader range of operations that may be applied to determinants. For example, operations to columns are not allowed when solving a system of equations by EROs.

Note

The solution scheme of Gaussian elimnation described above, exploits the fact that if [ A' b' ] is derived from [ A b ] by a sequence of EROs, then the problems A x = b  and A' x = b' are equivalent.

Example application: Electrical network

KIRCHOFF's CURRENT LAW:  At any point of a circuit (including the battery), the sum of the inflowing currents equals the sum of the outgoing currents.

KIRCHOFF's VOLTAGE LAW:  In any closed loop, the sum of the voltage drops equals the impressed electromotive force.

OHM's LAW:   The voltage drop across any resistor of resistance, R Ohms, is given by V = I R, where I (measured in Amps) is the current passing through the resistor.

Node P:     ;

Node Q:     ;

Right loop:     ;

Left loop:     .

Hence we can construct the augmented matrix H = [ A b ]:

The pivot row (or equation) is the first row with the non-zero    term. Also notice that the first two rows are, in fact, the same equation.

Now move row 2 to the end so that we have a non-zero   term in the pivot row (this process is known as PARTIAL PIVOTING).

Note that the last equation is redundant as it contains no new information.

We can now use back-substitution to find the solution:

Hence the solution is Amps, Amps, and Amps.

Determined/underdetermined/overdetermined systems.

Note that in the example above we had 4 equations in 3 unknowns.

When the number of equations equals the number of unkowns the system is said to be determined.

When the number of equations is less than the number of unkowns the system is said to be underdetermined.

When the number of equations is greater than the number of unkowns the system is said to be overdetermined.

So in the electrical circuit example above the system was overdetermined (though in fact we managed to solve the system to find a unique solution).

Example

Consider the system

To solve, construct the augmented matrix H = [ A b ]:

i.e.

This system has no solution.

Guass-Jordan method

The Gauss-Jordan methos is a continuation of the Gaussian elimination process (and as we'll see in the next section is used to calculate the inverse of the matrix of coefficients).

Start by constructing the augmented matrix H = [ A b ]:

At this point, with Gaussian elimination, we would back-substitute by first solving the 3rd equation etc. In the Gauss-Jordan method we continue applying EROs to reduce the left-hand submatrix to the 3⨯3 identity matrix:

The solution to this system is therefore s , , and .