9
$\begingroup$

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?

Additional info (based on comments):

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}$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – andre Jun 30 '15 at 23:26
  • $\begingroup$ Seems sort of symmetric -- there is probably some clever manipulation that can be done $\endgroup$ – 1110101001 Jul 1 '15 at 1:31
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

(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.

$\endgroup$
1
$\begingroup$

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$.

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

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.