# Solving a system of non-linear equations with 10 equations and 10 unknowns

I'm working on a problem where I seem to have run into a system of non-linear equations. I have ten equations and ten unknowns. In the equations below, all of the $\phi_{ij}$'s are known, but all of the $a_{1},...,e_{2}$ are unknown.

$$a_{1}b_{1}+a_{2}b_{2}=\phi_{ab}\\ a_{1}c_{1}+a_{2}c_{2}=\phi_{ac}\\ a_{1}d_{1}+a_{2}d_{2}=\phi_{ad}\\ a_{1}e_{1}+a_{2}e_{2}=\phi_{ae}\\ b_{1}c_{1}+b_{2}c_{2}=\phi_{bc}\\ b_{1}d_{1}+b_{2}d_{2}=\phi_{bd}\\ b_{1}e_{1}+b_{2}e_{2}=\phi_{be}\\ c_{1}d_{1}+c_{2}d_{2}=\phi_{cd}\\ c_{1}e_{1}+c_{2}e_{2}=\phi_{ce}\\ d_{1}e_{1}+d_{2}e_{2}=\phi_{de}\\$$

Would anyone have any strategies for solving this system of non-linear equations for the $a_{1},...,e_{2}$? Is it possible to convert this into a system of linear equations somehow?

The dot products of the vectors with themselves are all known quantities, and in fact equal to one: $$\phi_{aa}=1\\ \phi_{bb}=1\\ \phi_{cc}=1\\ \phi_{dd}=1\\ \phi_{ee}=1\\$$

Yes, it is true that $\phi_{ab}=\phi_{ba}$.

• what about $\phi_{ba}$ and the other missing ones? Can one assume $\phi_{ab} = \phi_{ba}$? I'm thinking of swapping (a,b,c,d,e) cyclicly. – andre Jun 30 '15 at 23:26
• Seems sort of symmetric -- there is probably some clever manipulation that can be done – 1110101001 Jul 1 '15 at 1:31

With the updated question...

Given the comments, I would write the equation using matrices. We are searching for $X\in\mathbb R^{2\times 5}$, such that $$X^T X = \Phi,$$ where $\Phi$ is a given symmetric matrix with ones on the diagonal.

Notice that the equation has a solution if only if $\Phi$ is positive semidefinite with rank $\le 2$. In that case we can compute $X$ using the eigenvalue decomposition of $\Phi$: $$\Phi = UDU^T,$$ where $D$ is a diagonal matrix with the eigenvalues, say $d_1 \ge \dotsb \ge d_5$, on the diagonal and $U$ is a matrix with the eigenvectors as columns.

Case 1 $\Phi$ has rank $1$: That is $d_1 > 0$ and $d_2\dotsb=d_5=0$. Then, choose the first row of $X$ as $\sqrt{d_1}$ times the first column of $U$.

Case 2 $\Phi$ has rank $2$: That is $d_1 \le d_2 > 0$ and $d_3\dotsb=d_5=0$. Then, choose the first row of $X$ as $\sqrt{d_1}$ times the first column of $U$, and choose the second row of $X$ as $\sqrt{d_2}$ times the second column of $U$.

Notes: If you compute the eigenvalue decomposition numerically, $\Phi$ might appear to have a higher rank than it actually has, due to rounding error and approximation.

A Groebner basis computation with Macaulay2 gives

$$0 = +\phi_{ab}\phi_{ac}\phi_{bd}\phi_{ce}\phi_{de}-\phi_{ab}\phi_{ac}\phi_{be}\phi_{cd}\phi_{de}\\ +\phi_{ab}\phi_{ad}\phi_{be}\phi_{cd}\phi_{ce}-\phi_{ab}\phi_{ad}\phi_{bc}\phi_{ce}\phi_{de}\\ +\phi_{ab}\phi_{ae}\phi_{bc}\phi_{cd}\phi_{de}-\phi_{ab}\phi_{ae}\phi_{bd}\phi_{cd}\phi_{ce}\\ +\phi_{ac}\phi_{ad}\phi_{bc}\phi_{be}\phi_{de}-\phi_{ac}\phi_{ad}\phi_{bd}\phi_{be}\phi_{ce}\\ +\phi_{ac}\phi_{ae}\phi_{bd}\phi_{be}\phi_{cd}-\phi_{ac}\phi_{ae}\phi_{bc}\phi_{bd}\phi_{de}\\ +\phi_{ad}\phi_{ae}\phi_{bc}\phi_{bd}\phi_{ce}-\phi_{ad}\phi_{ae}\phi_{bc}\phi_{be}\phi_{cd}\\ \Longleftrightarrow\\ 0 = +\phi_{ab}\phi_{ac}\phi_{de} (\phi_{bd}\phi_{ce}-\phi_{be}\phi_{cd})\\ +\phi_{ab}\phi_{ad}\phi_{ce} (\phi_{be}\phi_{cd}-\phi_{bc}\phi_{de})\\ +\phi_{ab}\phi_{ae}\phi_{cd} (\phi_{bc}\phi_{de}-\phi_{bd}\phi_{ce})\\ +\phi_{ac}\phi_{ad}\phi_{be} (\phi_{bc}\phi_{de}-\phi_{bd}\phi_{ce})\\ +\phi_{ac}\phi_{ae}\phi_{bd} (\phi_{be}\phi_{cd}-\phi_{bc}\phi_{de})\\ +\phi_{ad}\phi_{ae}\phi_{bc} (\phi_{bd}\phi_{ce}-\phi_{be}\phi_{cd})\\ \Longleftrightarrow\\ 0 = +\phi_{ab}\phi_{ac}\phi_{de} (\phi_{bd}\phi_{ce}-\phi_{be}\phi_{cd})\\ +\phi_{ad}\phi_{ae}\phi_{bc} (\phi_{bd}\phi_{ce}-\phi_{be}\phi_{cd})\\ +\phi_{ab}\phi_{ad}\phi_{ce} (\phi_{be}\phi_{cd}-\phi_{bc}\phi_{de})\\ +\phi_{ac}\phi_{ae}\phi_{bd} (\phi_{be}\phi_{cd}-\phi_{bc}\phi_{de})\\ +\phi_{ab}\phi_{ae}\phi_{cd} (\phi_{bc}\phi_{de}-\phi_{bd}\phi_{ce})\\ +\phi_{ac}\phi_{ad}\phi_{be} (\phi_{bc}\phi_{de}-\phi_{bd}\phi_{ce})\\ \Longleftrightarrow\\ 0 = +(\phi_{ab}\phi_{ac}\phi_{de}+\phi_{ad}\phi_{ae}\phi_{bc}) (\phi_{bd}\phi_{ce}-\phi_{be}\phi_{cd})\\ +(\phi_{ab}\phi_{ad}\phi_{ce}+\phi_{ac}\phi_{ae}\phi_{bd}) (\phi_{be}\phi_{cd}-\phi_{bc}\phi_{de})\\ +(\phi_{ab}\phi_{ae}\phi_{cd}+\phi_{ac}\phi_{ad}\phi_{be}) (\phi_{bc}\phi_{de}-\phi_{bd}\phi_{ce})$$

