Matrix Inversion, and Linear Programming

This site extends the existing one-way connections among the solving linear systems of equations, matrix inversion, and linear programming. The additional linkages empower the user to understand the wholeness and manifoldness of these topics. They also assist the user to model and solve a problem modeled as any one of the above topics by having access to a computer package solver. The goals are theoretical unification as well as advancements in applications. Illustrative numerical examples are presented.

To search the site, tryEdit |Find in page [Ctrl + f]. Enter a word or phrase in the dialogue box, e.g. "inverse"or "equations"If the first appearance of the word/phrase is not what you are looking for, tryFind Next.

MENU

- Introduction
- LP Problem Solved by System of Equation Solver
- System of Equations Solution by LP Solver
- Solving for the Inverse of a Matrix Using LP Solver
- Solving an LP by using a Matrix Inverse Solver
- Solve a System of Equation Using Matrix Inverse Solver
- Finding the Matrix Inverse Using System of Equations Solver
- Matrix Inversion: A Computational Algebra Approach
- Learning Objects: Online Interactive Solvers
- Rounding Errors and Stability Analysis
- Concluding Remarks
- References and Further Readings

Companion Sites:

- Linear Optimization Solvers to Download
- Success Science
- Leadership Decision Making
- Linear Programming (LP) and Goal-Seeking Strategy
- Artificial-variable Free LP Solution Algorithms
- Integer Optimization and the Network Models
- Tools for LP Modeling Validation
- The Classical Simplex Method
- Zero-Sum Games with Applications
- Computer-assisted Learning Concepts and Techniques
- From Linear to Nonlinear Optimization with Business Applications
- Construction of the Sensitivity Region for LP Models
- Zero Sagas in Four Dimensions
- Probabilistic Modeling
- Systems Simulation
- Business Keywords and Phrases
- Compendium of Web Site Review
- Collection of JavaScript E-labs Learning Objects
- Decision Science Resources

## Linear programming (LP), Linear systems of equations, and Matrix inversion are often favorite topics for both instructors and students. The ability to solve these problems by Gauss-Jordan pivoting (GJP), the widespread availability of software packages, and their wide range of applications make these topics accessible even for students with relatively weak mathematical backgrounds. The typical textbooks on LP usually devote separate sections for each topic. However, the relationships among these closely related topics are often not presented or thoroughly discussed. This article extends the existing one-way connections among these topics to construct a comprehensive two-way relationship as in the following figure. For each topic, it is shown how the problem may be modeled and solved by either of the associated methodologies.

Introduction

The additional linkages introduced here, empower the user to understand, to model and to solve a problem modeled as any one of the above topics by having access to a computer package-solver. The goals are theoretical unification as well as advancements in applications. The following six sections derive the linkages which are illustrated by small numerical examples. While some of these are quite well known, we include them here for completeness.

## This section is probably among the most familiar since many introductions to the Simplex Method of linear programming (LP) are developed using a system of linear equations approach.

LP Problem Solved by System of Equation Solver The coordinates of vertices are the basic feasible solution of the systems of equations obtained by setting some of the constraints at binding (i.e., equality) position. For a bounded feasible region, the number of vertices is at most combinatorial C

_{p}^{q}where p is the number of constraints and q is the number of variables. Therefore, by taking any q equations and solving them simultaneously one obtains a basic solution (if exists). By plugging this basic solution in the constraints of other equations, one can check for feasibility of the basic solution. If it is feasible, then this solution is a basic feasible solution that provides the coordinates of a corner point of the feasible region.Each solution to any system of equations is called a Basic Solution (BS). Those Basic Solutions which are feasible are called Basic Feasible Solutions (BFS). The vertices of set S are the BFS.

Suppose we have the following LP problem with all variables unrestricted in sign:

Max X1 + X2

subject to:

X1 + X2 ³ 10

X1 £ 8

X2 £ 12To illustrate the procedure, Set all the constraints at their binding (i.e., equality) position. The result is the following set of 3 equations with 2 unknowns:

