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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

This problem is known in the literature as permuted kernel problem, PKP. In 1989, Shamir proved NP-completeness by reduction from partition problem. In Garey and Johnson [1979], PKP was shown to be NP-complete in the strong sense by a reduction from 3-partition problem.

Shamir introduced a public-key scheme based on it. Post-quantum cryptography renewed interest in PKP-based Zero-Knowledge Identification scheme.

Answer 4

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