Linear Algebra & Linear Programming
Linear Algebra & Linear Programming
This series aims at exploring the intuitions and cores of linear systems. In particular, I hope to interleave my accounts on linear algebra with linear programming – a rich field of great theoretical significance that relies heavily on linear algebra. The reference materials that I’m using are
- MIT course 18.06 by Professor Gilbert Strang;
- Understanding and Using Linear Programming, by Matousek and Gartner.
The outline is sketched below (and might be subject to changes):
- Equations and matrices: Viewing multiplication as vector processing; Gauss-Jordan elimination and its consequence on matrix decomposition.
- Linear space: Exploiting the structure of solution to AX=b; rank, dimension and basis.
- with an appendix on general theory of linear space
- application in graph theory
- Linear programming fundamentals: Standard form of LP; basic feasible solutions, stressing connections with previous chapter.
- Orthogonality: Why is projection useful?
- Simplex method for LP: Geometry intuition and proof of correctness.
- Duality theorem for LP: Intuition; a proof from Simplex method, and a proof from Farkas lemma.
- Eigenvalues and eigenvectors.
- Determinant, permanent and their applications: Integral programming made simple, in particular Konig’s Theorem; finding and counting matchings.
