3.3 Systems of Linear Equations—Theoretical Aspects

This section and the next are devoted to the study of systems of linear equations, which arise naturally in both the physical and social sciences. In this section, we apply results from Chapter 2 to describe the solution sets of systems of linear equations as subsets of a vector space. In Section 3.4, we will use elementary row operations to provide a computational method for finding all solutions to such systems.

The system of equations

a11x1+a12x2+  +a1nxn=b1a21x1+a22x2+  +a2nxn=b2(S)am1x1+am2x2+  +amnxn=bm,
a11x1+a12x2+  +a1nxn=b1a21x1+a22x2+  +a2nxn=b2(S)am1x1+am2x2+  +amnxn=bm,

where aijaij and bibi (1im1im and 1jn1jn) are scalars in a field F and x1, x2, , xnx1, x2, , xn are n variables taking values in F, is called a system of m linear equations in n unknowns over the field F.

The m×nm×n matrix

A=(a11a12a1na21a22a2nam1am2amn)
A=a11a21am1a12a22am2a1na2namn

is called the coefficient matrix of the system (S).

If we let

x=(x1x2xn)andb=(b1b2bm),
x=x1x2xnandb=b1b2bm,

then the system (S) may be rewritten as a single matrix equation

Ax=b
Ax=b

To exploit the results that we have developed, we often consider a system of linear equations as a single matrix equation.

A solution to the system (S) is an n-tuple

s=(s1s2sn)Fn
s=s1s2snFn

such that As=bAs=b. The set of all solutions to the system (S) is called the solution set of the system. System (S) is called consistent if its solution set is nonempty; otherwise it is called inconsistent.

Example 1

  1. (a) Consider the system

    x1+x2=3x1x2=1.
    x1+x2x1x2==31.

    By use of familiar techniques, we can solve the preceding system and conclude that there is only one solution: x1=2, x2=1x1=2, x2=1 that is,

    s=(21).
    s=(21).

    In matrix form, the system can be written

    (1111)(x1x2)=(31);
    (1111)(x1x2)=(31);

    so

    A=(1111)andb=(31).
    A=(1111)andb=(31).
  2. (b) Consider

    2x1+3x2+x3=1x1x2+2x3=6;
    2x1x1+3x2x2++x32x3==16;

    that is,

    (231112)(x1x2x3)=(16).
    (213112)x1x2x3=(16).

    This system has many solutions, such as

    s=(627)ands=(843).
    s=627ands=843.
  3. (c) Consider

    x1+x2=0x1+x2=1;
    x1+x2x1+x2==01;

    that is,

    (1111)(x1x2)=(01).
    (1111)(x1x2)=(01).

It is evident that this system has no solutions. Thus we see that a system of linear equations can have one, many, or no solutions.

We must be able to recognize when a system has a solution and then be able to describe all its solutions. This section and the next are devoted to this end.

We begin our study of systems of linear equations by examining the class of homogeneous systems of linear equations. Our first result (Theorem 3.8) shows that the set of solutions to a homogeneous system of m linear equations in n unknowns forms a subspace of FnFn. We can then apply the theory of vector spaces to this set of solutions. For example, a basis for the solution space can be found, and any solution can be expressed as a linear combination of the vectors in the basis.

Definitions.

A system Ax=bAx=b of m linear equations in n unknowns is said to be homogeneous if b=0b=0. Otherwise the system is said to be nonhomogeneous.

Any homogeneous system has at least one solution, namely, the zero vector. The next result gives further information about the set of solutions to a homogeneous system.

Theorem 3.8.

Let Ax=0Ax=0 be a homogeneous system of m linear equations in n unknowns over a field F. Let K denote the set of all solutions to Ax=0Ax=0 . Then K=N(LA);K=N(LA); hence K is a subspace of FnFn of dimension nrank(LA)=nrank(A)nrank(LA)=nrank(A).

Proof.

Clearly, K={sFn: As=0}=N(LA)K={sFn: As=0}=N(LA). The second part now follows from the dimension theorem (p. 70).

Corollary.

If m<nm<n, the system Ax=0Ax=0 has a nonzero solution.

Proof.

Suppose that m<nm<n. Then rank(A)=rank(LA)mrank(A)=rank(LA)m. Hence

