The first goal is to produce zeros below the first entry in the first column, which translates into eliminating the first variable, x, from the second and third equations. The augmented matrix which represents this system is Since elementary row operations do not change the solutions of the system, the vectors x which satisfy the simpler system A′ x = b′ are precisely those that satisfy the original system, A x = b.Įxample 3: Solve the following system using Gaussian elimination: The solutions of the system represented by the simpler augmented matrix,, can be found by inspectoin of the bottom rows and back‐substitution into the higher rows.

The goal of these operations is to transform-or reduce-the original augmented matrix into one of the form where A′ is upper triangular ( a ij′ = 0 for i > j), any zero rows appear at the bottom of the matrix, and the first nonzero entry in any row is to the right of the first nonzero entry in any higher row such a matrix is said to be in echelon form. Add a multiple of one row to another row. Then, perform a sequence of elementary row operations, which are any of the following: Given a linear system expressed in matrix form, A x = b, first write down the corresponding augmented matrix: Gaussian elimination can be summarized as follows. Back‐substitution into the first row (that is, into the equation that represents the first row) yields x = 2 and, therefore, the solution to the system: ( x, y) = (2, 1). The new second row translates into −5 y = −5, which means y = 1. Adding −3 times the first row of the augmented matrix to the second row yields Likewise, the counterpart of adding a multiple of one equation to another is adding a multiple of one row to another row. Now, the counterpart of eliminating a variable from an equation in the system is changing one of the entries in the coefficient matrix to zero. You may choose to include a vertical line-as shown above-to separate the coefficients of the unknowns from the extra column representing the constants. The first row, r 1 = (1, 1, 3), corresponds to the first equation, 1 x + 1 y = 3, and the second row, r 2 = (3, −2, 4), corresponds to the second equation, 3 x − 2 y = 4. This is called the augmented matrix, and each row corresponds to an equation in the given system. Next, the coefficient matrix is augmented by writing the constants that appear on the right‐hand sides of the equations as an additional column: This is called the coefficient matrix of the system. The first step is to write the coefficients of the unknowns in a matrix: The previous example will be redone using matrices. This method reduces the effort in finding the solutions by eliminating the need to explicitly write the variables at each step. Gaussian elimination is usually carried out using matrices. (Back‐substitution of y = 1 into the original second equation, 3 x − 2 y = 4, would also yeild x = 2.) The solution of this system is therefore ( x, y) = (2, 1), as noted in Example 1.

Back‐substitution of y = 1 into the original first equation, x + y = 3, yields x = 2. This final equation, −5 y = −5, immediately implies y = 1. Multiplying the first equation by −3 and adding the result to the second equation eliminates the variable x: This method, characterized by step‐by‐step elimination of the variables, is called Gaussian elimination. Once this final variable is determined, its value is substituted back into the other equations in order to evaluate the remaining unknowns. The fundamental idea is to add multiples of one equation to the others in order to eliminate a variable and to continue this process until only one variable is left. The purpose of this article is to describe how the solutions to a linear system are actually found.

Elimination algebra