I am interested in the complexity of the following problem:



> 
> 
> > 
> > Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix?
> > 
> > 
> > 
> 
> 
> 


I am also interested in the case where "triangular" is replaced by **unitriangular**.


It says [here](http://mathworld.wolfram.com/01-Matrix.html) that Wilf (1997) has studied the first problem in "On Crossing Numbers, and some Unsolved Problems". However I don't have access to it, nor can I find it on his website.



> 
> Does anyone know of a reference, or if there has been any subsequent work?
> 
> 
> 


Many thanks.




---


**Clarification**: I am asking whether there exist two permutation matrices $P,Q$ such that $PMQ$ is triangular. Equivalently, one may freely swap both the rows and columns of $M$.




---


**Background**: Since an algorithm has been spelt out in detail, I'll briefly explain my motivation. 


Each finite (order-theoretic) lattice $L$ has an associated "poset of irreducibles" which may be viewed as the relation $R \subseteq J(L) \times M(L)$ between the join/meet-irreducibles where $R(j,m) \iff j \nleq\_L m$. In Theorem 11 of [Primes, Irreducibles and Extremal Lattices](http://www.researchgate.net/publication/226761265_Primes_irreducibles_and_extremal_lattices/links/00b4951d55952c1fe7000000.pdf), Markowsky proves that $R$ is lower or upper unitriangularisable iff $L$ has length $|M(L)|$ or $|J(L)|$ respectively.



Transforming a binary matrix into triangular form using permutation matrices
Luckily, the problem is no more in the "NP-limbo". The paper [Obtaining a triangular matrix by independent row-column permutations](https://hal.archives-ouvertes.fr/hal-01189621/document) Fertin, Rusu, and Vialette shows that the problem is NP-complete for binary square matrices.


**EDIT**: Also, the same problem was asked five years ago on CS Theory StackExchange and it was proven to be [NP-complete](https://cstheory.stackexchange.com/questions/1842/positive-topological-ordering-take-3). Here is the published version, [Topological orderings of weighted directed acyclic graphs, by Gerbner, Keszegh, Palmer, and Pálvölgyi](http://www.sciencedirect.com/science/article/pii/S0020019016300552)