Perhaps someone finds a nicer representation.

If one assumes that the vectors $a=(a_1,a_2),b=(b_1,b_2),c=(c_1,c_2),d=(d_1,d_2),e=(e_1,e_2)$ are the corners of a regular pentagon a Groebner basis computation gives

$$\phi_{ad}=\phi_{be},\\ \phi_{ac}=\phi_{bd}=\phi_{ce},\\ \phi_{ab}=\phi_{bc}=\phi_{cd}=\phi_{de}$$

With the given additional info on the symmetry of the $\phi_{\cdot,\cdot}$ it follows from the cyclic symmetry of the 10 equations that

$$\phi_{ae}=\phi_{ba}=\phi_{ab},\\ \phi_{ad}=\phi_{be}=\phi_{ca}=\phi_{ac},\\ \phi_{ac}=\phi_{bd}=\phi_{ce}=\phi_{da}=\phi_{ad}$$

Thus in the case of a regular pentagon all $\phi_{\cdot,\cdot} = \phi$ for a single given $\phi$.

(This is actually a comment)

We are given $10$ equations for $5$ vectors ${\bf a}$, $\ldots$, ${\bf e}\in{\mathbb R}^2$. For any solution $({\bf a}_0,\ldots,{\bf e}_0)$, rotating the five vectors by the same angle $\theta\in{\mathbb R}$ produces a new solution $({\bf a}_\theta,\ldots,{\bf e}_\theta)$. It follows that the $10$ equations are not "independent", and that the data $\phi_{ik}$ have to satisfy a certain a-priori condition. Any strategem to solve the given system of equations has to reconcile this fact.

Considering $(a_1, a_2), \ldots, (e_1, e_2)$ as vectors $A, \ldots, E \in \mathbb R^2$, you're specifying their dot products with each other (but not with themselves), thus all off-diagonal elements of their Gramian matrix. The constraints on the Gramian matrix are

1. It is positive semidefinite, so every principal minor is nonnegative.
2. Since these are vectors in $\mathbb R^2$, any three are linearly dependent, so every $3 \times 3$ principal minor is $0$.

I would start with (2), getting $10$ equations in the $5$ diagonal elements. Elimination is likely to lead to a finite number of possible solutions (if any), and then you can check (1) for each.

Once you have a feasible Gramian matrix $G$, you can find solutions as follows:

1. Start with any vector $A$ with $A \cdot A = G_{11}$.
2. Take any vector $B$ with $A . B = \phi_{ab}$ and $B \cdot B = G_{22}$ (generically there will be two possibilities).
3. Similarly $C$, $D$, $E$ are determined by their dot products with themselves and the previous vectors (if $A$ and $B$ are linearly independent, the dot products with $A$ and $B$ are enough to determine them uniquely).

EDIT: If the diagonal elements are all known to be $1$, you just have to check that the matrix is positive semidefinite and has rank $\le 2$, and then proceed as above. If all off-diagonal elements are $\pm 1$, then $A$ is any unit vector and all the others are $\pm A$ (depending on whether $\phi_{a\cdot} = +1$ or $-1$). Otherwise, without loss of generality suppose $|\phi_{ab}| < 1$. Let $A$ be any unit vector, and $V$ one of the two unit vectors orthogonal to $A$. Take $B = \phi_{ab} A + \sqrt{1-\phi_{ab}^2} V$. Thus $$V = \dfrac{-\phi_{ab}}{\sqrt{1-\phi_{ab}^2}} A + \dfrac{1}{\sqrt{1-\phi_{ab}^2}} B$$ so that $$C = \phi_{ac} A + (C \cdot V) V = \phi_{ac} A + \left(\dfrac{\phi_{bc} -\phi_{ab} \phi_{ac}}{\sqrt{1-\phi_{ab}^2}}\right) V$$ and similarly for $D$ and $E$.

• I like the idea that every $3\times 3$ principal minor is $0$. However, there are $6$ such minors for $5$ unknown diagonal elements :( – user251257 Jun 30 '15 at 23:36
• ${5 \choose 3} = 10$. – Robert Israel Jul 1 '15 at 2:50
• oh I only counted subsets containing 1 :) it doesn't make the thing better. – user251257 Jul 1 '15 at 3:12