6
$\begingroup$

The input of my problem is a 0/1 matrix. The problem consists in finding the largest triangular submatrix.

In my problem, a square matrix is called triangular if all the entries below (or above) the main diagonal (or the off diagonal) are zero and all the entries on the diagonal are equal to one.

For example, in the following matrix $$M=\begin{pmatrix} 1&1&1&1&1&1\\1&0&1&1&1&1\\1&1&1&0&0&1\\0&0&1&0&1&1\\1&1&1&1&1&1\\1&0&1&0&0&1 \end{pmatrix}, $$ there is an obvious 3x3 triangular submatrix $M([3,4,5],[4,5,6])$ but there also is a less obvious 4x4 triangular submatrix $M([2,3,6,4],[4,2,1,5])$.

For a given matrix, is there a known algorithm to find the largest triangular submatrix?

Thank you!

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you clarify what "triangular submatrix" means? $\endgroup$
    – Kevin Buzzard
    Commented Feb 1, 2017 at 19:08
  • $\begingroup$ The matrix $M([2,3,6,4],[4,2,1,5]) = \pmatrix{1 & 0 & 1 & 1\cr 0 & 1 & 1 & 0\cr 0 & 0 & 1 & 0\cr 0 & 0 & 0 & 1\cr}$ is indeed upper triangular, but $M([3,4,5],[4,5,6]) = \pmatrix{0 & 0 & 1\cr 0 & 1 & 1\cr 1 & 1 & 1\cr}$ is neither upper nor lower triangular. Perhaps you meant $M[(5,4,3],[4,5,6])$? $\endgroup$
    – Robert Israel
    Commented Feb 1, 2017 at 21:40
  • 3
    $\begingroup$ Of course, any matrix that is triangular in any of the four possible ways (upper, lower, "top left" or "bottom right") can be made upper triangular by reversing the order of its rows and/or columns, so you might as well ask for upper triangular. $\endgroup$
    – Robert Israel
    Commented Feb 1, 2017 at 21:43
  • $\begingroup$ @RobertIsrael Yes, exactly, I meant triangular in any of the four possible ways. $\endgroup$
    – Tam
    Commented Feb 1, 2017 at 21:59

1 Answer 1

Reset to default
2
$\begingroup$

Actually, it seems my problem has been studied in the following paper:

The authors proved the problem of finding the largest triangular submatrix is NP-complete. However, they do not provide any algorithm.

Improve this answer
$\endgroup$

You must log in to answer this question.

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