Finding integer solutions to a multivariable equation

160 Views Asked by At

I have a problem, in which I have an equation $$(x-19)^2+(y-59)^2+(z-65)^2+(w-79)^2=11586$$ with the conditions $x\geq 0, y\geq 0, z\geq 0, w\geq 0$, and all the variable are integers. I know the solution is $x=2,y=5,z=6,w=9$. But how do I solve this, and is this unique. Do I solve this using Lagrange's multiplier. Or can somebody suggest some solvers using Python or Matlab

Edit: I give an elaborate description of what my problem is and how I landed to the question. I have two matrices say $$A=\begin{bmatrix} 2&6\\5&9\end{bmatrix} ~~\text{and} ~\begin{bmatrix}79 & 65\\ 59&19\end{bmatrix}$$ I needed to arrange the matrix $B$, keeping $A$ fixed, such that the $$\sum_{i,j=1}(A_{ij}-B_{ij})^2$$ remains the minimum. For this is used the Assignment problem (Hungarian problem as suggested in one of my earlier questions). I got the optimum places for my elements in $B$ and it turned out to be $$B=\begin{bmatrix}19&65\\59&79\end{bmatrix}$$, with minimum cost being $11586$. Now, need to find out the matrix $A$ given only the new $B$ and the assignment index which is the vector $[4,2,3,1]$. Now this means that means that if the matrix $A$ was originally $$A=\begin{bmatrix} x & y\\ z&w\end{bmatrix}$$, the cost matrix that was formed was $$\begin{bmatrix} (x-79)^2 & (x-59)^2 & (x-65)^2 & (x-19)^2\\ (y-79)^2 & (y-59)^2 & (y-65)^2 & (y-19)^2\\ (z-79)^2 & (z-59)^2 & (z-65)^2 & (z-19)^2\\ (w-79)^2 & (w-59)^2 & (w-65)^2 & (w-19)^2\\ \end{bmatrix}$$, thus we know that the minimum cost is corresponding to the vector $[4,2,3,1]$, thus we solve $$(x-19)^2+(y-59)^2+(z-65)^2+(w-79)^2=11586$$ Now my questions on this problem is

  1. If I modify this problem from quadratic to just the absolute function $\sum_{i,j=1}|(A_{ij}-B_{ij})|$, can this problem be a bit easy to solve?
  2. Is my approach even worth trying to find the solution for, or is just too infeasable?
  3. Can this problem be solved by some other approach?
1

There are 1 best solutions below

0
On

This is not a 'real' answer but it was too big for a comment.

Well, I just coded something in Mathematica:

In[1]:=Solve[{(x - 19)^2 + (y - 59)^2 + (z - 65)^2 + (w - 79)^2 == 
   11586}, {w, x, y, z}, PositiveIntegers]

And it gave me a lot of solutions (the solutions I show downhere they are not all the solutions, if you want all the solutions that Mathematica found, you can contact me):

Out[1]={{w -> 1, x -> 2, y -> 1, z -> 22}, {w -> 1, x -> 2, y -> 1, 
  z -> 108}, {w -> 1, x -> 2, y -> 16, z -> 7}, {w -> 1, x -> 2, 
  y -> 16, z -> 123}, {w -> 1, x -> 2, y -> 22, z -> 3}, {w -> 1, 
  x -> 2, y -> 22, z -> 127}, {w -> 1, x -> 2, y -> 96, 
  z -> 3}, {w -> 1, x -> 2, y -> 96, z -> 127}, {w -> 1, x -> 2, 
  y -> 102, z -> 7}, {w -> 1, x -> 2, y -> 102, z -> 123}, {w -> 1, 
  x -> 2, y -> 117, z -> 22}, {w -> 1, x -> 2, y -> 117, 
  z -> 108}, {w -> 1, x -> 2, y -> 121, z -> 28}, {w -> 1, x -> 2, 
  y -> 121, z -> 102}, {w -> 1, x -> 6, y -> 57, z -> 138}, {w -> 1, 
  x -> 6, y -> 61, z -> 138}, {w -> 1, x -> 6, y -> 132, 
  z -> 63}, {w -> 1, x -> 6, y -> 132, z -> 67}, {w -> 1, x -> 8, 
  y -> 25, z -> 130}, {w -> 1, x -> 8, y -> 93, z -> 130}, {w -> 1, 
  x -> 8, y -> 124, z -> 31}, {w -> 1, x -> 8, y -> 124, 
  z -> 99}, {w -> 1, x -> 9, y -> 18, z -> 4}, {w -> 1, x -> 9, 
  y -> 18, z -> 126}, {w -> 1, x -> 9, y -> 40, z -> 136}, {w -> 1, 
  x -> 9, y -> 78, z -> 136}, {w -> 1, x -> 9, y -> 100, 
  z -> 4}, {w -> 1, x -> 9, y -> 100, z -> 126}, {w -> 1, x -> 9, 
  y -> 120, z -> 24}, {w -> 1, x -> 9, y -> 120, z -> 106}, {w -> 1, 
  x -> 9, y -> 130, z -> 46}, {w -> 1, x -> 9, y -> 130, 
  z -> 84}, {w -> 1, x -> 14, y -> 58, z -> 139}, {w -> 1, x -> 14, 
  y -> 60, z -> 139}, {w -> 1, x -> 14, y -> 133, z -> 64}, {w -> 1, 
  x -> 14, y -> 133, z -> 66}, {w -> 1, x -> 17, y -> 46, 
  z -> 138}, {w -> 1, x -> 17, y -> 72, z -> 138}, {w -> 1, x -> 17, 
  y -> 132, z -> 52}, {w -> 1, x -> 17, y -> 132, z -> 78}, {w -> 1, 
  x -> 18, y -> 54, z -> 139}, {w -> 1, x -> 18, y -> 64, 
  z -> 139}, {w -> 1, x -> 18, y -> 133, z -> 60}, {w -> 1, x -> 18, 
  y -> 133, z -> 70}, {w -> 1, x -> 20, y -> 54, z -> 139}, {w -> 1, 
  x -> 20, y -> 64, z -> 139}, {w -> 1, x -> 20, y -> 133, 
  z -> 60}, {w -> 1, x -> 20, y -> 133, z -> 70}, {w -> 1, x -> 21, 
  y -> 46, z -> 138}, {w -> 1, x -> 21, y -> 72, z -> 138}, {w -> 1, 
  x -> 21, y -> 132, z -> 52}, {w -> 1, x -> 21, y -> 132, 
  z -> 78}, {w -> 1, x -> 24, y -> 58, z -> 139}, {w -> 1, x -> 24, 
  y -> 60, z -> 139}, {w -> 1, x -> 24, y -> 133, z -> 64}, {w -> 1, 
  x -> 24, y -> 133, z -> 66}, {w -> 1, x -> 29, y -> 18, 
  z -> 4}, {w -> 1, x -> 29, y -> 18, z -> 126}, {w -> 1, x -> 29, 
  y -> 40, z -> 136}, {w -> 1, x -> 29, y -> 78, z -> 136}, {w -> 1, 
  x -> 29, y -> 100, z -> 4}, {w -> 1, x -> 29, y -> 100, 
  z -> 126}, {w -> 1, x -> 29, y -> 120, z -> 24}, {w -> 1, x -> 29, 
  y -> 120, z -> 106}, {w -> 1, x -> 29, y -> 130, z -> 46}, {w -> 1, 
  x -> 29, y -> 130, z -> 84}, {w -> 1, x -> 30, y -> 25, 
  z -> 130}, {w -> 1, x -> 30, y -> 93, z -> 130}, {w -> 1, x -> 30, 
  y -> 124, z -> 31}, {w -> 1, x -> 30, y -> 124, z -> 99}, {w -> 1, 
  x -> 32, y -> 57, z -> 138}, {w -> 1, x -> 32, y -> 61, 
  z -> 138}, {w -> 1, x -> 32, y -> 132, z -> 63}, {w -> 1, x -> 32, 
  y -> 132, z -> 67}, {w -> 1, x -> 36, y -> 1, z -> 22}, {w -> 1, 
  x -> 36, y -> 1, z -> 108}, {w -> 1, x -> 36, y -> 16, 
  z -> 7}, {w -> 1, x -> 36, y -> 16, z -> 123}, {w -> 1, x -> 36, 
  y -> 22, z -> 3}, {w -> 1, x -> 36, y -> 22, z -> 127}, {w -> 1, 
  x -> 36, y -> 96, z -> 3}, {w -> 1, x -> 36, y -> 96, 
  z -> 127}}