Gaussian Elimination

When we have a collection of lines we wish to know if they all intersect at some point. Many times we are interested in determining what that point is. In order to calculate this information, we first need an understanding of the lines themselves. The way the Gaussian Elimination Algorithm works is that the collection of lines are input using a notation of Ax = b, where the matrix A is called the coefficient matrix, as the nth row of it corresponds to the coefficients for the nth line being considered. The vector b represents the right hand side vector (in two dimensions, we would call these constants the y-intercepts of the lines. In higher dimensions they hold a similar property). The vector x represents the point where the lines intersect. It is this quantity which Gaussian Elimination seeks to determine.

The basic procedure of Gaussian Elimination is to use \"elementary row operations\" on the matrix (A|b), which is called the augmented matrix, to transform A into upper triangular form. Once this is done, a procedure called back-substitution can find the solution (x) to this problem.

The elementary row operations that we are allowed to perform are:

  • Interchange two rows.
  • Multiply a row by a nonzero number.
  • Add a row to another one multiplied by a number.

    For the last property listed above, we will determine this number by dividing the coefficient of the term we which to eliminate by the negative of the coefficient of the element on the main diagonal of the same column of the matrix. This will have the property of canceling out, or producing a desired zero in the resulting row.

    If this algorithm produces an upper triangular matrix from which we can solve for x using back-substitution. This procedure of back-substitution is simply solving for the vector x from the bottom of the matrix to the top. If the algorithm does not produce an upper triangular matrix (because somewhere along the line, we are unable to obtain a ratio because we have zero's on the diagonal and all zeros below the diagonal), then we say the matrix is singular. This means that there is no unique point where the lines all intersect.

    Show Work?
  • Recent Updates

  • 08-10-2017 Floyd-Warshall Shortest Paths
  • 08-01-2017 Degree Centrality of a Graph
  • 06-03-2017 Tarjan's Strongly Connected Components Algorithm
  • 03-20-2017 Longest Common Subsequence
  • 10-27-2016 Independent Set Puzzles
  • 06-28-2016 Lets Learn About XOR Encryption
  • 06-15-2016 Discrete-time Markov Chains
  • 03-01-2016 Topological Sort
  • 01-21-2016 The RSA Algorithm
  • 11-20-2015 How To Take Notes in Math Class
  • 10-28-2015 The Depth-First-Search Algorithm
  • 10-28-2015 The Breadth-First-Search Algorithm
  • 09-23-2015 ID3 Algorithm Decision Trees
  • 07-08-2015 Clique Problem Puzzles
  • 06-25-2015 Unidirectional TSP Puzzles
  • 04-04-2015 Learn About Descriptive Statistics
  • 02-19-2015 Slope Formula
  • 01-15-2015 Interactive Midpoint Formula
  • 12-18-2014 Triangle Sum Puzzle
  • 12-02-2014 The Bridge Crossing Problem