MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like LINGO it is clear that after permutation of rows, it turns out to be like a lower triangular matrix. I do not know what the permutation function should be. Since the matrix dimension is not square, I cannot use the LU decomposition to solve the system efficiently. Can you please let me know an efficient method for linear systems with non-square coefficient matrix?

share|cite|improve this question
Is $m > n$ or vice-versa? – Gilead Jun 22 '12 at 14:51
As it turns out, using an LP solver to solve linear equations isn't a terrible idea in practice. This may sound counter-intuitive, because it sounds overkill. However, because the efficiency of an LP solution depends so much on the linear algebra, good commercial LP solvers like CPLEX or Gurobi tend to incorporate highly optimized linear algebra routines (with excellent sparse matrix handling). There are other advantages to using an LP solvers: 1. matrix does not have to be square; 2. detection of inconsistencies through slacks; 3. inequality constrained solutions for underdefined systems. – Gilead Jun 22 '12 at 14:56
See here: – Gilead Jun 22 '12 at 14:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.