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.

andcolumns, or rowsorcolumns? $\endgroup$ – Federico Poloni Jan 2 '15 at 15:422more comments