# Solving symbolic system of non-linear equations takes too long

I am trying to solve a set of system of symbolic non-linear equations:

g1 = ptz + pz + 2 pty q0 q1 - 2 ptz q1^2 + 2 px q0 q2 - 2 pz q2^2 -
2 px q1 q3 - 2 pty q2 q3 - 2 ptz q3^2 - 2 pz q3^2 ;
g2 = 2 (ptx q0 q1 + px q0 q1 + ptz q1 q2 - pz q1 q2 + ptz q0 q3 +
pz q0 q3 - ptx q2 q3 + px q2 q3);
g3 = ptx + px - 2 ptx q1^2 - 2 px q1^2 - 2 pz q0 q2 - 2 pty q1 q2 -
2 px q2^2 - 2 pty q0 q3 - 2 pz q1 q3 - 2 ptx q3^2 ;
g4 = -2 pty q0 q2 - 2 py q0 q2 + 2 ptz q1 q2 - 2 pz q1 q2 -
2 ptz q0 q3 - 2 pz q0 q3 - 2 pty q1 q3 + 2 py q1 q3 ;
g5 = ptz + pz - 2 py q0 q1 - 2 pz q1^2 - 2 ptx q0 q2 - 2 ptz q2^2 -
2 ptx q1 q3 - 2 py q2 q3 - 2 ptz q3^2 - 2 pz q3^2 ;
g6 = -pty - py - 2 pz q0 q1 + 2 py q1^2 + 2 ptx q1 q2 + 2 pty q2^2 +
2 py q2^2 - 2 ptx q0 q3 + 2 pz q2 q3 + 2 pty q3^2 ;
g7 = q0^2 + q1^2 + q2^2 + q3^2;

NSolve[{g1 == 0, g2 == 0, g3 == 0, g4 == 0, g5 == 0, g6 == 0,
g7 == 1}, {q0, q1, q2, q3}, Reals]


The goal is to show that these equations are inconsistent. Here all symbols except q0, q1, q2 and q3 are considered fixed. The variables represent a unit quaternion. Testing for corner cases (by setting single element of quaternion to 0) reveals that these set of equations don't have a solution i.e. they are inconsistent. For the general case however, the code takes too long to run. Any suggestions would be appreciated.

I could treat the elements of quaternion and the permutations of the elements as separate variable and solve the system as Linear Equations, which I did for the corner cases. But here I don't have enough constraints (10 unknowns with 7 constraints) and hence can't employ that method.

Edit: I apologize for not being able to provide all the details to begin with.

In addition to the constraints above, the following constraints need to be met:

g8 = pz + ptx (-2 q0 q2 + 2 q1 q3) + pty (2 q0 q1 + 2 q2 q3) + ptz (q0^2 - q1^2 - q2^2 + q3^2)

g9 = px + pty (2 q1 q2 - 2 q0 q3) + ptz (2 q0 q2 + 2 q1 q3) + ptx (q0^2 + q1^2 - q2^2 - q3^2)

g10 =  py + ptx (2 q1 q2 + 2 q0 q3) + ptz (-2 q0 q1 + 2 q2 q3) + pty (q0^2 - q1^2 + q2^2 - q3^2)

With
g8 != 0
g9 = c
g10 = c


where c is an any real number.

• NSolve certainly won't work if you've got symbolic ptx, pty, ptz, px,py,pz. You need Solve and Reduce . Unfortunately even that approach is taking a very long time. Jul 5, 2020 at 19:32
• Yeah, I am trying Solve now and like you said, its taking too long. Jul 5, 2020 at 19:46
• You can find counter-examples quite easily though with: FindInstance[ g1 + g2 + g3 + g4 + g5 + g6 != 0 && g7 == 1, {q0, q1, q2, q3, px, py, pz, ptx, pty, ptz}, Reals] Jul 5, 2020 at 20:54
• ... and a specific solution at {q0 -> 0, q1 -> 0, q2 -> 0, q3 -> -1, px -> 0, py -> 0, pz -> 0, ptx -> 0, pty -> 0, ptz -> 0} Jul 5, 2020 at 21:00
• @flinty There are other conditions that need to be met. For instance simultaneously px, py, pz cant be zero and similarly ptx, pty and ptz cant be zero simultaneously. I was not sure how to incorporate this into the system. Hence I thought it better to find the general solution and then look for these other constraints. Jul 5, 2020 at 22:54