dim(K)=nrank(LA)nm>0,
dim(K)=nrank(LA)nm>0,

where K=N(LA)K=N(LA). Since dim(K)>0, K{0}dim(K)>0, K{0}. Thus there exists a nonzero vector sK;sK; so s is a nonzero solution to Ax=0Ax=0.

Example 2

  1. (a) Consider the system

    x1+2x2+x3=0x1x2x3=0.
    x1x1+2x2x2+x3x3==00.

    Let

    A=(121111)
    A=(112111)

    be the coefficient matrix of this system. It is clear that rank(A)=2rank(A)=2. If K is the solution set of this system, then dim(K)=32=1dim(K)=32=1. Thus any nonzero solution constitutes a basis for K. For example, since

    (123)
    123

    is a solution to the given system,

    {(123)}
    123

    is a basis for K. Thus any vector in K is of the form

    t(123)=(t2t3t),
    t123=t2t3t,

    where tRtR.

  2. (b) Consider the system x12x2+x3=0x12x2+x3=0 of one equation in three unknowns. If A=(121)A=(121) is the coefficient matrix, then rank(A)=1rank(A)=1. Hence if K is the solution set, then dim(K)=31=2dim(K)=31=2. Note that

    (210)and(101)
    210and101

    are linearly independent vectors in K. Thus they constitute a basis for K, so that

    K={t1(210)+t2(101): t1, t2R}.
    K=t1210+t2101: t1, t2R.

In Section 3.4, explicit computational methods for finding a basis for the solution set of a homogeneous system are discussed.

We now turn to the study of nonhomogeneous systems. Our next result shows that the solution set of a nonhomogeneous system Ax=bAx=b can be described in terms of the solution set of the homogeneous system Ax=0Ax=0. We refer to the equation Ax=0Ax=0 as the homogeneous system corresponding to Ax=bAx=b.

Theorem 3.9.

Let K be the solution set of a consistent system of linear equations Ax=bAx=b, and let KHKH be the solution set of the corresponding homogeneous system Ax=0Ax=0. Then for any solution s to Ax=bAx=b

K={s}+KH={s+k: kKH}.
K={s}+KH={s+k: kKH}.

Proof.

Let s be any solution to Ax=bAx=b. We must show that K={s}+KHK={s}+KH. If wKwK, then Aw=bAw=b. Hence

A(ws)=AwAs=bb=0.
A(ws)=AwAs=bb=0.

So wsKHwsKH. Thus there exists kKHkKH such that ws=kws=k. It follows that w=s+k{s}+KHw=s+k{s}+KH, and therefore

K{s}+KH.
K{s}+KH.

Conversely, suppose that w{s}+KH;w{s}+KH; then w=s+kw=s+k for some kKHkKH. But then Aw=A(s+k)=As+Ak=b+0=bAw=A(s+k)=As+Ak=b+0=b; so wKwK. Therefore {s}+KHK{s}+KHK, and thus K={s}+KHK={s}+KH.

Example 3

  1. (a) Consider the system

    x1+2x2+x3=7x1x2x3=4.
    x1x1+2x2x2+x3x3==74.

    The corresponding homogeneous system is the system in Example 2(a). It is easily verified that

    s=(114)
    s=114

    is a solution to the preceding nonhomogeneous system. So the solution set of the system is

    K={(114)+t(123): tR}
    K=114+t123: tR

    by Theorem 3.9.

  2. (b) Consider the system x12x2+x3=4x12x2+x3=4. The corresponding homogeneous system is the system in Example 2(b). Since

    s=(400)
    s=400

    is a solution to the given system, the solution set K can be written as

    K={(400)+t1(210)+t2(101): t1, t2R}.
    K=400+t1210+t2101: t1, t2R.

The following theorem provides us with a means of computing solutions to certain systems of linear equations.

Theorem 3.10.

Let Ax=bAx=b be a system of n linear equations in n unknowns. If A is invertible, then the system has exactly one solution, namely, A1bA1b. Conversely, if the system has exactly one solution, then A is invertible.

Proof.

