8
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Do you mean permuting rows and columns, or rows or columns? $\endgroup$
    – Federico Poloni
    Commented Jan 2, 2015 at 15:42
  • 1
    $\begingroup$ what is a binary matrix? what if the matrix is made up of all one's? $\endgroup$
    – abel
    Commented Jan 2, 2015 at 15:47
  • $\begingroup$ @FedericoPoloni: I mean "and", I will now clarify this. $\endgroup$
    – Rob Myers
    Commented Jan 2, 2015 at 15:54
  • 1
    $\begingroup$ This just had an answer which got deleted. Here's a simplification of it (definitely based on it). (a) prove that any row with a single 1 can serve as the first row. (b) use the following algorithm: choose a row with a single 1 for the first row. Delete the column that 1 is in. Then recurse. How do you prove any row with a single 1 can serve as the first row? Consider an $n \times n$ matrix $M$ with $M(i,j) = 1$ if $j \leq i$ except for row $i'$, which has exactly one $1$ in position $(i',j')$ with $j' \leq i'$. Cyclically permute the rows from $1$ to $i'$, and the columns from $1$ to $j'$. $\endgroup$
    – Peter Shor
    Commented Jan 4, 2015 at 20:23
  • 2
    $\begingroup$ As noted by Mohammad, I've asked the same thing five years ago on Mathoverflow, where you can find all the relevant literature: cstheory.stackexchange.com/questions/1842/… $\endgroup$
    – domotorp
    Commented Aug 28, 2016 at 7:57

3 Answers 3

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks a lot for this, I didn't expect such a perfect reference. $\endgroup$
    – Rob Myers
    Commented Jun 9, 2015 at 20:14
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How does this even address the question, which asks for references concerning the complexity of the given problem? $\endgroup$
    – Alex M.
    Commented Jan 13, 2019 at 16:26
  • $\begingroup$ To be fair, the Clarification of the OP might make it seem like this would be an answer, if one is reading too quickly. $\endgroup$
    – Todd Trimble
    Commented Jan 13, 2019 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .