# Determining if some permutation of a vector satisfies a system of linear equations

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?

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

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.

• No need for belief, just take $A=(1,1,\dots,1,-1,-1,\dots,-1)$. – Emil Jeřábek supports Monica Aug 3 '18 at 11:57
• 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. – Jack M Aug 3 '18 at 19:38
• @JackM See my addition "First..". – Brendan McKay Aug 4 '18 at 12:08

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.

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

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.]]