15
$\begingroup$

Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?

$\endgroup$
  • $\begingroup$ the obvious necessary condition is ${\rm det}\,A=0$. $\endgroup$ – Carlo Beenakker Aug 3 '18 at 10:14
  • $\begingroup$ @CarloBeenakker OP did not specify that $A$ is square. $\endgroup$ – Federico Poloni Aug 3 '18 at 10:14
  • 1
    $\begingroup$ There are only so many permutation matrices. You could just try them all. $\endgroup$ – Gerry Myerson Aug 3 '18 at 10:32
  • 3
    $\begingroup$ @GerryMyerson Not when the dimension is higher than about 12... $\endgroup$ – Jack M Aug 3 '18 at 10:33
  • 2
    $\begingroup$ Then maybe, Jack, you should go into more detail about what you really want. $\endgroup$ – Gerry Myerson Aug 3 '18 at 12:49
22
$\begingroup$

Let's see if I can convince everyone that this problem is NP-complete.

First: it is in NP because a permutation $P$ can be guessed and checked in polynomial time.

I'll restate the problem: Given a vector $x$ and a vector space $V$ (the null-space of $A$), is there a permutation of $x$ that lies in $V$?

I'll take the number of components of $x$ to be $2n$. I believe that any vector space is the null space of some matrix, so I'll take the vector space $V$ consisting of all vectors whose sum of the first $n$ components equals the sum of the other $n$ components. It has dimension $2n-1$.

Now take $x$ to be a vector of integers. There is a permutation of $x$ that lies in $V$ iff the entries of $x$ can be divided into two halves of the same sum. This is the PARTITION problem that we all teach our students to be NP-complete.

$\endgroup$
  • 4
    $\begingroup$ No need for belief, just take $A=(1,1,\dots,1,-1,-1,\dots,-1)$. $\endgroup$ – Emil Jeřábek supports Monica Aug 3 '18 at 11:57
  • $\begingroup$ So my problem is a generalization of PARTITION. Doesn't this only show that the problem is NP-hard? I don't see how it shows NP-completeness. $\endgroup$ – Jack M Aug 3 '18 at 19:38
  • 1
    $\begingroup$ @JackM See my addition "First..". $\endgroup$ – Brendan McKay Aug 4 '18 at 12:08
7
$\begingroup$

This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NP-hard problems are routinely solved in practice, even to fairly large scale, despite being "intractable". For $P$ being $n$ by $n$ with $n$ in the hundreds, it should be easy to solve, and possible with $n$ into the thousands.

The problem is to find a $P$ such that all entries of $P$ are $0$ or $1$, all rows of $P$ sum to $1$, all columns of $P$ sum to $1$, and $APx = 0$.

Formulation in CVX under MATLAB

cvx_begin
variable P(n,n) binary
sum(P,1) == 1
sum(P,2) == 1
A*P*x == 0
cvx_end

Formulation in YALMIP under MATLAB

P = binvar(n,n,'full')
optimize([sum(P,1) == 1,sum(P,2) == 1,A*P*x == 0])

The specific solver to use may be optionally specified for either CVX or YALMIP.

I don't claim this is the fastest way to solve the problem, but it is a valid formulation, and if it meets your needs, then it has accomplished something useful, protestations of NP-completeness not withstanding.

$\endgroup$
  • 1
    $\begingroup$ Thanks @Rodrigo de Azevedo for catching the typos. I have fixed them. $\endgroup$ – Mark L. Stone Nov 27 '18 at 14:00
2
$\begingroup$

Let $\mathbb P_n$ be the set of $n \times n$ permutation matrices. Given matrix $\mathrm A \in \mathbb R^{m \times n}$ and vector $\mathrm v \in \mathbb R^n$, we would like to find a permutation matrix $\mathrm P \in \mathbb P_n$ such that

$$\mathrm A \mathrm P \mathrm v = 0_m$$

The convex hull of $\mathbb P_n$ is the Birkhoff polytope $\mathbb B_n$ (the set of all $n \times n$ doubly stochastic matrices)

$$\mathbb B_n := \left\{ \mathrm X \in \mathbb R^{n \times n} \mid \mathrm X \mathrm 1_n = \mathrm 1_n, \mathrm 1_n^\top \mathrm X = 1_n^\top, \mathrm X \geq \mathrm O_n \right\}$$

Thus, a convex relaxation of the original discrete feasibility problem in $\mathrm P \in \mathbb P_n$ is the following continuous feasibility problem in $\mathrm X \in \mathbb B_n$

$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & \mathrm A \mathrm X \mathrm v = 0_m\\ & \mathrm X \mathrm 1_n = \mathrm 1_n\\ & \mathrm 1_n^\top \mathrm X = 1_n^\top\\ & \mathrm X \geq \mathrm O_n\end{array}$$

Let us look for a solution on the boundary of the feasible region. Hence, we generate a (nonzero) random matrix $\mathrm C \in \mathbb R^{n \times n}$ and minimize $\langle \mathrm C, \mathrm X \rangle$ instead. We have the following linear program (LP).

$$\begin{array}{ll} \text{minimize} & \langle \mathrm C, \mathrm X \rangle\\ \text{subject to} & \mathrm A \mathrm X \mathrm v = 0_m\\ & \mathrm X \mathrm 1_n = \mathrm 1_n\\ & \mathrm 1_n^\top \mathrm X = 1_n^\top\\ & \mathrm X \geq \mathrm O_n\end{array}$$

Although the vertices of the Birkhoff polytope are doubly stochastic matrices, the introduction of the equality constraints $\mathrm A \mathrm X \mathrm v = 0_m$ likely produces other vertices. We may have to generate several matrices $\rm C$ until we obtain an LP whose minimum is attained at a permutation matrix.


Numerical experiment

Suppose we are given

$$\rm A = \begin{bmatrix} 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 1 & 1\end{bmatrix}$$

$$\rm v = \begin{bmatrix} 1 & 1 & -1 & 0 & 0\end{bmatrix}^\top$$

Using NumPy to randomly generate matrix $\rm C$ and CVXPY to solve the LP:

from cvxpy import *
import numpy as np

A = np.array([[1,1,1,0,0],
              [0,1,1,1,0],
              [0,0,1,1,1]])
v = np.array([1,1,-1,0,0])

(m,n) = A.shape

C = np.random.rand(n,n)

ones_n = np.ones((n,1))

X = Variable(n,n)

# define optimization problem
prob = Problem( Minimize(trace(C.T * X)), [ A * X * v == np.zeros((m,1)), X * ones_n == ones_n, ones_n.T * X == ones_n.T, X >= 0 ])

# solve optimization problem
print prob.solve()
print prob.status

# print results
print "X = \n", np.round(X.value,2)

which outputs the following permutation matrix that exchanges the 2nd and 4th entries:

0.669610896837
optimal
X = 
[[ 1.  0.  0.  0.  0.]
 [ 0.  0. -0.  1.  0.]
 [-0. -0.  1.  0. -0.]
 [ 0.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  1.]]

I ran the Python script a few (maybe $5$) times until I obtained a matrix $\rm X$ that is (close enough to) a permutation matrix. Unsurprisingly, the script does not produce such nice results for all choices of $\rm C$.

Running the script a few more times, I obtained another permutation matrix:

1.46656456314
optimal
X = 
[[ 0.  0.  0.  1.  0.]
 [ 1.  0.  0.  0.  0.]
 [-0. -0.  1.  0. -0.]
 [ 0.  0. -0.  0.  1.]
 [ 0.  1.  0.  0.  0.]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.