# Linear Equations (1 Viewer)

### Users Who Are Viewing This Thread (Users: 0, Guests: 1)

#### Bob Ho

1. The problem statement, all variables and given/known data
The figure attached shows a network of one way streets. On a particular day the traffic flow was measured at each of the intersections a b c and d. The numbers in the figure represent the average number of vehicles per minute through the four intersections.

A) Set up and solve a system of linear equations to find x1,x2,x3, and x4
B) Street AD is temporarily closed due to an accident. What will be the average traffic flow on the other streets?

2. Relevant equations

3. The attempt at a solution

I reached the equations;
50=x1+x2
40=x2+x4
40=x3+x4
50=x1+x3

Which gave me x1=0, x2=50, x3=50,x4=-10

However... I think I did this incorrectly.

#### Attachments

• 8.4 KB Views: 148
Last edited:

#### The Electrician

Gold Member
What kind of class is this for? Linear algebra?

This is a somewhat tricky problem. It is similar to an electrical network problem.

Part A.
All you have to do is set it up so it looks like a matrix:

[ 1*x1 + 1*x2 + 0*x3 + 0*x4 ]......
[ 0*x1 + 1*x2 + 0*x3 + 1*x4 ]..=..
[ 0*x1 + 0*x2 + 1*x3 + 1*x4 ]......
[ 1*x1 + 0*x2 + 1*x3 + 0*x4 ]......

which becomes:

[ 1 1 0 0 ]......[x1]....
[ 0 1 0 1 ]..*..[x2].=.
[ 0 0 1 1 ]......[x3]....
[ 1 0 1 0 ]......[x4]....

Having done this, if you attempt to solve it with a calculator that can do matrix arithmetic, you may get an error because the 4x4 matrix is singular; it has rank 3.

But, the augmented matrix also has rank 3, so the system has an infinite number of solutions.

The solution you got satisfies the system, but there are other solutions. Do you know how to find them? Will any solution satisfy your instructor, or do you need to show how to find them all?

Part B.

The equations become:

50=x1+0*x2=x1
40=0*x2+x4=x4
40=x3+x4
50=x1+x3

Right away you can see that x1=50 and x4=40.

#### Bob Ho

I'm glad you got the same matrix as me for this problem.
This problem is for math108 (1st year Uni).

The question just says to set up and solve a system of linear equations to find the variables...
I'm assuming by that I don't have to mention there is an infinite number of solutions?

Thanks alot for your help

#### The Electrician

Gold Member
You know, in looking over your question again, I notice that the original statement of the problem says that the streets are one way. So your solution which has x4 = -10, while mathematically correct, has the cars going the wrong way on a one way street!

This probably won't be an acceptable solution!

Note that the solution to part B, x1 = 50, x2 = 0, x3 = 0, x4=40 is also a solution to part A.

But there is a solution to part A which has less traffic on all the roads. You might get extra credit if you point out that there are an infinite number of solutions to part A, although the smallest solution is non-integer. A real world solution has to be in integers because you can't have a fraction of a car on the road, can you?

#### tiny-tim

Homework Helper
… only solve what the question asks for …

A) Set up and solve a system of linear equations to find x1,x2,x3, and x4
B) Street AD is temporarily closed due to an accident. What will be the average traffic flow on the other streets?
Hi Bob! Read the question carefully …

A) only asks you to set up the equations.

It doesn't ask you to solve them, does it?

So when you've answered A) … go straight on to B)!

Let y1 y3 and y4 be the new figures when street AD is closed.

From A), what are y1 y3 and y4 in terms of x1 x2 x3 and x4 … ? #### The Electrician

Gold Member
A) Set up and SOLVE a system of linear equations....

Looks to me like it says solve them.

#### tiny-tim

Homework Helper
oops!

A) Set up and SOLVE a system of linear equations....

Looks to me like it says solve them.
Oh dear … I need glasses … In that case, my advice is the exact opposite … don't do what the question says … you can't solve A) completely, so go straight on to B)! Let y1 y3 and y4 etc …

Thanks, Electrician!

#### TheoMcCloskey

Bob Ho - I don't get the same system as you.

I get the following:

A) 30 + 20 - X1 - X2 = 0

B) X1 + X3 - 15 - 35 = 0

C) 25 + 15 - X3 - X4 = 0

D) X2 + X4 - 20 - 20 = 0

Which yieds

1 1 0 0 = 50
1 0 1 0 = 50
0 0 1 1 = 40
0 1 0 1 = 40

Which still results in an indeteriminate solution (?)

#### The Electrician

Gold Member
If you perform an elementary row operation--exchange rows 2 and 4--on your system, you will have his system.

#### TheoMcCloskey

Man! - I thought I gave that a good looked just for that - I don't know how I missed it. Maybe age <groan>

