I posted this on mathoverflow but haven't recieved any comments. I wonder if there might be some insight from this community. Thanks!
The problem
Suppose you have nonnegative integer vectors of length d, $x$, $y$, $z \in \mathbb{Z^+}^d$. We know that $\sum_{i=1}^d x_i + y_i = \sum_{i=1}^d z_i$. I wish to find permutation matrices $\Pi_1$ and $\Pi_2$ such that \begin{align} \Pi_1 x + \Pi_2 y = z \end{align}
without enumerating all possible permutations. If there is a solution, I'd like to know in as few steps as possible. If the solution is not unique, I'd like to know all permutation pairs which satisfy the above (or have an efficient means of enumerating them)
More context:
$x$ and $y$ actually represent integer partitions, and I actually have many $x$'s and many $y$'s for any given $z$, and will have to check all possible $x, y$ pairs for the given $z$.
Things I've tried:
- We can immediately rule out some $x, y$ pairs using majorization. Let $\tilde{x}$ and $\tilde{y}$ be the sorted versions of $x$ and $y$. I can show that $\tilde{x} + \tilde{y}$ majorizes all other permuted sums of $x$ and $y$. If $z$ majorizes $\tilde{x} + \tilde{y}$ (and is not equal to it, modulo permutation), then it majorizes all permuted sums of $x$ and $y$, so there is no solution. Similarly, $\tilde{x} + \text{reverse}(\tilde{y})$ is majorized by all other permuted sums. If $z$ is majorized by $\tilde{x} + \text{reverse}(\tilde{y})$, then it is majorized by all permuted sums and there is no solution. By partially ordering all the $x$'s using majorization and doing the same for $y$, this method potentially knocks out many pairs without having to check them all.
- We can avoid checking all pairs of permutations by using sorting. Let $\tilde{x}$ be the sorted version of $x$ and let $\widetilde{\Pi}_x$ be a permutation which sorts $x$, i.e. $\widetilde{\Pi}_x x = \tilde{x}$. Enumerate all unique permutations of $y$, and subtract them from $z$. Sort each difference vector, and compare it against $\tilde{x}$. Given a match, $\Pi_1$ and $\Pi_2$ can be determined by the permutation of $y$ and the permutation which ``unsorts'' $\tilde{s}$. Formally, suppose for some permutation $\Pi^*$, $s = z - \Pi^* y$ with $\tilde{s} = \tilde{x}$. Then $\Pi_1 = {\widetilde{\Pi}_s}^{-1} \widetilde{\Pi}_x$ and $\Pi_2 = \Pi^*$.
- I've found a reduction of the problem to filling in count matrices with specified row, column, and diagonal margins, but haven't found efficient ways of solving that problem. Please chime in if you have thoughts on this. I can say more about this if relevant.
I realize this question is somewhat algorithmic in nature, but I'm hoping there is some relevant area of mathematics that could help. I've tried to think about this from the perspective of symmetric groups, the elementary basis for symmetric functions, general equivalence classes, but I'm not getting very far. Any help or suggested directions would be appreciated!