X1 + X2 = 10

X1 = 8

X2 = 12Here we have p=3 equations with q=2 unknowns. In terms of a "binomial coefficient", there are at most C

_{3}^{2}= 3! / [2! (3-2)!] = 3 basic solutions. Solving the three resultant systems of equations, we have:

X1 X2 X1 + X2 8 2 10 8 12 20* -2 12 10

The optimal solution is X1 = 8, X2 = 12, with optimal value of 20.

For details and more numerical examples visit the Solution Algorithms for LP Models Web site.

## Suppose we have a system of equations we would like to solve and a LP solver but no solver for a system of equations available. To solve as an LP add a dummy objective function, and for generality we assume the variables are unrestricted in their sign. Thus substitute Xi = yi - z, everywhere. This substitution must be done since many LP packages such as LINDO, and QSB assume the variables are non-negative.

System of Equations Solution by LP Solver For example to solve the following system of equations

2X1 + X2 = 3

X1 -X2 = 3

Convert to the LP problem below:

Max (or min) Dummy, say Max (or min) z,

subject to: 2y1 + y2 - 3z = 3, and y1 - y2 = 3Using any LP solver such as LINDO we find the optimal solution to be y1 = 3, y2 = 0, z = 1. Therefore, the solution to the original system of equation is X1 = 3 -1 = 2, X2 = 0 - 1 = -1.

## To find the inverse to matrix AnXn we solve a series of n LP problems to find the inverse column by column. For example, to find the first column of the inverse matrix solve

Solving for the Inverse of a Matrix Using LP Solver Max Dummy

subject to: AX - z [SA1j , SA2j ,.... , SAnj]^{T }= (1, 0, 0, .....0)^{T }The first column of A-1 is then (X1

^{*}- z^{*}, X2^{*}- z^{*}, ...Xn^{*}- z^{*})^{T }Suppose we wish to find the inverse of the following matrix (if it exists)

2 1 A = 1 -1 To find the first column of A

^{-1}use an LP solver to solveMax Dummy

subject to: 2X1 + X2 - 3z =1, and X1 - X2 = 0

The optimal solution is X1 = 1/3, X2 = 1/3, and z = 0. Therefore the first column of A

^{-1}is [1/3 - 0, 1/3 - 0]^{T}= [1/3, 1/3]^{T}. To compute the second column solveMax Dummy

Subject to: 2X1 + X2 - 3z =0, and X1 - X2 = 1

The optimal solution is X1 = 1, X2 = 0, and z = 2/3. Therefore the second column of A

^{-1}is [1 - 2/3, 0 - 2/3]^{T}= [1/3, -2/3]^{T}. Therefore the inverse matrix is:

1/3 1/3 A ^{-1}= 1/3 -2/3

Notice:A matrix possessing an inverse is callednonsingular, or invertible. A matrix is called singular if it does not have an inverse. For example, the following matrix is a singular one:1 6 4

2 4 -1

-1 2 5

Therefore, in applying the above procedure for inverting a matrix, if the matrix is a singular one, then there is no the optimal solution.

## To solve an LP we find the inverse of each basis matrix with the appropriate number of slack/surplus variables set equal to zero. Then X = B

Solving an LP by using a Matrix Inverse Solver ^{-1}b, and we now use the objective function to find the optimal value and optimal solution. Suppose we wish to solve the following LP problem using an inverse solver.Max X1 + X2

subject to:

X1 + X2 ³ 10

X1 £ 8

X2 £ 12The first step is to convert all inequality constraints to equalities by introducing slack/surplus variables (the equality constraints, if any, remain unchanged), we have:

X1 + X2 - S1 = 10

X1 + S2 = 8

X2 + S3 = 12Then, by finding the inverse of the following three matrices, we obtain the basic solutions:

S_{2}=S_{3}= 0Its inverse is:

1 1 -1 B = 1 0 0 0 1 0 Therefore:

0 1 0 B ^{-1}= 0 0 1 -1 1 1

