Obtaining a Triangular Matrix by Independent Row-Column Permutations

Abstract

Given a square (0, 1)-matrix A, we consider the problem of deciding whether there exists a permutation of the rows and a permutation of the columns of A such that, after these have been carried out, the resulting matrix is triangular. The complexity of the problem was posed as an open question by Wilf [6] in 1997. In 1998, DasGupta et al. [3] seemingly answered the question, proving it is NP-complete. However, we show here that their result is flawed, which leaves the question still open. Therefore, we give a definite answer to this question by proving that the problem is NP-complete. We finally present an exponential-time algorithm for solving the problem.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In his contribution to the tribute to the late Professor Erdös [6], Wilf posed the following question: “Let A be an $m \times n$ matrix of 0’s and 1’s. Consider the computational problem: do there exist permutations P of the rows of A, and Q, of the columns of A such that after carrying out these permutations, A is triangular? The question we ask concerns the complexity of the problem. Is this problem NP -complete? Or, does there exist a polynomial-time algorithm for doing it?” As noted by Wilf, this problem is strongly related to job scheduling with precedence constraints, a well-known problem in theoretical computer science. The present paper is devoted to giving an answer to this question.

A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero. A triangular matrix is one that is either lower triangular or upper triangular. Because matrix equations with triangular matrices are easier to solve, they are very important in linear algebra and numerical analysis. We refer the reader to [4] for an advanced discussion.

For an arbitrary square matrix A, it is well-known that there exists an invertible matrix S such that $S^{-1}AS$ is upper triangular. We focus here, however, on permutation matrices. Recall that a permutation matrix is a square matrix obtained from the same size identity matrix by a permutation of rows. A product of permutation matrices (resp. the inverse of a permutation matrix) is also a permutation matrix. In fact, for any permutation matrix P, $P^{-1} = P^T$.

This paper is organized as follows. In Sect. 2, we provide the basic material needed for this paper. Section 3 is devoted to proving hardness of determining whether a square (0, 1)-matrix is permutation equivalent triangular, i.e. whether it can be transformed into a triangular matrix by independent row and column permutations. In Sect. 4, we give some properties of permutation equivalent triangular matrices, and present an exponential-time algorithm to determine whether a matrix is a permutation equivalent triangular matrix. The paper concludes with suggestions for further research directions.

2 Notations

For any positive integer n, denote $[n]=\{1, 2, \ldots , n\}$. Let $A = [a_{i,j}]$, $1 \le i \le m$ and $1 \le j \le n$, be a matrix of m rows and n columns. In the case that $m = n$, the matrix is square of order n. It is convenient to refer to either a row or a column of the matrix as a line of the matrix. We use the notation $A^T$ for the transpose of matrix A. We always designate a zero matrix by $\varvec{0}$, a matrix with every entry equal to 1 by J, and the identity matrix of order n by I. In order to emphasize the size of these matrices we sometimes include subscripts. Thus $J_{m,n}$ denotes the all 1’s matrix of size m by n, and this is abbreviated to $J_n$ if $m = n$. Notations $\varvec{0}_{m,n}$, $\varvec{0}_n$ and $I_n$ are similarly defined. In displaying a matrix we often use $*$ to designate a submatrix of appropriate dimensions. Two matrices A and B are said to be permutation equivalent if there exist permutation matrices P and Q of suitable sizes such that $B = PAQ$.

We will be mostly concerned with matrices whose entries consist exclusively of the integers 0 and 1. Such matrices are referred to as (0, 1)-matrices. For a (0, 1)-matrix A, we let $\omega (A)$ stand for the number of 1’s in A. A square matrix $A = [a_{i,j}]$ of order n is said to be lower left triangular (or llt, for short) if it has only 0’s above the main diagonal (i.e. $a_{i,j} = 0$ for $1 \le i < j \le n$). We write

for the llt (0, 1)-matrix whose 0’s are exclusively above the main diagonal. For two matrices $A = [a_{i,j}]$ and $B = [b_{i,j}]$ of size m by n, we write $A \le B$ if $a_{i,j} \le b_{i,j}$ for $1 \le i \le m$ and $1 \le j \le n$, so that a square matrix A of order n is llt if $A \le$

. In the context of permutation equivalent matrices, we will sometimes not be interested in any particular orientation of a triangular matrix and forget about any specific orientation such as “lower left”. Furthermore, for readability, a matrix which is permutation equivalent to a triangular matrix is said to be a pet matrix. The row sum vector ${{\mathrm{\mathcal {R}}}}(A) = \begin{bmatrix} r_1&r_2&\ldots&r_m \end{bmatrix}$ and the column sum vector ${{\mathrm{\mathcal {C}}}}(A) = \begin{bmatrix} c_1&c_2&\ldots&c_n \end{bmatrix}$ of A are defined by $r_i = \sum _{1 \le j \le n} a_{i,j}$ for $1 \le i \le m$ and $c_j = \sum _{1 \le i \le m} a_{i,j}$ for $1 \le j \le n$. The row sum vector ${{\mathrm{\mathcal {R}}}}(A)$ (resp. column sum vector ${{\mathrm{\mathcal {C}}}}(A)$) is stepwise bounded if $|\{i : r_i \le k \}| \ge k$ (resp. $|\{j : c_j \le k \}| \ge k$) for $1 \le k \le n$. It is clear that if a (0, 1)-matrix A is a pet matrix then both ${{\mathrm{\mathcal {R}}}}(A)$ and ${{\mathrm{\mathcal {C}}}}(A)$ are stepwise bounded. The permanent of $A = [a_{i,j}]$ is defined as the number given by the formula ${{\mathrm{per}}}(A) = \sum _{(j_1, j_2, \ldots , j_n) \in S_n} a_{1,j_1}\,a_{2,j_2}\, \ldots a_{n,j_n}$, where the summation is over all permutations $(j_1,j_2, \ldots , j_n)$ of [n]. Observe that, unlike the determinant, we do not put a minus sign in front of some of the terms in the summation. Of particular importance, the permanent does not change if the rows or columns of A are permuted.

For a set $K \subseteq [m]$ we will write $\overline{K}$ for the set $[m] \setminus K$. Let $K = \{i_1, i_2, \ldots , i_k\}$ be a set of k elements with $K \subseteq [m]$, and let $L = \{j_1, j_2, \ldots , j_l\}$ be a set of l elements with $L \subseteq [n]$. The sets K and L designate a collection of row indices and column indices, respectively, of the matrix A, and the k by l submatrix determined by them is denoted A[K, L]. Let $X = \{x_i : 1 \le i \le n\}$ be a non-empty set of n elements, that we call an n-set. Let $\mathcal {S} = (S_i : 1 \le i \le m)$ be m not necessarily distinct subsets of the n-set X. We refer to this collection of subsets of an n-set as a configuration of subsets. We set $a_{i,j} = 1$ if $x_j \in S_i$, and $a_{i,j} = 0$ if $x_i \notin S_i$. The resulting (0, 1)-matrix $A = [a_{i,j}]$, $1 \le i \le m$ and $1 \le j \le n$ of size m by n is the incidence matrix for the configuration of subsets $\mathcal {S}$ of the n-set X. The 1s in row $\alpha _i$ of A display the elements in the subset $S_i$, and the 1’s in column $\beta _j$ display the occurrences of $x_j$ among the subsets. Let $\mathcal {S} = (S_i : 1 \le i \le n)$ be a configuration of subsets of some ground n-set X. A bijective mapping $\varphi : \mathcal {S} \rightarrow [n]$ is said to be a stepwise bounded labeling (or sbl for short) of $\mathcal {S}$ if $\left| \bigcup _{\varphi (S_j) \le i}S_j\right| \le i$ for $1 \le i \le n$.

3 Answering Wilf’s Question

We prove in this section that, given a square (0, 1)-matrix A, deciding whether there exists a permutation matrix P and a permutation matrix Q of suitable size such that PAQ is triangular is NP-complete.

3.1 Disproving a Previous Related Result

Before giving our proof, it is worth mentioning that the following problem (called LBQIS(n, k) and rephrased to fit the context of this paper) is claimed to be NP-complete in [3]: Given a (0, 1)-matrix of order n and a positive integer $k \le n$, do there exist permutation matrices P and Q such that $PAQ = \begin{bmatrix} A_{1,1}&A_{1,2} \\ A_{2,1}&A_{2,2} \end{bmatrix}$ where $A_{1,2}$ is a square lower triangular matrix of size k by k? It is not very difficult to find a polynomial transformation from LBQIS to Wilf’s question, which would prove the NP-completeness of the latter. Just add $n-k$ all-zero rows and $n-k$ all-zero columns to matrix A to obtain a new matrix $A'$. Now, notice that each submatrix $A_{1,2}$ in a solution for LBQIS may be completed with the $n-k$ all-zero rows put before row 1 of $A_{1,2}$ and with the $n-k$ all-zero columns put after column k of $A_{1,2}$ to yield a solution for the instance $A'$ in Wilf’s question, and viceversa.

