Gauss-Jordan Elimination

Gauss-Jordan Elimination is a method for solving a linear system of equations. The method is named after Carl Friedrich Gauss and Wilhelm Jordan.

The content in today's blog is taken from Linear Algebra with Applications by Gareth Williams.

Consider the following system of linear equations:

x₁ - x₂ + 2x₃ = 3

2x₁ - 2x₂ + 5x₃ = 4

x₁ + 2x₂ - x₃ = -3

2x₂ + 2x₃ = 1

To use Gauss-Jordan Elimination, we start by representing the given system of linear equations as an augmented matrix.

Definition 1: Augmented Matrix Form

An augmented matrix is a matrix representation of a system of linear equations where each row of the matrix is the coefficients of the given equation and the equation's result.

Example 1:

The following system of linear equations:

x₁ - x₂ + 2x₃ = 3

2x₁ - 2x₂ + 5x₃ = 4

x₁ + 2x₂ - x₃ = -3

2x₂ + 2x₃ = 1

would be represented as:



The goal of Gauss-Jordan elimination is to transform the matrix into reduced echelon form.

Definition 2: Reduced Echelon Form

A matrix is said to be in reduced echelon form if:

(1) Any rows consisting entirely of zeros are grouped at the bottom of the matrix.

(2) The first nonzero element of any row is 1. This element is called a leading 1.

(3) The leading 1 of each row after the first is positioned to the right of the leading 1 of the previous row.

(4) If a column contains a leading 1, then all other elements in that column are 0.

Here are some examples of matrices that are not in reduced echelon form.

The matrix below violates (1). The rows consisting entirely of 0's are not grouped at the bottom.



The matrix below violates (2). In row 2, the first nonzero element is not a 1.



The matrix below violates (3). In row 3, the leading 1 is not to the right of the leading 1 in row 2.



The matrix below violates (4). The column associated with the leading 1 in row 2 contains a nonzero value.



Below are some examples of matrices that are in reduced echelon form:







Next, we need to use elementary row operations so the matrix results in reduced echelon form. The elementary row operations are operations that the result matrix represents the same system of linear equations. In other words, the two matrices are row equivalent.

Definition 3: Row Equivalence (Equivalent Systems)

Two matrices are row equivalent if they represent the same system of linear equations. They are also called equivalent systems.

The following three elementary operations preserve row equivalence. That is, the resulting matrix is row equivalent to the matrix before the operation.

(1) Interchanging two rows
(2) Multiplying the elements of a row by a nonzero constant
(3) Adding the elements of one row to the corresponding elements of another row.

(1) is clear. Changing the order of the linear equations does not change the values that solve them. (2) is equivalent to multiplying the same value to both sides of the equation. (3) is the idea that two linear equations imply that their sum is also a valid linear equation. In actual practice, we will combine (2) and (3) to get: (4) Add a multiple of the elements of one row to the corresponding elements of another row.

So, the following elementary operations result in a matrix that is row equivalent to the previous matrix:

Definition 4: Elementary Operations

(1) Row Exchange: The exchange of two rows.
(2) Row Scaling: Multiply the elements of a row by a nonzero constant.
(3) Row Replacement: Add a multiple of the elements of one row to the corresponding elements of another row.

Once the matrix is in reduced echelon form, we can convert the matrix back into a linear system of equations to see the solution.

Here's the full algorithm:

Definition 5: Gauss-Jordan Elimination

(1) Represent the linear system of equations as a matrix in augmented matrix form

(2) Use elementary row operations to derive a matrix in reduced echelon form

(3) Write the system of linear equations corresponding to the reduced echelon form.

Algorithm 1: Gauss-Jordan Elimination Algorithm

(1) Let A = an m x n matrix with m rows and n columns.

(2) Let k = 1, A_k = A, i=1

(3) If A_k is all zero's, then we are done and the A is in reduced echelon form.

(4) Let C_v be the first nonzero column in A_k such that C_v is not all zero's and v ≥ i.

(5) Let a_u,v be the first nonzero element in C_v such that u ≥ k.

(6) Let R_u be the row in A where a_u,v is found in C_v.

(7) R_u = R_u*(1/a_u,v) [After this, R_u has a leading 1, see proof below for explanation]

(8) If u ≠ k, then exchange R_u and R_k.

