Linear Algebra part 1 - Gauss Jordan Elimination

2007-10-24


Here are my first set of linear algebra notes. The full videos can be found on MIT's Opencourseware site.

Geometry of Linear Equations

Take for example the equation

2x-y = 0
-x + 2y = 3

The matrix that would be created to represent this system would be,

   
2
-1
   
-1
2
       
x
y
     =    
0
3
    


This follows the main equation of linear algebra of Ax=b, where A is the matrix, x is your vector of variables and b is your result vector. In other words, Ax is a combination of the columns of A. We can see this by the folowing..

 x    
2
-1
     +  y    
-1
2
     =    
0
3
    


Elimination with Matrices

The basic way to solve a system of linear of equations is to do elimination. For example, take the matrx,

   
1
3
0
   
2
8
4
   
1
1
1
       
x
y
z
     =    
2
12
2
    


The idea is to take the first variable in the upper left corner.. let's call it a1,1. The 1,1 correspond to the row, and the column. In this case, a1,1 is equal to 1. We will call this our pivot variable. Now we are able to do row operations to eliminate all other numbers in that column. For row 2, we multiply row 1 by 3 and the subtract row2. A.k.a row2-3*(row1). Then for row 3, since it is already 0, we don't need to do anything. This leaves us with the matrix,

   
1
0
0
   
2
2
4
   
1
-2
1
    


Next, we take the element a2,2 which is 2 as our next pivot. We eliminate the column below it resulting in row3 - 2*row2. The resulting matrix is,

   
1
0
0
   
2
2
0
   
1
-2
5
    


As we can see, that all elements below the diagonal are zero... This is then equal to what is called the Upper Triangular Matrix (U). Now if we augment this matrix by the b matrix, which in this case was the vector [2,12,2]T, we will see that after the row operations, the b vector will contain the correct answers. In the end we can see the augmented matrix is equal to,

   
1
0
0
   
2
2
0
   
1
-2
5
   
2
6
-10
    


Lastly, we back substitute starting with the bottom of the matrix, 5z = 10... z=2. Then we can use the z=2 and find the value of row 2, etc.. To represent this as a matrix operation, consider the following where we multipled row 1 by 3 and subtracted from row 2.

   
1
-3
0
   
0
1
0
   
0
0
1
       
1
3
0
   
2
8
4
   
1
1
1
     =    
1
0
0
   
2
2
4
   
1
-2
1
    


Here we can see that the matrix in front of our A matrix takes 1 of the first row, then -3 of the second row + second row, and 1 of the third row. Lets call this matrix E2,1. The 2,1 represents the elimination element. Then we also needed to eliminate the 3,1 variable, but that's already 0. The last element we needed to eliminate was the 3,2 position. Let's call that E3,2. So what we are left with is the following formula,

E3,2E2,1A = U

The property that is helpful here is the associative property.. (E3,2E2,1)A is equal to E3,2(E2,1A)