Unfortunately, paper [3] contains a serious flaw in the proof. To fix things, note that in [3] LBQIS is stated in terms of bipartite graphs, for which matrix A is the reduced adjacency matrix. Then, LBQIS(n, k) is proved NP-complete by reduction from another problem on bipartite graphs called LBIS(n, k), using the so-called Rearrangement Lemma (Lemma 3.5 in [3]). However, the proof of this lemma is not correct, as shown by the two following counter-examples, which address two different assertions in the proof. Let G be the graph (input for LBIS) with vertices $U=\{i\, |\, 1\le i\le 4\}$ and $V=\{i\, |\, 1\le i\le 4\}$, whose edges are (1, 1), (2, 1), (2, 2), (3, 2), (3, 4), (4, 3) and (4, 4). Thus, $n=4$. Define $k=1$. Let $G'$ be the input graph for LBQIS built as in [3], and $k'=k^2+k=2$. In the proof of the Rearrangement Lemma, the first line claims that, given $U'$ and $V'$ with respective vertex orders $\sigma _1$ and $\sigma _2$ that realize an LBQIS of size $k'$ for $G'$, one may assume that the vertices in $\sigma _1$ and $\sigma _2$ (which are pairs of integers) are in non-decreasing order of their first integer. This is contradicted by the sets $U'=\{[2,4], [1,2]\}$ and $V'=\{[1,3], [2,2]\}$ which realize an LBQIS of size $k'$ (i.e. 2) with the orders already indicated in $U'$ and $V'$, but which cannot be reordered as $U'=\{ [1,2],[2,4]\}$ and $V'=\{[1,3], [2,2]\}$ since these new orders do not realize an LBQIS any longer. So the first assertion in the proof is false. Moreover, the vertex subset $U'\cup V'$ of $G'$, with $U'=\{[1,1], [2,1]\}$ and $V'=\{[1,2], [1,3]\}$ is a solution of LBQIS of size $k'$ for which the second assertion in the same lemma (“clearly $q_1\le p_1$”) is also false. So, the proof of the Rearrangement Lemma is not correct, and consequently this also holds for the proof of the NP-completeness of LBQIS.

3.2 Our NP-completeness Proof for Wilf’s Question

We present our results in terms of sbl for configurations of subsets. The rationale for considering sbl for configurations of subsets stems from the following lemma.

Lemma 1

Let $\mathcal {S} = (S_i : 1 \le i \le n)$ be a configuration of subsets of some ground n-set, and let A be the corresponding incidence matrix. There exist permutation matrices P and Q of order n such that $PAQ \le$

iff there exists an sbl of $\mathcal {S}$.

We need to focus our attention on a special type of sbl. Call a bijective mapping $\varphi : \mathcal {S} \rightarrow [n]$ normalized if $\varphi$ maps the identical subsets of elements of $\mathcal {S}$ to a set of consecutive integers. Most of the interest in normalized bijective labelings stems from the following intuitive lemma.

Lemma 2

Let $\mathcal {S} = (S_i : 1 \le i \le n)$ be a configuration of subsets of some ground n-set. If there exists an sbl of $\mathcal {S}$ then there exists a normalized sbl of $\mathcal {S}$.

We are now ready to prove that deciding whether there exists an sbl of some configuration of subsets is NP-complete thereby proving that deciding whether a square (0,1)-matrix is a pet matrix is NP-complete as well. The proof proceeds by a reduction from the NP-complete 3Sat problem [2]. Let an arbitrary instance of the 3Sat problem be given by a 3CNF formula $\phi = c_1 \vee c_2 \vee \ldots \vee c_m$ over variables $x_1, x_2, \ldots , x_n$. Our construction is divided into two steps: (1) construction of a (polynomial size) ground set $\mathbf{X }$ and (2) construction of a configuration of subsets C of the ground set $\mathbf{X }$. Throughout the proof, parts of the ground set $\mathbf{X }$ are written as capital bold letters ($\mathbf{V }, \mathbf T , \mathbf F , \ldots$) and subsets of the configuration are written with capital calligraphic letters ($\mathcal {V}_i, \mathcal {T}_i, \mathcal {F}_i, \ldots$).

Fig. 1.

Illustration of the construction for the 3CNF formula $\phi = (x_1 \vee x_2 \vee x_3) \wedge (\overline{x}_1 \vee \overline{x}_2 \vee x_3) \wedge (\overline{x}_1 \vee x_2 \vee \overline{x}_3)$. Identical subsets are not distinguishable in our representation. A satisfying truth assignment is given by $f(x_1) = \mathrm {TRUE}$, $f(x_2) = \mathrm {FALSE}$ and $f(x_3) = \mathrm {FALSE}$. For sake of clarity, neither the ground set $\mathbf X$ nor the collection of subsets C is fully represented.

To begin with, define $p_i = 3(n + m + 1 - i) + 2$, $q_i = 3(n + m + 1 - i) + 1$ and $r_i = 3(n + m + 1 - i)$ for $1 \le i \le n + m$. Furthermore, define $p_{n+m+1}=1$, $K = \sum _{i=1}^{n} q_i + 2 \sum _{i=n+1}^{n+m} q_i$ and $L = \sum _{i=1}^{n+m} (p_{i+1} + r_i)$. Let us now define the ground set $\mathbf {X}$. Consider the pairwise disjoint sets defined as follows: $\mathbf {V}_i = \{v_{i, j} \mid 1 \le j \le p_i\}$, $\mathbf {V}'_i = \{v'_{i, j} \mid 1 \le j \le r_i\}$, $\mathbf {T}_i = \{t_{i, j} \mid 1 \le j \le q_i\}$, $\mathbf {F}_i = \{f_{i, j} \mid 1 \le j \le q_i\}$ for $1 \le i \le n$. Furthermore, define $\mathbf {C}_i = \{c_{i, j} \mid 1 \le j \le p_{n + i}\}$ $\mathbf {C}'_i = \{c'_{i, j} \mid 1 \le j \le r_{n + i}\}$ for $1 \le i \le m$, and $\mathbf {L}_{i, k} = \{\ell _{i, k, j} \mid 1 \le j \le q_{n + i}\}$ for $1 \le i \le m$ and $1 \le k \le 3$. Finally, define $\mathbf {S} = \{s\}$. For simplicity of notation, write $\mathbf {V} = \bigcup _{1 \le i \le n} \mathbf {V}_i$, $\mathbf {V}'= \bigcup _{1 \le i \le n} \mathbf {V}'_i$, $\mathbf {T} = \bigcup _{1 \le i \le n} \mathbf {T}_i$, $\mathbf {F} = \bigcup _{1 \le i \le n} \mathbf {F}_i$, $\mathbf {C} = \bigcup _{1 \le i \le m} \mathbf {C}_i$, $\mathbf {C}' = \bigcup _{1 \le i \le m} \mathbf {C}'_i$, and $\mathbf {L}_i = \bigcup _{1 \le k \le 3} \mathbf {L}_{i, k}$ for $1 \le i \le m$ and $\mathbf {L} = \bigcup _{1 \le i \le m} \mathbf {L}_i$. Informally, elements of $\mathbf {V} \cup \mathbf {V}'$ are associated to variables, elements of $\mathbf {T} \cup \mathbf {F}$ are associated to literals, elements of $\mathbf {C} \cup \mathbf {C}'$ are associated to clauses, elements of $\mathbf {L}$ are associated to literals in clauses and $\mathbf {S}$ is a separator set. The ground set $\mathbf {X}$ of our construction is defined to be $\mathbf {X} = \mathbf {V} \cup \mathbf {V}' \cup \mathbf {T} \cup \mathbf {F} \cup \mathbf {C} \cup \mathbf {C}' \cup \mathbf {L} \cup \mathbf {S}$.

