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 wellunderstood?

$\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
Let's see if I can convince everyone that this problem is NPcomplete.
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 nullspace 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 $2n1$.
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 NPcomplete.

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 NPhard? I don't see how it shows NPcompleteness. $\endgroup$ – Jack M Aug 3 '18 at 19:38

1
This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NPhard 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 NPcompleteness not withstanding.

1$\begingroup$ Thanks @Rodrigo de Azevedo for catching the typos. I have fixed them. $\endgroup$ – 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.]]