# Math 22a Fall 2018

## 22a Linear Algebra and Vector Analysis

# About Gauss-Jordan elimination

Some clay tablets from the**Euphrates and Tigris valley**indicate the earliest cases, where systems of linear equations have appeared 4000 years ago. The

**Gauss-Jordan algorithm**appeared first in the Nine Chapters on the Mathematical Art, which was authored around 300 BC in China. Due to a tradition of anonymity in that primary text, we might never know the details of that development. But Chapter 8 in that text definitely already uses an early elimination technique. Flash forward for almost 2000 years to Europe:

**Isaac Newton**wrote some notes in 1670, which described elimination the first time in Europe. Also

**Gottfried Leibniz**developed a method for solving systems of linear equations. But Leibniz used determinants.

**Carl Friedrich Gauss**in 1809 in ``Disquisitio de Elementis ellipticis Palladis" devised an algorithm to solve least-squares problems. Gauss himself considered the method as ``commonly known" and used them for astronomical purposes (he predicted earlier the path of the minor planet Ceres successfully). Gauss developed later also finer methods like the

**Gauss-Seidel algorithm**. This happened around 1823. His more sophisticated method was used for his work on the triangulation of Hanover. The name

**Gauss-Jordan elimination**for transforming a matrix into reduced echelon form also includes the name Jordan because a similar version was described by

**Wilhelm Jordan**in 1888 in his book ``Handbuch der Vermessungskunde" independently of

**B.-I. Clasen**who published something similar in the same year. The geodesist Jordan also used the method to minimze the squared error in observations. The story of elimination is also related to the history of matrices. Formally, matrices were introduced in 1855 by Arthur Cayley but according to Morris Kline the subject of matrices ``was well developed before it was created". The method of elimination was also implemented in the first stored-program digital computer, the Manchester Baby which in 1948 was historically

**the first to run a computer program on an electronic stored-program computer**. This machine was further developed in the form of the Manchester Mark 1, which is not to be confused with the Harvard Mark I here at Harvard, which began computations already earlier, namely in 1944. The Mark I (here an other website about it) did not use Gaussian elimination yet. Also the Harvard Mark II from 1947 inverted matrices differently: (I-A)

^{-1}can be written as 1+A+A

^{2}+ ... This idea was used for input-output models of the economist

**Wassily Leontief**. The series approach is a third and completely different way to solve systems of linear equations. It is different from the determinant methods like Leibniz or Cramer used and also different from the Gaussian elimination. It works well if the matrix entries of A are small.

- Randy Schwarz: A classic from China: the Nine Chapters [PDF].
- [PNG] Thomas Yuster's proof of the uniqueness of rref: Mathematics Magazine, 57, 1984.
- Joseph Grcar: How Ordinary Elimination became Gaussian Elimination .
- Jean-Luc Chabert: A history of algorithms.
- W. Jordan: Handbuch der Vermessungskunde
- Steven C. Althoen and Renate McLaughlin: Gauss-Jordan Reduction: A Brief History [PDF]
- Gaussian Elimination History [PDF] from the website of Carl D. Meyer. the author of ``Matrix analysis and applied linear algebra".