#### Bob Ho

You know, in looking over your question again, I notice that the original statement of the problem says that the streets are one way. So your solution which has x4 = -10, while mathematically correct, has the cars going the wrong way on a one way street!

This probably won't be an acceptable solution!

Note that the solution to part B, x1 = 50, x2 = 0, x3 = 0, x4=40 is also a solution to part A.

But there is a solution to part A which has less traffic on all the roads. You might get extra credit if you point out that there are an infinite number of solutions to part A, although the smallest solution is non-integer. A real world solution has to be in integers because you can't have a fraction of a car on the road, can you?
You are right, thanks alot! I will change my working for that question and definitely include there are infinite solutions.

Unfortunately, now i'm stuck on a further subquestion which relates to the same diagram.

Q.) What are the maximum and minimum possible traffic flows on each street?

I assumed you can make every entering car turn down the side streets, so I worked out a maximum cars for street AD=90, AB=90, CB=90, and CD=90 also. Feel free to prove me wrong, as I most likely am as the numbers represent average numbers of vehicles per minute.

I put the minimum as just 0.....

Last edited:

#### The Electrician

Gold Member
I'm surprised that you're getting questions like this in a first course. The answer requires more sophistication than I would expect.

Let the problem be formulated as a matrix problem:

[ 1 1 0 0 ]......[x1]....
[ 0 1 0 1 ]..*..[x2].=.
[ 0 0 1 1 ]......[x3]....
[ 1 0 1 0 ]......[x4]....

this can be written as:

A * x = B

The system has an infinite number of solutions which are 4 element vectors:

[ x1 x2 x3 x4 ]

Vectors have a Euclidean length which is the square root of the sum of the squares of the elements. One of the infinite solutions has a minimum Euclidean length; it is:

[ x1 x2 x3 x4 ] = [ 27.5 22.5 22.5 17.5 ]

You can test any proposed solution by premultiplying the alleged solution vector by the A matrix; if you get the B vector (column matrix), then you have a solution.

Consider the vector [ -.5 .5 .5 -.5 ]. If you premultiply this vector by the A matrix you will get [ 0 0 0 0 ]; this means that [ -.5 .5 .5 -.5 ] is in the null space of A. Any multiple of this null space vector can be added to a good solution vector to get another solution vector.

The infinite number of solutions can thus be expressed as:

[ x1 x2 x3 x4 ] = [ 27.5 22.5 22.5 17.5 ] + n * [ -.5 .5 .5 -.5 ]

where n can be any number. You can see why; any multiple of [ -.5 .5 .5 -.5 ] when premultiplied by A simply gives [ 0 0 0 0 ] which when added to the product of A times any good solution vector doesn't change anything.

Now, look carefully at:

[ x1 x2 x3 x4 ] = [ 27.5 22.5 22.5 17.5 ] + n * [ -.5 .5 .5 -.5 ]

I you add some multiple of [ -.5 .5 .5 -.5 ] to a good solution vector, you will be adding a negative quantity to x1 and x4, and a positive quantity to x2 and x3. Since the streets are one way, we can't let any of the x's become negative. If we let n = 35, and evaluate the expression above, we will get:

[ x1 x2 x3 x4 ] = [ 10 40 40 0 ]

which is a solution of the original system. We can't use a value of n larger than 35 because the traffic on x4 would become negative, and that isn't allowed on one way streets.

Now let n = -45 and evaluate the above expression. we get:

[ x1 x2 x3 x4 ] = [ 50 0 0 40 ]

also a valid solution of the original system. We can't let n be more negative than -45 because x2 and x3 would become negative which isn't allowed on the one way streets.

I'm assuming that when you are asked:

Q.) What are the maximum and minimum possible traffic flows on each street?

what is meant is "over all valid solutions, what are the min and max flows?"

No valid solution allows for flows of 90 on any one street, because to do so would require a negative value for the flow on some other street. Such a solution can happen mathematically, but would violate the one way restriction.

So, it appears that the minimums are:

x1 = 10, x2 = 0, x3 = 0, x4 =0

and the maximums are:

x1 = 50, x2 = 40, x3 = 40, x4 = 40

I hope you see why x1 can never be less than 10 in a valid solution. It's because that would require some other flow to be negative which is not allowed.

#### tiny-tim

Homework Helper
I'm surprised that you're getting questions like this in a first course. The answer requires more sophistication than I would expect.
No it doesn't!

It's really easy! Bob Ho, your original equations were correct:
I reached the equations;
50=x1+x2
40=x2+x4
40=x3+x4
50=x1+x3
Then just let y1 y3 and y4 be the new figures when street AD is closed.

From the four equations above, what are y1 y3 and y4 in terms of x1 x2 x3 and x4 … ? (Alternatively, just look at the diagram with AD rubbed out … )