Having defined the ground set $\mathbf {X}$, we now turn to the detailed construction of a configuration of subsets C of $\mathbf {X}$. For sake of clarity, this will be divided into several steps. First, each variable $x_i$, $1 \le i \le n$, is associated to identical subsets $\mathcal {V}_{i, j}$, $1 \le j \le q_i$, in C. These subsets are defined as follows: $\mathcal {V}_{i, j} = \left( \bigcup _{1 \le k \le i} \mathbf {V}_k \right) \cup \left( \bigcup _{1 \le k \le i-1} \mathbf {V}'_k \right)$ for $1 \le i \le n$ and $1 \le j \le q_i$. Let us denote by $\mathcal {V}_i$, $1 \le i \le n$, the collection $(\mathcal {V}_{i, j} \mid 1 \le j \le q_i)$. Next, each (positive) literal $x_i$, $1 \le i \le n$, is associated to identical subsets $\mathcal {T}_{i, j}$, $1 \le j \le r_i$, and to identical subsets $\mathcal {T}'_{i, j}$, $1 \le j \le p_{i + 1}$. These subsets are defined as follows: $\mathcal {T}_{i, j} = \mathbf {T}_i \cup \left( \bigcup _{1 \le k \le i} \mathbf {V}_k \right) \cup \left( \bigcup _{1 \le k \le i-1} \mathbf {V}'_k \right)$ for $1 \le i \le n$ and $1 \le j \le r_i$, and $\mathcal {T}'_{i, j} = \mathbf {T}_i \cup \left( \bigcup _{1 \le k \le i} \mathbf {V}_k \right) \cup \left( \bigcup _{1 \le k \le i} \mathbf {V}'_k \right)$ for $1 \le i \le n$ and $1 \le j \le p_{i+1}$. Of course, a similar construction of subsets applies for the negation $\overline{x}_i$ of each variable $x_i$, i.e., $\mathcal {F}_{i, j} = \mathbf {F}_i \cup \left( \bigcup _{1 \le k \le i} \mathbf {V}_k \right) \cup \left( \bigcup _{1 \le k \le i-1} \mathbf {V}'_k \right)$ for $1 \le i \le n$ and $1 \le j \le r_i$, and $\mathcal {F}'_{i, j} = \mathbf {F}_i \cup \left( \bigcup _{1 \le k \le i} \mathbf {V}_k \right) \cup \left( \bigcup _{1 \le k \le i} \mathbf {V}'_k \right)$ for $1 \le i \le n$ and $1 \le j \le p_{i+1}$. For readability, write $\mathcal {T}_i = (\mathcal {T}_{i, j} \mid 1 \le j \le r_i)$, $\mathcal {T}'_i = (\mathcal {T}'_{i, j} \mid 1 \le j \le p_{i+1})$, $\mathcal {F}_i = (\mathcal {F}_{i, j} \mid 1 \le j \le r_i)$ and $\mathcal {F}'_i = (\mathcal {F}'_{i, j} \mid 1 \le j \le p_{i+1})$ for $1 \le i \le n$. Note that the following (strict) inclusions hold for all $1 \le i \le n$, $1 \le j_1 \le q_i$, $1 \le j_2 \le r_i$ and $1 \le j_3 \le p_{i+1}$: (i) $\mathcal {V}_{i, j_1} \subset \mathcal {T}_{i, j_2} \subset \mathcal {T}'_{i, j_3}$ and (ii) $\mathcal {V}_{i, j_1} \subset \mathcal {F}_{i, j_2} \subset \mathcal {F}'_{i, j_3}$. We now turn to the m clauses of the 3CNF formula. Each clause $c_i$, $1 \le i \le m$, is associated to identical subsets $\mathcal {C}_{i, j}$, $1 \le j \le q_{n+i}$. These subsets are defined as follows: $\mathcal {C}_{i, j} = \mathbf {V} \cup \mathbf {V}' \cup \left( \bigcup _{1 \le k \le i} \mathbf {C}_k \right) \cup \left( \bigcup _{1 \le k \le i-1} \mathbf {C}'_k \right)$ for $1 \le i \le m$ and $1 \le j \le q_{n+i}$. Let us denote by $\mathcal {C}_i$, $1 \le i \le m$, the collection $(\mathcal {C}_{i, j} \mid 1 \le j \le q_{n+i})$. It is easily seen that $\mathcal {V}_{i, j_1} \subset \mathcal {C}_{k, j_2}$ for all $1 \le i \le n$, $1 \le j_1 \le q_i$, $1 \le k \le m$ and $1 \le j_2 \le q_{n+k}$.

Now, we consider the only part of the construction that depends on which literal occurs in which clauses. Denote by $\lambda _{i, k}$ the k-th literal of clause $c_i$, that is write $c_i = \lambda _{i, 1} \vee \lambda _{i, 2} \vee \lambda _{i, 3}$ for $1 \le i \le m$, where each $\lambda _{i, k}$ is a variable or its negation. The k-th literal, $1 \le k \le 3$, of each clause $c_i$, $1 \le i \le m$, is associated to identical subsets $\mathcal {L}_{i, k, j}$, $1 \le j \le r_{n+i}$, and to identical subsets $\mathcal {L}'_{i, k, j}$, $1 \le j \le p_{n+i+1}$. These subsets are defined as follows: $\mathcal {L}_{i, k, j} = \mathbf {V} \cup \mathbf {V}' \cup \mathbf {A}_k \cup \mathbf {L}_{i, k} \cup \left( \bigcup _{1 \le \ell \le i} \mathbf {C}_\ell \right) \cup \left( \bigcup _{1 \le \ell \le i-1} \mathbf {C}'_\ell \right)$ for $1 \le i \le m$, $1 \le j \le r_{n+i}$ and $1 \le k \le 3$ and $\mathcal {L}'_{i, k, j} = \mathbf {V} \cup \mathbf {V}' \cup \mathbf {A}_k \cup \mathbf {L}_{i, k} \cup \left( \bigcup _{1 \le \ell \le i} \mathbf {C}_\ell \right) \cup \left( \bigcup _{1 \le \ell \le i} \mathbf {C}'_\ell \right)$ for $1 \le i \le m$, $1 \le j \le p_{n+i+1}$ and $1 \le k \le 3$, where $\mathbf {A}_k = \mathbf {T}_\ell$ if $\lambda _{i, k} = x_\ell$ and $\mathbf {A}_k = \mathbf {F}_\ell$ if $\lambda _{i, k} = \overline{x}_\ell$. For the sake of clarity, write $\mathcal {L}_{i, k} = (\mathcal {L}_{i, k, j} \mid 1 \le j \le r_{n+i})$ and $\mathcal {L}'_{i, k} = (\mathcal {L}'_{i, k, j} \mid 1 \le j \le p_{n+i+1})$ for $1 \le i \le m$ and $1 \le k \le 3$. Again, observe that $\mathcal {C}_{i, j_1} \subset \mathcal {L}_{i, k, j_2} \subset \mathcal {L}_{i, k, j_2}$ for all $1 \le i \le m$, $1 \le j_1 \le q_{n+i}$, $1 \le j_2 \le r_{n+i}$, $1 \le j_3 \le p_{n+i+1}$ and $1 \le k \le 3$.

Our construction ends with $p_1 + K - 1$ utility subsets. These subsets will be partitioned into two separate classes according to their intended function: bootstrap subsets and separator subsets. First, C contains identical bootstrap subsets $\mathcal {B}_i$, $1 \le i \le p_1 - 1$, defined as follows: $\mathcal {B}_i = \emptyset$ for $1 \le i \le p_1 - 1$. The idea is to force any sbl to map the $p_1 - 1$ empty sets of $\mathcal {B}$ to the first $p_1 - 1 = 3(n + m) + 1$ integers. Indeed, it is easily seen that all the above defined subsets of the configuration of subsets C but those of $\mathcal {B}$ contain at least $p_1$ elements and hence cannot be mapped to an integer $i \le p_1 - 1$ in any sbl of C. Second, C contains identical separator subsets $\mathcal {S}_i$, $1 \le i \le K$, defined by: $\mathcal {S}_i = \mathbf {V} \cup \mathbf {V}' \cup \mathbf {C} \cup \mathbf {C}' \cup \mathbf {S}$ for $1 \le i \le K$. The rationale of these subsets is that we need a separator between subsets in C corresponding to a satisfying truth assignment f for the 3CNF formula $\phi$ and garbage subsets of C, that is subsets not involved in the satisfying truth assignment f. For simplicity, let us denote by $\mathcal {B}$ the collection $(\mathcal {B}_i \mid 1 \le i \le p_1 - 1)$ and by $\mathcal {S}$ the collection $(\mathcal {S}_i \mid 1 \le i \le K)$. Clearly our construction can be carried out in polynomial time: indeed, we have $|\mathbf {X}| = O(m^2 + n^2)$ and $|C| = O(m^2 + n^2)$.

Lemma 3

There exists a satisfying truth assignment f for $\phi$ iff there exists an sbl of the configuration of subsets C of the ground set $\mathbf {X}$.

The key elements of the proof are as follows. First, it is crucial to focus on solutions that map identical subsets of elements of C to a set of consecutive elements (see Lemma 2). Second, the general shape of the solution is largely guided by the construction. Indeed, the empty subsets have to be placed first, followed by subsets corresponding to literals (either the positive or the negative literal of each variable is chosen) and next by subsets corresponding to clauses (one satisfying literal of each clause is chosen). Finally the separator subsets have to be placed, with the result that (thanks to the large polynomial number of such subsets) the remaining subsets can be placed in any order without violating the sought sbl property. The reader is invited to consider Fig. 1 for a schematic illustration of the reduction. We now briefly discuss, in an informal way, the two key arguments that are used in the proof. First, the whole procedure is, to some extent, similar to the accounting method used in amortized complexity analysis. Indeed, one might view the operation of placing a set (one after the other) as the process of charging some customer, the cost being the number of new elements that are introduced. With this metaphor in mind, notice that we do not charge when a subset does not introduce any new element, so that the leftover amount can be stored as “credit”. When we place a new subset that does introduce some new elements, we can use the “credit” stored to pay for the cost of the operation. Second, when a subset uses the “credit” stored to pay the cost of introducing new elements, the following invariants can be shown to hold true: (i) it uses all the available credit and (ii) it does not allow to accumulate (it should be now clear that consecutive identical subsets do allow for accumulating credit) as much credit as it has consumed, thereby proving that subsets introduce less and less new elements as we progress adding subsets one after the other.

Theorem 1

Let A be a (0, 1)-matrix. Deciding whether A is a pet matrix is NP-complete.

4 Exponential-Time Algorithm

We present here an exponential-time algorithm for deciding whether a given a (0, 1)-matrix A of order n is a pet matrix. We start by presenting some basic properties of square (0, 1)-matrices that can be transformed into some triangular matrix by row and column independent permutations to help solving involved algorithmic issues. We of course focus of polynomial-time checkable properties.

We first focus on the permanent of a square (0, 1)-matrix. A well-known result (see e.g. [1]) states that for a (0, 1)-matrix A of order n, one has ${{\mathrm{per}}}(A)=1$ iff the lines of A may be permuted to yield a triangular matrix with 1’s in the n main diagonal positions and 0’s above the main diagonal. This theorem amounts to saying that ${{\mathrm{per}}}(A)=1$ iff there exist permutation matrices P and Q such that $I \le PAQ \le$

. As shown in the following lemma, ${{\mathrm{per}}}(A)=1$ is certainly a threshold value in our context.

Lemma 4

Let A be (0, 1)-matrix. If A is a pet matrix then ${{\mathrm{per}}}(A) \le 1$.

Notice that deciding ${{\mathrm{per}}}(A) \le 1$ for (0, 1)-matrices of order n reduces to computing at most $n+1$ perfect matchings in bipartite graphs [1], and hence the above test is $O(n^3\,\sqrt{n})$ time as the Hopcroft–Karp algorithm for computing a maximum matching in a bipartite graph $B = (V,E)$ runs in $O(|E|\,\sqrt{|V|})$ [5].

Next, it is a simple matter to check that if a (0, 1)-matrix A of order n is a pet matrix, then it contains at most $\frac{1}{2}n(n+1)$ 1’s (i.e., $\omega (A) \le \frac{1}{2}n(n+1)$). The following lemma gives a lower bound.

Lemma 5

Let A be (0, 1)-matrix of order n, $n \ge 2$. If A contains at most $n+1$ 1’s, then A is a pet matrix.

Notice that, albeit not very impressive, Lemma 5 is tight as the square matrix $\begin{bmatrix} I_{n-2}&\varvec{0}_{n-2,2} \\ \varvec{0}_{2,n-2}&J_{2} \end{bmatrix}$ of order n has $n-2+4 = n + 2$ 1’s and is not a pet matrix.

Finally, the following trivial lemma gives another condition that helps improving the running time of the algorithm in practice.

Lemma 6

Let A be (0, 1)-matrix of order n and D(A) the directed graph associated to A (i.e., the adjacency matrix of D(A) is A). If D(A) is acyclic (excluding self-loops), then A is a pet matrix.

We now turn to presenting our exponential-time algorithm. The simplest exhaustive algorithm considers every possible pair of permutation matrices (P, Q) yielding an $O((n!)^2 \;\cdot \; {{\mathrm{poly}}}(n))$ time algorithm. However, according to Lemma 1, it is enough to consider every permutation matrix P of order n and check whether the first i, $1 \le i \le n$, rows of PA have 1’s in at most i columns. This observation yields an $O(n! \,\cdot \, {{\mathrm{poly}}}(n))$ time algorithm. We propose here another exhaustive algorithm that improves on the $O(n! \,\cdot \, {{\mathrm{poly}}}(n))$ time algorithm. The basic idea is to recursively split into smaller submatrices, instead of enumerating all permutations. For a (0, 1)-matrix A of order n, we consider every possible set R of $\left\lceil n/2 \right\rceil$ rows of A and every possible set of $\left\lceil n/2 \right\rceil$ columns C of A, and check whether these lines induce a zero matrix (or a matrix with at most one 1 in case the matrix has odd order; details follow).

Fig. 2.

Obtaining a triangular (0,1)-matrix by recursively placing a $\varvec{0}$ matrix in the upper right part.

If n is even, we let P and Q be two permutation matrices that put the rows in R at the first $\left\lceil n/2 \right\rceil$ positions and the columns in C at the last $\left\lceil n/2 \right\rceil$ positions. The key element for the improvement is that no specific order is required for the rows in R nor for the columns in C. The algorithm rejects the matrix A for the subsets R and C if $\omega (A[R, C]) > 1$, otherwise we can write PAQ as in Fig. 2(a), where $A_1$ and $A_2$ are matrices of order $\left\lceil n/2 \right\rceil = n/2$, and we proceed by recursively checking that both $A_1$ and $A_2$ are pet matrices. The case when n is odd is a bit more involved. First, the algorithm rejects matrix A for the subsets R and C if $\omega (A[R, C]) > 1$. Otherwise, we need to consider two (possibly positive) cases: $\omega (A[R, C]) = 1$ or $\omega (A[R, C]) = 0$. If $\omega (A[R, C]) = 1$, we let P and Q be two permutation matrices that put the rows in R at the first $\left\lceil n/2 \right\rceil$ positions and the columns of C at the last $\left\lceil n/2 \right\rceil$ positions (no specific order for the rows in R nor for the columns in C, except that the 1 of A is at row index $\left\lceil n/2 \right\rceil$ and at column index $\left\lceil n/2 \right\rceil$ in PAQ). We can write PAQ as in Fig. 2(b), where $A_1$ and $A_2$ are matrices of order $\left\lfloor n/2 \right\rfloor$, and we proceed by recursively checking that both $A_1$ and $A_2$ are pet matrices. Finally, if $\omega (A[R, C]) = 0$, for every row index $i \in R$ and every column index $j \in C$, we let P and Q be two permutation matrices that put the rows in R at the first $\left\lceil n/2 \right\rceil$ positions and the columns of C at the last $\left\lceil n/2 \right\rceil$ positions (no specific order for the rows in R nor for the columns in C except that row i in A is at row index $\left\lceil n/2 \right\rceil$ and column index j is at column index $\left\lceil n/2 \right\rceil$ in PAQ). We can write PAQ as in Fig. 2(c), where $A_1$ and $A_2$ are matrices of order $\left\lfloor n/2\right\rfloor$, and we proceed by recursively checking that both $A_1$ and $A_2$ are pet matrices.