The equations are consistent, as can be shown as follows. First, note that the first six expressions, {g1, g2, g3, g4, g5, g6}, are linear in {px, py, pz, ptx, pty, ptz}. The coefficient matrix of the first six expressions with respect to these variables is

m = Last@CoefficientArrays[{g1, g2, g3, g4, g5, g6}, {px, py, pz, ptx, pty, ptz}] // Normal;


The rank of m is

MatrixRank[m]
(* 5 *)


indicating that there is a nontrivial solution to the six expressions, even when set equal to zero. That non-trivial solution is proportional to

nv = Simplify[q3 NullSpace[m]] // Flatten
(* {-q1, -q2, -q3, q1, q2, q3} *)


In other words, the first six equations are satisfied nontrivially by

Thread[{px, py, pz, ptx, pty, ptz} -> c nv]
(* {px -> -c q1, py -> -c q2, pz -> -c q3, ptx -> c q1, pty -> c q2, ptz -> c q3} *)


with c an arbitrary constant. Hence, with these values for {px, py, pz, ptx, pty, ptz} the first six expressions are identically zero. This leaves g7 == 1, and a three-dimensional infinity of {q0, q1, q2, q3} satisfy it. For instance,

{g1 == 0, g2 == 0, g3 == 0, g4 == 0, g5 == 0, g6 == 0, g7 == 1} /.
Thread[{px, py, pz, ptx, pty, ptz} -> c nv] /. Thread[{q0, q1, q2, q3} -> 1/2]
(* {True, True, True, True, True, True, True} *)


Addendum: Further reducing the Rank of m

Still more solutions can be obtained by determining the characteristic polynomial of m and applying g7 -> 1:

CoefficientList[CharacteristicPolynomial[m, x], x] // Simplify // Factor;
char = % /. g7 :> 1
(* {0, 0, 0,
2 (q0 q1 - 4 q0 q1^3 + 4 q0^3 q1^3 + 4 q0 q1^5 + q0 q2 - 4 q0 q1^2 q2
- 4 q0^3 q1^2 q2 - 4 q0 q1^4 q2 - 8 q0 q1 q2^2 + 20 q0 q1^3 q2^2
+ 12 q0 q1^2 q2^3 + 3 q1 q3 - 8 q0^2 q1 q3 - 4 q1^3 q3 + 4 q0^2 q1^3 q3
+ 4 q1^5 q3 + q2 q3 - 2 q0^2 q2 q3 + 6 q1^2 q2 q3 + 16 q0^2 q1^2 q2 q3
- 16 q1^4 q2 q3 - 12 q1 q2^2 q3 + 12 q0^2 q1 q2^2 q3 - 2 q2^3 q3 + 12 q1 q2^4 q3
+ 4 q0 q1 q3^2 - 4 q0^3 q1 q3^2 - 16 q0 q1^3 q3^2 + 12 q0 q1^2 q2 q3^2
- 4 q0 q1 q2^2 q3^2 - 12 q1 q3^3 + 12 q0^2 q1 q3^3 - 2 q2 q3^3
+ 24 q1 q2^2 q3^3 - 4 q0 q1 q3^4 + 12 q1 q3^5),
-2 (-q1^2 - 3 q1 q2 - 2 q0^2 q1 q2 + 6 q1^3 q2 + 4 q0^2 q2^2 + 4 q1^2
q2^2 + 2 q1 q2^3 - 3 q0 q3 + 8 q0 q1^2 q3 + 4 q0 q2^2 q3 + q3^2 + 2 q0^2 q3^2
+ 2 q1^2 q3^2 + 2 q1 q2 q3^2 - 2 q2^2 q3^2 + 4 q0 q3^3 - 2 q3^4),
4 q1 q3, 1} *)


On this basis, the rank of m is only 3, and many more solutions for

{q0, q1, q2, q3, px, py, pz, ptx, pty, ptz}


exist. For instance, assuming q3 -> 0 yields solutions

