Is a matrix $A$ convertible to an upper-triangular matrix by row and column exchanges? (A problem in Philp N. Klein's "Coding the matrix") I am reading "Coding the matrix" by Philip N. Klein.
I want to know the solution of Problem 4.6.12.
What is a graph algorithm that solves the following problem?

*

*p.167 Problem 4.6.12:
(For the student with knowlege of graph algorithms) Design an algorithm that, for a given matrix, finds a list of a row-labels and a list of column-labels with respect to which the matrix is triangular (or report that no such lists exist).

If you have never read "Coding the matrix", you will not know the definition that a matrix is triangular.
A matrix $A = (a_{i j})$ is triangular if and only if there exist permutations $\sigma,  \tau$ such that $B = (b_{i j}) = (a_{\sigma(i) \tau(j))})$ is an upper-triangular matrix.
My answer (which doesn't use graph algorithms) is here:
$$m_i := \#\{a_{i j} \mid a_{i j} \ne 0, j \in \{1, 2, \cdots, n\}\}$$
$$n_j := \#\{a_{i j} \mid a_{i j} \ne 0, i \in \{1, 2, \cdots, n\}\}$$
$A$ is a triangular matrix if and only if $\{m_i \mid i \in \{1, 2, \cdots, n\}\} = \{1, 2, \cdots, n\}$ and $\{n_j \mid j \in \{1, 2, \cdots, n\}\} = \{1, 2, \cdots, n\}$.
If $A$ is triangular, then

*

*sort $m_1, m_2, \cdots, m_n$ and get $\sigma \in S_n$ such that $m_{\sigma(i)} = n - i + 1$

*sort $n_1, n_2, \cdots, n_n$ and get $\tau \in S_n$ such that $m_{\tau(j)} = j$.

Now, $B = (b_{i j}) = (a_{\sigma(i) \tau(j)})$ is an upper-triangular matrix.
 A: Firstly let see that your solution is wrong. Consider matrix
$$A_1 = \begin{bmatrix}
1 & 0 & 1 & 1\\
0 & 1 & 1 & 0\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 1\\
\end{bmatrix}.$$
Matrix $A_1$ is upper-triangular therefore it is triangular, but you would say it is not triangular, because there is no $j$ such that $n_j = 4$.
It could seem that replacing conditions $n'_j = j$ and $m'_i = i$ by $n'_j \le j$ and $m'_i \le i$ (where $n'_1, n'_2, \ldots, n'_n$ and $m'_1, m'_2, \ldots, m'_n$ are non-decreasing permutations of $n_1, \ldots, n_n$ and $m_1, \ldots, m_n$ correspondingly) may help. But that is not right too. One of possible counterexamples is
$$A_2 = \begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 1 & 1\\
0 & 1 & 1 & 1\\
0 & 0 & 1 & 1\\
\end{bmatrix}.$$

This problem is known to be NP-complete. Exponential time algorithm is presented in this paper. Brief description is here:


*

*If permanent is greater than $1$ then no desired permutation of rows and columns exists.

*If permanent is equal to $1$ then we can place corresponding 1's on the main diagonal. Consider remaining matrix as adjacency matrix of digraph and check whether there is topological order of this digraph (which correspond to upper-triangular permutation of matrix rows and columns).

*If permanent is equal to $0$ then some exhaustive search should be done.


Check whether permanent is $0$, $1$ or greater than $1$ can be done in polynomial time. It is based on easy fact that permanent of a $(0, 1)$-matrix $A$ is the number of perfect matchings in bipartite graph with biadjacency matrix $A$.
