[Math] How to solve a system of quadratic equations

groebner-basisquadraticssystems of equations

I was watching a video where a problem in Galois theory was posed such that it became necessary to tell if a certain element was a perfect square in a finite field extension of the rationals. By writing a general element in terms of its $\mathbb{Q}$-basis and squaring it, the result was a system of quadratic equations. In particular, it was system of three non-homogeneous equations in three unknowns.

The video deferred the solution to a computer algebra system, which felt unsatisfying. I was wondering what techniques would be useful for solving general equations of this kind.

My only thought was that Groebner bases might be useful (and I'm sure that's how the computer algebra system solves it). But I don't know much about them, and I wonder how amenable the Buchberger algorithm is to solving it by hand.

Best Answer

Consider a quadratic equation of form $ax^2 +by^2 +cxy+dx+ey+f=0$. The polynomial can be decomposed into two factors (polynomial) such as $ax+By+C$ and $dx+Ey+F$. Therefore for a system of two quadratic equations we get four polynomials of first degree (i.e linear equations). The combination of these four equations give four systems of equations where the solutions satisfy the initial quadratic system of equations; look at this example: Solve following system of quadratic equations:

$$\begin{cases} 2x^2+2y^2 +5xy-x+y-1=0 \\ -3x^2-2y^2+5xy+10x-8y-8=0 \\ \end{cases} $$ The first equation can be written as:

$$(x+2y-1)(2x+y+1)=0$$ and the second one can be written as:

$$(-x+y+2)(3x-2y-4)=0$$

We get four systems of equations, which give following solutions: $$\begin{cases} x+2y-1=0 \\ -x+y+2=0 \\ \end{cases} $$ give $x=5/3$ and $y=-1/3$

$$\begin{cases} x+2y-1=0 \\ 3x-2y-4=0 \\ \end{cases} $$ give $x=5/4$ and $y = -1/8$

$$\begin{cases} 2x+y+1=0 \\ -x+y+2=0 \\ \end{cases} $$ give $x=1/3$ and $y=-5/3$ and

$$\begin{cases} 2x+y+1=0 \\ 3x -2y-4=0 \\ \end{cases} $$
give $x=2/7$ and $y=-11/7$

These are the solutions of the quadratic system of equations.

Related Solutions

[Math] Finding a redundant equation in a system of linear simultaneous equations

As those in the comments have said, the way to really solve such a problem is via Gaussian Elimination

In Python this is easily implemented either from first principles using lots of for loops and summations. But an even easier (and faster!) solution is to use the NumPy package routine "numpy.linalg.solve".

You are quite correct that the matrix must be square and of full rank in order for you to be able to solve it.

[Aside note: A square matrix is full rank if and only if it's determinant is nonzero.]

Using numpy.linalg.solve(A,B) is neat as it will raise an error "LinAlgError" if A is singular or not square. The example given at the bottom of the documentation page is entirely self explanatory, so I will not insult your intelligence by going over it again!

So you could do something like this, but you'd need your chemist to already have written the thing up as a matrix or you could be kinder to them and write a little code to create the matrices from the equations they enter as plain text (e.g. https://stackoverflow.com/questions/45220032/how-to-balance-a-chemical-equation-in-python-2-7-using-matrices/45220319)

A = input("Enter the coefficents of your matrix: ")
B = input("Enter the ordinate values: ")
x = np.linalg.solve(A, B)
print x

Hope this helps, have fun and good luck! :-)

Best Answer

Related Solutions

[Math] Finding a redundant equation in a system of linear simultaneous equations

Related Question