X _{1}8 X _{2}= B ^{-1}.b= 12 S _{1}10 S=_{1}S_{3}= 0Its inverse is:

1 1 0 B = 1 0 1 0 1 0 Therefore:

1 0 -1 B ^{-1}= 0 0 1 -1 1 1

X _{1}-2 X _{2}= B ^{-1}.b= 12 S _{2}10

S=_{1}S= 0_{2}Its inverse is:

1 1 0 B = 1 0 0 0 1 1

Therefore:

1 1 0 B ^{-1}= 1 -1 0 -1 1 1

X _{1}8 X _{2}= B ^{-1}.b= 12 S _{3}10 Evaluating the objective function for the feasible basic solution, we obtain the optimal solution which is (X1 = 8, X2 = 12), with optimal value =20

## For completeness, we include the well known matrix inverse approach to solving a system of equations. To solve the following system of equations,

Solve a System of Equation Using Matrix Inverse Solver 2X1 + X2 = 3

X1 -X2 = 3

which may be written as matrix equation AX = b, then X= A

^{-1}.b, if the inverse existsIts inverse is:

2 1 A = 1 -1 Therefore:

1/3 1/3 A ^{-1}= 1/3 -2/3

X _{1}2 = A ^{-1}b= X_{ 2}-1

Therefor X1 = 2, and X2 = -1 is the unique solution.

## To find the inverse of a square matrix of size n, solve n systems of equations with a unit vector as their right hand side. The following proposition justifies this claim:

Finding the Matrix Inverse Using System of Equations Solver Proposition 2: Given a matrix AnXn has an inverse, then the jth column of the inverse denoted by A

^{-1}.j is the unique solution of AX =Ij, whereIj in a unit vector where the "1" element located at the jth row, j =1, 2,..,n.Suppose we wish to find the inverse of the following matrix (if it exists)

To find the first column of A

2 1 A = 1 -1 ^{-1}solve:2X1 + X1 = 1

X1 - X2 = 0This gives X1 = 1/3 , X2 = 1/3. To find the second column of A

^{-1}solve:2X1 + X1 = 0

X1 - X2 = 1This gives X1 = 1/3 , X2 = -2/3. Therefore, A

^{-1}is

1/3 1/3 A ^{-1}= 1/3 -2/3

Notice:A matrix possessing an inverse is callednonsingular, or invertible. A matrix is called singular if it does not have an inverse. For example, the following matrix is a singular one:1 6 4

2 4 -1

-1 2 5

Therefore, in applying the above procedure for inverting a matrix, if the matrix is a singular one, then at least of the systems of equations has no solution.

## A standard method for computing A

Matrix Inversion: A Computational Algebra Approach ^{-1}for an r x n matrix A is to use Gauss-Jordan row operations to reduce the n x 2n augmented matrix [A | I] to [I | C], whence A^{-1}= C.Instead, we propose reducing the [n by (n + 1)] augmented matrix [A | R], where R is an [n by 1] column vector of unspecified variable r. The G-J symbolic reduction of [A | R] to [I | D] yields A

^{-1}as the matrix of coefficients of the r_{i}'s in D.It is shown that, this approach yields substantial savings in both space and computational time over approaches used in existing computer algebra systems. A computational complexity analysis of the required number of operations shows that, for large n, their proposed method saves about 25% over the conventional method [Arsham 1993]. This reduction results from starting each row of R with just one (symbolic) term, instead of the n (numerical) terms in each row of I. Clearly, this approach has pedagogical advantages of their approach. One advantage is that simultaneously the generic linear system with coefficient matrix A is solved and A

^{-1}is found, as discussed before.Suppose we wish to find the inverse of the following matrix (if it exists):

2 1 A = 1 -1

2 1 r _{1}1 -1 r _{2}

1 1/2 r _{1}/ 20 -3/2 -r _{1}/ 2 + r_{2}

1 0 r _{1}/ 3 + r_{2}/ 30 1 r _{1}/ 3 - 2r_{2}/ 3