Suppose that A is invertible. Substituting A1bA1b into the system, we have A(A1b)=(AA1)b=bA(A1b)=(AA1)b=b. Thus A1bA1b is a solution. If s is an arbitrary solution, then As=bAs=b. Multiplying both sides by A1A1 gives s=A1bs=A1b. Thus the system has one and only one solution, namely, A1bA1b.

Conversely, suppose that the system has exactly one solution s. Let KHKH denote the solution set for the corresponding homogeneous system Ax=0Ax=0. By Theorem 3.9, {s}={s}+KH{s}={s}+KH. But this is so only if KH={0}KH={0}. Thus N(LA)={0}N(LA)={0}, and hence A is invertible.

Example 4

Consider the following system of three linear equations in three unknowns:

2x2+4x3=22x1+4x2+2x3=33x1+3x2+x3=1.
2x13x1++2x24x23x2+++4x32x3x3===231.

In Example 5 of Section 3.2, we computed the inverse of the coefficient matrix A of this system. Thus the system has exactly one solution, namely,

(x1x2x3)=A1b=(185834143412383814)(231)=(785418).
x1x2x3=A1b=181438583438341214231=785418.

We use this technique for solving systems of linear equations having in-vertible coefficient matrices in the application that concludes this section.

In Example 1(c), we saw a system of linear equations that has no solutions. We now establish a criterion for determining when a system has solutions. This criterion involves the rank of the coefficient matrix of the system Ax=bAx=b and the rank of the matrix (A|b)(A|b). The matrix (A|b)(A|b) is called the augmented matrix of the system Ax=bAx=b.

Theorem 3.11.

Let Ax=bAx=b be a system of linear equations. Then the system is consistent if and only if rank(A)=rank(A|b)rank(A)=rank(A|b).

Proof.

To say that Ax=bAx=b has a solution is equivalent to saying that bR(LA)bR(LA). (See Exercise 8.) In the proof of Theorem 3.5 (p. 153), we saw that

R(LA)=span({a1, a2, , an}),
R(LA)=span({a1, a2, , an}),

the span of the columns of A. Thus Ax=bAx=b has a solution if and only if bspan({a1, a2, , an})bspan({a1, a2, , an}). But bspan({a1, a2, , an})bspan({a1, a2, , an}) if and only if span({a1, a2, , an})=span({a1, a2, , an, b})span({a1, a2, , an})=span({a1, a2, , an, b}). This last statement is equivalent to

dim(span({a1, a2, , an}))=dim(span({a1, a2, , an, b})).
dim(span({a1, a2, , an}))=dim(span({a1, a2, , an, b})).

So by Theorem 3.5, the preceding equation reduces to

rank(A)=rank(A|b).
rank(A)=rank(A|b).

Example 5

Recall the system of equations

x1+x2=0x1+x2=1
x1+x2x1+x2==01

in Example 1(c).

Since

A=(1111)and(A|b)=(110111),
A=(1111)and(A|b)=(111101),

rank(A)=1rank(A)=1 and rank(A|b)=2rank(A|b)=2. Because the two ranks are unequal, the system has no solutions.

Example 6

We can use Theorem 3.11 to determine whether (3, 3, 2) is in the range of the linear transformation T: R3R3T: R3R3 defined by

T(a1, a2, a3)=(a1+a2+a3, a1a2+a3, a1+a3).
T(a1, a2, a3)=(a1+a2+a3, a1a2+a3, a1+a3).

Now (3, 3, 2)R(T)(3, 3, 2)R(T) if and only if there exists a vector s=(x1, x2, x3)s=(x1, x2, x3) in R3R3 such that T(s)=(3, 3, 2)T(s)=(3, 3, 2). Such a vector s must be a solution to the system

x1+x2+x3=3x1x2+x3=3x1+x3=2.
x1x1x1+x2x2+++x3x3x3===332.

Since the ranks of the coefficient matrix and the augmented matrix of this system are 2 and 3, respectively, it follows that this system has no solutions. Hence (3, 3, 2)R(T)(3, 3, 2)R(T).

An Application

In 1973, Wassily Leontief won the Nobel prize in economics for his work in developing a mathematical model that can be used to describe various economic phenomena. We close this section by applying some of the ideas we have studied to illustrate two special cases of his work.

