An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Hidden Figures in Computer Graphics

In video games, the speed at which a computer can render changing graphics views is vitally important. To increase a computer's ability to render a scene, programs often try to identify those parts of the images a viewer could see and those parts the viewer could not see. For example, in a scene involving buildings, the viewer could not see any images blocked by a solid building. In the mathematical world, this can be visualized by graphing surfaces. In Figure 23.1 we see a crude image of a house made up of small polygons (this is how programs generally represent surfaces). On the left in Figure 23.1 we see all of the polygons that are needed to construct the entire surface, even those polygons that lie behind others which we could not see if the surface was solid. On the right in Figure 23.1 we have hidden the parts of the polygons that we cannot see from our view.

We also see this idea in mathematics when we graph surfaces. Figure 23.2 shows the graph of the surface defined by \(f(x,y) = \sqrt{4-x^2}\) that is made up of polygons. At left we see all of the polygons and at right only those parts that would be visible from our viewing perspective.

By eliminating the parts of the polygons we cannot see from our viewing perspective, the computer program can more quickly render the viewing image. Later in this section we will explore one method for how programs remove the hidden portions of images. This process involves the dot product of vectors.

Subsection Introduction

Orthogonality, a concept which generalizes the idea of perpendicularity, is an important concept in linear algebra. We use the dot product to define orthogonality and more generally angles between vectors in \(\R^n\) for any dimension \(n\text{.}\) The dot product has many applications, e.g., finding components of forces acting in different directions in physics and engineering. The dot product is also an example of a larger concept, inner products, that we will discuss later. We introduce and investigate dot products in this section.

We will illustrate the dot product in \(\R^2\text{,}\) but the process we go through will translate to any dimension. Recall that we can represent the vector \(\vv = \left[ \begin{array}{c} v_1 \\ v_2 \end{array} \right]\) as the directed line segment (or arrow) from the origin to the point \((v_1, v_2)\) in \(\R^2\text{,}\) as illustrated in Figure 23.3. Using the Pythagorean Theorem we can then define the length (or magnitude or norm) of the vector \(\vv\) in \(\R^2\) as

We can also write this norm as

The expression under the square root is an important one and we extend it and give it a special name.

If \(\vu = [ u_1 \ u_2 ]^{\tr}\) and \(\vv = [ v_1 \ v_2]^{\tr}\) are vectors in \(\R^2\text{,}\) then we call the expression \(u_1v_1+u_2v_2\) the dot product of \(\vu\) and \(\vv\text{,}\) and denote it as \(\vu \cdot \vv\text{.}\) With this idea in mind, we can rewrite the norm of the vector \(\vv\) as

The definition of the dot product translates naturally to \(\R^n\) (see Exercise 5 in Section 5).

The dot product then allows us to define the norm (or magnitude or length) of any vector in \(\R^n\text{.}\)

We also use the words magnitude or length as alternatives for the word norm. We can equivalently write the norm of the vector \(\vv = [ v_1 \ v_2 \ \cdots \ v_n ]^{\tr}\) as

We can also realize the dot product as a matrix product. If \(\vu = [ u_1 \ u_2 \ \cdots \ u_n ]^{\tr}\) and \(\vv = [ v_1 \ v_2 \ \cdots \ v_n ]^{\tr}\text{,}\) then

³⁹.

Subsection The Distance Between Vectors

Finding optimal solutions to systems is an important problem in applied mathematics. It is often the case that we cannot find an exact solution that satisfies certain constraints, so we look instead for the “best” solution that satisfies the constraints. An example of this is fitting a least squares line to a set of data. As we will see, the dot product will allow us to find “best” solutions to certain types of problems, where we measure accuracy using the notion of a distance between vectors. Geometrically, we can represent a vector \(\vu\) as a directed line segment from the origin to the point defined by \(\vu\text{.}\) If we have two vectors \(\vu\) and \(\vv\text{,}\) we can think of the length of the difference \(\vu - \vv\) as a measure of how far apart the two vectors are from each other. It is natural, then to define the distance between vectors as follows.

