alternative treatment of some topics in v2.22.SLE.SSLE

[Ron Webber]

NOTES ON SYSTEMS OF LINEAR EQUATIONS --- VERSION 1

Definition. A LIST is a sequence of OBJECTS (and thus the objects are
ordered). Every list has a CLASS and all of the objects in the list
are in that class. Each object is in a POSITION in the list; if the
number of positions is more than zero, the positions are labeled 1st,
2nd,.... An object can occur more than once in a list, that is, in
more than one position. The SIZE of a list is its number of positions
(which may be zero, any finite positive integer, or infinity). An
EMPTY LIST has no objects (its size is 0), but, like every list, it
has a class. Two lists are EQUAL if they have the same class, have the
same size, and corresponding positions in the two lists contain equal
objects.

Definition. A VARIABLE LIST has the class complex-variable; a variable
list is also called a COMPLEX VARIABLE LIST for emphasis.

Definition. A COEFFICIENT LIST has the class complex-number; a
coefficient list is also called a COMPLEX COEFFICIENT LIST for
emphasis. A ZERO COEFFICIENT LIST has the complex zero in all
positions.

Definition. A LINEAR EQUATION is an equation of the form

a_1 * x_1 + a_2 * x_2 + ... + a_n * x_n = b,

where (a_1,...,a_n) is a complex coefficient list of size n,
(x_1,...,x_n) is a complex variable list of size n, and b is a complex
number called the CONSTANT of the linear equation.

Definition. A SYSTEM OF LINEAR EQUATIONS is a list of size m (>=0)
whose class is linear-equation. Every linear equation in the list has
the same complex variable list of size n. When there is no ambiguity,
a system of linear equations is sometimes called a SYSTEM.

Example: The general system of linear equations has the expression:

a_11 * x_1 + ... + a_1n * x_n = b_1
.
.
.
a_m1 * x_1 + ... + a_mn * x_n = b_m.

Definition: A SOLUTION of a linear equation

a_1 * x_1 + ... + a_n * x_n = b

of size n is a complex number list (s_1,...,s_n) of size n with the
property that the equation

a_1 * s_1 + ... + a_n * s_n = b

is true. A solution of a linear equation is said to SATISFY the
linear equation.

Definition: The SOLUTION SET of a linear equation is the set of all
solutions of the linear equation.

Therorem: If the coefficient list of a linear equation is the zero
coefficient list, then the solution set is empty when the constant of
the linear equation is nonzero and is infinite when the constant
is zero. In the latter case, the solution set is all complex number
lists of size n.

Proof: Suppose a linear equation of size n has a zero coefficient
list. Then any complex number list of size n that replaces the
variable list will result in a zero value for the left-hand side of
the equation. If the constant of the linear equation is nonzero, then
the equation is false and the solution set of the system is empty. If
the constant of the linear equation is zero, then the equation is true
for any complex coefficient list. In this case the solution set is the
set of all complex number lists of size n, which is infinite.

Definition: The intersection of the solution sets of the linear
equations in a system of linear equations is called the SOLUTION SET
of the system of linear equations.

Theorem: A solution in the solution set of a system of linear
equations satisfies every linear equation in the system.

Proof: A solution of the system of linear equations is in the
intersection of the solution sets of all the linear equations in the
system, so, in particular, satifies each equation in the system.

Definition: A PERMUTATION of a system of linear equations is a
transformation of the system of linear equations to a transformed
system of linear equations that differs from the original system only
in the order of the equations in the list of linear equations.

Theorem: If a system of linear equations is transformed by a
permutation, the solution sets of the original system and the
transformed system are equal.

Proof: The conclusion follows from the commutativity of the set
intersection operation.

Definition: A SCALING of a linear equation is a transformation of the
equation to a transformed equation resulting from multiplying the
equation
by a nonzero complex number.

("Multiplying an equation by a nonzero complex number" means
mutiplying the expression on the left side of the equation by the
nonzero number and multiplying the expression on the right side by the
same nonzero number and forming an equation between the two products.)

Theorem: The solutions sets of a linear equation and a scaling of the
linear equation are equal.

Proof: Multiplying both sides of a true equation by a nonzero complex
number results in a true equation, and multiplying both sides of a
false equation by a nonzero complex number results in a false
equation. Thus the solution set of a linear equation is the same as
the solution set of a scaling of it.

Definition: A SCALING of a system of linear equations is a
transformation of the system to a transformed system of linear
equations
resulting from scaling each linear equation in the first system. In
general, the scaling factors differ for the different linear equations
in the first system.

Theorem: The solution sets of a system of linear equations and a
scaling of the system are equal.

Proof: A linear equation in the original system of linear equations
and its scaling in the second system of linear equations have equal
solutions set by the previous theorem. Since this true for each
equation in the original system and its corresponding scaling in the
second system, the intersections of the solution sets of the linear
equations in the original system and the intersection of the solution
sets of the linear equations in the transformed system are equal sets.

Definition: A COMBINATION of a number of linear equations having the
same complex variable list is the linear equation having the same
complex variable list resulting from adding the equations and
collecting like terms on the left side.

("Adding a set of linear equations" means adding the left sides of the
equations and equating the sum to the sum of the right sides.)

("Collecting like terms" in this case means using the distributive law
for each variable in the complex variable list to add the coefficients
of that variable obtaining a complex number that becomes the
coefficient of the variable in the combination.)

Definition: A COMBINATION EXPANSION of a system of linear equations is
a transformation of the original system of size m to a transformed
system of size m+1 obtained by appending a combination from the
original system to the list of the linear equations in the original
system.

("Appending an object to a list of size m" means adding an (m+1)th
position to the list and putting the object in that position. The size
of the transformed list is one more than the size of the original
list.)

Theorem: The solution sets of a system of linear equations and a
combination expansion of the system are equal.

Proof: Suppose that S is the solution set of the of the original
system of linear equations, that S_i for 1<=i<=k are the solution sets
of the equations in the combination, and that S_combo is the solution
set
of the combination.

Then S_combo includes the intersection of the sets S_i, 1<=i<=k,
because a solution in the intersection satisfies the k equations in
the combination and thus it satisfies the combination. S_combo
therefore includes S by the transitivity of set inclusion so the
intersection of S_combo and S is S. Therefore the solution set of the
combination expansion is S.

Definition: A COMBINATION CONTRACTION of a system of linear equations
is a transformation of the original system of size m to a transformed
system of size m-1 obtained by removing a particular linear equation
from the system list. The particular linear equation must be a
combination of the other linear equations in the original system.

("Removing an object from a list of size m" means removing the object
and the object's position from the list and adjusting the remaining
position labels. The size of the transformed list is one less than the
size of the original list.)

Theorem: The solutions sets of a system of linear equations and a
combination contraction of the system are equal.

Proof: Suppose that S is the solution set of the of the original
system of linear equations, that S_i for 1<=i<=k are the solution sets
of the equations in the combination, and that S_combo is the solution
set
of the combination.

Then S_combo includes the intersection of the sets S_i, 1<=i<=k,
because a solution in the intersection satisfies the k equations in
the combination and thus it satisfies the combination. Thus S_combo
includes S by the transitivity of set inclusion so the intersection of
S_combo and S is S. Therefore the solution set of the combination
contraction is S.

Definition: A COMBINATION EXPANSION/CONTRACTION of a system of linear
equations is either a combination expansion transformation or a
combination contraction transformation of the system.

Theorem: The solutions sets of a system of linear equations and a
combination expansion/contraction of the system are equal.

Proof: The previous two theorems prove this theorem.

Definition: A SYSTEM TRANSFORMATION of a system of linear equations is
either a permutation, a scaling, or a combination
expansion/contraction.

Theorem: Every system transformation has a unique inverse.

Proof: A permutation transformation that changes the position of a
linear equation from position i to position j in a system of size m
has the inverse permutation that changes the position of a linear
equation in position j to position i for 1<=i,j<=m.

A scaling transformation with a factor list has an inverse scaling
transformation whose factor list has the multiplicative inverses of
the original factors in the same positions.

A combination expansion/contraction tranformation that appends a
combination has the inverse that removes the combination. A
combination
expansion/contraction that removes a combination has the inverse that
appends the combination.

Defintion: A TRANSFORMATION LIST for a system of linear equations is a
list of class system-transformation in which every object in the
transformation list is a system transformation of the given system.

Definition: Given a system of linear equations and given a
transformation list for the system of size t, a TRANSFORMATION LIST
APPLICATION is a list of size t+1 of class systems-of-linear-equations
whose 1st position contains the original system of linear equations
and whose (k+1)th position, where 1<=k<=t, contains the system of
linear equations obtained by transforming the system in the kth
position with the system transformation in the kth position of the
given transformation list.

Definition: Two systems of linear equations are EQUIVALENT if each
system can be obtained from the other by a transformation list
application of a transformation list whose first position contains one
system and whose last position contains the other.

Theorem: The definition of equivalent in the previous definition is an
equivalence relation.

Proof: Every system transformation has an inverse so that if one
system of linear equations is equivalent to a second, the second is
equivalent to the first using the transformation list containing the
inverse system transformations in reverse order.

If one system of linear equations is equivalent to a second system of
linear equations, and the second system is equivalent to a third, then
the first system is equivalent to the third using the concatenation of
the two transformation lists.

(The "concatenation" of two lists with the same class is the list of
the same class obtained by starting with the first list and
sucessively appending the objects in the second list. The size of the
concatenated list is the sum of the sizes of the two original lists.)

Theorem: All the systems of linear equations contained in a
transformation list application are equivalent.

Proof: Using the notation in the proof of the previous theorem, by
induction, the (k+1)th system in the transformation list application,
where 1<=k<=t, is equivalent to the kth system in the transformation
list application using one of the three theorems showing that any
system transformation preserves the solution set of the original
system.

Theorem: Equivalent systems of linear equations have the same solution
set.

Proof: Each step in a transformation list application preserves the
solution set so equivalent systems have equal solution sets.
====================================================================