7 Solving systems of linear equations

This chapter covers

  • Detecting collisions of objects in a 2D video game
  • Writing equations to represent lines and finding where lines intersect in the plane
  • Picturing and solving systems of linear equations in 3D or beyond
  • Rewriting vectors as linear combinations of other vectors

When you think of algebra, you probably think of problems that require “solving for x.” For instance, you probably spent quite a bit of time in algebra class learning to solve equations like 3x2 + 2x + 4 = 0; that is, figuring out what value or values of x make the equation true.

Linear algebra, being a branch of algebra, has the same kinds of computational questions. The difference is that what you want to solve for may be a vector or matrix rather than a number. If you take a traditional linear algebra course, you might cover a lot of algorithms to solve these kinds of problems. But because you have Python at your disposal, you only need to know how to recognize the problem you’re facing and choose the right library to find the answer for you.

I’m going to cover the most important class of linear algebra problems you’ll see in the wild: systems of linear equations. These problems boil down to finding points where lines, planes, or their higher dimensional analogies intersect. One example is the infamous high school math problem involving two trains leaving Boston and New York at different times and speeds. But because I don’t assume railroad operation interests you, I’ll use a more entertaining example.

In this chapter, we build a simple remake of the classic Asteroids arcade game (figure 7.1). In this game, the player controls a triangle representing a spaceship and fires a laser at polygons floating around it, which represent asteroids. The player must destroy the asteroids to prevent them from hitting and destroying the spaceship.

Figure 7.1 Setup of the classic Asteroids arcade game

One of the key mechanics in this game is deciding whether the laser hits an asteroid. This requires us to figure out whether the line defining the laser beam intersects with the line segments outlining the asteroids. If these lines intersect, the asteroid is destroyed. We’ll set up the game first, and then we’ll see how to solve the underlying linear algebra problem.

After we implement our game, I’ll show you how this 2D example generalizes to 3D or any number of dimensions. The latter half of this chapter covers a bit more theory, but it will round out your linear algebra education. We’ll have covered many of the major concepts you’d find in a college-level linear algebra class, albeit in less depth. After completing this chapter, you should be well prepared to crack open a denser textbook on linear algebra and fill in the details. But for now, let’s focus on building our game.

7.1 Designing an arcade game

In this chapter, I focus on a simplified version of the asteroid game where the ship and asteroids are static. In the source code, you’ll see that I already made the asteroids move, and we’ll cover how to make them move according to the laws of physics in part

2 of this book. To get started, we model the entities of the game−the spaceship, the laser, and the asteroids−and show how to render them onscreen.

7.1.1 Modeling the game

In this section, we display the spaceship and the asteroids as polygons in the game. As before, we model these as collections of vectors. For instance, we can represent an eight-sided asteroid by eight vectors (indicated by arrows in figure 7.2), and we can connect them to draw its outline.

Figure 7.2 An eight-sided polygon representing an asteroid

The asteroid or spaceship translates or rotates as it travels through space, but its shape remains the same. Therefore, we store the vectors representing this shape separately from the x − and y-coordinates of its center, which can change over time. We also store an angle, indicating the rotation of the object at the current moment. The PolygonModel class represents a game entity (the ship or an asteroid) that keeps its shape but can translate or rotate. It’s initialized with a set of vector points that define the outline of the asteroid, and by default, its center x − and y-coordinates and its angle of rotation are set to zero:

class PolygonModel():
    def __init__(self,points):
        self.points = points
        self.rotation_angle = 0
        self.x = 0
        self.y = 0

When the spaceship or asteroid moves, we need to apply the translation by self .x,self.y and the rotation by self.rotation_angle to find out its actual location. As an exercise, you can give PolygonModel a method to compute the actual, transformed vectors outlining it.

The spaceship and asteroids are specific cases of PolygonModel that initialize automatically with their respective shapes. For instance, the ship has a fixed triangular shape, given by three points:

class Ship(PolygonModel):
    def __init__(self):
        super().__init__([(0.5,0), (−0.25,0.25), (−0.25,-0.25)])

For the asteroid, we initialize it with somewhere between 5 and 9 vectors at equally spaced angles and random lengths between 0.5 and 1.0. This randomness gives the asteroids some character:

class Asteroid(PolygonModel):
    def __init__(self):
        sides = randint(5,9)                                          
        vs = [vectors.to_cartesian((uniform(0.5,1.0), 2*pi*i/sides)) 
                for i in range(0,sides)]                              
        super().__init__(vs)

An asteroid has a random number of sides between 5 and 9.

Lengths are randomly selected between 0.5 and 1.0, and the angles are multiples of 2π/n, where n is the number of sides.

With these objects defined, we can turn our attention to instantiating them and rendering them onscreen.

7.1.2 Rendering the game

For the initial state of the game, we need a ship and several asteroids. The ship can begin at the center of the screen, but the asteroids should be randomly spread out over the screen. We can show an area of the plane ranging from −10 to 10 in the x and y directions like this:

ship = Ship()

asteroid_count = 10
asteroids = [Asteroid() for _ in range(0,asteroid_count)]   

for ast in asteroids:                                       
    ast.x = randint(−9,9)
    ast.y = randint(−9,9)

Creates a list of a specified number of Asteroid objects, in this case, 10

Sets the position of each object to a random point with coordinates between −10 and 10 so it shows up onscreen

I use a 400×400 pixel screen, which requires transforming the x − and y-coordinates before rendering them. Using PyGame’s built-in 2D graphics instead of OpenGL, the top left pixel on the screen has the coordinate (0, 0) and the bottom right has the coordinate (400, 400). These coordinates are not only bigger, they’re also translated and upside down, so we need to write a to_pixels function (illustrated in figure 7.3) that does the transformation from our coordinate system to PyGame’s pixels.

Figure 7.3 The to_pixels function maps an object from the center of our coordinate system to the center of the PyGame screen.

With the to_pixels function implemented, we can write a function to draw a polygon defined by points to the PyGame screen. First, we take the transformed points (translated and rotated) that define the polygon and convert them to pixels. Then we draw them with a PyGame function:

GREEN = (0, 255, 0)
def draw_poly(screen, polygon_model, color=GREEN):
    pixel_points = [to_pixels(x,y) for x,y in polygon_model.transformed()]
    pygame.draw.aalines(screen, color, True, pixel_points, 10)            

Draws lines connecting given points to a specified PyGame object. The True parameter connects the first and last points to create a closed polygon.

You can see the whole game loop in the source code, but it basically calls draw_poly for the ship and each asteroid every time a frame is rendered. The result is our simple triangular spaceship surrounded by an asteroid field in a PyGame window (figure 7.4).

Figure 7.4 The game rendered in a PyGame window

7.1.3 Shooting the laser

Now it’s time for the most important part: giving our ship a way to defend itself! The player should be able to aim the ship using the left and right arrow keys and then shoot a laser by pressing the spacebar. The laser beam should come out of the tip of the spaceship and extend to the edge of the screen.

In the 2D world we’ve invented, the laser beam should be a line segment starting at the transformed tip of the spaceship and extending in whatever direction the ship is pointed. We can make sure it reaches the end of the screen by making it sufficiently long. Because the laser’s line segment is associated with the state of the Ship object, we can make a method on the Ship class to compute it:

class Ship(PolygonModel):
    ...
   def laser_segment(self):
        dist = 20. * sqrt(2)                        
        x,y = self.transformed()[0]                 
        return ((x,y), 
            (x + dist * cos(self.rotation_angle), 
             y + dist*sin(self.rotation_angle)))    

Uses the Pythagorean theorem to find the longest segment that fits onscreen

Gets the value of the first of the definition points (the tip of the ship)

Uses trigonometry to find an endpoint for the laser if it extends dist units from the tip (x,y) at a self.rotation_angle (figure 7.5)

Figure 7.5 Using trigonometry to find the off-screen point where the laser beam ends

In the source code, you can see how to make PyGame respond to keystrokes and draw the laser as a line segment only if the spacebar is pressed. Finally, if the player fires the laser and hits an asteroid, we want to know something happened. In every iteration of the game loop, we want to check each asteroid to see if it is currently hit by the laser. We do this with a does_intersect(segment) method on the PolygonModel class, which computes whether the input segment intersects any segment of the given PolygonModel. The final code includes some lines like the following:

laser = ship.laser_segment()                  
keys = pygame.key.get_pressed()               
    if keys[pygame.K_SPACE]:
    draw_segment(*laser)

    for asteroid in asteroids:
        if asteroid.does_intersect(laser):    
            asteroids.remove(asteroid)

Calculates the line segment representing the laser beam based on the ship’s current position and orientation