As Figure 23.9 illustrates, if vectors \(\vu\) and \(\vv\) emanate from the same initial point, and \(P\) and \(Q\) are the terminal points of \(\vu\) and \(\vv\text{,}\) respectively, then the difference \(|| \vu - \vv||\) is the standard Euclidean distance between the points \(P\) and \(Q\text{.}\)

Subsection The Angle Between Two Vectors

Determining a “best” solution to a problem often involves finding a solution that minimizes a distance. We generally accomplish a minimization through orthogonality — which depends on the angle between vectors. Given two vectors \(\vu\) and \(\vv\) in \(\R^n\text{,}\) we position the vectors so that they emanate from the same initial point. If the vectors are nonzero, then they determine a plane in \(\R^n\text{.}\) In that plane there are two angles that these vectors create. We will define the angle between the vectors to be the smaller of these two angles. The dot product will tell us how to find the angle between vectors. Let \(\vu\) and \(\vv\) be vectors in \(\R^n\) and \(\theta\) the angle between them as illustrated in Figure 23.10.

Using the Law of Cosines, we have

Rearranging, we obtain

So the angle \(\theta\) between two nonzero vectors \(\vu\) and \(\vv\) in \(\R^n\) satisfies the equation

Of particular interest to us will be the situation where vectors \(\vu\) and \(\vv\) are orthogonal (perpendicular).⁴⁰ Intuitively, we think of two vectors as orthogonal if the angle between them is \(90^{\circ}\text{.}\)

Subsection Orthogonal Projections

When running a sprint, the racers may be aided or slowed by the wind. The wind assistance is a measure of the wind speed that is helping push the runners down the track. It is much easier to run a very fast race if the wind is blowing hard in the direction of the race. So that world records aren't dependent on the weather conditions, times are only recorded as record times if the wind aiding the runners is less than or equal to 2 meters per second. Wind speed for a race is recorded by a wind gauge that is set up close to the track. It is important to note, however, that weather is not always as cooperative as we might like. The wind does not always blow exactly in the direction of the track, so the gauge must account for the angle the wind makes with the track. If the wind is blowing in the direction of the vector \(\vu\) in Figure 23.12 and the track is in the direction of the vector \(\vv\) in Figure 23.12, then only part of the total wind vector is actually working to help the runners. This part is called the orthogonal projection of the vector \(\vu\) onto the vector \(\vv\) and is denoted \(\proj_{\vv} \vu\text{.}\) The next activity shows how to find this projection.

To summarize:

The orthogonal projection of a vector \(\vu\) onto a vector \(\vv\) is really a projection of the vector \(\vu\) onto the space \(\Span\{\vv\}\text{.}\) The vector \(\proj_{\vv} \vu\) is the best approximation to \(\vu\) of all the vectors in \(\Span\{\vv\}\) in the sense that \(\proj_{\vv} \vu\) is the closest to \(\vu\) among all vectors in \(\Span\{\vv\}\text{,}\) as we will prove later.

Subsection Orthogonal Complements

In Activity 23.2 we defined two vectors \(\vu\) and \(\vv\) in \(\R^n\) to be orthogonal (or perpendicular) if \(\vu \cdot \vv = 0\text{.}\) A use of orthogonality in geometry is to define a plane. A plane through the origin in \(\R^3\) is a two dimensional subspace of \(\R^3\text{,}\) and a plane is defined to be the set of all vectors in \(\R^3\) that are orthogonal to a given vector (called a normal vector). For example, to find the equation of the plane through the origin in \(\R^3\) orthogonal to the normal vector \(\vn = [1 \ 2 \ -1]^{\tr}\text{,}\) we seek all the vectors \(\vv = [x \ y \ z]^{\tr}\) such that

This gives us the equation

as the equation of this plane. The collection of all vectors that are orthogonal to a given subspace of vectors is called the orthogonal complement of that subspace in \(\R^n\text{.}\)

There is a more general idea here as defined in Preview Activity 23.6. If we have a set \(S\) of vectors in \(\R^n\text{,}\) we let \(S^{\perp}\) (read as “\(S\) perp”, called the orthogonal complement of \(S\)) be the set of all vectors in \(\R^n\) that are orthogonal to every vector in \(S\text{.}\) In our plane example, the set \(S\) is \(\{\vn\}\) and \(S^{\perp}\) is the plane with equation \(x+2y-z=0\text{.}\)

The activity proves the following theorem:

To show that a vector is in the orthogonal complement of a subspace, it is not necessary to demonstrate that the vector is orthogonal to every vector in the subspace. If we have a basis for the subspace, it suffices to show that the vector is orthogonal to every vector in that basis for the subspace, as the next theorem demonstrates.

We will work more closely with projections and orthogonal complements in later sections.

Subsection Examples

What follows are worked examples that use the concepts from this section.

Example 23.17.

Let \(\ell\) be the line defined by the equation \(ax+by+c=0\) with in \(\R^2\) and let \(P = (x_0,y_0)\) be a point in the plane. In this example we will learn how to find the distance from \(P\) to \(\ell\text{.}\)

(a)

Show that \(\vn = [a \ b]^{\tr}\) is orthogonal to the line \(\ell\text{.}\) That is, \(\vn\) is orthogonal to any vector on the line \(\ell\text{.}\)

Solution.

Any vector on the line \(\ell\) is a vector between two points on the line. Let \(Q = (x_1,y_1)\) and \(R = (x_2,y_2)\) be points on the line \(\ell\text{.}\) Then \(\vu = \overrightarrow{QR} = [x_2-x_1 \ y_2-y_1]^{\tr}\) is a vector on line \(\ell\text{.}\) Since \(Q\) and \(R\) are on the line, we know that \(ax_1+by_1+c=0\) and \(ax_2+by_2+c = 0\text{.}\) So \(-c = ax_1+by_1 = ax_2+by_2\) and

\begin{equation*} 0 = a(x_2-x_1) + b(y_2-y_1) = [a \ b]^{\tr} \vu\text{.} \end{equation*}

Thus, \(\vn = [a \ b]^{\tr}\) is orthogonal to every vector on the line \(\ell\text{.}\)

(b)

Let \(Q = (x_1, y_1)\) be any point on line \(\ell\text{.}\) Draw a representative picture of \(P\text{,}\) \(\vn\) with its initial point at \(P\text{,}\) along with \(Q\) and \(\ell\text{.}\) Explain how to use a projection to determine the distance from \(P\) to \(\ell\text{.}\)

Solution.

A picture of the situation is shown in Figure 23.18. If \(\vv = \overrightarrow{PQ}\text{,}\) then the distance from point \(P\) to line \(\ell\) is given by \(||\proj_{\vn} \vv||\text{.}\)

(c)

Use the idea from part (b) to show that the distance \(d\) from \(P\) to \(\ell\) satisfies

\begin{equation} d = \frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}\text{.}\tag{23.3} \end{equation}

Solution.

Recall that \(\vn = [a \ b]^{\tr}\) and \(\vv = \overrightarrow{PQ} = [x_1-x_0 \ y_1-y_0]^{\tr}\text{.}\) Since \(ax_1+by_1+c = 0\text{,}\) we have

\begin{align*} \proj_{\vn} \vv \amp = \frac{\vv \cdot \vv}{||\vn||^2} \vn\\ \amp = \frac{a(x_1-x_0)+ b(y_1-y_0)}{a^2+b^2} [a \ b]^{\tr}\\ \amp = \frac{ax_1+by_1-ax_0-by_0}{a^2+b^2} [a \ b]^{\tr}\\ \amp = \frac{-c-ax_0-by_0}{a^2+b^2} [a \ b]^{\tr}\text{.} \end{align*}

So

\begin{equation*} ||\proj_{\vn} \vv|| = \frac{|ax_0+by_0+c|}{a^2+b^2} \sqrt{a^2+b^2} = \frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}\text{.} \end{equation*}

(d)

Use Equation (23.3) to find the distance from the point \((3,4)\) to the line \(y = 2x+1\text{.}\)

Solution.

Here we have \(P = (3,4)\text{,}\) and the equation of our line is \(2x-y+1=0\text{.}\) So \(a=2\text{,}\) \(b=-1\text{,}\) and \(c=-1\text{.}\) Thus, the distance from \(P\) to the line is

\begin{equation*} \frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}} = \frac{|2(3)-(4)+1|}{\sqrt{4+1}} = \frac{3}{\sqrt{5}}\text{.} \end{equation*}

Subsection Summary

• The dot product of vectors \(\vu = [u_1 \ u_2 \ \cdots \ u_n ]^{\tr}\) and \(\vv = [ v_1 \ v_2 \ \cdots \ v_n ]^{\tr}\) in \(\R^n\) is the scalar

  \begin{equation*} \vu \cdot \vv = u_1v_1 + u_2v_2 + \cdots + u_nv_n = \displaystyle \sum_{i=1}^n u_iv_i\text{.} \end{equation*}

• The angle \(\theta\) between two nonzero vectors \(\vu\) and \(\vv\) in \(\R^n\) satisfies the equation

  \begin{equation*} \cos(\theta) = \frac{\vu \cdot \vv}{||\vu|| \ ||\vv||} \end{equation*}

  and \(0\leq \theta \leq 180\text{.}\)

• Two vectors \(\vu\) and \(\vv\) are orthogonal if \(\vu \cdot \vv = 0\text{.}\)

• The length, or norm, of the vector \(\vu\) can be found as \(\ds || \vu || = \sqrt{\vu \cdot \vu}\text{.}\)

• The distance between the vectors \(\vu\) and \(\vv\) in \(\R^n\) is \(||\vu - \vv ||\text{,}\) which is the length of the difference \(\vu - \vv\text{.}\)

• Let \(\vu\) and \(\vv\) be vectors in \(\R^n\text{.}\)

  • The orthogonal projection of \(\vu\) onto \(\vv\) is the vector

    \begin{equation*} \proj_{\vv} \vu = \frac{\vu \cdot \vv}{||\vv||^2} \vv\text{.} \end{equation*}

  • The projection of \(\vu\) perpendicular to \(\vv\) is the vector

    \begin{equation*} \proj_{\perp \vv} \vu = \vu - \proj_{\vv} \vu\text{.} \end{equation*}

• The orthogonal complement of the subspace \(W\) of \(\R^n\) is the set

  \begin{equation*} W^{\perp} = \{\vx \in \R^n : \vx \cdot \vw = 0 \text{ for all } \vw \in W\}\text{.} \end{equation*}

Subsection Project: Back-Face Culling

To identify hidden polygons in a surface, we will utilize a technique called back face culling. This involves identifying which polygons are back facing and which are front facing relative to the viewer's perspective. The first step is to assign a direction to each polygon in a surface.

Project Activity 23.9.

Consider the polygon \(ABCD\) in Figure 23.20. Since a polygon is flat, every vector in the polygon is perpendicular to a fixed vector (which we call a normal vector to the polygon). A normal vector \(\vn\) for the polygon \(ABCD\) in Figure 23.20 is shown. In this activity we learn how to find a normal vector to a polygon.

