Transforming a binary matrix into triangular form using permutation matrices 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 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, Markowsky proves that $R$ is lower or upper unitriangularisable iff $L$ has length $|M(L)|$ or $|J(L)|$ respectively.
 A: Luckily, the problem is no more in the "NP-limbo". The paper Obtaining a triangular matrix by independent row-column permutations 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. Here is the published version, Topological orderings of weighted directed acyclic graphs, by Gerbner, Keszegh, Palmer, and Pálvölgyi
A: This problem was studied by Knuth's PhD student Ramsey W. Haddad in his thesis: Triangularization: A Two-Processor Scheduling Problem.
According to the thesis, the problem is in the "NP-limbo" (not known to be NP-complete or in P). The thesis was published in 1990, which is prior to the reference you mention. However, it contains a lot of observations on the problem and the complexity analysis of some extensions of the problem, which may be of your interest.
Also, you may be able to track up new references starting from there. 
A: I think I have an algo to find a permutation that can transform any matrix to lower triangular form. Given any random lower triangular matrix $L$ and any random permutation matrix $P$, I can produce the matrix $C = P^{-1} L P$.
Now, given the matrix $C$ and nothing else, my algo can find a permutation $P'$ (sometimes different from $P$) which satisfies $C=P'^{-1} L' P'$ and $L'$ is lower triangular. If you imagine each element of a matrix as a link from a father (column $j$) to a child (row $i$), each time the first child is before the father (first $i<j$), that means something wrong: you have to put the father at the place of this child an then slide this child and all other childs between the wrong child and the father, it's $j-i$ permutations to do on the matrix. Repeat the same process on each permuted matrix obtained.