We begin by considering a simple society composed of three people (industries)—a farmer who grows all the food, a tailor who makes all the clothing, and a carpenter who builds all the housing. We assume that each person sells to and buys from a central pool and that everything produced is consumed. Since no commodities either enter or leave the system, this case is referred to as the closed model.

Each of these three individuals consumes all three of the commodities produced in the society. Suppose that the proportion of each of the commodities consumed by each person is given in the following table. Notice that each of the columns of the table must sum to 1.

  Food Clothing Housing
Farmer 0.40 0.20 0.20
Tailor 0.10 0.70 0.20
Carpenter 0.50 0.10 0.60

Let p1, p2p1, p2, and p3p3 denote the incomes of the farmer, tailor, and carpenter, respectively. To ensure that this society survives, we require that the consumption of each individual equals his or her income. Note that the farmer consumes 20% of the clothing. Because the total cost of all clothing is p2p2, the tailor’s income, the amount spent by the farmer on clothing is 0.20p20.20p2. Moreover, the amount spent by the farmer on food, clothing, and housing must equal the farmer’s income, and so we obtain the equation

0.40p1+0.20p2+0.20p3=p1.
0.40p1+0.20p2+0.20p3=p1.

Similar equations describing the expenditures of the tailor and carpenter produce the following system of linear equations:

0.40p1+0.20p2+0.20p3=p10.10p1+0.70p2+0.20p3=p20.50p1+0.10p2+0.60p3=p3.
0.40p1+0.20p2+0.20p30.10p1+0.70p2+0.20p30.50p1+0.10p2+0.60p3===p1p2p3.

This system can be written as Ap=pAp=p, where

p=(p1p2p3)
p=p1p2p3

and A is the coefficient matrix of the system. In this context, A is called the input—output (or consumption) matrix, and Ap=pAp=p is called the equilibrium condition.

For vectors b=(b1, b2, , bn)b=(b1, b2, , bn) and c=(c1, c2, , cn)c=(c1, c2, , cn) in RnRn, we use the notation bc [b>c]bc [b>c] to mean bici [bi>ci]bici [bi>ci] for all i. The vector b is called nonnegative [positive] if b0 [b>0]b0 [b>0].

At first, it may seem reasonable to replace the equilibrium condition by the inequality AppApp, that is, the requirement that consumption not exceed production. But, in fact, AppApp implies that Ap=pAp=p in the closed model. For otherwise, there exists a k for which

pk>jAkjpj.
pk>jAkjpj.

Hence, since the columns of A sum to 1,

ipi>ijAijpj=j(iAij)pj=jpj,
ipi>ijAijpj=j(iAij)pj=jpj,

which is a contradiction.

One solution to the homogeneous system (IA)x=0(IA)x=0, which is equivalent to the equilibrium condition, is

p=(0.250.350.40).
p=0.250.350.40.

We may interpret this to mean that the society survives if the farmer, tailor, and carpenter have incomes in the proportions 25 : 35 : 40 (or 5 : 7 : 8).

Notice that we are not simply interested in any nonzero solution to the system, but in one that is nonnegative. Thus we must consider the question of whether the system (IA)x=0(IA)x=0 has a nonnegative solution, where A is a matrix with nonnegative entries whose columns sum to 1. A useful theorem in this direction (whose proof may be found in “Applications of Matrices to Economic Models and Social Science Relationships,” by Ben Noble, Proceedings of the Summer Conference for College Teachers on Applied Mathematics, 1971, CUPM, Berkeley, California) is stated below.

Theorem 3.12.

Let A be an n×nn×n input-output matrix having the form

A=(BCDE),
A=(BDCE),

where D is a 1×(n1)1×(n1) positive vector and C is an (n1)×1(n1)×1 positive vector. Then (IA)x=0(IA)x=0 has a one-dimensional solution set that is generated by a nonnegative vector.

Observe that any input-output matrix with all positive entries satisfies the hypothesis of this theorem. The following matrix does also:

(0.750.500.6500.250.350.250.250).
0.7500.250.500.250.250.650.350.

In the open model, we assume that there is an outside demand for each of the commodities produced. Returning to our simple society, let x1, x2x1, x2, and x3x3 be the monetary values of food, clothing, and housing produced with respective outside demands d1, d2d1, d2, and d3d3. Let A be the 3×33×3 matrix such that AijAij represents the amount (in a fixed monetary unit such as the dollar) of commodity i required to produce one monetary unit of commodity j. Then the value of the surplus of food in the society is

