# Finding a permutation that makes a matrix lower triangular

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?

• Is your system overdetermined (m>n) or underdetermined (m<n)? If it is overdetermined, there may not be a solution and you might want to find the solution which minimizes the least square norm. If it is underdetermined, there may be many solutions and in this case often one finds a solution with the smallest L2 norm. – Costis Jun 22 '12 at 12:51
• My system is overdetermined. However, it is already an LP. I converted it to a system of linear equations because I need just a feasible solution for this LP. All the entries of the matrix $A$ are 0,+1,_1 and some numbers between (0,1]. It is quite sparse as well. – Star Jun 22 '12 at 13:05
• Good LP solvers will find a suitable permutation by themselves. Feasibility is not significantly easier than optimality. Just try out some of the NEOS online solvers with your present formulation! – Arnold Neumaier Jun 22 '12 at 15:13
• If this question is really about LP feasibility, I feel that it's a duplicate of Star's LP feasibility question. Is this really supposed to be about LP feasibility? – Geoff Oxberry Jun 22 '12 at 17:20
• If you are asking about a permutation of rows, the answer is simple if not trivial: sort the rows descending according to latest appearance (by column) of nonzero entries. If you are asking about both row and column entries, the problem is more interesting. – hardmath Jun 22 '12 at 19:37