1.1 Introduction to linear equations

Back

A linear equation in n unknowns x1; x2; ¢ ¢ ¢ ; xn is an equation of the form

a1x1 + a2x2 + ¢ ¢ ¢ + anxn = b;

where a1; a2; : : : ; an; b are given real numbers.

For example, with x and y instead of x1 and x2, the linear equation

2x + 3y = 6 describes the line passing through the points (3; 0) and (0; 2).

Similarly, with x; y and z instead of x1; x2 and x3, the linear equa-

tion 2x + 3y + 4z = 12 describes the plane passing through the points

(6; 0; 0); (0; 4; 0); (0; 0; 3).

A system of m linear equations in n unknowns x1; x2; ¢ ¢ ¢ ; xn is a family

of linear equations

a11x1 + a12x2 + ¢ ¢ ¢ + a1nxn = b1

a21x1 + a22x2 + ¢ ¢ ¢ + a2nxn = b2

...

am1x1 + am2x2 + ¢ ¢ ¢ + amnxn = bm:

We wish to determine if such a system has a solution, that is to ¯nd

out if there exist numbers x1; x2; ¢ ¢ ¢ ; xn which satisfy each of the equations

simultaneously. We say that the system is consistent if it has a solution.

Otherwise the system is called inconsistent.

1

2 CHAPTER 1. LINEAR EQUATIONS

Note that the above system can be written concisely as

Xn

j=1

aijxj = bi; i = 1; 2; ¢ ¢ ¢ ; m:

The matrix 2

6664

a11 a12 ¢ ¢ ¢ a1n

a21 a22 ¢ ¢ ¢ a2n

...

...

am1 am2 ¢ ¢ ¢ amn

3

7775

is called the coe±cient matrix of the system, while the matrix

2

6664

a11 a12 ¢ ¢ ¢ a1n b1

a21 a22 ¢ ¢ ¢ a2n b2

...

...

...

am1 am2 ¢ ¢ ¢ amn bm

3

7775

is called the augmented matrix of the system.

Geometrically, solving a system of linear equations in two (or three)

unknowns is equivalent to determining whether or not a family of lines (or

planes) has a common point of intersection.

EXAMPLE 1.1.1 Solve the equation

2x + 3y = 6:

Solution. The equation 2x + 3y = 6 is equivalent to 2x = 6 ¡ 3y or

x = 3 ¡ 3

2y, where y is arbitrary. So there are in¯nitely many solutions.

EXAMPLE 1.1.2 Solve the system

x + y + z = 1

x ¡ y + z = 0:

Solution. We subtract the second equation from the ¯rst, to get 2y = 1

and y = 1

2 . Then x = y ¡ z = 1

2 ¡ z, where z is arbitrary. Again there are

in¯nitely many solutions.

EXAMPLE 1.1.3 Find a polynomial of the form y = a0+a1x+a2x2+a3x3

which passes through the points (¡3; ¡2); (¡1; 2); (1; 5); (2; 1).

1.1. INTRODUCTION TO LINEAR EQUATIONS 3

Solution. When x has the values ¡3; ¡1; 1; 2, then y takes corresponding

values ¡2; 2; 5; 1 and we get four equations in the unknowns a0; a1; a2; a3:

a0 ¡ 3a1 + 9a2 ¡ 27a3 = ¡2

a0 ¡ a1 + a2 ¡ a3 = 2

a0 + a1 + a2 + a3 = 5

a0 + 2a1 + 4a2 + 8a3 = 1:

This system has the unique solution a0 = 93=20; a1 = 221=120; a2 =

¡23=20;

a3 = ¡41=120. So the required polynomial is

y =

93

20

+

221

120

x ¡

23

20

x2 ¡

41

120

x3:

In [26, pages 33{35] there are examples of systems of linear equations

which arise from simple electrical networks using Kirchho®'s laws for elec-

trical circuits.

Solving a system consisting of a single linear equation is easy. However if

we are dealing with two or more equations, it is desirable to have a systematic

method of determining if the system is consistent and to ¯nd all solutions.

Instead of restricting ourselves to linear equations with rational or real

coe±cients, our theory goes over to the more general case where the coef-

¯cients belong to an arbitrary ¯eld. A ¯eld F is a set F which possesses

operations of addition and multiplication which satisfy the familiar rules of

rational arithmetic. There are ten basic properties that a ¯eld must have:

THE FIELD AXIOMS.

1. (a + b) + c = a + (b + c) for all a; b; c in F;

2. (ab)c = a(bc) for all a; b; c in F;

3. a + b = b + a for all a; b in F;

4. ab = ba for all a; b in F;

5. there exists an element 0 in F such that 0 + a = a for all a in F;

6. there exists an element 1 in F such that 1a = a for all a in F;

4 CHAPTER 1. LINEAR EQUATIONS

7. to every a in F, there corresponds an additive inverse ¡a in F, satis-

fying

a + (¡a) = 0;

8. to every non{zero a in F, there corresponds a multiplicative inverse

a¡1 in F, satisfying

aa¡1 = 1;

9. a(b + c) = ab + ac for all a; b; c in F;

10. 0 6= 1.

With standard de¯nitions such as a ¡ b = a + (¡b) and

a

b

= ab¡1 for

b 6= 0, we have the following familiar rules:

¡(a + b) = (¡a) + (¡b); (ab)¡1 = a¡1b¡1;

¡(¡a) = a; (a¡1)¡1 = a;

¡(a ¡ b) = b ¡ a; (

a

b

)¡1 =

b

a

;

a

b

+

c

d

=

ad + bc

bd

;

a

b

c

d

=

ac

bd

;

ab

ac

=

b

c

;

a ¡b

c

¢ =

ac

b

;

¡(ab) = (¡a)b = a(¡b);

¡

³a

b

´

= ¡a

b

=

a

¡b

;

0a = 0;

(¡a)¡1 = ¡(a¡1):

Fields which have only ¯nitely many elements are of great interest in

many parts of mathematics and its applications, for example to coding the-

ory. It is easy to construct ¯elds containing exactly p elements, where p is

a prime number. First we must explain the idea of modular addition and

modular multiplication. If a is an integer, we de¯ne a (mod p) to be the

least remainder on dividing a by p: That is, if a = bp+r, where b and r are

integers and 0 · r < p, then a (mod p) = r.

For example, ¡1 (mod 2) = 1; 3 (mod 3) = 0; 5 (mod 3) = 2.

1.1. INTRODUCTION TO LINEAR EQUATIONS 5

Then addition and multiplication mod p are de¯ned by

a © b = (a + b) (mod p)

a ­ b = (ab) (mod p):

For example, with p = 7, we have 3 © 4 = 7 (mod 7) = 0 and 3 ­ 5 =

15 (mod 7) = 1. Here are the complete addition and multiplication tables

mod 7:

© 0 1 2 3 4 5 6

0 0 1 2 3 4 5 6

1 1 2 3 4 5 6 0

2 2 3 4 5 6 0 1

3 3 4 5 6 0 1 2

4 4 5 6 0 1 2 3

5 5 6 0 1 2 3 4

6 6 0 1 2 3 4 5

­ 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6

2 0 2 4 6 1 3 5

3 0 3 6 2 5 1 4

4 0 4 1 5 2 6 3

5 0 5 3 1 6 4 2

6 0 6 5 4 3 2 1

If we now let Zp = f0; 1; : : : ; p¡1g, then it can be proved that Zp forms

a ¯eld under the operations of modular addition and multiplication mod p.

For example, the additive inverse of 3 in Z7 is 4, so we write ¡3 = 4 when

calculating in Z7. Also the multiplicative inverse of 3 in Z7 is 5 , so we write

3¡1 = 5 when calculating in Z7.

In practice, we write a©b and a­b as a+b and ab or a£b when dealing

with linear equations over Zp.

The simplest ¯eld is Z2, which consists of two elements 0; 1 with addition

satisfying 1+1 = 0. So in Z2, ¡1 = 1 and the arithmetic involved in solving

equations over Z2 is very simple.

EXAMPLE 1.1.4 Solve the following system over Z2:

x + y + z = 0

x + z = 1:

Solution. We add the ¯rst equation to the second to get y = 1. Then x =

1 ¡ z = 1 + z, with z arbitrary. Hence the solutions are (x; y; z) = (1; 1; 0)

and (0; 1; 1).

We use Q and R to denote the ¯elds of rational and real numbers, re-

spectively. Unless otherwise stated, the ¯eld used will be Q.

6 CHAPTER 1. LINEAR EQUATIONS

Навигация