Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Klaus Hartmann  wrote:

>
>----- Original Message -----
>From: Scott Justin Shumaker <sjs...@um...>
>To: <gda...@li...>
>Sent: Saturday, July 15, 2000 9:15 AM
>Subject: Re: [Algorithms] decompose onto non-orthogonal vectors
>
>
>> Okay, let me try and explain this as simply as possible.  You want to find
>> scalars u,v such that u*a + v*b = p.  Since these are 3-dimensional
>> vectors, you have 3 equations and 2 unknowns:
>>
>> u*a1 + v*b1 = p1
>> u*a2 + v*b2 = p2
>> u*a3 + v*b3 = p3
>>
>> where p1,p2,p3 are the coordinates of the point p, likewise for a1,a2,a3
>> and a, and b1,b2,b3 and b.
>>
>> How do you solve a system of 3 linear equations with 2 unknowns?  If you
>> don't know Gaussian elimination, this can be done with some simple
>> algebraic rules and substituion.
>
>Okay, this may become very embarrassing for me now... :) How can you solve a
>system of 3 linear equations in two unknows, u, v, if they cannot be reduced
>to two linear equations 

The system of three equations is equivalent to (i.e, has exactly the
same solutions as) a system of two equations if and only if one of the
equations is a linear combination of the other two.  And you determine
whether or not this is the case by Gaussian elimination. "Elimination"
entails eliminating unknowns from equations.  If there are more
equations than unknowns,  then Gaussian elimination will get you to a
step where one of the equations has no remaining unknowns.  If this
unknownless equation is a TRUE equation, e.g.  0=0 or 127 = 127, then
it is irrelevant, the three equations were indeed linearly dependent,
and the Gaussian elimination will have left you with a system of two
equations in two unknowns.   If this unknownless equation is a FALSE
equation, e.g.  0 = 1,  then we know that the original system of three
equations is inconsistent and has NO solutions.

Each step of Gaussian elimination consists of multiplying an equation
term wise by a constant, or replacing one of the equations by the
term-wise sum of itself with a multiple of one of the other equations.
One can easily see that this does not change the set of possible
solutions to the system.  The trick then is to choose the two
equations and the multiplier at each step so that it results in
eliminating one of the unknowns from one of the equations.  It's not a
hard trick and I'm not going to say any more about it here, except to
point out that there are various versions of the algorithm motivated
by minimizing the number of steps or minimizing the potential
numerical errors in the result.

This is all VERY ELEMENTARY LINEAR ALGEBRA,  It discourages me that a
mail list supposedly on game algorithms spends so much time on stuff
that everyone ought to have had in their basic formation, and which is
better learned from math courses and text books than from mail lists.