Therefore the inverse matrix is:

1/3 1/3 A ^{-1}= 1/3 -2/3

Notice:A matrix possessing an inverse is callednonsingular, or invertible. A matrix is called singular if it does not have an inverse. For example, the following matrix is a singular one:1 6 4

2 4 -1

-1 2 5

Therefore, in applying the above procedure for inverting a matrix, if the matrix is a singular one, then at least one row will have All Zero Elements during the G-J operations.

Learning Objects: Online Interactive Solvers Computer Assisted Learning:I do recommend the following online interactive solvers sites to understand the concepts presented on this site by performing some numerical experimentation:System of Equations and Matrix Inversion.

Linear Optimization.

## Rounding errors is due to the hardware limitation of any computer package. Therefore, one must be concerned about the stability analysis of the solution with respect to the input parameters. Following are three numerical examples for Linear programming, matrix inversion, and solving system of linear equations, respectively:

Rounding Errors and Stability Analysis Linear Programming: Consider the following problem:

Max 6X1 + 4X2

subject to:

3.01X1 + 2X2 £ 24

X1 + 2X2 £ 16 all decision variables ³ 0.The optimal solution is (X1 = 3.9801, X2 = 6.0100). However, the optimal solution for the same problem but with a slight change in the constraints' coefficients matrix one may get a completely different optimal solution. For example, if we change 3.01 to 2.99, then the optimal solution is (X1 = 8.0268, X2 = 0). That is, decreasing the one element of the technology-matrix by 0.66%, the solution changes drastically! Therefore, the optimal solution is unstable with respect to this input parameter.

Matrix Inversion: Consider the following matrix:

1.9998 0.9999 A = 5.9994 3.0009 This matrix has a proper inverse, however rounding the elements of matrix A,

2 1 A _{r}= 6 3 it becomes a singular matrix, i.e., it has no inverse.

Solving System of Equations: Consider the following system of equation:

2.04X1 + 2.49X2 = 0.45

2.49X1 + 3.04X2 = 0.55which has a unique solution (X1 = -1, X2 = 1). However, rounding the coefficient matrix to:

2.0X1 + 2.5X2 = 0.45

2.5X1 + 3.0X2 = 0.55now the solution become (X1 = 0.1, X2 = 0.1) a startling change.

## This site expands the discussion of the interrelationships between linear system of equations, matrix inversion and linear programming so each may be modeled and solved by either of the other two methodologies. Although few of these linkages are well known, this site completes the remaining missing links.

Concluding Remarks

References and Further Readings:

Arsham H., Links Among a Linear System of Equations, Matrix Inversion, and Linear Program Solver Routines,Journal of Mathematical Education in Science and Technology, 29(5), 764-769, 1998.

Arsham H., Matrix Inversion: A Computational Algebra Approach,Journal of Mathematical Education in Science and Technology, 27(4), 599-605, 1996.

Arsham H., A Linear Symbolic-Based Approach to Matrix Inversion,Journal of Mathematics and Computers in Simulation, 35(6), 493-500, 1993.

Arsham H., The Gauss-Jordan matrix inversion is not optimal: A symbolic adaptation,The 5, Ed. J. Lewis, 528-532, 1994.^{th}SIAM Conference on Applied Linear Algebra

Bellman R.,Introduction to Matrix Analysis, SIAM: Society for Industrial & Applied Mathematics, 1997.

The Copyright Statement: The fair use, according to the 1996 Fair Use Guidelines for Educational Multimedia, of materials presented on this Web site is permitted for non-commercial and classroom purposes only.

This site may be mirrored intact (including these notices), on any server with public access, and linked to other Web pages. All files are available at http://home.ubalt.edu/ntsbarsh/Business-stat for mirroring.Kindly e-mail me your comments, suggestions, and concerns. Thank you.

This site was launched on 2/25/1994, and its intellectual materials have been thoroughly revised on a yearly basis. The current version is the 8^{th} Edition. All external links are checked once a month.

EOF: Ó 1994-2015.