A detailed description is given in Algorithms 1, 2 and 3. We now turn to evaluating the time complexity of this algorithm and we write T(n) for the time complexity of calling ${\textsf {permTriangular}}(A)$ for some (0, 1)-matrix A or order n. We have

$$ T(n) \le {\left\{ \begin{array}{ll} \left( \left\lceil n/2 \right\rceil \right) ^2 \left( {\begin{array}{c}n\\ \left\lceil n/2 \right\rceil \end{array}}\right) ^2 \left( 2T\left( \left\lfloor n/2 \right\rfloor \right) +1\right) + O(n^3\sqrt{n}) &{} \text {if { n} is odd} \\ 2\,\left( \left\lceil n/2 \right\rceil \right) ^2 \left( {\begin{array}{c}n\\ \left\lceil n/2 \right\rceil \end{array}}\right) ^2\; T\left( \left\lfloor n/2 \right\rfloor \right) + O(n^3\sqrt{n})&\text {if { n} is even} \end{array}\right. } $$

with $T(1) = O(1)$. The $O(n^3\sqrt{n})$ term is the time complexity for lines 2 and 3 in Algorithm 1. We also observe that the worst case occurs when $n = 2^m - 1$ as $\left\lfloor n/2 \right\rfloor , \left\lfloor n/4 \right\rfloor , \ldots$ are odd integers. Looking for an asymptotic solution of the worst case, we thus write the following simplified recurrence: $T(2^m) = 2^{2m - 2} \, \left( {\begin{array}{c}2^m\\ 2^{m-1}\end{array}}\right) ^2 \, \left( 2T(2^{m-1}) + 1\right) + 2^{7m/6}$, with $T(1) = 1$. Now, write $\alpha (2^m) = 2^{2m - 2} \, \left( {\begin{array}{c}2^m\\ 2^{m-1}\end{array}}\right) ^2$. Clearly, $\alpha (2^m) \ge 2^{7m/6}$, and hence we focus for now on on the recurrence $T(2^m) = 2\,\alpha (2^m)\,\left( T(2^{m-1}) + 1\right)$. A convenient non-recursive form of $T(2^m)$ is given in the following lemma.

Lemma 7

$T(2^m) = \left( 2^m \prod _{i=1}^{m} \alpha (2^{i}) \right) + \left( \sum _{i=1}^{m} 2^{m-i+1} \prod _{j=i}^{m} \alpha (2^{j}) \right)$.

We now need the following lemma, in order to give an asymptotic solution for T(n) in Proposition 1.

Lemma 8

$\sum _{i=1}^{m} 2^{m-i} \prod _{j=i}^{m} \alpha (2^{j}) = O\left( m \, 2^{2^{m+2}+m+1}\right)$.

Proposition 1

Algorithm permTriangular runs in $O\left( n\,2^{4n}\,\pi ^{-\log (n)} \right)$ time.

Proof

We have already observed that the worst case occurs for $n=2^m-1$. According to Lemma 8, we have $T(2^m) = O\left( 2^{2^{m+2}+m-3}\,\pi ^{-m} \right)$ and hence $T(n) = O\left( 2^{2^{\log (n)+2}+\log (n)-3}\,\pi ^{-\log (n)} \right) = O\left( n\,2^{4n}\,\pi ^{-\log (n)} \right)$.    $\square$

5 Conclusion

We suggest further research directions regarding the hardness of recognizing pet (0,1)-matrices. (i) What is the average running time of Algorithm permTriangular for pet matrices? (ii) A graph labeling strongly related to symmetric pet (0,1)-matrices can be defined as follows: Given a graph $G=(V,E)$ or order n, decide whether there exists a bijective mapping $f : V \rightarrow [n]$ such that $f(u) + f(v) > n$ for every edge $\{u,v\} \in E$ (i.e., $PAP^T \le$

). Investigating the relationships between the two combinatorial problems is expected to yield fruitful results.