Detects which keys are pressed. If the spacebar is pressed, renders the laser beam to the screen with a helper function draw_segment (similar to draw_poly).

For every asteroid, checks whether the laser line segment intersects it. If so, destroys the given asteroid by removing it from the list of asteroids.

The work that remains is implementing the does_intersect(segment) method. In the next section, we cover the math to do so.

7.1.4 Exercises

Exercise 7.1: Implement a transformed() method on the PolygonModel that returns the points of the model translated by the object’s x and y attributes and rotated by its rotation_angle attribute.

Solution: Make sure to apply the rotation first; otherwise, the translation vector is rotated by the angle as well; for example,

class PolygonModel():
    ...
    def transformed(self):
        rotated = [vectors.rotate2d(self.rotation_angle, v) for v  in self.points]
        return [vectors.add((self.x,self.y),v) for v  in rotated]

  

Exercise 7.2: Write a function to_pixels(x,y) that takes a pair of x − and y-coordinates in the square where −10 < x < 10 and −10 < y < 10 and maps them to the corresponding PyGame x and y pixel coordinates, each ranging from 0 to 400.

Solution:

width, height = 400, 400
def to_pixels(x,y):
    return (width/2 + width * x/ 20, height/2 − height * y / 20)

7.2 Finding intersection points of lines

The problem at hand is to decide whether the laser beam hits the asteroid. To do this, we’ll look at each line segment defining the asteroid and decide whether it intersects with the segment defining the laser beam. There are a few algorithms we could use, but we’ll solve this as a system of linear equations in two variables. Geometrically, this means looking at the lines defined by an edge of the asteroid and the laser beam and seeing where they intersect (figure 7.6).

Figure 7.6 The laser hitting an edge of an asteroid (left) and the corresponding system of linear equations (right)

Once we know the location of the intersection, we can see whether it lies within the bounds of both segments. If so, the segments collide and the asteroid is hit. We first review equations for lines in the plane, then cover how to find where pairs of lines intersect. Finally, we write the code for the does_intersect method for our game.

7.2.1 Choosing the right formula for a line

In the previous chapter, we saw that 1D subspaces of the 2D plane are lines. These subspaces consist of all of the scalar multiples t · v for a single chosen vector v. Because one such scalar multiple is 0 · v, these lines always pass through the origin, so t · v is not quite a general formula for any line we encounter.

If we start with a line through the origin and translate it by another vector u, we can get any possible line. The points on this line have the form u + t · v for some scalar t. For instance, take v = (2, −1). Points of the form t · (2, −1) lie on a line through the

origin. But if we translate by a second vector, u = (2, 3), the points are now (2, 3) + t · (2, −1), which constitute a line that doesn’t pass through the origin (figure 7.7).

Figure 7.7 Vectors z = (2, 3) and v = (2, −1). Points of the form z + t · v lie on a straight line.

Any line can be described as the points u + t · v for some selection of vectors u and v and all possible scalar multiples t. This is probably not the general formula for a line you’re used to. Instead of writing y as a function of x, we’ve given both the x − and y-coordinates of points on the line as functions of another parameter t. Sometimes, you’ll see the line written r(t) = u + t · v to indicate that this line is a vector valued function r of the scalar parameter t. The input t decides how many units of v you go from the starting point u to get the output r(t).

The advantage of this kind of formula for a line is that it’s dead simple to find if you have two points on the line. If your points are u and w, then you can use u as the translation vector, and w u as the vector that is scaled (figure 7.8).

Figure 7.8 Given z and w, the line that connects them is r(t) = z + t · (w − u).

The formula r(t) = u + t · v also has its downside. As you’ll see in the exercises, there are multiple ways to write the same line in this form. The extra parameter t also makes it harder to solve equations because there is one extra unknown variable. Let’s look at some alternative formulas with other advantages.

If you recall any formula for a line from high school, it is probably y = m · x + b. This formula is useful because it gives you a y-coordinate explicitly as a function of the x-coordinate. In this form, it’s easy to graph a line; you go through a bunch of x values, compute the corresponding y values, and put dots at the resulting (x, y) points. But this formula also has some limitations. Most importantly, you can’t represent a vertical line like r(t) = (3, 0) + t · (0, 1). This is the line consisting of vectors where x = 3.

We’ll continue to use the parametric formula r(t) = u + t · v because it avoids this problem, but it would be great to have a formula with no extra parameter t that can represent any line. The one we use is ax + by = c. As an example, the line we’re looking at in the last few images can be written as x + 2y = 8 (figure 7.9). It is the set of (x, y) points in the plane satisfying that equation.

Figure 7.9 All (x, y) points on the line satisfy x + 2y = 8.

The form ax + by = c has no extra parameters and can represent any line. Even a vertical line can be written in this form; for instance, x = 3 is the same as 1 · x + 0 · y = 3. Any equation representing a line is called a linear equation and this, in particular, is called the standard form for a linear equation. We prefer to use it in this chapter because it makes it easy to organize our computations.

7.2.2 Finding the standard form equation for a line

The formula x + 2y = 8 is the equation for a line containing one of the segments on the example asteroid. Next, we’ll look at another one (figure 7.10) and then try to systematize finding the standard form for linear equations. Brace yourself for a bit of algebra! I’ll explain each of the steps carefully, but it may be a bit dry to read. You’ll have a better time if you follow along on your own with a pencil and paper.

Figure 7.10 The points (1, 5) and (2, 3) define a second segment of the asteroid.

The vector (1, 5) − (2, 3) is (−1, 2), which is parallel to the line. Because (2, 3) lies on the line, a parametric equation for the line is r(t) = (2, 3) + t · (−1, 2). Knowing that all points on the line have the form (2, 3) + t · (−1, 2) for some t, how can we rewrite this condition to be a standard form equation? We need to do some algebra and, particularly, get rid of t. Because (x, y) = (2, 3) + t · (−1, 2), we really have two equations to start with:

x = 2 − t

y = 3 + 2t

We can manipulate both of them to get two new equations that have the same value (2t):

4 − 2x = 2t

y − 3 = 2t

Because both of the expressions on the left-hand sides equal 2t, they equal each other:

4 - 2x = y - 3

We’ve now gotten rid of t ! Finally, pulling the x and y terms to one side, we get the standard form equation:

2x + y = 7

This process isn’t too hard, but we need to be more precise about how to do it if we want to convert it to code. Let’s try to solve the general problem: given two points (x1, y1) and (x2, y2), what is the equation of the line that passes through them (see figure 7.11)?

Figure 7.11 The general problem of finding the equation of the line that passes through two known points

Using the parametric formula, the points on the line have the following form:

(x, y) = (x1, y1) + t · (x2 - x1, y2 - y1)

There are a lot of x and y variables here, but remember that x1, x2, y1, and y2 are all constants for the purpose of this discussion. We assume we have two points with known coordinates, and we could have called them (a, b) and (c, d) just as easily. The variables are x and y(with no subscripts), which stand for coordinates of any point on the line. As before, we can break this equation into two pieces:

x = x1 + t · (x2x1)

y = y1 + t · (y2y1)

We can move x1 and y1 to the left-hand side of their respective equations:

xx1 = t · (x2x1)

yy1 = t · (y2y1)

Our next goal is to make the right-hand side of both equations look the same, so we can set the left-hand sides equal to each other. Multiplying both sides of the first equation by (y2y1) and both sides of the second equation by (x2x1) gives us

(y2y1) · (xx1) = t · (x2x1) · (y2y1)

(x2x1) · (yy1) = t · (x2x1) · (y2y1)

Because the right-hand sides are identical, we know that the first and second equations’ left-hand sides equal each other too. That lets us create a new equation with no t in it:

(y2y1) · (xx1) = (x2x1) · (yy1)

Remember, we want an equation of the form ax + by = c, so we need to get x and y on the same side and the constants on the other side. The first thing we can do is expand both sides:

(y2y1) · x − (y2y1) · x = (x2x1) · y − (x2x1) · y1

Then we can move the constants to the left and the variables to the right:

(y2y1) · x − (x2x1) · y = (y2y1) · x1 − (x2x1) · y1

Expanding the right side, we see some of the terms cancel out:

(y2y1) · x − (x2x1) · y = y2x1y1x1 − x2y1 + x1y1 = x1y2x2y1

We’ve done it! This is the linear equation in standard form ax + by = c, where a = (y2y1), = −(x2x1), or in other words, (x1x2), and c = (x1 y2x2 y1). Let’s check this with the previous example we did, using the two points (x1, y1) = (2, 3) and (x2, y2) = (1, 5). In this case,

a = y2y1 = 5 − 3 = 2

b = −(x2x1) = −(1 − 2) = 1

and

c = x1y2x2y1 = 2 · 5 − 3 · 1 = 7

