When a given square sparse matrix can be permuted into a lower triangular form?

For some, the question in the title of this post could look trivial. After all, they have been doing LU decomposition in Matlab and using Matlab’s mldivide (or “backslash”) to solve systems with the factor matrices. These are usually done without worrying if the pivoting took place and permuted those factor matrices (Matlab used to call them psychologically triangular matrices. For “why?” and “who said that?”, see here). Because, the help page of mldivide says that it tests if a matrix “is square, is not diagonal, looks triangular, is actually triangular, there are zeros in the diagonal, is a permuted triangular”. So this must be taken care of…

Davis’s “Direct Methods for Sparse Linear Systems” book (a real gem) asks in its Exercise 3.7:

…Consider a matrix $\mathbf{A}$ that may be a permuted upper or lower triangular matrix with both rows and columns permuted by unknown permutations $\mathbf{P}$ and $\mathbf{Q}$. Write an algorithm that determines if the matrix is in this form and, if so, solves $\mathbf{A}x = b$….

Then the book hints an algorithm, which builds the permutation matrices essentially by picking a row with a single nonzero, ordering that row and the associated column, and then by deleting both from the matrix and so on. But this is ok, only if we can recover a full diagonal! What if, at some point, we have rows or columns with no entries at all? The “algorithm” does not handle this case.

It is perhaps ok in the context of LU decomposition, in which case one is warned of about the numerical rank deficiency during LU decomposition (before one attempts to solve the linear systems). But in general it is not ok; at Mathworks, folks are aware of this (see here). If the matrix is not coming from LU decomposition, then we may well be in trouble. We are back to the question: When a given square sparse matrix can be permuted into a lower triangular form?

Some other cases are also easy. If there is a perfect matching in the given matrix, then all standard matching algorithms find it quickly, and after permuting the matching entries to the diagonal, we can check if the matrix is reducible into $1\times 1$ blocks (or the directed graph of $\mathbf{B}=\mathbf{AQ}$ is acyclic, where $\mathbf{Q}$ permutes the columns of $\mathbf{A}$ to have a zero-free diagonal in $\mathbf{B}$). Every step of this is linear time—even computing the matching with the standard tricks). So this case is handled. The question is complicated when we do not have a perfect matching. It is in fact NP-complete to decide if a given square sparse matrix can be permuted into a lower/upper triangular form [1] with unsymmetric permutations.

So writing it once more to emphasize it:

It is easily decidable to test if $\mathbf{A}$ can be symmetrically permuted to a lower/upper triangular form. The directed graph of $\mathbf{A}$ should be acyclic (or $\mathbf{PAP}^T$ is lower/upper triangular).

It is NP-complete to decide if a given square sparse matrix can be permuted to a lower/upper triangular form. Otherwise said, one can find two permutation matrices $\mathbf{P}$ and $\mathbf{Q}$ such that $\mathbf{PAQ}$ is lower/upper triangular only with non-polynomial time algorithms, assuming P$\neq$ NP.

The topic was discussed elsewhere before.

References

1. Guillaume Fertin, Irena Rusu, and Stéphane Vialette:
Obtaining a triangular matrix by independent row-column permutations. ISAAC 2015: 165–175 (doi)