Factor[char /. q3 -> 0];
Solve[Flatten[{q0^2 + q1^2 + q2^2 == 1, Thread[%[[4 ;; 5]] == 0]}],
{q0, q1, q2}, Reals] // N
(* {{q0 -> -1., q1 -> 0., q2 -> 0.}, {q0 -> 0., q1 -> 0., q2 -> -1.},
{q0 -> 0., q1 -> 0., q2 -> 1.}, {q0 -> 0., q1 -> -0.707107, q2 -> 0.707107},
{q0 -> 0., q1 -> 0.707107, q2 -> -0.707107}, {q0 -> 0., q1 -> -0.258819, q2 -> -0.965926},
{q0 -> 0., q1 -> 0.258819, q2 -> 0.965926}, {q0 -> 0., q1 -> -0.965926, q2 -> -0.258819},
{q0 -> 0., q1 -> 0.965926, q2 -> 0.258819}, {q0 -> 1., q1 -> 0., q2 -> 0.},
{q0 -> -0.707107, q1 -> -0.5, q2 -> -0.5}, {q0 -> -0.707107, q1 -> 0.5,  q2 -> 0.5},
{q0 -> 0.707107, q1 -> -0.5, q2 -> -0.5}, {q0 -> 0.707107, q1 -> 0.5, q2 -> 0.5}} *)


and corresponding values for {px, py, pz, ptx, pty, ptz}. Which of these numerous solutions are desired depends on the "other conditions that need to be met" mentioned in passing in a comment above.

A constraint recently was added to the question, namely that

pz + ptx (-2 q0 q2 + 2 q1 q3) + pty (2 q0 q1 + 2 q2 q3) + ptz (q0^2 - q1^2 - q2^2 + q3^2)


does not vanish. However, the following shows that it does vanish for every solution of the first six equations.

Rest[Eliminate[{g1 == 0, g2 == 0, g3 == 0, g4 == 0, g5 == 0, g6 == 0, g7 == 1},
{px, py}] /. {And -> List, Equal -> Subtract}];
Collect[First@%, {pz, ptx, pty, ptz}, Simplify] /.
(1 - 2 q1^2 - 2 q2^2) -> Simplify[1 - 2 q1^2 - 2 q2^2 - (1 - g7)]
(* pz + ptx (-2 q0 q2 + 2 q1 q3) + 2 pty (q0 q1 + q2 q3) + ptz (q0^2 - q1^2 - q2^2 + q3^2) *)


which is identical to the constraint but vanishes.

• I have updated my post with the additional constraints. Jul 7, 2020 at 1:05
• Thank you for the answer. I appreciate it. I have updated my post with the additional constraint. The main constraint that I used in my analysis is: pz + ptx (-2 q0 q2 + 2 q1 q3) + pty (2 q0 q1 + 2 q2 q3) + ptz (q0^2 - q1^2 - q2^2 + q3^2) != 0. I analyzed a few solutions that you mentioned in your answer and those solutions don't satisfy this constraint. To analysis specific case, I set q0=0, this also eliminates q0^2, q0q1, q0q2, q0q3 which then gives me enough constraints to analyze the mentioned system as linear in q1,q2,q3 and is inconsistent. Jul 7, 2020 at 1:06
• It is interesting to see the alternative approach of considering the system as being linear in px, py, pz, ptx, pty, ptz. I did not consider it. The reason I chose q0, q1,q2, q3 as variables is that since they represent a quaternion, ergo a rotation, the system could potentially be analyzed for all valid rotation quaternions in a brute force manner. Jul 7, 2020 at 1:17
• @AbhishekGoudar Please note that my answer provides only sample solutions. The only way to demonstrate that pz + ptx (-2 q0 q2 + 2 q1 q3) + pty (2 q0 q1 + 2 q2 q3) + ptz (q0^2 - q1^2 - q2^2 + q3^2)  vanishes for all solutions is to derive it from the {g1, g2, g3, g4, g5, g6}, which may be possible. I know how to attempt to do so, but I shall not have time until the end of the week. Jul 7, 2020 at 1:52
• @AbhishekGoudar It turns out that demonstrating that g8` always vanishes is not difficult. See the last addendum to my answer. Jul 7, 2020 at 4:19