Part II · Algebra Chapter 11 of 60
Systems of equations and inequalities
When there are several conditions, one equation isn't enough. Let's open a small toy workshop: find prices from two invoices, work an ancient Chinese counting board, run into the limits of the storeroom and find out why the most profitable plan always sits in a corner.
Builds on: 10 · Quadratic equations
You will learn
- solve systems of two linear equations by substitution, elimination and Cramer's rule, and understand why there is exactly one solution, none or infinitely many
- draw inequalities and systems of them in the plane and find the largest value of a linear function on a polygon
- solve inequalities in one variable by the method of intervals
The last chapter ended with a problem from a stationery shop: three notebooks and two pens cost 190, and two notebooks and three pens cost 160. How much is a notebook? There's a trick here. Put both purchases together: five notebooks and five pens cost 350, so a notebook and a pen cost 70. Now compare the purchases: the first has one more notebook and one fewer pen, and it cost 30 more. So a notebook costs 30 more than a pen. A notebook is 50, a pen 20. Check: $150 + 40 = 190$ and $100 + 60 = 160$.
The trick worked because the numbers in the problem were symmetric. We need a method that doesn't depend on luck, and not only for equalities: in real life conditions more often sound like "no more than". No more than there is in the storeroom, no longer than the machine can run. To have something to try it on, let's open a workshop that makes wooden toys: little cars and little boats. In one chapter we'll buy materials, balance the accounts with an ancient Chinese recipe, run into the limits of the storeroom, draw up the most profitable plan and find out what batch size keeps the workshop in the black.
Two invoices
The workshop buys wooden bars and paint. The supplier forgot to put prices on the invoices and wrote only the totals: 4 bars and 3 cans of paint come to 1150, and 2 bars and 5 cans to 1100. Call the price of a bar $x$ and the price of a can $y$. Each invoice turns into an equation, and both must hold at the same time:
$$\begin{cases} 4x + 3y = 1150, \\ 2x + 5y = 1100. \end{cases}$$A system of equations is several equations that must hold at the same time; they are joined by a curly bracket. A solution of a system in the unknowns $x$ and $y$ is a pair of numbers $(x, y)$ that makes every equation true. To solve a system means to find all its solutions or prove there are none.
One invoice doesn't fix the prices: 1150 can be split between four bars and three cans in infinitely many ways. An answer appears only when the conditions work together.
Substitution
The first method is to express one unknown in terms of the other. From the second equation $2x = 1100 - 5y$, that is, $x = 550 - 2.5y$. Substitute this expression for $x$ in the first equation:
$$4(550 - 2.5y) + 3y = 1150, \qquad 2200 - 10y + 3y = 1150, \qquad 7y = 1050, \qquad y = 150.$$Then $x = 550 - 2.5 \cdot 150 = 175$. Substitution turned the system into one equation in one unknown, and we've been solving those since chapter 8. Substitution is especially handy when some unknown has the coefficient one: then it can be expressed without fractions.
Elimination
The second method is to add the equations so that one unknown disappears. Multiply the second equation by $2$: we get $4x + 10y = 2200$. Now $x$ has the coefficient $4$ in both equations, and if we subtract the first equation from the new one, $x$ is gone:
$$(4x + 10y) - (4x + 3y) = 2200 - 1150, \qquad 7y = 1050.$$Again $y = 150$, and from the second equation $2x = 1100 - 750 = 350$, $x = 175$. A bar costs 175 and a can of paint 150. Check against both invoices: $4 \cdot 175 + 3 \cdot 150 = 700 + 450 = 1150$ and $2 \cdot 175 + 5 \cdot 150 = 350 + 750 = 1100$.
Why are we allowed to add equations? If both invoices are right, any combination of them is right too: equals added to equals. But we need more than that: the new system mustn't gain extra solutions or lose the ones we want.
If one equation of a system is replaced by the sum of itself and another equation multiplied by any number $t$, the new system has the same solutions. Multiplying an equation by a non-zero number doesn't change the solutions either.
Write the system as $A = B$, $C = D$, where $A$, $B$, $C$, $D$ are expressions in $x$ and $y$, and replace the second equation with $C + tA = D + tB$. There are two directions to check.
Let a pair of numbers be a solution of the old system. Substitute it: we get true numerical equalities $A = B$ and $C = D$. Multiply the first by $t$ and add it to the second; we're adding equals to equals, so $C + tA = D + tB$ is true as well. The pair is a solution of the new system.
Let a pair be a solution of the new system. Then $A = B$ and $C + tA = D + tB$ are true. Multiply the first by $t$ and subtract it from the second: $C = D$. The pair is a solution of the old system. Since every solution of either system is a solution of the other, their solutions are the same.
Multiplication is similar: $C = D$ implies $sC = sD$, and when $s \ne 0$, $sC = sD$ implies $C = D$ back again: just divide by $s$. With $s = 0$ we'd get $0 = 0$, and the equation would drop out of the system together with the information it carried.
Solve the system $\begin{cases} 2x + y = 11, \\ x - y = 1. \end{cases}$ Give the answer as a pair $(x, y)$.
Add the equations: $y$ and $-y$ cancel, leaving $3x = 12$, $x = 4$. From the second equation $y = x - 1 = 3$. Check: $2 \cdot 4 + 3 = 11$ and $4 - 3 = 1$. Answer: $(4, 3)$.
Two lines
Each of these equations can be drawn. From $4x + 3y = 1150$ we get $y = \frac{1150 - 4x}{3}$, a linear function from the last chapter, and its graph is a line. All the pairs $(x, y)$ that fit the first invoice lie on one line, and those that fit the second on another. The solution of the system is their common point.
Two lines in the plane cross at one point, run parallel or coincide. It seems to be an observation about pictures, but behind it there's a theorem about numbers.
A system of two linear equations in two unknowns, each of which defines a line, has either exactly one solution, or none, or infinitely many. It can't have two, three or ten.
The trick is to watch not both lines at once but how much higher one is than the other.
Now let's derive the answer for all systems at once. Write the system in general form: $a_1x + b_1y = c_1$, $a_2x + b_2y = c_2$, where in each equation at least one coefficient of the unknowns is non-zero (otherwise the equation doesn't define a line), and repeat elimination with letters instead of numbers.
Let $\Delta = a_1b_2 - a_2b_1$. If $\Delta \ne 0$, the system has exactly one solution: $x = \frac{c_1b_2 - c_2b_1}{\Delta}$, $y = \frac{a_1c_2 - a_2c_1}{\Delta}$. If $\Delta = 0$, there are no solutions or infinitely many.
The idea is to eliminate the unknowns one at a time, as with the invoices. Multiply the first equation by $b_2$ and the second by $b_1$: we get $a_1b_2x + b_1b_2y = c_1b_2$ and $a_2b_1x + b_1b_2y = c_2b_1$. Now $y$ has the same coefficient in both; subtract the second from the first and $y$ disappears: $(a_1b_2 - a_2b_1)x = c_1b_2 - c_2b_1$, that is, $\Delta \cdot x = c_1b_2 - c_2b_1$. In the same way, multiplying the first equation by $a_2$ and the second by $a_1$ and subtracting the first from the second, we eliminate $x$: $\Delta \cdot y = a_1c_2 - a_2c_1$.
If there is a solution and $\Delta \ne 0$, divide by $\Delta$, and we get exactly the numbers in the formulas. So there can be no other solutions. It remains to check that these numbers really work. Substitute them into the first equation:
$$a_1 \cdot \frac{c_1b_2 - c_2b_1}{\Delta} + b_1 \cdot \frac{a_1c_2 - a_2c_1}{\Delta} = \frac{a_1b_2c_1 - a_1b_1c_2 + a_1b_1c_2 - a_2b_1c_1}{\Delta} = \frac{c_1(a_1b_2 - a_2b_1)}{\Delta} = c_1.$$The second works the same way: $\frac{a_2(c_1b_2 - c_2b_1) + b_2(a_1c_2 - a_2c_1)}{\Delta} = \frac{c_2(a_1b_2 - a_2b_1)}{\Delta} = c_2$. There is one solution, and we've found it.
If $\Delta = 0$, then $a_1b_2 = a_2b_1$. When $b_1$ and $b_2$ are non-zero, this means $-\frac{a_1}{b_1} = -\frac{a_2}{b_2}$: the lines have the same slope. When, say, $b_1 = 0$, the first line is vertical, $a_1 \ne 0$, and $a_1b_2 = 0$ gives $b_2 = 0$, so the second is vertical too. Either way the lines are parallel or coincide, and by the previous theorem there are no solutions or infinitely many.
The number $\Delta$ is called the determinant of the system. What it means geometrically, the factor by which a linear transformation of the plane changes areas, is explained in the chapter on matrices.
Nearly parallel lines
When $\Delta$ is close to zero, a system becomes temperamental. The system $x + y = 2$, $x + 1.01y = 2.01$ has the solution $(1, 1)$: subtract the first equation from the second, $0.01y = 0.01$. Change one right-hand side by a hundredth, $2.01 \to 2.02$, and the solution moves off to $(0, 2)$. The lines are nearly parallel, and a tiny shift of one of them pushes the crossing point far away. If the coefficients come from measurements with errors, the answer of such a system can't be trusted. Numerical analysts call such systems ill-conditioned and know how to handle them; that's in the chapter on Gaussian elimination.
How many solutions does the system $\begin{cases} 2x - 3y = 5, \\ -4x + 6y = -10 \end{cases}$ have?
The second equation is the first multiplied by $-2$. Both define the same line, and every point of it is a solution: $(1, -1)$, $(4, 1)$, $(-2, -3)$ and so on. Here $\Delta = 2 \cdot 6 - (-4)(-3) = 12 - 12 = 0$.
The counting board
Elimination is much older than letters. The eighth chapter of the Chinese treatise The Nine Chapters on the Mathematical Art, which took shape about two thousand years ago, works through problems like ours, only with three unknowns. The first of them goes like this (we retell it closely):
There are 3 sheaves of high-yield grain, 2 sheaves of medium-yield and 1 sheaf of low-yield; together they give 39 dou. There are 2 sheaves of high-yield, 3 of medium-yield and 1 of low-yield: 34 dou. There is 1 sheaf of high-yield, 2 of medium-yield and 3 of low-yield: 26 dou. How much grain is there in one sheaf of each kind?
A dou is an old measure of grain by volume. The calculator laid out the numbers with counting rods on a board: each condition is a separate column, the columns are read from right to left, the numbers of sheaves of the three kinds go from top to bottom, and the total is at the bottom. Then he worked with whole columns: multiplied a whole column by a number and subtracted one column from another, until the top numbers of the middle and left columns were gone, and then the second number of the left column too: only one kind is left there. The method was called fangcheng, "arrangement in a rectangle". In modern Chinese the word simply means "equation".
The answer: a sheaf of the high kind holds $9\frac14$ dou, of the medium kind $4\frac14$, of the low kind $2\frac34$. Check with the first condition: $3 \cdot 9\frac14 + 2 \cdot 4\frac14 + 2\frac34 = 27\frac34 + 8\frac12 + 2\frac34 = 39$.
In other problems of the same chapter the subtraction goes below zero, and right there, in chapter 8, rules are given for working with positive and negative numbers. How they were laid out is explained by the commentator Liu Hui (3rd century): red rods for the former, black for the latter. We already met them in the chapter on the minus sign. In Europe this method is called Gaussian elimination: Carl Friedrich Gauss solved systems this way in the early nineteenth century when computing orbits, and it gets a chapter of its own.
No more than in the storeroom
The materials are bought, and it's time to work. In a day the workshop can turn out $x$ cars and $y$ boats, but not any number it likes. The conditions are:
- each toy needs one wooden blank, and there are only $8$ blanks a day: $x + y \le 8$;
- the lathe runs for three hours; a car takes 30 minutes of it (the wheels!), a boat 10: $30x + 10y \le 180$;
- the painter also works three hours; he paints a car in 10 minutes and a boat with a sail in 30: $10x + 30y \le 180$;
- there can't be fewer than zero toys: $x \ge 0$, $y \ge 0$.
Start with a simple question: how many cars can we make if we make no boats at all? Put $y = 0$: the lathe gives $30x \le 180$, so $x \le 6$; the painter $10x \le 180$, $x \le 18$; the blanks $x \le 8$. All three conditions together mean $x \le 6$: the bottleneck is the lathe.
Such inequalities are solved almost like equations: you can add the same number to both sides, and multiply or divide both sides by the same positive number. There's one caveat, about negative factors.
If $a < b$ and $c > 0$, then $ac < bc$. If $a < b$ and $c < 0$, then $ac > bc$: multiplying by a negative number reverses the inequality sign.
The inequality $a < b$ means the difference $b - a$ is positive. Multiply it by $c$: $(b - a)c = bc - ac$. By the rule of signs (chapter 2), when $c > 0$ a positive number times $c$ is positive, that is, $bc - ac > 0$ and $ac < bc$. When $c < 0$ it's negative: $bc - ac < 0$, that is, $ac > bc$. Dividing by $c$ is multiplying by $\frac1c$, which has the same sign as $c$.
For example, $12 - 3x > 0$: move the $12$ across to get $-3x > -12$, divide by $-3$ and reverse the sign: $x < 4$. Check: at $x = 0$ we get $12 > 0$, true; at $x = 5$ we get $-3$, false.
With two unknowns an inequality describes not an interval on a line but a piece of the plane. Take the condition on blanks, $x + y \le 8$. The points where $x + y = 8$ lie on the line $y = 8 - x$. And the inequality means $y \le 8 - x$: above each $x$ the points that fit are those no higher than this line.
A line divides the plane into two half-planes, the two parts on either side of it. The line itself is called the boundary; if its points are counted too, the half-plane is called closed.
If $a$ and $b$ are not both zero, the solutions of the inequality $ax + by \le c$ form a closed half-plane with the boundary $ax + by = c$.
Take three cases by the sign of $b$. If $b > 0$, divide the inequality by $b$, keeping the sign: $y \le \frac{c - ax}{b}$. On the right is a linear function of $x$, and its graph is the boundary line. Above each $x$ the inequality holds exactly at the points no higher than the point of the line, so the solutions are the line and everything below it. If $b < 0$, dividing reverses the sign (by the previous theorem): $y \ge \frac{c - ax}{b}$, the line and everything above it. If $b = 0$, then $a \ne 0$ and the inequality $ax \le c$ says something only about $x$: $x \le \frac ca$ when $a > 0$, or $x \ge \frac ca$ when $a < 0$, the vertical line $x = \frac ca$ and everything to its left or right. In every case we get a half-plane together with its boundary.
The easiest way to find out which of the two is to use a test point. Substitute the origin into $30x + 10y \le 180$: $0 \le 180$ is true, so the half-plane we want is the one containing $(0, 0)$. If the test point failed, it would be the opposite one.
All the conditions together form a system of inequalities. Its solutions are the points that lie in all the half-planes at once. In planning problems the set of such points is called the feasible region. For the workshop it's a pentagon with vertices $(0, 0)$, $(6, 0)$, $(5, 3)$, $(3, 5)$ and $(0, 6)$.
The vertices are the points where two boundary lines meet, and they're found with systems from the earlier sections. For example, $(5, 3)$ lies both on the lathe's line and on the blanks' line: $30x + 10y = 180$ and $x + y = 8$. Divide the first equation by $10$ and subtract the second: $2x = 10$, $x = 5$, $y = 3$.
Which daily plan can the workshop carry out?
Check every condition for $(4, 4)$: blanks $4 + 4 = 8$, lathe $120 + 40 = 160$ minutes, painter $40 + 120 = 160$ minutes. Everything is within limits. Each of the other plans breaks at least one condition, and that's enough to rule it out.
The most profitable plan
A car brings the workshop a profit of 300, a boat 400. The profit from the plan $(x, y)$ is $P = 300x + 400y$. Which plan in the pentagon is the most profitable? We can't try every point: there are infinitely many, and even if we count only whole ones, we'd like to understand why the answer is what it is.
The problem of finding the largest or smallest value of a linear function subject to linear constraints, equalities and inequalities, is called a linear programming problem, and the function itself the objective function. "Programming" here means planning, not writing programs.
Let's draw all the plans with the same profit. For $P = 1200$ these are the points of the line $300x + 400y = 1200$: the plan $(4, 0)$, the plan $(0, 3)$ and everything between them. For $P = 2400$ it's the line $300x + 400y = 2400$, parallel to the first and farther from the origin. Such lines are called level lines. The larger the profit, the farther the line; we need to push it out as long as it still touches the pentagon.
The level line touches the vertex $(3, 5)$ last: three cars and five boats give $900 + 2000 = 2900$. For comparison, at the other vertices: $(6, 0)$ gives 1800, $(5, 3)$ gives 2700, $(0, 6)$ gives 2400. The optimum landing on a vertex is no accident.
If the feasible region is a polygon, then the largest and smallest values of a linear function $P = px + qy$ on it are attained at some of its vertices. So it's enough to compare the values at the vertices.
The trick is to walk from any point of the polygon to a vertex so that the profit never decreases along the way.
Sometimes the level line lies along a whole side of the polygon: then both vertices of that side and every point between them are equally profitable. Try making the car and the boat equally profitable in the widget, 400 each: $(5, 3)$ and $(3, 5)$ give the same 3200.
The profit on a car has gone up to 500, and on a boat it has dropped to 300. The constraints are the same. What is the largest daily profit the workshop can make?
Compare the vertices: $(0, 0)$ gives $0$, $(6, 0)$ gives $3000$, $(5, 3)$ gives $2500 + 900 = 3400$, $(3, 5)$ gives $1500 + 1500 = 3000$, $(0, 6)$ gives $1800$. The best plan is 5 cars and 3 boats, a profit of 3400. The optimum has moved to the neighbouring vertex: cars have become more valuable.
In real problems there are hundreds or thousands of unknowns, and the polygon becomes a polyhedron in a space of huge dimension. Such a polyhedron can have so many vertices that no computer could compare them all in time. In 1947 the American mathematician George Dantzig proposed the simplex method: start at some vertex and move along the edges to a neighbouring one as long as the profit grows. The same theorem for polyhedra guarantees that an optimum is among the vertices, and the walk along the edges finds it, usually after looking at only a small fraction of them. The "Simplex method" button in the widget always goes to the neighbouring vertex with the larger profit: from $(0, 0)$ to $(0, 6)$ with its 2400, from there to $(3, 5)$ with 2900, and there's nowhere further to go, because both neighbouring vertices, $(0, 6)$ and $(5, 3)$, are worse. The route through $(6, 0)$ and $(5, 3)$, with profits $1800$ and $2700$, would arrive at the same place, just one step later.
One of the first problems solved by the simplex method was the diet problem. In 1945 the economist George Stigler looked among 77 foods for the cheapest yearly diet that covers a person's needs for nine nutrients, and found by hand one costing 39.93 dollars at 1939 prices. In 1947 the simplex computation on desk calculators took, as Dantzig recalled, about 120 person-days and gave 39.69 dollars: Stigler was off by only 24 cents.
Signs on the line
The workshop's last question is about batch size. A shop is ready to take a batch of $x$ identical toys, but the larger the batch, the less it pays for each one: $12 - x$ hundred per toy. Setting up a batch costs 2000. The profit, in hundreds, is
$$P(x) = x(12 - x) - 20 = -x^2 + 12x - 20.$$For which $x$ does the workshop make money, that is, $P(x) > 0$? Multiply the inequality by $-1$, reversing the sign: $x^2 - 12x + 20 < 0$. By Vieta's formulas the roots of the quadratic are $2$ and $10$: their sum is $12$ and their product $20$. So $x^2 - 12x + 20 = (x - 2)(x - 10)$, and the question comes down to the sign of a product.
The factor $x - 2$ is negative to the left of two and positive to the right. The factor $x - 10$ changes sign at ten. On each of the three intervals into which the points $2$ and $10$ divide the line, the signs of the factors are constant, so the sign of the product is constant too: for $x < 2$ minus times minus gives plus, between $2$ and $10$ plus times minus gives minus, and for $x > 10$ it's plus. We need minus: $2 < x < 10$. A batch pays off if it has from 3 to 9 toys; the most profitable batch has 6, at the vertex of the parabola: $P(6) = 16$, that is, 1600.
Let an expression be a product or quotient of factors of the form $(x - r)$ raised to some powers, multiplied by a non-zero number. Then between neighbouring points where some factor becomes zero, the sign of the expression is constant. Passing through a point $r$, the expression changes sign if the factor $(x - r)$ appears to an odd power, and keeps its sign if to an even power.
The factor $x - r$ is positive for $x > r$ and negative for $x < r$; so inside an interval that contains none of the points $r$, the sign of each factor doesn't change. The sign of a product or quotient depends only on the signs of the factors: by the rule of signs it depends on whether the number of negative ones among them is even or odd. Since no factor changes sign inside the interval, neither does the whole expression. Passing through a point $r$, only the factor $x - r$ changes sign; if it's raised to the power $m$, then $(x - r)^m$ changes sign $m$ times in a row, that is, it ends up changing it for odd $m$ and keeping it for even $m$. The other factors don't change sign near $r$.
This is the basis of the method of intervals: to solve an inequality $f(x) > 0$ (or $\ge$, $<$, $\le$), factor $f$, mark the zeros of the factors on the line, find the sign on one interval and fill in the rest by the rule for sign changes. The zeros of a denominator are always excluded: the expression isn't defined there.
The solution of the inequality $x^2 > 4$ is
$x^2 - 4 = (x - 2)(x + 2) > 0$. The zeros of the factors are $-2$ and $2$; to the right of two both factors are positive and so is the product; between $-2$ and $2$ it's minus; to the left of $-2$ it's plus again. Answer: $x < -2$ or $x > 2$.
Solve the inequality $\frac{x - 5}{x + 1} > 0$. Write the answer as intervals.
The zeros of the factors are $5$ (numerator) and $-1$ (denominator; this point is excluded in any case). For $x > 5$ the numerator and denominator are both positive, so the fraction is positive. Between $-1$ and $5$ the numerator is negative and the denominator positive: minus. For $x < -1$ both are negative: plus. Answer: $(-\infty, -1) \cup (5, +\infty)$. Check: at $x = 6$ the fraction is $\frac17 > 0$, at $x = 0$ it's $-5 < 0$.
Practice
The trainer has three levels. At the first, systems are easy to solve by substitution: one of the unknowns has the coefficient one. At the second you'll have to add equations after multiplying them by suitable numbers, and sometimes there are no solutions or infinitely many. At the third there are word problems: tickets, coins, a boat on a river and shop prices; the system has to be set up first.
For problems of your own there are solvers: systems of linear equations step by step and inequalities by the method of intervals. All the trainers are collected on the practice page.
Where next
Almost all the dependencies in this chapter are linear. Each extra car adds the same 300 to the profit, each boat the same 30 minutes of the painter's time. There's another kind of growth, where a quantity isn't added to but multiplied. A legend tells of the inventor of chess, who asked the ruler for a reward in grain: one grain on the first square of the board, two on the second, four on the third, and so on, each square twice as many as the one before. The ruler laughed at such a modest request. How many grains will there be on the whole board? And the reverse question: how many times do you have to double one to get a million? Questions like these are the business of the chapter on powers and logarithms.