# Strategies for solving simultaneous equations?

Suppose you're given a set of $n$ functions of $k$ variables\begin{align}f_1(x_1, x_2,\ldots, x_k)& =0\\f_2(x_1, x_2,\ldots, x_k)& =0\\ & {}\ \vdots \\f_n(x_1, x_2,\ldots, x_k)& =0 \end{align}

And you want to eliminate $n-1$ $x$s to give \begin{align}g_1(x_1, x_2,\ldots, x_{k-n-1})& =0 \end{align} The standard way to keep out of trouble would be to eliminate the same variable from one function paired off with each function in turn to give $n-1$ functions of $k-1$ variables. The same procedure is carried on this new set of functions and so on until you end up with the requred function at the end.

What other strategies work, in particular those that may carry some advantages?

-
Actually only the problem $f(x_1,\ldots,x_k)=0$ is already a really hard problem. Can you reveal some more information about the $f_i$? – Listing Jul 26 '11 at 14:16
@Listing I'm looking at D'Alembert's principle en.wikipedia.org/wiki/D'Alembert's_principle and using the constaints to reduce the number of variables. – John McVirgo Jul 26 '11 at 14:27
In the linear case, a whole lot can be said, this is the study of linear algebra. In general, this is an extremely hard problem. You will need to have some structure in the $f_i$'s to make this problem tractable. – Thomas Rot Jul 26 '11 at 15:41
@Thomas Is is really that hard? I think a computer is all that is needed to amke things a lot easier – John McVirgo Jul 26 '11 at 19:54
@John: Yes I think so. Whole areas of math are devoted to the question of existence of solutions of these types of equations (even if n=1). In general you definitely cannot expect nice expressions (formulas) for the solutions. This already happens for a degree 5 polynomial (with n=1). en.wikipedia.org/wiki/Abel-Ruffini_theorem . But maybe I misinterpret your question? – Thomas Rot Jul 26 '11 at 23:08

## 1 Answer

As noted in the comments, the answer depends strongly on the nature of the $f_i$. If they are linear, linear algebra does the trick. If they are perfectly general, chances are you're out of luck - how are you going to eliminate a variable from $\sin x+\log x+e^y+\cos y=17$? An intermediate case which is of great practical importaqnce and has not been mentioned in the comments is the case where the functions are (multivariate) polynomials. Here the keyphrases are Grobner basis and Buchberger's algorithm. It's a long story, but Buchberger's algorithm will get you started.

-
I fixed the link in your post. I hope you don't mind! – JavaMan Jul 27 '11 at 0:42
@DJC, thanks, I was hoping someone would fix the link. One of these days I'll remember there's a way to do these things when the URL has an underscore or other character that torpedos the naive method. – Gerry Myerson Jul 27 '11 at 1:03
I don't remember the code either. I simply use the link button (atop the answer box directly to the right of bold and italic buttons) to post all links in an answer. – JavaMan Jul 27 '11 at 1:24
Convert the equation into a differential equation:$\quad dx(\cos x + \frac 1 x) + e^ydy = 0$ and use that to eliminate a differential variable. Solve the resulting differential equation using numerical methods. – John McVirgo Jul 27 '11 at 13:09
@John, are you being serious? I would say that your suggestion has nothing to do with what OP is asking for, but...OP is you! Anyway, what happened to $\cos y$? – Gerry Myerson Jul 28 '11 at 0:40