#### The Electrician

Gold Member
tiny-tim, you seem to be referring to part B) in Bob Ho's original post, but he has added a third question. That is what I was responding to .

#### tiny-tim

Homework Helper
tiny-tim, you seem to be referring to part B) in Bob Ho's original post, but he has added a third question. That is what I was responding to .
Ah! … though bold would have helped …

Sorry … but it's still really easy.

From equations 2 and 4:
x2 = x3
and therefore:
x1 = x4 + 10.​
And also:
x1 + x2 = 50,
x4 + x2 = 40.​
And, of course
x1 x2 x3 and x4 are all ≥ 0.
These are the only constraints.

The first equation imposes no max or min.

The second equation imposes only x1 ≥ 10.

The third imposes x1 and x2 ≤ 50.

The fourth x4 and x2 ≤ 40.

So, combining them, and taking the lesser of the two maxima for x2:
10 ≤ x1 ≤ 50, 0 ≤x2 = x3 ≤ 40, 0 ≤x4 ≤ 40. #### The Electrician

Gold Member
Assuming that your numbering of the equations given by Bob Ho in his original post is:

Equation 1: 50=x1+x2
Equation 2: 40=x2+x4
Equation 3: 40=x3+x4
Equation 4: 50=x1+x3

How does it follow from equations 2 and 4 that x2 = x3?

It seems to me that the most you can say from those two equations is that x2=40-x4 and x3=50-x1, not that x2=x3.

And without x2=x3 you can't conclude that x1=x4+10, etc.

Last edited:

#### tiny-tim

Homework Helper
… to prove x2 = x3 …

Hi Electrician! Equation 2: 40=x2+x4
Equation 3: 40=x3+x4 subtracting: x2 - x3 = 0. #### The Electrician

Gold Member
Or you could use equations 1 and 4 to obtain the same result.

But if you'll look at your post again, you'll see that you said to use equations 2 and 4, from which it does NOT follow that x2=x3.

You then said:

"and therefore:
x1=x4+10"

as though it followed from x2=x3 without explaining that THEN is the time to use equations 2 and 4, substituting x2=x3 into one of them. Or you could have explained that the result x1=x4+10 can be obtained from equations 1 and 2 together, or 3 and 4 together.

But using only equations 2 and 4 (or 1 and 3) together gets you nothing.

You got the correct final answer, but the beginning stages of your exposition were not clear and complete.

In one of your earlier posts, you said:

"In that case, my advice is the exact opposite … don't do what the question says … you can't solve A) completely, so go straight on to B)!"

This isn't true. I gave the complete solution in my post (#12) about the third question, and my comment about the level of sophistication was mostly directed at part A). I wanted to show that if part A) were completely solved, the other questions could be answered using that result.

Part A) can be solved with Gaussian elimination, finding a free variable and then back substituting, with the free variable taking on any value thus giving all the infinite solutions. But the concept of adding a multiple of a vector in the null space causing no change in the solution is powerful and elegant, and worth demonstrating.

#### tiny-tim

Homework Helper
… plain and simple cooking …

… The answer requires more sophistication than I would expect. …
hmm … my main object was to help the OP by showing him a very unsophisticated method which would still impress the examiners. So which method would you recommend to Bob Ho …
your sophisticated method in post #12, with its matrix, Euclidean lengths, and Gaussian elimination,
or my unsophisticated one (with the lines renumbered, and adding "there are 41 solutions, one for each value of x2 = x3 from 0 to 40, for each of which, x1 = 50 - x2, x4 = 40 - x2") in post#15?

#### The Electrician

Gold Member
"...which method would you recommend to Bob Ho.."

I would recommend any correct exposition rather than an incorrect one. And, of course, a corrected version of post #15 would be acceptable.

However much the examiners might be impressed by any solution to question 3, they definitely wouldn't be impressed if the OP took your advice from post #7:

"my advice is the exact opposite … don't do what the question says … you can't solve A) completely, so go straight on to B)!"

I don't think your method is "very unsophisticated". If it were, you wouldn't have been saying in post #7 "you can't solve A)" and then taking until post #19 (making several careless errors along the way) to provide a solution to part A). Your "method" is, in fact, an elimination method, equivalent to gaussian elimination; it's just not organized in a systematic way.

When you say "...with the lines renumbered..." are you acknowledging that the initial part of your exposition in post #15 was incorrect? The examiners wouldn't have been very impressed if he had turned that in, would they?

I don't know exactly what the content of the OP's course is, but I suspect the examiners might be more impressed by a knowledge of methods that will work with any linear system rather than an ad hoc method that works with one particular system, or a few such.

Gaussian elimination is such a general method and probably one of the topics he's been studying, and a demonstrated knowledge of it is probably what the examiners are looking for.

### The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving