Friday, December 24, 2010

Proving Equality to Zero

Say you have several variables - in a computer program, for example - and you want to make sure that they all equal to zero. (For the sake of this example, let's assume that they are all real numbers, i.e, 5.5 rather than 5+8i). With one variable, it's easy; you just have to set up some form of the equation

x = 0
[1]


Of course, you'd have to actually implement that in code, but that depends on the programming language and isn't really relative to this. With one variable, you have a very nice, neat equation, and it works.

With two variables, you could still do something along the lines of

x = 0 AND y=0
[2]

But that becomes very unwieldy - and decidedly unelegant - when you want to use any more than two variables. Surely there's a simple equation that one can use. What about this:


[3]

Unfortunately, this equation is a flop; it only requires at least one of the variables be zero*.
If x=0, then y and z can be any number, and so on for y=0 or z=0. What about addition, then?

x + y + z = 0
[4]

This is marginally better; it is slightly less likely to produce a false positive. However, it doesn't work. The set (x,y,z)=(2,4,-6) is a 'solution', yet none of the three variables equal zero.

A logical next step is to modify that linear equation to eliminate some false positives. for example:

x(y+n)(z+n) + y(x+n)(z+n) + z(x+n)(y+n) = 0
[5]

This eliminates most false positives, and it does in fact work if n is guaranteed to be of greater magnitude than x, y, and z, i.e, n is a sufficiently large positive or negative number that x+n, y+n, and z+n are all positive or all negative. Otherwise, however, there are still at least four solution sets: (-n,-n,-n), (0,-n,-n), (-n,0,-n), and (-n,-n,0). Additionally, if you try to generalize to complex numbers it doesn't work, and it's just plain ugly.

Eliminating those four trivial solutions is possible, if don't mind an even uglier equation:

x(y+a)(z+b) + y(x+c)(z+d) + z(x+e)(y+f) = 0
[6]

But, the problem with equations 5 and 6 is that they're not truly solving the problem. Unless variables a through f are picked very carefully, there might be a few values of x, y, and z that create a false positive, and with that many variables theres no general method to check that this is not the case. They don't generalize well to either lots of variables (to prove that ten variables all equal zero by this method, you'd need as many as 55 arbitrary variables a through j) or to complex numbers.

Now, let's think about the problem geometrically. What we are looking to prove is that the point (x,y,z) in 3D space is equal to (0,0,0). Or, if you prefer vectors, that <x,y,z> = <0,0,0> =

In other words, that our point (x,y,z) is within a radius of zero from (0,0,0). Now there's a handy equation for distance:



[7]

In this case, a=b=c=0 for the origin point (0,0,0). However, if the square root equals 0, then the equation inside also equals zero. Thus, we get a very neat equation:


[8]

And equation 8 is pretty nifty. It generalizes to any number of real variables. It's elegant - it requires only a small amount of code that works on basically system, and it uses only squares and addition - operates that are much faster than square roots or division.

Additionally, if you have a system like Mathematica or a graphing calculator that can deal with vectors, it gets better. Most systems can't check the equality

<x,y,z> = <0,0,0>
[9]

or, where = vector u,



[10]

However, there's a nicely equivalent operation, taking the magnitude (length of the vector), that does work:


[11]

For vector-ready systems, equation 11 is elegant, though not as fast due to the square root involved in taking the magnitude of the vector.



Equation 8 can also be modified to make it even more powerful; this version allows determination of which single variable is nonzero. The exact constants do not matter; they simply must be primes greater than 3.


[12]

Thus, if the result of the left side is nonzero, it can be examined. If it is divisible by an odd power of 5, x is the non zero variable, and so forth. If it is not divisible by an odd power of either of the three constants, then two or three of the variables are nonzero.


All of the really nice-looking equations are made using Codecogs LaTeX Equation Editor; Detexify is spectacularly useful for finding LaTeX symbols.

* Incidentally, equation 3 actually generates the three coordinate planes when graphed.

No comments: