6
$\begingroup$

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a solution to the system:

\begin{align} ax^{1}+by^{1}+cz^{1}+\cdots&=k_{1}\\ ax^{2}+by^{2}+cz^{2}+\cdots&=k_{2}\\ ax^{3}+by^{3}+cz^{3}+\cdots&=k_{3} \end{align}
so on ... till $$ax^{n}+by^{n}+cz^{n}+\cdots=k_{n}$$

for variables $x,y,z\in \{1,2\ldots, n\}$.

The value of constants $a$,$b$,$c$... remain same in all these equations.

And these constants can also be equal to each other. For e.g: $a = b$ so that values of $x$ and $y$ can become interchangeable. In such cases one working solution is suffice.

Can we find a solution or determine none exist in polynomial time?


Edit: For the sake of clarity here is a simple example.

If $n=3$, I know $x,y,z$ can only take 1, 2 or 3 as their values. So if I have $x + y + z = 9$, I clearly know that $x, y$ and $z$ are all 3. But if I have $x + y + z = 6$, I don't know whether they are $2,2,2$ or $1,2,3$. Then I can make use of $x^2 + y^2 + z^2 = 14$. Then I will know they are $1,2,3$.

$\endgroup$
  • 2
    $\begingroup$ Have you looked at solution techniques for solving Diophantine equations? Would those work for your situation, or would you need something better? Of course, you want 'the best', but the best you can afford is usually 'good enough'. $\endgroup$ – Discrete lizard Mar 14 at 10:07
  • $\begingroup$ @Discretelizard I'm still a noob. Aren't Diophantine equation solving NP complete. I was looking for something P. Because I have extra data, the solution set is not any integer but only first n positive integers. And I have n equations. Even if I did not know they were integers I could still solve them, its just that I have been given with extra information, and I am wondering how can I make use of it and accomplish this in P time. $\endgroup$ – VARUN.N RAO Mar 14 at 10:19
  • $\begingroup$ Yes, solving Diophantine equations is hard in general, undecidable even. But there are heuristic approaches that might work for your case. I think the question whether this specific case is polynomial time solvable is more focused than your current question. It also allows for a 'no' answer. $\endgroup$ – Discrete lizard Mar 14 at 10:29
  • $\begingroup$ You can try Grobner bases. See for example math.berkeley.edu/~bernd/cbms.pdf. $\endgroup$ – Yuval Filmus Mar 14 at 14:13
  • $\begingroup$ @YuvalFilmus is solving Grobner bases possible in polynomial time? $\endgroup$ – VARUN.N RAO Mar 14 at 14:34
4
$\begingroup$

Let us denote the unknowns by $x_1,\ldots,x_n$, and the coefficients by $c_1,\ldots,c_n$. For a polynomial $P(x)$, we denote $$ [P(x)] = \sum_{i=1}^n c_i P(x_i). $$ We are given the values of $[1],[x],\ldots,[x^n]$, from which we can calculate $[P(x)]$ for every polynomial of degree at most $n$. In particular, we can compute, for each $j \in \{1,\ldots,n\}$, the value $$ \left[ \prod_{k \neq j} \frac{x-k}{j-k} \right] = \sum_{i\colon x_i=j} c_i. $$ To complete the solution, we need to solve several SUBSET-SUM instances, which possibly interact.

Conversely, we can encode SUBSET-SUM using your equations. Given a set of positive coefficients $c_1,\ldots,c_n$ summing to $C$ and a target $S$, we encode a solution using $\{1,2\}$-valued variables (where $1$ represents a value in the subset summing to $S$), and can compute $[x^k] = S + (C-S)2^k$. These numbers satisfy $$ [x^k(x-1)(x-2)] = [x^{k+2}-3x^{k+1}+2x^k] = \\ (S + (C-S)2^{k+2}) - 3(S+(C-S)2^{k+1}) + 2(S+(C-S)2^k) = \\ (1-3+2)S + (4-6+2)(C-S)2^k = 0. $$ Therefore the argument above shows that every $\{1,\ldots,n\}$-valued solution is actually $\{1,2\}$-valued. Therefore a solution to your problem exists if and only if the SUBSET-SUM instance is a Yes instance.

When all coefficients $c_i$ are equal, the argument above allows us to calculate directly the number of $x_i$'s equal to $j$. Let us take your example: $[1] = 3$, $[x] = 6$ and $[x^2] = 14$. Denoting by $y_j$ the number of $x_i$'s equal to $j$, we compute $$ \begin{align*} y_1 &= \left[ \frac{(x-2)(x-3)}{(1-2)(1-3)} \right] = \frac{[x^2-5x+6]}{2} = \frac{14-5\cdot6+6\cdot3}{2} = 1, \\ y_2 &= \left[ \frac{(x-1)(x-3)}{(2-1)(2-3)} \right] = [-x^2+4x-3] = -14+4\cdot6-3\cdot3 = 1, \\ y_3 &= \left[ \frac{(x-1)(x-2)}{(3-1)(3-2)} \right] = \frac{[x^2-3x+2]}{2} = \frac{14-3\cdot6+2\cdot3}{2} = 1. \end{align*} $$

