       Re: Re: Strange empty set of solutions

• To: mathgroup at smc.vnet.net
• Subject: [mg71853] Re: [mg71814] Re: Strange empty set of solutions
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Fri, 1 Dec 2006 06:22:03 -0500 (EST)
• References: <ekh7pg\$sgs\$1@smc.vnet.net> <ekjfrf\$d7h\$1@smc.vnet.net> <200611301105.GAA08424@smc.vnet.net>

```JosÃ© Carlos Santos wrote:
> On 29-11-2006 8:19, Jens-Peer Kuska wrote:
>
>
>>and we can't read you mind and the memory of your computer
>>so we must imagine a matrix M and write down
>
>
> Do you want an example? Here it is:
>
> M = {{4/5(c - 1), -2/Sqrts, 2/5(1 - c)},
>       {2/5(1 - c), -1 + s/Sqrt, 4/5 + c/5},
>       {-2s/Sqrt, -c, -1 + s/Sqrt}} // N
>
> with c = Cos[Sqrt] and s = Sin[Sqrt].
>
> If I type
>
> Solve[{M.{x, y, z} == {0, 0, 0}}, {x, y, z}]
>
> I get
>
> {{x -> 0. - 0.0438861 z, y -> 0. + 1. z}}
>
> but if I type
>
> Solve[{M.{x, y, z} == {0, 0, 0}, x^2 + y^2 + z^2 == 1}, {x, y, z}]
>
> then I get the empty set. Why is that?
>
> Best regards,
>
> Jose Carlos Santos

In the first example you have three equations in three variables. They
are linear and have rank of 2. The numerical row reduction code
correctly deduces this and returns a one dimensional solution set.

When you augment by the norm=1 you now have four equations in three
variables. They are overdetermined but no longer linear. Now ou are in
the realm of polynomial algebra where dependencies are more difficult to
assess, and indeed this one is missed. Solve believes it has an
overdetermined system and returns an empty solution set.

Ways to avoid this pitfall are to work with the exact system, or with a
higher precision numericization. Also I would recommend NSolve in the
case where you expect to have finitely many solutions.

c = Cos[Sqrt];
s = Sin[Sqrt];
exactM = {{4/5(c - 1), -2/Sqrts, 2/5(1 - c)},
{2/5(1 - c), -1 + s/Sqrt, 4/5 + c/5},
{-2s/Sqrt, -c, -1 + s/Sqrt}};
M100 = N[exactM, 100];
allpolys100 = Flatten[{M100.{x,y,z}, x^2+y^2+z^2-1}];

Now you get your two solutions.

solns = NSolve[allpolys100, {x,y,z}]

I should mention that this is a tenuous area. You are working with
finite precision on a problem for which perturbations give no solution.
So you really need to use the benefits afforded by significance
arithmetic, or else code a method that can handle "fuzzy zeros".

An alternative, for problems like this where you have a linear solution
set and wish to select certain members, is to use a linear algebra
method first and then post-process. This is advantageous because linear
algebra is both faster and, if you use appropriate methods e.g. singular
value decomposition, better studied and more robust in terms of
assessing and handling rank deficiencies.

Daniel Lichtblau
Wolfram Research

```