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?



Determining if some permutation of a vector satisfies a system of linear equations
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.


