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?
 A: 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.
A: 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.
A: 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.]]

A: 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.