x1(A11x1+A12x2+A13x3).
x1(A11x1+A12x2+A13x3).

that is, the value of food produced minus the value of food consumed while producing the three commodities. The assumption that everything produced is consumed gives us a similar equilibrium condition for the open model, namely, that the surplus of each of the three commodities must equal the corresponding outside demands. Hence

xi3j=1Aijxj=difor i=1, 2, 3.
xij=13Aijxj=difor i=1, 2, 3.

In general, we must find a nonnegative solution to (IA)x=d(IA)x=d, where A is a matrix with nonnegative entries such that the sum of the entries of each column of A does not exceed one, and d0d0. It is easy to see that if (IA)1(IA)1 exists and is nonnegative, then the desired solution is (IA)1d(IA)1d.

Recall that for a real number a, the series 1+a+a2+1+a+a2+ converges to (1a)1(1a)1 if |a|<1|a|<1. Similarly, it can be shown (using the concept of convergence of matrices developed in Section 5.3) that the series I+A+A2+I+A+A2+ converges to (IA)1(IA)1 if {An}{An} converges to the zero matrix. In this case, (IA)1(IA)1 is nonnegative since the matrices I, A, A2, I, A, A2,  are nonnegative.

To illustrate the open model, suppose that 30 cents worth of food, 10 cents worth of clothing, and 30 cents worth of housing are required for the production of $1 worth of food. Similarly, suppose that 20 cents worth of food, 40 cents worth of clothing, and 20 cents worth of housing are required for the production of $1 of clothing. Finally, suppose that 30 cents worth of food, 10 cents worth of clothing, and 30 cents worth of housing are required for the production of $1 worth of housing. Then the input-output matrix is

A=(0.300.200.300.100.400.100.300.200.30);
A=0.300.100.300.200.400.200.300.100.30;

so

IA=(0.700.200.300.100.600.100.300.200.70)and(IA)1=(2.01.01.00.52.00.51.01.02.0).
IA=0.700.100.300.200.600.200.300.100.70and(IA)1=2.00.51.01.02.01.01.00.52.0.

Since (IA)1(IA)1 is nonnegative, we can find a (unique) nonnegative solution to (IA)x=d(IA)x=d for any demand d. For example, suppose that there are outside demands for $30 billion in food, $20 billion in clothing, and $10 billion in housing. If we set

d=(302010),
d=302010,

then

x=(IA)1d=(906070).
x=(IA)1d=906070.

So a gross production of $90 billion of food, $60 billion of clothing, and $70 billion of housing is necessary to meet the required demands.

