9
$\begingroup$

I have a similar problem addressed in System of Equations Generator. What I need is an automatic way of generating a system of equations with unique solutions, but the equations are not exclusively linear.

The method of working backwards, by randomly assigning integer values to variables and then generating the coefficients and computing the determinant matrix is perfect for a system of linear equations of the form:

\begin{align}x + y = 7\\3x - 2y = 6\end{align}

I can verify that the solution is unique with x = 4 and y = 3.

Now I would like to add two more operators: multiplication and division. The expected equations would be like this:

\begin{align}x + y = 4\\2x * y = 6\end{align}

How to generate these systems of equations and verify if the solution is unique, assuming integer variables and up to 5 variables? I found a lot of papers about uniqueness in non-linear equations, but I guess my requirement is a little simpler.

$\endgroup$
10
$\begingroup$

Generating systems. The same method that works for linear equations works also for polynomial equations. Starting with a solution in mind (in mathematics and computer science, we call this a planted solution), generate in some way left-hand sides of equations, and then compute the corresponding right-hand sides. If you use more than one equation per variable then you are likely not to get additional solutions.

Verifying uniqueness. Modern computer algebra systems can find the complete set of solutions of a system of polynomial equations. Under the hood, they might use Gröbner bases.

As an example, in sage you can write

sage: var('x, y')
(x, y)
sage: solve([x + y == 4, 2*x*y == 6], [x, y])
[[x == 1, y == 3], [x == 3, y == 1]]

Sage correctly found the two unique solutions.

Assuming that sage is using Gröbner bases, here is what happens. First, sage computes a Gröbner basis in elimination order.

sage: R.<x,y> = PolynomialRing(ZZ, 2, order = 'lex')
sage: I = ideal(x + y - 4, 2*x*y - 6)
sage: I.groebner_basis()
[x + y - 4, 2*y^2 - 8*y + 6]

It solves the quadratic to find all possible values of $y$, substitutes them, and finds the corresponding values of $x$. The same idea works with more variables, although the degrees can get quite large.

| improve this answer | |
$\endgroup$
5
$\begingroup$

If you are looking at intersecting the zero sets of two polynomials in two variables, then by Bezout's theorem you should anticipate that the number of solutions will be equal to the product of the degrees of the polynomials. So in general, you will not get unique solutions. You will need to be very careful to hide these extra solutions "at infinity" or in the complex plane, or as "double roots".

| improve this answer | |
$\endgroup$
  • $\begingroup$ Or, as Yuval suggests, add more equations. $\endgroup$ – Steven Gubkin Jul 24 at 11:47

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.