Linear Algebra 101: Gaussian Elimination (1)

The first topic in linear algebra as it is generally taught is Gaussian elimination on linear systems. This is a simple algorithm which allows you to solve systems of linear equations. Before we can solve them, though, we should know what a system of linear equations actually is.

Conceptually quite simple, a system of linear equations is any collection of linear equations involving the same variables. A linear equation is any equation of the form

a₁x₁ + a₂x₂ + a₃x₃ ... + a_nx_n = b

Where a is a set of coefficients (such as 2, 7.5, 1/3, π), x is a set of variables and b is the solution. Thus, if

2x + 2y = 2

is a linear equation, a linear system might be

2x + 2y = 2
2x - 2y = -2

There are a few points to note about these systems:

1. You may have more equations than variables.
2. You may have more variables than equations.
3. Not every variable need appear in every equation.
4. A linear system may have one solution, no solutions, or an infinite number of solutions.

In the next post, we'll look at the Gaussian elimination algorithm itself and use it to solve this linear system.