Exercises

  1. Label the following statements as true or false.

    1. (a) Any system of linear equations has at least one solution.

    2. (b) Any system of linear equations has at most one solution.

    3. (c) Any homogeneous system of linear equations has at least one solution.

    4. (d) Any system of n linear equations in n unknowns has at most one solution.

    5. (e) Any system of n linear equations in n unknowns has at least one solution.

    6. (f) If the homogeneous system corresponding to a given system of linear equations has a solution, then the given system has a solution.

    7. (g) If the coefficient matrix of a homogeneous system of n linear equations in n unknowns is invertible, then the system has no nonzero solutions.

    8. (h) The solution set of any system of m linear equations in n unknowns is a subspace of FnFn.

  2. For each of the following homogeneous systems of linear equations, find the dimension of and a basis for the solution space.

    1. (a) x1+3x2=02x1+6x2=0x1+3x22x1+6x2==00

    2. (b) x1+x2x3=04x1+x22x3=0x14x1++x2x2x32x3==00

    3. (c) x1+2x2x3=02x1+x2+x3=0x12x1++2x2x2+x3x3==00

    4. (d) 2x1+x2x3=0x1x2+x3=0x1+2x22x3=02x1x1x1++x2x22x2+x3x32x3===000

    5. (e) x1+2x23x3+x4=0x1+2x23x3+x4=0

    6. (f) x1+2x2=0x1x2=0x1x1+2x2x2==00

    7. (g) x1+2x2+x3+x4=0x2x3+x4=0x1+2x2+x3+x4x2x3+x4==00

  3. Using the results of Exercise 2, find all solutions to the following systems.

    1. (a) x1+3x2=52x1+6x2=10x12x1++3x26x2==510

    2. (b) x1+x2x3=14x1+x22x3=3x14x1++x2x2x32x3==13

    3. (c) x1+2x2x3=32x1+x2+x3=6x12x1++2x2x2+x3x3==36

    4. (d) 2x1+x2x3=5x1x2+x3=1x1+2x22x3=42x1x1x1++x2x22x2+x3x32x3===514

    5. (e) x1+2x23x3+x4=1x1+2x23x3+x4=1

    6. (f) x1+2x2=5x1x2=1x1x1+2x2x2==51

    7. (g) x1+2x2+x3+x4=1x2x3+x4=1x1+2x2x2+x3x3++x4x4==11

  4. For each system of linear equations with the invertible coefficient matrix A,

    (1) Compute A1A1.

    (2) Use A1A1 to solve the system.

    1. (a) x1+3x2=42x1+5x2=3x12x1++3x25x2==43

    2. (b) x1+2x2x3=5x1+x2+x3=12x12x2+x3=4x1x12x1++2x2x22x2++x3x3x3===514

  5. Give an example of a system of n linear equations in n unknowns with infinitely many solutions.

  6. Let T: R3R2T: R3R2 be defined by T(a, b, c)=(a+b, 2ac)T(a, b, c)=(a+b, 2ac). Determine T1(1, 11)T1(1, 11).

  7. Determine which of the following systems of linear equations has a solution.

    1. (a) x1+x2x3+2x4=2x1+x2+2x3=12x1+2x2+x3+2x4=4x1x12x1+++x2x22x2++x32x3x3++2x42x4===214

    2. (b) x1+x2x3=12x1+x2+3x3=2x12x1++x2x2+x33x3==12

    3. (c) x1+2x2+3x3=1x1+x2x3=0x1+2x2+x3=3x1x1x1+++2x2x22x2++3x3x3x3===103

    4. (d) x1+x2+3x3x4=0x1+x2+x3+x4=1x12x2+x3x4=14x1+x2+8x3x4=0x1x1x14x1+++x2x22x2x2++++3x3x3x38x3+x4x4x4x4====0110

    5. (e) x1+2x2x3=12x1+x2+2x3=3x14x27x3=4x12x1x1++2x2x24x2+x32x37x3===134

  8. Let T: R3R3T: R3R3 be defined by T(a, b, c)=(a+b, b2c, a+2c)T(a, b, c)=(a+b, b2c, a+2c). For each vector v in R3R3, determine whether vR(T)vR(T).

    1. (a) v=(1, 3, 2)v=(1, 3, 2)

    2. (b) v=(2, 1, 1)v=(2, 1, 1)

  9. Prove that the system of linear equations Ax=bAx=b has a solution if and only if bR(LA)bR(LA). Visit goo.gl/JfwjBa for a solution.

  10. Prove or give a counterexample to the following statement: If the coefficient matrix of a system of m linear equations in n unknowns has rank m, then the system has a solution.

  11. In the closed model of Leontief with food, clothing, and housing as the basic industries, suppose that the input-output matrix is

    A=(7161231651616516141312).
    A=7165161412161331651612.

    At what ratio must the farmer, tailor, and carpenter produce in order for equilibrium to be attained?

  12. A certain economy consists of two sectors: goods and services. Suppose that 60% of all goods and 30% of all services are used in the production of goods. What proportion of the total economic output is used in the production of goods?

  13. In the notation of the open model of Leontief, suppose that

    A=(12151315)andd=(25)
    A=12131515andd=(25)

    are the input-output matrix and the demand vector, respectively. How much of each commodity must be produced to satisfy this demand?

  14. A certain economy consisting of the two sectors of goods and services supports a defense system that consumes $90 billion worth of goods and $20 billion worth of services from the economy but does not contribute to economic production. Suppose that 50 cents worth of goods and 20 cents worth of services are required to produce $1 worth of goods and that 30 cents worth of goods and 60 cents worth of services are required to produce $1 worth of services. What must the total output of the economic system be to support this defense system?

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.129.249.194