Linear Algebra and Linear Programming

This is a year two module. It is taught intensively by Birmingham academics over eight weeks. There is continuous assessment and a final examination.

Linear algebra grew out of the development of techniques at the start of the 18th century by Leibniz, Cramer and Gauss to solve systems of linear equations. Cayley developed matrix algebra in the middle of the 19th century and the definition of a vector space was made by Peano at the end of the 19th century, resulting in a theory of linear transformations and vector spaces in the early 20th century. Linear algebra is not only fundamental to both pure and applied mathematics, but also has applications ranging from quantum theory to Google search algorithms. This module develops the theory of vector spaces introduced in Vectors, Geometry & Linear Algebra, covering eigenvectors, characteristic polynomials, inner products, and diagonalisation.

If linear algebra grew out of the solution of systems of linear equations, then linear programming grew out of attempts to solve systems of linear inequalities, allowing one to optimise linear functions subject to constraints expressed as inequalities. The theory was developed independently at the time of World War II by the Soviet mathematician Kantorovich, for production planning, and by Dantzig, to solve complex military planning problems. Koopmans applied it to shipping problems and the technique enjoyed rapid development in the postwar industrial boom.

The first complete algorithm to solve linear programming problems, called the simplex method, was published by Dantzig in 1947 and in the same year von Neumann established the theory of duality. In 1975, Kantorovich and Koopmans shared the Nobel Prize in Economics for their work and Dantzig’s simplex method has been voted the second most important algorithm of the 20th century after the Monte Carlo method. Linear programming is a modern and immensely powerful technique that has numerous applications, not only in business and economics, but also in engineering, transportation, telecommunications, and planning.

By the end of the module students should be able to:

  • understand and use the basic concepts of linear algebra and matrices, including linear transformations, eigenvectors and the characteristic polynomial
  • understand the basic theory of inner products and apply it to questions of orthogonality and/or diagonalisability
  • explain the basic techniques of linear programming (graphical method and simplex method)
  • construct linear programming models of a variety of managerial> problems and interpret the results obtained by applying the linear programming techniques to these problems
  • explain why and when the simplex method fails to provide a solution and how to resolve such a situation
  • present, prove and use the results of duality theory and interpret them
  • explain the computational complexity of SIMPLEX and LP