As expected, this means the standard form equation is 2x + y = 7. This formula seems trustworthy! As one final application, let’s find the standard form equation for the line defined by the laser. It looks like it passes through (2, 2) and (4, 4) as I drew it before (figure 7.12).

Figure 7.12 The laser passes through the points (2, 2) and (4, 4).

In our asteroid game, we have exact start and end points for the laser line segment, but these numbers are nice for an example. Plugging into the formula, we find

a = y2y1 = 4 − 2 = 2

b = −(x2x1) = −(4 − 2) = −2

and

c = x1y2x2y1 = 2 · 4 − 2 · 4 = 0

This means the line is 2y − 2x = 0, which is equivalent to saying xy = 0 (or simply x = y). To decide whether the laser hits the asteroid, we’ll have to find where the line xy = 0 intersects the line x + 2y = 8, the line 2x + y = 7, or any of the other lines bounding the asteroid.

7.2.3 Linear equations in matrix notation

Let’s focus on an intersection we can see: the laser clearly hits the closest edge of the asteroid, whose line has equation x + 2y = 8 (figure 7.13).

Figure 7.13 The laser hits the asteroid where the lines x − y = 0 and x + 2y = 8 intersect.

After quite a bit of build-up, we’ve met our first real system of linear equations. It’s customary to write systems of linear equations in a grid like the following, so that the variables x and y line up:

xy = 0

x + 2y = 8

Thinking back to chapter 5, we can organize these two equations into a single matrix equation. One way to do this is to write a linear combination of column vectors, where x and y are coefficients:

Another way is to consolidate this even further and write it as a matrix multiplication. The linear combination of (1,−1) and (−1,−2) with coefficients x and y is the same as a matrix product:

When we write it this way, the task of solving the system of linear equations looks like solving for a vector in a matrix multiplication problem. If we call the 2-by2 matrix a, the problem becomes what vector (x, y) is multiplied by the matrix a to yield (0, 8)? In other words, we know that an output of the linear transformation a is (0, 8) and we want to know what input yields it (figure 7.14).

Figure 7.14 Framing the problem as finding an input vector that yields the desired output vector

These different notations show new ways to look at the same problem. Solving a system of linear equations is equivalent to finding a linear combination of some vectors that produces another given vector. It’s also equivalent to finding an input vector to a linear transformation that produces a given output. Thus, we're about to see how to solve all of these problems at once.

7.2.4 Solving linear equations with NumPy

Finding the intersection of xy = 0 and x + 2y = 8 is the same as finding the vector (x, y) that satisfies the matrix multiplication equation:

This is only a notational difference, but framing the problem in this form allows us to use pre-built tools to solve it. Specifically, Python’s NumPy library has a linear algebra module and a function that solves this kind of equation. Here’s an example:

>>> import numpy as np
>>> matrix = np.array(((1,−1),(1,2)))       
>>> output = np.array((0,8))                

>>> np.linalg.solve(matrix,output)          
array([2.66666667, 2.66666667])             

Packages the matrix as a NumPy array object

Packages the output vector as a NumPy array (although it needn’t be reshaped to a column vector)

The numpy.linalg.solve function takes a matrix and an output vector and finds the input vector that produces it.

The result is (x, y) = (2.66..., 2.66...).

NumPy has told us that the x- and y-coordinates of the intersection are approximately 22/3or 8/3 each, which looks about right geometrically. Eyeballing the diagram, it looks like both coordinates of the intersection point should be between 2 and 3. We can check to see that this point lies on both lines by plugging it in to both equations:

1x − 1y = 1 ⋅ (2.66666667) − 1 (2.66666667) = 0

1x + 2y = 1 (2.66666667) + 2 (2.66666667) = 8.00000001

These results are close enough to (0, 8) and, indeed, make an exact solution. This solution vector, roughly (8/3, 8/3) is also the vector that satisfies the matrix equation 7.1.

As figure 7.15 shows, we can picture (8/3, 8/3) as the vector we pass into the linear transformation machine defined by the matrix that gives us the desired output vector.

Figure 7.15 The vector (8/3, 8/3) when passed to the linear transformation produces the desired output (0, 8).

We can think of the Python function numpy.linalg.solve as a differently shaped machine that takes in matrices and output vectors, and returns the “solution” vectors for the linear equation they represent (figure 7.16).

Figure 7.16 The numpy.linalg.solve function takes a matrix and a vector and outputs the solution vector to the linear system they represent.

This is perhaps the most important computational task in linear algebra; starting with a matrix a, and a vector w, and finding the vector v such that a v = w. Such a vector gives the solution to a system of linear equations represented by a and w. We’re lucky to have a Python function that can do this for us so we don’t have to worry about the tedious algebra required to do it by hand. We can now use this function to find out when our laser hits asteroids.

7.2.5 Deciding whether the laser hits an asteroid

The missing piece of our game was an implementation for the does_intersect method on the PolygonModel class. For any instance of this class, which represents a polygon-shaped object living in our 2D game world, this method should return True if an input line segment intersects any line segment of the polygon.

For this, we need a few helper functions. First, we need to convert the given line segments from pairs of endpoint vectors to linear equations in standard form. At the end of the section, I give you an exercise to implement the function standard_form, which takes two input vectors and returns a tuple (a, b, c) where ax + by = c is the line on which the segment lies.

Next, given two segments, each represented by its pair of endpoint vectors, we want to find out where their lines intersect. If u 1 and u 2 are endpoints of the first segment, and v 1 and v 2 are endpoints of the second, we need to first find the standard form equations and then pass them to NumPy to solve. For example,

def intersection(u1,u2,v1,v2):
    a1, b1, c1 = standard_form(u1,u2)
    a2, b2, c2 = standard_form(v1,v2)
    m = np.array(((a1,b1),(a2,b2)))
    c = np.array((c1,c2))
    return np.linalg.solve(m,c)

The output is the point where the two lines on which the segments lie intersect. But this point might not lie on either of the segments as shown in figure 7.17.

Figure 7.17 One segment connects u1 and u2 and the other connects points v1 and v2. The lines extending the segments intersect, but the segments themselves don’t.

To detect whether the two segments intersect, we need to check that the intersection point of their lines lies between the two pairs of endpoints. We can check that using distances. In figure 7.17, the intersection point is further from point v2 than point v1. Likewise, it’s further from u1 than u2. This indicates that the point is on neither segment. With four total distance checks, we can confirm whether the intersection point of the lines (x, y) is an intersection point of the segments as well:

def do_segments_intersect(s1,s2):
    u1,u2 = s1
    v1,v2 = s2
    d1, d2 = distance(*s1), distance(*s2)         
    x,y = intersection(u1,u2,v1,v2)               
    return (distance(u1, (x,y)) <= d1 and         
            distance(u2, (x,y)) <= d1 and
            distance(v1, (x,y)) <= d2 and
            distance(v2, (x,y)) <= d2)

Stores the lengths of the first and second segments as d1 and d2, respectively

Finds the intersection point (x, y) of the lines on which the segments lie

Does four checks to ensure the intersection point lies between the four endpoints of the line segments, confirming the segments intersect

Finally, we can write the does_intersect method by checking whether do _segments_intersect returns True for the input segment and any of the edges of the (transformed) polygon:

class PolygonModel():
    ...
    def does_intersect(self, other_segment):
        for segment in self.segments():
            if do_segments_intersect(other_segment,segment):
                return True                                  
        return False

If any of the segments of the polygon intersect other_segment, the method returns True.

In the exercises that follow, you can confirm that this actually works by building an asteroid with known coordinate points and a laser beam with a known start and end point. With does_intersect implemented as in the source code, you should be able to rotate the spaceship to aim at asteroids and destroy them.

7.2.6 Identifying unsolvable systems

Let me leave you with one final admonition: not every system of linear equations in 2D can be solved! It’s rare in an application like the asteroid game, but some pairs of linear equations in 2D don’t have unique solutions or even solutions at all. If we pass NumPy a system of linear equations with no solution, we get an exception, so we need to handle this case.

When a pair of lines in 2D are not parallel, they intersect somewhere. Even the two lines in figure 7.18 that are nearly parallel (but not quite) intersect somewhere off in the distance.

Figure 7.18 Two lines that are not quite parallel intersect somewhere in the distance.

Where we run into trouble is when the lines are parallel, meaning the lines never intersect (or they’re the same line!) as shown in figure 7.19.

Figure 7.19 A pair of parallel lines that never intersect and a pair of parallel lines that are, in fact, the same line despite having different equations

In the first case, there are zero intersection points, while in the second, there are infinitely many intersection points−every point on the line is an intersection point. Both of these cases are problematic computationally because our code demands a single, unique result. If we try to solve either of these systems with NumPy, for instance, the system consisting of 2x + y = 6 and 4x + 2y = 8, we get an exception:

>>> import numpy as np
>>> m = np.array(((2,1),(4,2)))
>>> v  = np.array((6,4))
>>> np.linalg.solve(m,v)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
...
numpy.linalg.linalg.LinAlgError: Singular matrix

NumPy points to the matrix as the source of the error. The matrix

is called a singular matrix, meaning there is no unique solution to the linear system. A system of linear equations is defined by a matrix and a vector, but the matrix on its own is enough to tell us whether the lines are parallel and whether the system has a unique solution. For any non-zero w we pick, there won’t be a unique v that solves the system.

We’ll philosophize more about singular matrices later, but for now you can see that the rows (2, 1) and (4, 2) and the columns (2, 4) and (1, 2) are both parallel and, therefore, linearly dependent. This is the key clue that tells us the lines are parallel and that the system does not have a unique solution. Solvability of linear systems is one of the central concepts in linear algebra; it closely relates to the notions of linear independence and dimension. We discuss that in the last two sections of this chapter.

For the purpose of our asteroid game, we can make the simplifying assumption that any parallel line segments don’t intersect. Given that we’re building the game with random floats, it’s highly unlikely that any two segments are exactly parallel. Even if the laser lined up exactly with the edge of an asteroid, this would be a glancing hit and the player doesn’t deserve to have the asteroid destroyed. We can modify do_segments_intersect to catch the exception and return the default result of False :

def do_segments_intersect(s1,s2):
    u1,u2 = s1
    v1,v2 = s2
    l1, l2 = distance(*s1), distance(*s2)
    try:
        x,y = intersection(u1,u2,v1,v2)
        return (distance(u1, (x,y)) <= l1 and
                distance(u2, (x,y)) <= l1 and
                distance(v1, (x,y)) <= l2 and
                distance(v2, (x,y)) <= l2)
    except np.linalg.linalg.LinAlgError:
        return False

7.2.7 Exercises

Exercise 7.3: It’s possible that u + t · v can be a line through the origin. In this case, what can you say about the vectors u and v ?

Solution: One possibility is that u = 0 = (0, 0); in which case, the line automatically passes through the origin. The point u + 0 · v is the origin in this case, regardless of what v is. Otherwise, if u and v are scalar multiples, say u = s · v, then the line passes through the origin as well because us · v = 0 is on the line.

  

Exercise 7.4: If v = 0 = (0, 0), do points of the form u + t · v represent a line?

Solution: No, regardless of the value of t, we have u + t · v = u + t · (0, 0) = u. Every point of this form is equal to u.

  

Exercise 7.5: It turns out that the formula u + t · v is not unique; that is, you can pick different values of u and v to represent the same line. What is another line representing (2, 2) + t · (−1, 3)?

Solution: One possibility is to replace v = (−1, 3) with a scalar multiple of itself such as (2, 6). The points of the form (2, 2) + t · (−1, 3) agree with the points (2, 2) + s · (2, 6) when t = −2 · s. You can also replace u with any point on the line. Because (2, 2) + 1 · (−1, 3) = (1, 5) is on the line, (1, 5) + t · (2, 6) is a valid equation for the same line as well.

  

Exercise 7.6: Does a · x + b · y = c represent a line for any values of a, b, and c ?

Solution: No, if both a and b are zero, the equation does not describe a line. In that case, the formula would be 0 · x + 0 · y = c. If c = 0, this would always be true, and if c ≠ 0, it would never be true. Either way, it establishes no relationship between x and y and, therefore, it would not describe a line.

  

Exercise 7.7: Find another equation for the line 2x + y = 3, showing that the choices of a, b, and c are not unique.

Solution: One example of another equation is 6x + 3y = 9. In fact, multiplying both sides of the equation by the same non-zero number gives you a different equation for the same line.

  

Exercise 7.8: The equation ax + by = c is equivalent to an equation involving a dot product of two 2D vectors: (a, b) · (x, y) = c. You could, therefore, say that a line is a set of vectors whose dot product with a given vector is constant. What is the geometric interpretation of this statement?

Solution: See the discussion in section 7.3.1.

  

Exercise 7.9: Confirm that the vectors (0, 7) and (3.5, 0) both satisfy the equation 2x + y = 7.

Solution: 2 · 0 + 7 = 7 and 2 · (3.5) + 0 = 7.

  

Exercise 7.10: Draw a graph for (3, 0) + t · (0, 1) and convert it to the standard form using the formula.

Solution: (3, 0) + t · (0, 1) yields a vertical line, where x = 3:

The formula x = 3 is already the equation of a line in standard form, but we can confirm this with the formulas. The first point on our line is already given: (x1, y1) = (3, 0). A second point on the line is (3, 0) + (0, 1) = (3, 1) = (x2, y2). We have a = y2y1 = 1, b = x1x2 = 0, and c = x1 y2x2y1 = 3 · 1 − 1 · 0 = 3. This gives us 1 · x + 0 · y = 3 or simply x = 3.

  

Exercise 7.11: Write a Python function standard_form that takes two vectors v 1 and v 2 and finds the line ax + by = c passing through both of them. Specifically, it should output the tuple of constants (a, b, c).

Solution: All you need to do is translate the formulas you wrote in Python:

def standard_form(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    a = y2 − y1
    b = x1 − x2
    c = x1 * y2 − y1 * x2
    return a,b,c

  

Exercise 7.12-Mini Project: For each of the four distance checks in do _segments_intersect, find a pair of line segments that fail one of the checks but pass the other three checks.

Solution: To make it easier to run experiments, we can create a modified version of do_segments_intersect that returns a list of the True/False values returned by each of the four checks:

def segment_checks(s1,s2):
    u1,u2 = s1
    v1,v2 = s2
    l1, l2 = distance(*s1), distance(*s2)
    x,y = intersection(u1,u2,v1,v2)
    return [
        distance(u1, (x,y)) <= l1,
        distance(u2, (x,y)) <= l1,
        distance(v1, (x,y)) <= l2,
        distance(v2, (x,y)) <= l2
    ]

In general, these checks fail when one endpoint of a segment is closer to the other endpoint than to the intersection point.

Here are some other solutions I found using segments on the lines y = 0 and x = 0, which intersect at the origin. Each of these fails exactly one of the four checks. If in doubt, draw them yourself to see what’s going on.

>>> segment_checks(((−3,0),(−1,0)),((0,−1),(0,1)))
[False, True, True, True]
>>> segment_checks(((1,0),(3,0)),((0,−1),(0,1)))
[True, False, True, True]
>>> segment_checks(((−1,0),(1,0)),((0,3),(0,−1)))
[True, True, False, True]
>>> segment_checks(((−1,0),(1,0)),((0,1),(0,3)))
[True, True, True, False]

  

Exercise 7.13: For the example laser line and asteroid, confirm the does_intersect function returns True. (Hint: use grid lines to find the vertices of the asteroid and build a PolygonModel object representing it.)

The laser hits the asteroid.

Solution: In counterclockwise order, starting with the topmost point, the vertices are (2, 7), (1, 5), (2, 3), (4, 2), (6, 2), (7, 4), (6, 6), and (4, 6). We can assume the endpoints of the laser beam are (1, 1) and (7, 7):

>>> from asteroids import PolygonModel
>>> asteroid = PolygonModel([(2,7), (1,5), (2,3), (4,2), (6,2), (7,4), (6,6), (4,6)])
>>> asteroid.does_intersect([(0,0),(7,7)])
True

This confirms the laser hits the asteroid! By contrast, a shot directly up the y-axis from (0, 0) to (0, 7) does not hit:

>>> asteroid.does_intersect([(0,0),(0,7)])
False

  

Exercise 7.14: Write a does_collide(other_polygon) method to decide whether the current PolygonModel object collides with another other_polygon by checking whether any of the segments that define the two are intersecting. This could help us decide whether an asteroid has hit the ship or another asteroid.

Solution: First, it’s convenient to add a segments() method to PolygonModel to avoid duplication of the work of returning the (transformed) line segments that constitute the polygon. Then, we can check every segment of the other polygon to see if it returns true for does_intersect with the current one:

class PolygonModel():
    ...
    def segments(self):
        point_count = len(self.points)
        points = self.transformed()
        return [(points[i], points[(i+1)%point_count])
                for i in range(0,point_count)]

    def does_collide(self, other_poly):
        for other_segment in other_poly.segments():
            if self.does_intersect(other_segment):
                return True
        return False

We can test this by building some squares that should and shouldn’t overlap, and seeing whether the does_collide method correctly detects which is which. Indeed, it does:

>>> square1 = PolygonModel([(0,0), (3,0), (3,3), (0,3)])
>>> square2 = PolygonModel([(1,1), (4,1), (4,4), (1,4)])
>>> square1.does_collide(square2)
True
>>> square3 = PolygonModel([(−3,3),(−2,3),(−2,−2),(−3,−2)])
>>> square1.does_collide(square3)
False

  

Exercise 7.15-Mini Project: We can’t pick a vector w so that the following system has a unique solution v.

Find a vector w such that there are infinitely many solutions to the system; that is, infinitely many values of v that satisfy the equation.

Solution: If w = (0, 0), for example, the two lines represented by the system are identical. (Graph them if you are skeptical!) The solutions have the form v = (a, −2a) for any real number a. Here are some of the infinite possibilities for v when w = (0, 0):

7.3 Generalizing linear equations to higher dimensions

Now that we’ve built a functional (albeit minimal) game, let’s broaden our perspective. We can represent a wide variety of problems as systems of linear equations, not just arcade games. Linear equations in the wild often have more than two “unknown” variables, x and y. Such equations describe collections of points in more than two dimensions. In more than three dimensions, it’s hard to picture much of anything, but the 3D case can be a useful mental model. Planes in 3D end up being the analogy of lines in 2D, and they are also represented by linear equations.

7.3.1 Representing planes in 3D

To see why lines and planes are analogous, it’s useful to think of lines in terms of dot products. As you saw in a previous exercise, or may have noticed yourself, the equation ax + by = c is the set of points (x, y) in the 2D plane where the dot product with a fixed vector (a, b) is equal to a fixed number c. That is, the equation ax + by = c is equivalent to the equation (a, b) · (x, y) = c. In case you didn’t figure out how to interpret this geometrically in the exercise, let’s go through it here.

If we have a point and a (non-zero) vector in 2D, there’s a unique line that is perpendicular to the vector and also passes through the point as shown in figure 7.20.

Figure 7.20 A unique line passing through a given point and perpendicular to a given vector

If we call the given point (x0, y0) and the given vector (a, b), we can write a criterion for a point (x, y) to lie on the line. Specifically, if (x, y) lies on the line, then (xx0, yy0) is parallel to the line and perpendicular to (a, b) as shown in figure 7.21.

Figure 7.21 The vector (xx0, yy0) is parallel to the line and, therefore, perpendicular to (a, b).

Because two perpendicular vectors have a zero dot product, that’s equivalent to the algebraic statement:

(a, b) · (xx0, yy0) = 0

That dot product expands to

a(xx0) + b(yy0) = 0

or

ax + by = ax0 + by0

The quantity on the right-hand side of this equation is a constant, so we can rename it c, giving us the general form equation for a line: ax + by = c. This is a handy geometric interpretation of the formula ax + by = c, and one that we can generalize to 3D.

Given a point and a vector in 3D, there is a unique plane perpendicular to the vector and passing through that point. If the vector is (a, b, c) and the point is (x0, y0, z0), we can conclude that if a vector (x, y, z) lies in the plane, then (xx0, y -y0, zz0) is perpendicular to (a, b, c). Figure 7.22 shows this logic.

Figure 7.22 A plane parallel to the vector (a, b, c) passes through the point (x0, y0, z0 ).

Every point on the plane gives us such a perpendicular vector to (a, b, c), and every vector perpendicular to (a, b, c) leads us to a point in the plane. We can express this perpendicularity as a dot product of the two vectors, so the equation satisfied by every point (x, y, z) in the plane is

(a, b, c) · (xx0, yy0, zz0) = 0

This expands to

ax + by + cz = ax0 + by0 + cz0

And because the right-hand side of the equation is a constant, we can conclude that every plane in 3D has an equation of the form ax + by + cz = d. In 3D, the computational problem is to decide where the planes intersect or which values of (x, y, z) simultaneously satisfy multiple linear equations like this.

7.3.2 Solving linear equations in 3D

A pair of non-parallel lines in the plane intersects at exactly one point. Is that single intersection point true for planes as well? If we draw a pair of intersecting planes, we can see that it’s possible for non-parallel planes to intersect at many points. In fact, figure 7.23 shows there is a whole line, consisting of an infinite number of points where two non-parallel planes intersect.

Figure 7.23 Two non-parallel planes intersect along a line.

If you add a third plane that is not parallel to this intersection line, you can find a unique intersection point. Figure 7.24 shows that each pair among the three planes intersects along a line and the lines share a single point.

Figure 7.24 Two non-parallel planes intersect along a line.

Finding this point algebraically requires finding a common solution to three linear equations in three variables, each representing one of the planes and having the form ax + by + cz = d. Such a system of three linear equations would have the form:

a1x + b1y + c1z = d1

a2x + b2y + c2z = d2

a3x + b3y + c3z = d3

Each plane is determined by four numbers: ai, bi, ci, and di, where i = 1, 2, or 3 and is the index of the plane we’re looking at. Subscripts like this are useful for systems of linear equations where there can be a lot of variables that need to be named. These twelve numbers in total are enough to find the point (x, y, z) where the planes intersect, if there is one. To solve the system, we can convert the system into a matrix equation:

Let’s try an example. Say our three planes are given by the following equations:

x + yz = −1

2yz = 3

x + z = 2

You can see how to plot these planes in Matplotlib in the source code for this book. Figure 7.25 shows the result.

Figure 7.25 Three planes plotted in Matplotlib

It’s not easy to see, but somewhere in there, the three planes intersect. To find that intersection point, we need the values of x, y, and z that simultaneously satisfy all three linear equations. Once again, we can convert the system to matrix form and use NumPy to solve it. The matrix equation equivalent to this linear system is

Converting the matrix and vector to NumPy arrays in Python, we can quickly find the solution vector:

>>> matrix = np.array(((1,1,−1),(0,2,−1),(1,0,1)))
>>> vector = np.array((−1,3,2))
>>> np.linalg.solve(matrix,vector)
array([−1., 3., 3.])

This tells us that (−1, 3, 3) is the (x, y, z) point where all three planes intersect and the point that simultaneously satisfies all three linear equations.

While this result was easy to compute with NumPy, you can see it’s already a bit harder to visualize systems of linear equations in 3D. Beyond 3D, it’s difficult (if not impossible) to visualize linear systems, but solving them is mechanically the same. The analogy to a line or a plane in any number of dimensions is called a hyperplane, and the problem boils down to finding the points where multiple hyperplanes intersect.

7.3.3 Studying hyperplanes algebraically

To be precise, a hyperplane in n dimensions is a solution to a linear equation in n unknown variables. A line is a 1D hyperplane living in 2D, and a plane is a 2D hyperplane living in 3D. As you might guess, a linear equation in standard form in 4D has the following form:

aw + bx + cy + dz = e

The set of solutions (w, x, y, z) form a region that is a 3D hyperplane living in 4D space. We need to be careful when we use the adjective 3D because it isn’t necessarily a 3D vector subspace of 4. This is analogous to the 2D case: the lines passing through the origin in 2D are vector subspaces of 2, but other lines are not. Vector space or not, the 3D hyperplane is 3D in the sense that there are three linearly independent directions you could travel in the solution set, like there are two linearly independent directions you can travel on any plane. I’ve included a mini-project at the end of this section to help you check your understanding of this.

When we write linear equations in even higher numbers of dimensions, we’re in danger of running out of letters to represent coordinates and coefficients. To solve this, we’ll use letters with subscript indices. For instance, in 4D, we could write a linear equation in standard form as:

a1 x1 + a2 x2 + a3 x3 + a4 x4 = b

Here, the coefficients are a1, a2, a3, and a4, and the 4D vector has the coordinates (x1, x2, x3, x4). We could just as easily write a linear equation in 10 dimensions:

a1 x1 + a2 x2 + a3 x3 + a4 x4 + a5 x5 + a6 x6 + a7 x7 + a8 x8 + a9 x9 + a10 x10 = b

When the pattern of terms we’re summing is clear, we sometimes use an ellipsis (...) to save space. You may see equations like the previous one written a1 x1 + a2 x2 + ... + a10 x10 = b. Another compact notation you’ll see involves the summation symbol Σ, which is the Greek letter sigma. If I want to write the sum of terms of the form aixi with the index i ranging from i = 1 to i = 10, and I want to state that the sum is equal to some other number b, I can use the mathematical shorthand:

This equation means the same thing as the earlier one; it is merely a more concise way of writing it. Whatever number of dimensions n we’re working in, the standard form of a linear equation has the same shape:

a1 x1 + a2 x2 + ... + anxn = b

To represent a system of m linear equations in n dimensions, we need even more indices. Our array of constants on the left-hand side of the equals sign can be denoted aij, where the subscript i indicates which equation we’re talking about and the subscript j indicates which coordinate (xj) the constant is multiplied by. For example,

a11 x1 + a12 x2 + ... + a1n xn = b1

a21 x1 + a22 x2 + ... + a2n xn = b2

...

am1 x1 + am2 x2 + ... + amn xn = bm

You can see that I also used the ellipsis to skip equations three through m −1 in the middle. There are m equations and n constants in each equation, so there are mn constants of the form aij in total. On the right-hand side, there are m constants in total, one per equation: b1, b2, ..., bm.

Regardless of the number of dimensions (the same as the number of unknown variables) and the number of equations, we can represent such a system as a linear equation. The previous system with n unknowns and m equations can be rewritten as shown in figure 7.26.

Figure 7.26 A system of m linear equations with n unknowns written in matrix form

7.3.4 Counting dimensions, equations, and solutions

We saw in both 2D and 3D that it’s possible to write linear equations that don’t have a solution, or at least not a unique one. How will we know if a system of m equations in n unknowns is solvable? In other words, how will we know if m hyperplanes in n -dimensions have a unique intersection point? We’ll discuss this in detail in the last section of this chapter, but there’s one important conclusion we can draw now.

In 2D, a pair of lines can intersect at a single point. They won’t always (for instance, if the lines are parallel), but they can. The algebraic equivalent to this statement is that a system of two linear equations in two variables can have a unique solution.

In 3D, three planes can intersect at a single point. Likewise, this is not always the case, but three is the minimum number of planes (or linear equations) required to specify a point in 3D. With only two planes, you have at least a 1D space of possible solutions, which is the line of intersection. Algebraically, this means you need two linear equations to get a unique solution in 2D and three linear equations to get a unique solution in 3D. In general, you need n linear equations to be able to get a unique solution in n -dimensions.

Here’s an example when working in 4D with the coordinates (x1, x2, x3, x4), which can seem overly simple but is useful because of how concrete it is. Let’s take our first linear equation to be x4 = 0. The solutions to this linear equation form a 3D hyperplane, consisting of vectors of the form (x1, x2, x3, 0). This is clearly a 3D space of solutions, and it turns out to be a vector subspace of 4 with basis (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0).

A second linear equation could be x2 = 0. The solutions of this equation on its own are also a 3D hyperplane. The intersection of these two 3D hyperplanes is a 2D space, consisting of vectors of the form (x1, 0, x3, 0), which satisfy both equations. If we could picture such a thing, we would see this as a 2D plane living in 4D space. Specifically, it is the plane spanned by (1, 0, 0, 0) and (0, 0, 1, 0).

Adding one more linear equation, x1 = 0, which defines its own hyperplane, the solutions to all three equations are now a 1D space. The vectors in this 1D space lie on a line in 4D, and have the form (0, 0, x3, 0). This line is exactly the x3 -axis, which is a 1D subspace of 4.

Finally, if we impose a fourth linear equation, x3 = 0, the only possible solution is (0, 0, 0, 0), a zero-dimensional vector space. The statements x4 = 0, x2 = 0, x1 = 0, and x3 = 0 are, in fact, linear equations, but these are so simple they describe the solution exactly: (x1, x2, x3, x4) = (0, 0, 0, 0). Each time we add an equation, we reduced the dimension of the solution space by one, until we got a zero-dimensional space consisting of the single point (0, 0, 0, 0).

Had we chosen different equations, each step would not have been as clear; we would have to test whether each successive hyperplane truly reduces the dimension of the solution space by one. For instance, if we started with

x1 = 0

and

x2 = 0

we would have reduced the solution set to a 2D space, but then adding another equation to the mix

x1 + x2 = 0

there is no effect on the solution space. Because x1 and x2 are already constrained to be zero, the equation x1 + x2 = 0 is automatically satisfied. This third equation, therefore, adds no more specificity to the solution set.

In the first case, four dimensions with three linear equations to satisfy left us with a 4 − 3 = 1 dimensional solution space. But in the second case, three equations described a less specific 2D solution space. If you have n dimensions (n unknown variables) and n linear equations, it’s possible there’s a unique solution−a zero-dimensional solution space−but this is not always the case. More generally, if you’re working in n dimensions, the lowest dimensional solution space you can get with m linear equations is n m. In that case, we call the system of linear equations independent.

Every basis vector in a space gives us a new independent direction we can move in the space. Independent directions in a space are sometimes called degrees of freedom ; the z direction, for instance, “freed” us from the plane into larger 3D space. By contrast, every independent linear equation we introduce is a constraint; it removes a degree of freedom and restricts the space of solutions to have a smaller number of dimensions. When the number of independent degrees of freedom (dimensions) equals the number of independent constraints (linear equations), there are no longer any degrees of freedom, and we are left with a unique point.

This is a major philosophical point in linear algebra, and one you can explore more in some mini-projects that follow. In the final section of this chapter, we’ll connect the concepts of independent equations and (linearly) independent vectors.

7.3.5 Exercises

Exercise 7.16: What’s the equation for a line that passes through (5, 4) and that is perpendicular to (−3, 3)?

Solution: Here’s the set up:

For every point (x, y) on the line, the vector (x − 5, y − 4) is parallel to the line and, therefore, perpendicular to (−3, 3). That means that the dot product (x − 5, y − 4) · (−3, 3) is zero for any (x, y) on the line. This equation expands to 3x + 15 + 3y − 12 = 0, which rearranges to give 3x + 3y = 3. We can divide both sides by 3 to get a simpler, equivalent equation: xy = 1.

  

Exercise 7.17-Mini Project: Consider a system of two linear equations in 4D:

x1 + 2x2 + 2x3 + x4 = 0

x1x4 = 0

Explain algebraically (rather than geometrically) why the solutions form a vector subspace of 4D.

Solution: We can show that if (a1, a2, a3, a4) and (b1, b2, b3, b4) are two solutions, then a linear combination of those is a solution as well. That would imply that the solution set contains all linear combinations of its vectors, making it a vector subspace.

Let’s start with the assumption that (a1, a2, a3, a4) and (b1, b2, b3, b4) are solutions to both linear equations, which explicitly means:

a1 + 2a2 + 2a3 + a4 = 0

b1 + 2b2 + 2b3 + b4 = 0

a1a4 = 0

b1b4 = 0

Picking scalars c and d, the linear combination c(a1, a2, a3, a4) + d(b1, b2, b3, b4) is equal to (ca1 + db1, ca2 + db2, ca3 + db3, ca4 + db4). Is this a solution to the two equations? We can find out by plugging the four coordinates in for x1, x2, x3, and x4. In the first equation,

x1 + 2x2 + 2x3 + x4

becomes

(ca1 + db1) + 2(ca2 + db2) + 2(ca3 + db3) + (ca4 + db4)

That expands to give us

ca1 + db1 + 2ca2 + 2db2 + 2ca3 + 2db3 + ca4 + db4

which rearranges to

c(a1 + 2a2 +2a3 + a4) + d(b1 + 2b2 + 2b3 + b4)

Because a1 + 2a2 + 2a3 + a4 and b1 + 2b2 + 2b3 + b4 are both zero, this expression is zero:

c(a1 + 2a2 + 2a3 + a4) + d(b1 + 2b2 + 2b3 + b4) = c · 0 + d · 0 = 0

That means the linear combination is a solution to the first equation. Similarly, plugging the linear combination into the second equation, we see it’s a solution to that equation as well:

(ca1 + db1) − (ca4 + db4) = c(a1a4) + d(b1b4) = c · 0 + d · 0 = 0

Any linear combination of any two solutions is also a solution, so the solution set contains all of its linear combinations. That means the solution set is a vector subspace of 4D.

  

Exercise 7.18: What is the standard form equation for a plane that passes through the point (1, 1, 1) and is perpendicular to the vector (1, 1, 1)?

Solution: For any point (x, y, z) in the plane, the vector (x − 1, y − 1, z − 1) is perpendicular to (1, 1, 1). That means that the dot product (x − 1, y − 1, z − 1) · (1, 1, 1) is zero for any x, y, and z values giving a point in the plane. This expands to give us (x − 1) + (y − 1) + (z − 1) = 0 or x + y + z = 3, the standard form equation for the plane.

  

Exercise 7.19−Mini Project: Write a Python function that takes three 3D points as inputs and returns the standard form equation of the plane that they lie in. For instance, if the standard form equation is ax + by + cz = d, the function could return the tuple (a, b, c, d).

Hint: Differences of any pairs of the three vectors are parallel to the plane, so cross products of the differences are perpendicular.

Solution: If the points given are p1, p2, and p3, then the vector differences like p3p1 and p2p1 are parallel to the plane. The cross product (p2 p1) × (p3 p1) is then perpendicular to the plane. (All is well as long as the points p1, p2, and p3 form a triangle, so the differences are not parallel.) With a point in the plane (for instance, p1) and a perpendicular vector, we can repeat the process of finding the standard form of the solution as in the previous two exercises:

from vectors import *

def plane_equation(p1,p2,p3):
    parallel1 = subtract(p2,p1)
    parallel2 = subtract(p3,p1)
    a,b,c = cross(parallel1, parallel2)
    d = dot((a,b,c), p1)
    return a,b,c,d

For example, these are three points from the plane x + y + z = 3 from the preceding exercise:

>>> plane_equation((1,1,1), (3,0,0), (0,3,0))
(3, 3, 3, 9)

The result is (3, 3, 3, 9), meaning 3x + 3y + 3z = 9, which is equivalent to x + y + z = 3. That means we got it right!

  

Exercise 7.20: How many total constants aij are in the following matrix equation? How many equations are there? How many unknowns? Write the full matrix equation (no dots) and the full system of linear equations (no dots).

An abbreviated system of linear equations in matrix form

Solution: To be clear, we can write out the full matrix equation first:

The unabbreviated version of the matrix equation

In total, there are 5 · 7 = 35 entries in this matrix and 35 aij constants on the left-hand side of the equations in the linear system. There are 7 unknown variables: x1, x2, ..., x7 and 5 equations (one per row of the matrix). You can get the full linear system by carrying out the matrix multiplication:

a11x1 + a12x2 + a13x3 + a14x4 + a15x5 + a16x6 + a17x7 = b1

a21x1 + a22x2 + a23x3 + a24x4 + a25x5 + a26x6 + a27x7 = b2

a31x1 + a32x2 + a33x3 + a34x4 + a35x5 + a36x6 + a37x7 = b3

a41x1 + a42x2 + a43x3 + a44x4 + a45x5 + a46x6 + a47x7 = b4

a51x1 + a52x2 + a53x3 + a54x4 + a55x5 + a56x6 + a57x7 = b5

The full system of linear equations represented by this matrix equation

You can see why we avoid this tedious writing with abbreviations!

  

Exercise 7.21: Write the following linear equation without summation shorthand. Geometrically, what does the set of solutions look like?

Solution: The left-hand side of this equation is a sum of terms of the form xi for i, ranging from 1 to 3. That gives us x1 + x2 + x3 = 1. This is the standard form of a linear equation in three variables, so its solutions form a plane in 3D space.

  

Exercise 7.22: Sketch three planes, none of which are parallel and do not have a single point of intersection. (Better yet, find their equations and graph them!)

Solution: Here are three planes: z + y = 0, zy = 0, and z = 3 and the graph:

Three non-parallel planes that don’t share an intersection point

I’ve drawn the intersections of the three pairs of planes, which are parallel lines. Because these lines never meet, there is no single point of intersection for all three planes. This is like the example you saw in chapter 6: three vectors can be linearly dependent even when no pair among them is parallel.

  

Exercise 7.23: Suppose we have m linear equations and n unknown variables. What do the following values of m and n say about whether there is a unique solution?

  1. m = 2, n = 2

  2. m = 2, n = 7

  3. m = 5, n = 5

  4. m = 3, n = 2

Solution:

  1. With two linear equations and two unknowns, there can be a unique solution. The two equations represent lines in the plane, and they will intersect at a unique point unless they are parallel.

  2. With two linear equations and seven unknowns, there cannot be a unique solution. Assuming the 6D hyperplanes defined by these equations are not parallel, there will be a 5D space of solutions.

  3. With five linear equations and five unknowns, there can be a unique solution, as long as the equations are independent.

  4. With three linear equations and two unknowns, there can be a unique solution, but it requires some luck. This would mean that the third line happens to pass through the intersection point of the first two lines, which is unlikely but possible.

Three lines in the plane that happen to intersect at a point

  

Exercise 7.24: Find 3 planes whose intersection is a single point, 3 planes whose intersection is a line, and 3 planes whose intersection is a plane.

Solution: The planes zy = 0, z + y = 0, and z + x = 0 intersect at the single point (0, 0, 0). Most randomly selected planes will intersect at a unique point like this.

Three planes intersecting at a single point

  

The planes zy = 0, z + y = 0, and z = 0 intersect on a line, specifically the x-axis. If you play with these equations, you’ll find both y and z are constrained to be zero, but x doesn’t even appear, so it has no constraints. Any vector (x, 0, 0) on the x-axis is, therefore, a solution.

Three planes whose intersection points form a line

Finally, if all three equations represent the same plane, then that whole plane is a set of solutions. For instance, zy = 0, 2z − 2y = 0, and 3z − 3y = 0 all represent the same plane.

Three identical planes overlaid; their set of solutions is the whole plane.

  

Exercise 7.25: Without using Python, what is the solution of the system of linear equations in 5D? x5 = 3, x2 = 1, x4 = −1, x1 = 0, and x1 + x2 + x3 = −2? Confirm the answer with NumPy.

Solution: Because four of these linear equations specify the value of a coordinate, we know the solution has the form (0,1, x3, −1,3). We need to do some algebra using the final equation to find out the value of x3. Because x1 + x2 + x3 = −2, we know 0 + 1 + x3 = −2, and x3 must be 3. The unique solution point is, therefore, (0, 1, 3, −1, 3). Converting this system to matrix form, we can solve it with NumPy to confirm we got it right:

>>> matrix = np.array(((0,0,0,0,1),(0,1,0,0,0),(0,0,0,1,0),(1,0,0,0,0),(1,1,1,0,0)))
>>> vector = np.array((3,1,−1,0,−2))
>>> np.linalg.solve(matrix,vector)
array([ 0., 1., 3., −1., 3.])

  

Exercise 7.26−Mini Project: In any number of dimensions, there is an identity matrix that acts as the identity map. That is, when you multiply the n -dimensional identity matrix I by any vector v, you get the same vector v as a result; therefore, I v = v .

This means that I v = w is an easy system of linear equations to solve: one possible answer for v is v = w. The idea of this mini-project is that you can start with a system of linear equations, a v = w, and multiply both sides by another matrix B such that (BA) = I. If that is the case, then you have (BA)v = B w and I v = B w or v = B w. In other words, if you have a system a v = w, and a suitable matrix B, then B w is the solution to your system. This matrix B is called the inverse matrix of a.

Let’s look again at the system of equations we solved in section 7.3.2:

Use the NumPy function numpy.linalg.inv(matrix), which returns the inverse of the matrix it is given to find the inverse of the matrix on the left-hand side of the equation. Then, multiply both sides by this matrix to find the solution to the linear system. Compare your results with the results we got from NumPy’s solver.

Hint: You might also want to use NumPy’s built-in matrix multiplication routine, numpy.matmul, to make computations simpler.

  

Solution: First, we can compute the inverse of the matrix using NumPy:

>>> matrix = np.array(((1,1,−1),(0,2,−1),(1,0,1)))
>>> vector = np.array((−1,3,2))
>>> inverse = np.linalg.inv(matrix)
>>> inverse
array([[ 0.66666667, -0.33333333,  0.33333333],
       [-0.33333333,  0.66666667,  0.33333333],
       [-0.66666667,  0.33333333,  0.66666667]])

The product of the inverse matrix with the original matrix gives us the identity matrix, having 1’s on the diagonal and 0’s elsewhere, albeit with some numerical error:

>>> np.matmul(inverse,matrix)
array([[ 1.00000000e+00,  1.11022302e−16, −1.11022302e−16],
       [ 0.00000000e+00,  1.00000000e+00,  0.00000000e+00],
       [ 0.00000000e+00,  0.00000000e+00,  1.00000000e+00]])

The trick is to multiply both sides of the matrix equation by this inverse matrix. Here I’ve rounded the values in the inverse matrix for the sake of readability. We already know that the first product on the left is a matrix and its inverse, so we can simplify accordingly:

Multiplying both sides of the system by the inverse matrix and simplifying

This gives us an explicit formula for the solution (x, y, z); all we need to do is to carry out the matrix multiplication. It turns out numpy.matmul also works for matrix vector multiplication:

>>> np.matmul(inverse, vector)
array([−1., 3., 3.])

This is the same as the solution we got earlier from the solver.

7.4 Changing basis by solving linear equations

The notion of linear independence of vectors is clearly related to the notion of independence of linear equations. The connection comes from the fact that solving a system of linear equations is the equivalent of rewriting vectors in a different basis. Let’s explore what this means in 2D. When we write coordinates for a vector like (4, 3), we are implicitly writing the vector as a linear combination of the standard basis vectors:

(4, 3) = 4e1 + 3e2

In the last chapter, you learned that the standard basis consisting of e1 = (1, 0) and e2 = (0, 1) is not the only basis available. For instance, a pair of vectors like u1 = (1, 1) and u2 = (−1, 1) form a basis for 2. As any 2D vector can be written as a linear combination of e1 and e2, so can any 2D vector be written as a linear combination of this u1 and u2. For some c and d, we can make the following equation true, but it’s not immediately obvious what the values of c and d are:

c · (1, 1) + d · (−1, 1) = (4, 2)

Figure 7.27 shows a visual representation of this.

Figure 7.27 Writing (4, 2) as a linear combination of u1 = (1, 1) and u2 = (−1, 1)

As a linear combination, this equation is equivalent to a matrix equation, namely:

This, too, is a system of linear equations! In this case, the unknown vector is written (c, d) rather than (x, y), and the linear equations hidden in the matrix equation are cd = 4 and c + d = 2. There is a 2D space of vectors (c, d) that define different linear combinations of u1 and u2, but only one simultaneously satisfies these two equations.

Any choice of the pair (c, d) defines a different linear combination. As an example, let’s look at an arbitrary value of (c, d), say (c, d) = (3, 1). The vector (3, 1) doesn’t live in the same vector space as u1 and u2 ; it lives in a vector space of (c, d) pairs, each of which describe a different linear combination of u1 and u2. The point (c, d) = (3, 1) describes a specific linear combination in our original 2D space: 3u1 + 1u2 gets us to the point (x, y) = (2, 4) (figure 7.28).

Figure 7.28 There is a 2D space of values (c, d), where (c, d) = (3, 1) and yields the linear combination 3u1 + 1u2 = (2, 4).

Recall that we’re trying to make (4, 2) as a linear combination of u1 and u2, so this isn’t the linear combination we were looking for. For c u1 + d u2 to equal (4, 2), we need to satisfy cd = 4 and c + d = 2, as we saw previously.

Let’s draw the system of linear equations in the c, d plane. Visually, we can tell that (3, −1) is a point that satisfies both c + d = 2 and cd = 4. This gives us the pair of scalars to use in a linear combination to make (4, 2) out of u1 and u2 as shown in figure 7.29.

Figure 7.29 The point (c, d) = (3, −1) satisfies both c + d = 2 and cd = 4. Therefore, it describes the linear combination we were looking for.

Now we can write (4, 2) as a linear combination of two different pairs of basis vectors: (4, 2) = 4e1 + 2e2 and (4, 2) = 3u1 − 1u2. Remember, the coordinates (4, 2) are exactly the scalars in the linear combination 4e1 + 2e2. If we had drawn our axes differently, u1 and u2 could just as well have been our standard basis; our vector would be 3u1u2 and we would say its coordinates were (3, 1). To emphasize that coordinates are determined by our choice of basis, we can say that the vector has coordinates (4, 2) with respect to the standard basis, but it has coordinates (3, −1) with respect to the basis consisting of u1 and u2.

Finding the coordinates of a vector with respect to a different basis is an example of a computational problem that is really a system of linear equations in disguise. It’s an important example because every system of linear equations can be thought of in this way. Let’s try another example, this time in 3D, to see what I mean.

7.4.1 Solving a 3D example

Let’s start by writing an example of a system of linear equations in 3D and then we’ll work on interpreting it. Instead of a 2-by2 matrix and a 2D vector, we can start with a 3-by3 matrix and a 3D vector:

The unknown here is a 3D vector; we need to find three numbers to identify it. Doing the matrix multiplication, we can break this up into three equations:

1 · x 1 · y + 0 · z = 1

0 · x 1 · y 1 · z = 3

 

1 · x + 0 · y + 2 · z = 7

This is a system of three linear equations with three unknowns, and ax + by + cz = d is the standard form for a linear equation in 3D. In the next section, we look at the geometric interpretation for 3D linear equations. (It turns out they represent planes in 3D as opposed to lines in 2D.)

For now, let’s look at this system as a linear combination with coefficients to be determined. The previous matrix equation is equivalent to the following:

Solving this equation is equivalent to asking the question: What linear combination of (1, 0, 1), (−1, −1, 0), and (0, −1, 2) yields the vector (1, 3, 7)? This is harder to picture than the 2D example, and it is harder to compute the answer by hand as well. Fortunately, we know NumPy can handle systems of linear equations in three unknowns, so we simply pass a 3-by3 matrix and 3D vector as inputs to the solver like this:

>>> import numpy as np
>>> xw = np.array((1,3,7))
>>> xa = np.array(((1,−1,0),(0,−1,−1),(1,0,2)))
>>> np.linalg.solve(a,w)
array([ 3., 2., 5.])

The values that solve our linear system are, therefore, x = 3, y = 2, and z = 5. In other words, these are the coefficients that build our desired linear combination. We can say that the vector (1, 3, 7) has coordinates (3, 2, 5) with respect to the basis (1, 0, 1), (−1, −1, 0), (0, −1, 2).

The story is the same in higher dimensions; as long as it is possible to do so, we can write a vector as a linear combination of other vectors by solving a corresponding system of linear equations. But, it’s not always possible to write a linear combination, and not every system of linear equations has a unique solution or even a solution at all. The question of whether a collection of vectors forms a basis is computationally equivalent to the question of whether a system of linear equations has a unique solution.

This profound connection is a good place to bookend part 1 with its focus on linear algebra. There will be plenty of more linear algebra nuggets throughout the book, but they are even more useful when we pair them with the core topic of part 2: calculus.

7.4.2 Exercises

Exercise 7.27: How can you write the vector (5, 5) as a linear combination of (10, 1) (3, 2)?

Solution: This is equivalent to asking what numbers a and b satisfy the equation

or what vector (a, b) satisfies the matrix equation:

We can find a solution with NumPy:

>>> matrix = np.array(((10,3),(1,2)))
>>> vector = np.array((5,5))
>>> np.linalg.solve(matrix,vector)
array([-0.29411765, 2.64705882])

This means the linear combination (which you can check!) is as follows:

  

Exercise 7.28: Write the vector (3, 0, 6, 9) as a linear combination of the vectors (0, 0, 1, 1), (0, −2, −1, −1), (1, −2, 0, 2), and (0, 0, −2, 1).

Solution: The linear system to solve is

where the columns of the 4-by4 matrix are the vectors we want to build the linear combination from. NumPy gives us the solution to this system:

>>> matrix = np.array(((0, 0, 1, 0), (0, −2, −2, 0), (1, −1, 0, −2), (1, −1, 2, 1)))
>>> vector = np.array((3,0,6,9))
>>> np.linalg.solve(matrix,vector)
array([ 1., 3., 3., −1.])

This means that the linear combination is

Summary

  • Model objects in a 2D video game can be done as polygonal shapes built out of line segments.

  • Given two vectors u and v, the points of the form u + tv for any real number t lie on a straight line. In fact, any line can be described with this formula.

  • Given real numbers a, b, and c, where at least one of a or b is non-zero, the points (x, y) in the plane satisfying ax + by = c lie on a straight line. This is called the standard form for the equation of a line, and any line can be written in this form for some choice of a, b, and c. Equations for lines are called linear equations.

  • Finding the point where two lines intersect in the plane is equivalent to finding the values (x, y) that simultaneously satisfy two linear equations. A collection of linear equations that we seek to solve simultaneously is called a system of linear equations.

  • Solving a system of two linear equations is equivalent to finding what vector can be multiplied by a known 2-by2 matrix to yield a known vector.

  • NumPy has a built-in function, numpy.linalg.solve, that takes a matrix and a vector and solves the corresponding system of linear equations automatically, if possible.

  • Some systems of linear equations cannot be solved. For instance, if two lines are parallel, they can have either no intersection points or infinitely many (which would mean they are the same line). This means there is no (x, y) value that simultaneously satisfies both lines’ equations. A matrix representing such a system is called singular.

  • Planes in 3D are the analogs of lines in 2D. They are the sets of points (x, y, z) satisfying equations of the form ax + by + cz = d.

  • Two non-parallel planes in 3D intersect at infinitely many points, and specifically, the set of points they share form a 1D line in 3D. Three planes can have a unique point of intersection that can be found by solving the system of three linear equations representing the planes.

  • Lines in 2D and planes in 3D are both cases of hyperplanes, sets of points in n -dimensions that are solutions to a single linear equation.

  • In n -dimensions, you need a system of at least n linear equations to find a unique solution. If you have exactly n linear equations and they have a unique solution, those are called independent equations.

  • Figuring out how to write a vector as a linear combination of a given set of vectors is computationally equivalent to solving a system of linear equations. If the set of vectors is a basis for the space, this is always possible.

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

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