Gaussian elimination — Safekipedia Discoverer

Gaussian elimination is a powerful method in mathematics used to solve systems of linear equations. Named after the famous mathematician Carl Friedrich Gauss, this technique involves performing a series of operations on the rows of a matrix to simplify it. By using three basic row operations—swapping rows, multiplying a row by a nonzero number, and adding a multiple of one row to another—mathematicians can transform the matrix into a form that makes solving the equations much easier.

Animation of Gaussian elimination. Red row eliminates the following rows, green rows change their order.

One key goal of Gaussian elimination is to turn the matrix into what is called reduced row echelon form. In this form, each nonzero row has a leading 1, and these leading 1s move further to the right in each subsequent row, with zeros below and above them. This organized structure helps clearly show the solutions to the equations.

Gaussian elimination is not just a theoretical tool; it has practical uses in many areas, such as computer science, engineering, and physics, where solving systems of equations is common. Whether in calculating trajectories for space travel or designing structures, this method provides a reliable way to find answers efficiently.

Definitions and example of algorithm

Row reduction of an invertible matrix expressed as left multiplication by elementary matrices.

The process of row reduction uses simple operations on the rows of a matrix to solve systems of equations. These operations include swapping two rows, multiplying a row by a number, or adding a multiple of one row to another. These steps help organize the matrix so we can see if there are solutions and what they might be.

One goal is to arrange the matrix into a special form called "row echelon form," where each row's first number (called a leading entry) is to the right of the one above it, and zeros fill the space below each leading entry. This makes solving the equations easier. For example, a matrix might look like this after organizing it: the first row starts with a number in the second column, the next row starts with a number in the third column, and the last row is all zeros. This helps us see the solution clearly.

System of equations	Row operations	Augmented matrix
2 x + y − z = 8 − 3 x − y + 2 z = − 11 − 2 x + y + 2 z = − 3 {\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}}		[ 2 1 − 1 8 − 3 − 1 2 − 11 − 2 1 2 − 3 ] {\displaystyle \left[{\begin{array}{rrr\|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]}
2 x + y − z = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}}	L 2 + 3 2 L 1 → L 2 L 3 + L 1 → L 3 {\displaystyle {\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}}	[ 2 1 − 1 8 0 1 2 1 2 1 0 2 1 5 ] {\displaystyle \left[{\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]}
2 x + y − z = 8 1 2 y + 1 2 z = 1 − z = 1 {\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}}	L 3 + − 4 L 2 → L 3 {\displaystyle L_{3}+-4L_{2}\to L_{3}}	[ 2 1 − 1 8 0 1 2 1 2 1 0 0 − 1 1 ] {\displaystyle \left[{\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]}
The matrix is now in row echelon form (also called triangular form)
2 x + y = 7 1 2 y = 3 2 − z = 1 {\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}}	L 1 − L 3 → L 1 L 2 + 1 2 L 3 → L 2 {\displaystyle {\begin{aligned}L_{1}-L_{3}&\to L_{1}\\L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\end{aligned}}}	[ 2 1 0 7 0 1 2 0 3 2 0 0 − 1 1 ] {\displaystyle \left[{\begin{array}{rrr\|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]}
2 x + y = 7 y = 3 z = − 1 {\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}}	2 L 2 → L 2 − L 3 → L 3 {\displaystyle {\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}}	[ 2 1 0 7 0 1 0 3 0 0 1 − 1 ] {\displaystyle \left[{\begin{array}{rrr\|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]}
x = 2 y = 3 z = − 1 {\displaystyle {\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}}	L 1 − L 2 → L 1 1 2 L 1 → L 1 {\displaystyle {\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}}	[ 1 0 0 2 0 1 0 3 0 0 1 − 1 ] {\displaystyle \left[{\begin{array}{rrr\|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]}
The matrix is now in reduced row echelon form

History

Gaussian elimination, a way to solve math problems with many equations, was used long ago. It first showed up in a Chinese book called The Nine Chapters on the Mathematical Art, written around 150 BC. Later, Isaac Newton wrote about it in the late 1600s, and it became a common way to teach solving equations in algebra books.

The method we learn today is named after Carl Friedrich Gauss, though it was used by many before him. Some people call a special version of it "Gauss–Jordan elimination," named after Wilhelm Jordan, who described it in 1888.

Applications

Gaussian elimination is a method used to solve systems of equations by performing operations on rows of numbers. It can also help us understand important properties of matrices.

One key use is to find the determinant of a square matrix. By carefully swapping rows, multiplying rows by numbers, or adding multiples of one row to another, we can simplify the matrix. The determinant changes in predictable ways during these steps, allowing us to calculate it efficiently.

Gaussian elimination can also help find the inverse of a matrix, if it exists. By attaching an identity matrix to the original matrix and then simplifying both sides through row operations, we can determine whether an inverse exists and what it is. This process works for matrices of any size.

Computational efficiency

Gaussian elimination is a method used to solve systems of equations by performing operations on rows of numbers. The number of steps needed depends on how many equations there are. For a system with n equations, it takes about 2_n_³/3 steps to solve. This makes it practical for solving systems with hundreds of equations, but not for very large systems with thousands of equations.

There is a special version of Gaussian elimination called the Bareiss algorithm that avoids problems with very large numbers appearing during the calculations. This version works well when the numbers in the original problem are whole numbers, keeping all results as whole numbers without needing fractions. It allows solving certain problems in a way that guarantees the calculations stay manageable.

Generalizations

Gaussian elimination can be used with any type of number system, not just regular numbers you learn in school. There is also a method called Buchberger's algorithm that extends Gaussian elimination to solve problems with equations that have variables raised to powers.

For more complex math structures called tensors, finding certain properties is very difficult, and may not have a fast solution similar to Gaussian elimination.

Pseudocode

Gaussian elimination is a way to solve problems with many equations by using a special set of steps on a table of numbers, called a matrix. The goal is to make the matrix simpler so the answers can be found more easily.

The steps involve looking for the biggest number in a certain spot, swapping rows if needed, and then using that number to make other numbers in the same column zero. This process is repeated until the matrix is in a form where the answers to the original equations can be worked out step by step. This method helps make sure the calculations stay accurate, especially when using computers.

Main article: row-echelon form