$\endgroup$
  • $\begingroup$ Hey, I think your approach gives the number of variables which have j value. The problem with this is, we cannot directly assign the value to a variable. For E.g if x +y - z = 0, the answer would still be same, there would be one 1, one 2 and one 3. But the value 3 does not get assigned to z, instead I only know that there is a variable whose value is 3. If n gets sufficiently large and if an equation has all the n values but different coefficients it just becomes useless $\endgroup$ – VARUN.N RAO Mar 14 at 17:31
  • $\begingroup$ I have to disagree. My method gives, for each $j$, the sum of coefficients of variables equal to $j$. Whether this is helpful or not, is another matter. $\endgroup$ – Yuval Filmus Mar 14 at 17:33
  • $\begingroup$ Exaclty, but that is not the question, we need to assign the values to variables, that was the goal, but here we will get the frequency of a value in an equation. $\endgroup$ – VARUN.N RAO Mar 14 at 17:38
  • $\begingroup$ Well, you'll have to take it from there, I'm afraid. $\endgroup$ – Yuval Filmus Mar 14 at 17:40
  • $\begingroup$ That's all right, but what I said was correct right? we only get the frequencies of the value. The math you have used is quite complicated, I'm an utter noob. $\endgroup$ – VARUN.N RAO Mar 14 at 17:42
1
$\begingroup$

My algorithm is not an exact one but actually an approximation algorithm.

Algorithm

  1. Define three matrices

$$ X = \left[ \begin{matrix} x & y & z & \cdots \\ x^2 & y^2 & z^2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ x^n & y^n & z^n & \cdots \end{matrix} \right]_{n \times n} $$

$$ C = \left[ \begin{matrix} a \\ b \\ c \\ \vdots \end{matrix} \right]_{ n \times 1} $$

$$ K = \left[ \begin{matrix} k_1 \\ k_2 \\ k_3 \\ \vdots \end{matrix} \right]_{ n \times 1} $$

We can see that $X \cdot C = K$

  1. Find the Inverse Matrix for C. (Yes, inverse of a column matrix) $$ C^{-1} = \frac{C^T}{C_{sq}} \\ C_{sq} = \sum_{i=1}^n c_i^2 = a^2 + b^2 + c^2 + \cdots $$

$C^{-1}$ satisfies all properties that a normal matrix inverse does $$ C^{-1} \cdot C = I_{1 \times 1} \\ C \cdot C^{-1} \cdot C = C $$

  1. Now comes the tricky part. Calculate $C^* = C \cdot C^{-1}$. We can now use this to obtain

$$ X \cdot C \cdot C^{-1} = K \cdot C^{-1} \\ X \cdot C^* = K \cdot C^{-1} \\ X = K \cdot C^{-1} \cdot C^{*{-1}} $$

The tricky part is that $C^*$ is always singular i.e. $|C^*| = 0$. So it does not have a unique inverse, but has many pseudo-inverses. (Refer: Moore-Penrose Inverse ).

So we have to keep searching for all pseudo-inverses of $C^*$ i.e. $C^{*{-1}}$ such that the result $K \cdot C^{-1} \cdot C^{*{-1}}$ we obtain, matches the pattern observed in $X$.

$\endgroup$
  • $\begingroup$ Oh God, nature is resilient. The whole point was to make the algorithm in polynomial time, but the moment you said "So we have to keep searching for all pseudo-inverses of C∗" The "polynomialness" is gone. $\endgroup$ – VARUN.N RAO Mar 20 at 11:11
  • $\begingroup$ @RandomPerfectHashFunction this is the best answer yet, thank you so much for the answer and the effort $\endgroup$ – VARUN.N RAO Mar 20 at 11:12
  • $\begingroup$ @RandomPerfectHashFunction but I still have some concerns, this is generalized solution, but here the solution set is known, the solution can only be from 1 to n, and it has to be a positive integer. Can we use this data to our advantage while choosing which pseudo inverse we should be checking? $\endgroup$ – VARUN.N RAO Mar 20 at 11:16
  • $\begingroup$ Searching for all pseudo-inverses can take exponential time. I don't see any analysis of the running time of this approach; it seems to me this approach might well be even slower than the naive brute-force search over all possible solutions; I don't see any reason to expect it to be faster. So I don't see how this is useful. (Also, this is not an approximation algorithm.) $\endgroup$ – D.W. Mar 20 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.