(9) For each row R_w in A, if w ≠ k, then R_w = R_w + (-a_w,v)*R_k [After this, the only nonzero element in C_v is found at a_k,v, see proof below for explanation if needed]

(10) If k = m, then we are done and A is in reduced echelon form.

(11) Otherwise, we designate a partion of A_k such that:



[Note: In other words, A_k+1 = all but the top row of A_k]

(12) Let k = k + 1; i = v; and go to step #3

End

Here's an example:

Example 2: Using Gauss-Jordan Elimination

(1) We start with a system of linear equations:

x₁ - 2x₂ + 4x₃ = 12

2x₁ - x₂ + 5x₃ = 18

-x₁ + 3x₂ - 3x₃ = -8

(2) We represent them in augmented matrix form:



(3) We use elementary row operations to put this matrix into reduced echelon form (I will use R1, R2, R3 for Row 1, Row 2, and Row 3):

(a) Let R2 = R2 + (-2)R1 [Operation #3]



(b) Let R3 = R3 + R1 [Operation #3]



(c) Let R2 = (1/3)R2 [Operation #2]



(d) Let R1 = R1 + 2*R2 [Operation #3]



(e) Let R3 = R3 + (-1)*R2 [Operation #3]



(f) Let R3 = (1/2)R3 [Operation #2]



(g) Let R1 = R1 + (-2)*R3 [Operation #3]



(h) Let R2 = R2 + R3 [Operation #3]



(4) We now write down the system of linear equations corresponding to the reduced echelon form:

x₁ = 2

x₂ = 1

x₃ = 3

Of course, we need to be sure that we can always get to reduced echelon form. Here is the theorem that guarantees this:

Theorem 1: Every matrix is row equivalent to a reduced echelon form matrix

Proof:

(1) The Gauss-Jordan Elimination Algorithm works for any 1 x n matrix.

(a) Let A = 1 x n matrix

(b) Assume that A is not all zeros (if it were, then A is already in reduced echelon form)

(c) Let a_1,i be the first nonzero element in A.

(d) Let A = (1/a_1,i)*A

(f) A now has a leading 1 and since this is a one-row matrix, A is now in reduced echelon form.

(2) Assume that the Gauss-Jordan Elimination Algorithm works for any matrix up to k rows.

(3) We can now show that it will work for a matrix with k+1 rows.

(a) Let A = a nonzero matrix with k+1 rows [We can assume it is nonzero since if it were zero, it would already be in reduced echelon form]

(b) Assume that we've run the Gauss-Jordan Elimination Algorithm up to the kth row so that if we define B such that:



(c) We can see that B is in reduced echelon form since

(i) B has k rows

(ii) We can assume by our assumption in step #2 that the algorithm works for any matrix of k rows or less

(iii) The algorithm leaves B unchanged if we run it again.

(d) We can also see that A_k+1 consists of a single row which is zero for every column where there is a leading 1 in B. [Since these are zero'd out by the algorithm above]

(e) If there is a nonzero column in A_k+1, it must therefore be to the right of all the leading 1s in B.

(f) Assume that there is a nonzero column in A_k+1 [If there were not, we would be done, since then A_k+1 would consist of all zero's and A would then be in reduced echelon form]

(g) In this case, none of the rows in B are all zeros. [In order for A_k+1 to be nonzero, each of the previous rows must have had at least one nonzero column. If one was all zeros, it would have been exchanged with A_k+1 and then A_k+1 would be all zeros which it is not]

(h) Let a_k+1,x = the first nonzero element in A_k+1

(i) Let A_k+1 = (1/a_k+1,x)A_k+1

(j) For all rows i, 1 thru k, let R_i = R_i + (-a_i,x)*R_k+1.

(k) Clearly, this will zero out each of the remaining rows.

(l) A is now in reduced echelon form since:

(a) Any rows consisting entirely of zeros are grouped at the bottom of the matrix. [Note: there are none]

(b) The first nonzero element of any row is 1. [We assumed this was true of all rows in B and now we have shown it is also true of R_k+1]

(c) The leading 1 of each row after the first is positioned to the right of the leading 1 of the previous row. [From step #3e]

(d) If a column contains a leading 1, then all other elements in that column are 0. [From step #3j]

QED

References

• Gareth Williams, Linear Algebra with Applications, Wm. C. Brown Publishers, 1996.
• "Row Reduction", PlanetMath.org
• Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.

Properties of Matrix Multiplication

Multiplication can only occur between matrices A and B if the number of columns in A match the number of rows in B. This presents the very important idea that while multiplication of A with B might be a perfectly good operation; this does not guarantee that multiplication of B with A is a perfectly good operation.

Even if matrix A can be multiplied with matrix B and matrix B can be multiplied to matrix A, this doesn't necessarily give us that AB=BA. In other words, unlike the integers, matrices are noncommutative.

Property 1: Associative Property of Multiplication

A(BC) = (AB)C

where A,B, and C are matrices of scalar values.

Proof:

(1) Let D = AB, G = BC
(2) Let F = (AB)C = DC
(3) Let H = A(BC) = AG
(4) Using Definition 1, here, we have for each D,F,G,H:

d_i,j = ∑_k a_i,k*b_k,j

g_i,j = ∑_k b_i,k*c_k,j

f_i,j = ∑_k d_i,k*c_k,j

(5) So, expanding f_i,j gives us:

f_i,j = ∑_k (∑_l a_i,l*b_l,j)c_k,j =

(∑_k ∑_l) a_i,l*b_l,k*c_k,j =

= ∑_l a_i,l*(∑_k b_l,k*c_k,j) =

= ∑_l a_i,l*g_l,j = h_i,j

QED

Property 2: Distributive Property of Multiplication

A(B + C) = AB + AC
(A + B)C = AC + BC

where A,B,C are matrices of scalar values.

Proof:

(1) Let D = AB such that for each:

d_i,j = ∑_k a_i,k*b_k,j

(2) Let E = AC such that for each:

e_i,j = ∑_k a_i,k*c_k,j

(3) Let F = D + E = AB + AC such that for each:

f_i,j = ∑_k a_i,k*b_k,j+a_i,k*c_k,j = ∑_k a_i,k[b_k,j + c_k,j]

(4) Let G = B+C such that for each:

g_i,j = b_i,j + c_i,j

(5) Let H = A(B+C) = AG such that for each:

h_i,j = ∑_k a_i,k*g_k,j

(6) Then we have AB + AC = A(B+C) since for each:

h_i,j = ∑_k a_i,k[b_k,j + c_k,j]

(7) Let M = A + B such that for each:

m_i,j = a_i,j + b_i,j

(8) Let N = (A+B)C = MC such that:

n_i,j = ∑_k m_i,k*c_k,j =

= ∑_k (a_i,k + b_i,k)*c_k,j

(9) Let O = BC such that:

o_i,j = ∑_k b_i,k*c_k,j

(10) Let P = AC + BC = E + O such that:

p_i,j = e_i,j + o_i,j =

= ∑_k a_i,k*c_k,j + ∑_k b_i,k*c_k,j =

= ∑_k [a_i,k*c_k,j + b_i,k*c_k,j] =

= ∑_k (a_i,k + b_i,k)*c_k,j

QED

Property 3: Scalar Multiplication

c(AB) = (cA)B = A(cB)

Proof:

(1) Let D = AB such that:

d_i,j = ∑_k a_i,k*b_k,j

(2) Let E = c(AB) = cD such that for each:

e_i,j = c*d_i,j = c*∑_k a_i,k*b_k,j

(3) Let F = (cA)B such that:

f_i,j = ∑_k (c*a_i,k)*b_k,j = c*∑_k a_i,k*b_k,j

(4) Let G = A(cB) such that:

g_i,j = ∑_k a_i,k*(c*b_k,j) =

= c*∑_k a_i,k*b_k,j

QED

Property 4: Muliplication of Matrices is not Commutative

AB does not have to = BA

Proof:

(1) Let A =



(2) Let B =



(3) AB =



(4) BA =



QED

References

• Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.

Matrix Addition

The content in today's blog is taken straight from Gareth Williams' Linear Algebra.

Matrices in terms of their properties present an interesting contrast to numbers. Whereas with numbers, we can perform addition and subtraction on all elements, with matrices, this is not the case.

Indeed, one of the most important properties of matrices is that there are certain preconditions required before operations can be performed on two matrices. For example, addition can only occur between two matrices that have the same dimensions. It is not possible to add a 1 x 2 matrix with a 2 x 2 matrix.

Definition 1. Zero Matrix: Z_m,n

A zero matrix is any matrix which consists completely of 0's.

For example, below is Z_2,3:



Below are the basic properties of matrix addition.

Property 1: Commutative property of Addition

A + B = B + A

where A and B are matrices of the same dimension and consist of scalar values.

Proof:

(1) Let A = set of values a_i,j where i is the row and j is the column.

(2) Let B = set of values b_i,j

(3) A + B = the set of values a_i,j + b_i,j

(4) B + A = the set of values b_i,j + a_i,j

(5) Clearly, since all a_i,j and b_i,j are scalar, a_i,j + b_i,j = b_i,j + a_i,j

QED

Property 2: Associative property of Addition

A + (B + C) = (A + B) + C

where A, B, and C are matrices of the same dimension and consist of scalar values.

Proof:

(1) All A,B,C have the same dimensions since this is a prerequisite for addition.

(2) Let A = the set a_i,j, B = the set b_i,j, C = the set c_i,j

(3) A + (B + C) = the set a_i,j + (b_i,j + c_i,j)

(4) (A + B) + C = the set (a_i,j + b_i,j) + c_i,j

(5) Since a_i,j, b_i,j, c_i,j are all scalar, a_i,j + (b_i,j + c_i,j) = (a_i,j + b_i,j) + c_i,j

QED

Property 3: Addition by Z_m,n

A + Z_m,n = Z_m,n+ A = A

where A is an m x n matrix which consists of scalar values.

Proof:

(1) Let A be the set of a_i,j

(2) Let Z be the set of z_i,j where each z_i,j=0 [See Definition 1 above]

(3) A + Z_m,n = the set of a_i,j + z_i,j = the set of a_i,j = A

(4) Z_m,n + A = the set of z_i,j + a_i,j = a_i,j = A.

QED

Property 4: Distributive Property of Scalars with Addition of Matrices

c(A + B) = cA + cB

where A and B are matrices of the same dimension and consist of scalar values and c is a scalar value.

Proof:

(1) Let A = the set of a_i,j, let B = the set of b_i,j

(2) A + B = the set a_i,j + b_i,j

(3) c(A+B) = the set c(a_i,j + b_i,j) = a_i,jc + b_i,jc .

(4) cA + cB = the set of a_i,jc + the set of b_i,jc = the set of a_i,jc + b_i,jc.

QED

Property 5: Distributive Property of Matrices with Addition of Scalars

(a + b)C = aC + bC

where a,b are scalar values and C is a matrix of scalar values.

Proof:

(1) Let C = the set of c_i,j

(2) (a + b)C = the set of (a + b)c_i,j = ac_i,j + bc_i,j

(3) aC + bC = the set of ac_i,j+ the set of bc_i,j = the set of ac_i,j + bc_i,j

QED

Property 6: Associative Property of Multiplication of Scalars with Matrices

(ab)C = a(bC)

where a,b are scalar values and C is a matrix of scalar values.

Proof:

(1) Let C be the set of c_i,j

(2) (ab)C = the set of abc_i,j

(3) a(bC) = a*(the set of bc_i,j) = the set of abc_i,j

QED

References

• Gareth Williams, Linear Algebra with Applications, Wm. C. Brown Publishers, 1996.

Matrix Multiplication

Matrix multiplication can be best understood by understanding how matrices relate to a system of linear equations.

A system of linear of equations is a set of n equations with n variables where the goal is to solve each of the equations. For example, if we had three unknowns: x,y,z, a system of linear equations could consist of the following:

x + 3y - z = 4

3x + 2y - 5z = -2

2x - y + 3z = 8

The first step in moving to matrices is the idea of thinking of each unknown as an element of the same type. From this perspective, rather than thinking of them as x,y, and z, we can just as easily think of them as x₁, x₂, and x₃.

This has the advantage that we could now have 27 unknowns without running out of letters. So, with the new form, the 3 equations become:

x₁ + 3x₂ - x₃ = 4

3x₁ + 2x₂ - 5x₃ = -2

2x₁ - x₂ + 3x₃ = 8

The second step is to separate the values x₁, x₂, x₃ from their coefficients.

This is where matrices come in. It would be really nice for example, if matrix multiplication were defined in such a way that we could think of the above systems of equations as a multplication between two matrices. That is:




Indeed, this is exactly the case. Matrix multiplication is defined so that the coefficients of the system of linear equations can be easily abstracted from the unknowns.

Definition 1: Matrix Multiplication

If A is an m x n matrix and B is an n x p matrix, then C = AB is an m x p matrix where



That is:

c_i,j = a_i,1*b_1,j + a_i,2*b_2,j + ... + a_i,n*b_n,j for all i in (1 .. m) and for all j in (1 .. p).

In other words, each element is the sum of the multiplication of each element in a column for A with each element in a row for B. If the first row for A = [1, 1, 1] and the first column of B = [1, 2, 3] then the first element of C = (1*1 + 1*2 + 1*3) = 6 (see the example below).

Matrix multiplication is only defined for the case where the number of columns of the first matrix is equal to the number of rows of the second.

By this definition, it should be clear that while AB may be a meaningful matrix product, BA may very well not be allowed. For example, it is fine to multiply a 2 x 3 matrix with a 3 x 1 matrix. It is not allowed to multiply a 3 x 1 matrix with a 2 x 3 matrix since the number of columns in a 3 x 1 does not match the number of rows in the 2 x 3 one.

Here is an example of multiplying a 2 x 3 matrix with a 3 x 2 matrix to get a 2 x 2 matrix:




References

• Gareth Williams, Linear Algebra with Applications, Wm. C. Brown Publishers, 1996.
  

Introduction to Matrices

A matrix is a rectangular array of elements; it can be composed from any set of elements arranged evenly into rows and columns. While these elements can themselves be matrices, for purposes of this blog, I will assume that the elements are numbers.

Definitition 1: Matrix

A matrix is an ordering of elements into rows and columns. A matrix M that is an r x c matrix consists of r rows and c columns.

For example, a 2 x 3 matrix contains 6 elements ordered into 2 rows and 3 columns.

I will refer to a matrix as a capital letter and the elements that make up a matrix as a lowercase letter followed by a subscript that specifies row and column.

For example, a 2 x 3 matrix M consists of the following elements: m_1,1, m_1,2, m_1,3, m_2,1, m_2,2, m_2,3 that would look like this:



So that we have, M = [ m_i,j ]_{2 x 3}

Definition 2: Matrix Equality

If A is an m x n matrix and B is a p x q matrix, then A = B if and only if m=p and n=q and a_i,j = b_i,j for all i in (1 .. m) and for all j in (1 .. n).

In other words, two matrices are equal if they consist of the same number of rows and columns and all their elements are equal.

Definition 3: Matrix Addition

If A, B are two matrices of the same dimensions m x n, then the sum C = A + B is given by:

c_i,j = a_i,j + b_i,j for all i in (1 .. m) and all j in (1 .. n)

where C is also an m x n matrix.

For example:



Matrices can be only be added together when they consist of the same number of rows and columns.

Definition 4: Scalar

A scalar is any element of a matrix which is a number.

In this blog, I have made the assumption that all the elements of a matrix are scalar.

I will represent a scalar value as a lowercase letter that does not have a subscript.

Definition 5: Scalar Multiplication

If a is a scalar and B is an m x n matrix, then C = aB is also an m x n matrix such that:

c_i,j = a*b_i,j for all i in (1..m) and for all j in (1 .. n).

For example:



In my next blog, I will review matrix multiplication.

References

• Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.
  

Identity Matrix

In a previous blog, I reviewed the basic properties of 2 x 2 matrices. In today's blog, I generalize the definition of the identity matrix and show some of its properties.

Let me start by defining the Identity Matrix I_n.

Definition 1: I_n: Identity Matrix for n x n matrix



The Identity Matrix for n is an n x n matrix consists of values [a_i,j] where i = the row and j = column where:

i = j → a_i,j = 1

i ≠ j → a_i,j=0

Here are a few examples:






If A_n,n is an n x n matrix, we have:

Property 1: A_n,nI_n = A_n,n

Proof:

(1) Let:



(2) Then, A_n,nI_n =






QED

Property 2: I_nA_n,n = A_n,n

Proof:

(1) Let:



(2) Then, I_nA_n,n =






QED

If A_n,m is an n x m matrix, we have:

Property 3: A_n,mI_m=A_n,m

(1) Let:



(2) Then, A_n,mI_m =






QED

References

• "Identity Matrix", Wikipedia.org