Let \(\vx = [x_1 \ x_2 \ x_3]^{\tr}\) and \(\vy = [y_1 \ y_2 \ y_3]^{\tr}\) be two vectors in \(\R^3\text{.}\) If \(\vx\) and \(\vy\) are linearly independent, then \(\vx\) and \(\vy\) determine a polygon as shown in Figure 23.20. Our goal is to find a vector \(\vn\) that is orthogonal to both \(\vx\) and \(\vy\text{.}\) Let \(\vw = [w_1 \ w_2 \ w_3]^{\tr}\) be another vector in \(\R^3\) and let \(C = \left[ \begin{array}{c} \vw^{\tr} \\ \vx^{\tr} \\ \vy^{\tr} \end{array} \right]\) be the matrix whose rows are \(\vw\text{,}\) \(\vx\text{,}\) and \(\vy\text{.}\) Let \(C_{ij}\) be the \(ij\)th cofactor of \(C\text{,}\) that is \(C_{ij}\) is \((-1)^{i+j}\) times the determinant of the submatrix of \(C\) obtained by deleting the \(i\)th row and \(j\)th column of \(C\text{.}\) Now define the vector \(\vx \times \vy\) as follows:

\begin{equation*} \vx \times \vy = C_{11}\ve_1 + C_{12}\ve_2 + C_{13} \ve_3\text{.} \end{equation*}

The vector \(\vx \times \vy\) is called the cross product of the vectors \(\vx\) and \(\vy\text{.}\) (Note that the cross product is only defined for vectors in \(\R^3\text{.}\)) We will show that \(\vx \times \vy\) is orthogonal to both \(\vx\) and \(\vy\text{,}\) making \(\vx \times \vy\) a normal vector to the polygon defined by \(\vx\) and \(\vy\text{.}\)

(a)

Show that

\begin{equation*} \vx \times \vy = \left[ \begin{array}{c} x_2y_3-x_3y_2 \\ x_3y_1-x_1y_3 \\ x_1y_2-x_2y_1 \end{array} \right]\text{.} \end{equation*}

(b)

Use a cofactor expansion of \(C\) along the first row and properties of the dot product to show that

\begin{equation*} \det(C) = \vw \cdot (\vx \times \vy)\text{.} \end{equation*}

(c)

Use the result of part (b) and properties of the determinant to calculate \(\vx \cdot (\vx \times \vy)\) and \(\vy \cdot (\vx \times \vy)\text{.}\) Explain why \(\vx \times \vy\) is orthogonal to both \(\vx\) and \(\vy\) and is therefore a normal vector to the polygon determined by \(\vx\) and \(\vy\text{.}\)

Project Activity 23.9 shows how we can find a normal vector to a parallelogram — take two vectors \(\vx\) and \(\vy\) between the vertices of the parallelogram and calculate their cross products. Such a normal vector can define a direction for the parallelogram. There is still a problem, however.

Project Activity 23.10 shows that the cross product is anticommutative, so we get different directions if we switch the order in which we calculate the cross product. To fix a direction, we establish the convention that we always label the vertices of our parallelogram in the counterclockwise direction as shown in Figure 23.20. This way we always use \(\vx\) as the vector from vertex \(A\) to vertex \(B\) rather than the reverse. With this convention established, we can now define the direction of a parallelogram as the direction of its normal vector.

Once we have a normal vector established for each polygon, we can now determine which polygons are back-face and which are front-face. Figure 23.21 at left provides the gist of the idea, where we represent the polygons with line segments to illustrate. If the viewer's eye is at point \(P\) and views the figures, the normal vectors of the visible polygons point in a direction toward the viewer (front-face) and the normal vectors of the polygons hidden from the viewer point away from the viewer (back-face). What remains is to determine an effective computational way to identify the front and back facing polygons.

for all polygons on the surface do
  calculate the normal vector n using the ______ product for the current polygon
  calculate the center C of the current polygon
  calculate the viewing vector ______
    if ______ then
      render the current polygon
  end if
end for

As a final comment, back-face culling generally reduces the number of polygons to be rendered by half. This algorithm is not perfect and does not always do what we want it to do (e.g., it may not remove all parts of a polygon that we don't see), so there are other algorithms to use in concert with back-face culling to correctly render objects.