Given a matrix $A$ and vector $x$, is it possible to find the permutation of $x$ that minimizes $\lVert APx \rVert$?

Question

Let $A$ be some $n\times n$ matrix, and $x$ be a column vector of length $n$. I am looking to find the permutation matrix $P$ of size $n\times n$ that minimizes the vector norm of $APx$.

There are $n!$ such permutation matrices, so to exhaustively search for the minimizing $P$ quickly becomes intractable. I'm wondering if it is possible to show analytically what this $P$ should be, but am having trouble proceeding on this question.

Any help or leads would be much appreciated!

EDIT: While interested in the general case, which seems to be NP-complete, I would be happy to hear if there are special results concerning the special case that $A = QQ^\dagger-I$, where $Q^\dagger$ is the Moore-Penrose inverse of $Q$.

Answer 1

Unfortunately, this problem is $NP$-complete in the general case. Let us consider the associated decisional problem : give, $A$, $x$ and a real number $b$, does it exist a permutation matrix $P$ such that $\|APx\| \leqslant b$ ? It is clearly $NP$ and you can reduce it to the $3$-partition problem (cf https://en.wikipedia.org/wiki/3-partition_problem), even in the speacial case $b = 0$.

Indeed, consider $S$ to be a multiset of $n = 3m$ integers whose sum is $mT$ for some integers $m,T$. Let $U$ be the $m \times m$ matrix whose all coefficients are $1$ and $A$ be the $n \times n$ matrix defined by, $$ A = \begin{pmatrix} mI_n - U & mI_n - U & mI_n - U \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, $$ where each bloc is a $m \times m$ matrix. Let $x$ be the vector whose coefficients are the integers of the multiset $S$. Then, for all permutation $y = Px$ of $x$, you can associate a partition $(S_i)$ of $S$ defined by $S_i = (y_i,y_{i + m},y_{i + 2m})$ for all $i$. Reciprocally, if $(S_i)$ is a partition of $S$, write for all $i$, $S_i = (y_i,y_{i + m},y_{i + 2m})$. Then $y$ is a partition of $x$ (it is not unique but it doesn't matter). And we have for all $i \leqslant n$, $$ (Ay)_i = my_i - \sum_{j = 1}^m y_j + my_{i + m} - \sum_{j = m + 1}^{2m} y_j + my_{i + 2m} - \sum_{j = 2m + 1}^{3m} y_j = m\sum_{y \in S_i} y - mT. $$ We deduce that $Ay = 0$ if and only if the associated partition is a solution to the original $3$-partition problem. Therefore, there is no polynomial algorithm that solves your problem unless $P = NP$.

Answer 2

An approximation is to replace the permutation matrix $P$ by an orthogonal matrix $U$, getting with the polar presentation $A^TA=V^TD^2V$ where $V$ is orthogonal and $D^2=\mathrm{diag}(d_1^2,\ldots,d_n^2)$ $$\|AUx\|^2=\langle U^TA^TAU x,x\rangle =\|VU D x\|^2.$$ Choosing $VU=I_n$ we get $$(d_1x_1)^2+\cdots+(d_nx_n)^2$$ If $x_1^2\leq \ldots\leq x_n^2$ and chosing $V$ such that $d_1^2\geq \ldots\geq d_n^2$ we get the minimum of $U\mapsto \|AUx\|^2.$