3 views

Skip to first unread message

May 8, 2011, 5:53:04 AM5/8/11

to fcla-discuss

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.

====================================================================

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.

====================================================================

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu