An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Fractals

Sierpinski triangles and Koch's curves have become common phrases in many mathematics departments across the country. These objects are examples of what are called fractals, beautiful geometric constructions that exhibit self-similarity. Fractals are applied in a variety of ways: they help make smaller antennas (e.g., for cell phones) and are used in fiberoptic cables, among other things. In addition, fractals can be used to model realistic objects, such as the Black Spleenwort fern depicted as a fractal image in Figure 37.1. As we will see later in this section, one way to construct a fractal is with an Iterated Function System (IFS).

Subsection Introduction

We have encountered functions throughout our study of mathematics — we explore graphs of functions in algebra and differentiate and integrate functions in calculus. In linear algebra we have investigated special types of functions, e.g., matrix and coordinate transformations, that preserve the vector space structure. Any function that has the same properties as matrix and coordinate transformations is a linear transformation. Linear transformations are important in linear algebra in that we can study similarities and connections between vector spaces by examining transformations between them. Linear transformations model or approximately model certain real-life processes (like discrete dynamical systems, geometrical transformations, Google PageRank, etc.). Also, we can determine the behavior of an entire linear transformation by knowing how it acts on just a basis.

These transformations are called linear because they respect linear combinations. We can combine both parts of this definition into one statement and say that a mapping \(T\) from a vector space \(V\) to a vector space \(W\) is a linear transformation if

for all vectors \(\vu, \vv\) in \(V\) and all scalars \(a\) and \(b\text{.}\) We can extend this property of a linear transformation (by mathematical induction) to any finite linear combination of vectors. That is, if \(\vv_1\text{,}\) \(\vv_2\text{,}\) \(\ldots\text{,}\) \(\vv_k\) are any vectors in the domain of a linear transformation \(T\) and \(c_1\text{,}\) \(c_2\text{,}\) \(\ldots\text{,}\) \(c_k\) are any scalars, then

This is the property that \(T\) respects linear combinations.

Subsection Onto and One-to-One Transformations

Recall that in Section 7 we expressed existence and uniqueness questions for matrix equations in terms of one-to-one and onto properties of matrix transformations. The question about the existence of a solution to the matrix equation \(A \vx = \vb\) for any vector \(\vb\text{,}\) where \(A\) is an \(m \times n\) matrix, is also a question about the existence of a vector \(\vx\) so that \(T(\vx) = \vb\text{,}\) where \(T(\vx) = A \vx\text{.}\) If, for each \(\vb\) in \(\R^m\) there is at least one \(\vx\) with \(T(\vx) = \vb\text{,}\) then \(T\) is an onto transformation. We can make a similar definition for any linear transformation.

Similarly, the uniqueness of a solution to \(A \vx = \vb\) for any \(\vb\) in \(\Col A\) is the same as saying that for any \(\vb\) in \(\R^m\text{,}\) there is at most one \(\vx\) in \(\R^n\) such that \(T(\vx) = \vb\text{.}\) A matrix transformation with this property is one-to-one, and we can make a similar definition for any linear transformation.

With matrix transformations we saw that there are easy pivot criteria for determining whether a matrix transformation is one-to-one (a pivot in each column) or onto (a pivot in each row). If a linear transformation can be represented as a matrix transformation, then we can use these ideas. However, not every general linear transformation can be easily viewed as a matrix transformation, and in those cases we might have to resort to applying the definitions directly.

Subsection The Kernel and Range of Linear Transformation

As we saw in Preview Activity 37.1, any linear transformation sends the additive identity to the additive identity. If \(T\) is a matrix transformation defined by \(T(\vx) = A \vx\) for some \(m \times n\) matrix \(A\text{,}\) then we have seen that the set of vectors that \(T\) maps to the zero vector is \(\Nul A = \{\vx : A \vx = \vzero\}\text{,}\) which is also \(\Ker(T) = \{\vx : T(\vx) = \vzero\}\text{.}\) We can extend this idea of the kernel of a matrix transformation to any linear transformation \(T\text{.}\)

Just as the null space of an \(m \times n\) matrix \(A\) is a subspace of \(\R^n\text{,}\) the kernel of a linear transformation from a vector space \(V\) to a vector space \(W\) is a subspace of \(V\text{.}\) The proof is left to the exercises.

The kernel of a linear transformation provides a convenient way to determine if the linear transformation is one-to-one. If \(T\) is one-to-one, then the only solution to \(T(\vx) = \vzero_W\) is \(\vzero_V\) and \(\Ker(T)\) contains only the zero vector. If \(T\) is not one-to-one (and the domain of \(T\) is not just \(\{\vzero\}\)), then the number of solutions to \(T(\vx) = \vzero_W\) is infinite and \(\Ker(T)\) contains more than just the zero vector. We formalize this idea in the next theorem. (Compare to Theorem 13.3.) The formal proof is left for the exercises.

Recall that the matrix-vector product \(A \vx\) is a linear combination of the columns of \(A\) and the set of all vectors of the form \(A \vx\) is the column space of \(A\text{.}\) For the matrix transformation \(T\) defined by \(T(\vx) = A\vx\text{,}\) the set of all vectors of the form \(A \vx\) is also the range of the transformation \(T\text{.}\) We can extend this idea to arbitrary linear transformations to define the range of a transformation.

We also call the range of a transformation \(T\) the image of the transformation and use the notation \(\Image(T)\text{.}\)

If \(T(\vx) = A\vx\) for some \(m \times n\) matrix \(A\text{,}\) we know that \(\Col A\text{,}\) the span of the columns of \(A\text{,}\) is a subspace of \(\R^m\text{.}\) Consequently, the range of \(T\text{,}\) which is also the column space of \(A\text{,}\) is a subspace of \(\R^m\text{.}\) In general, the range of a linear transformation \(T\) from \(V\) to \(W\) is a subspace of \(W\text{.}\) The fact that the range of a transformation is a subspace of the codomain is a consequence of the more general result in the following theorem.

Letting \(U = V\) shows that \(\Range(T)\) is a subspace of \(W\text{.}\)

The subspace \(\Range(T)\) provides us with a convenient criterion for the transformation \(T\) being onto. The transformation \(T\) is onto if for each \(\vb\) in \(W\text{,}\) there is at least one \(\vx\) for which \(T(\vx)=\vb\text{.}\) This means that every \(\vb\) in \(W\) belongs to \(\Range(T)\) for \(T\) to be onto.

Subsection Isomorphisms

If \(V\) is a vector space with a basis \(\CB = \{\vv_1, \vv_2, \ldots, \vv_n\}\text{,}\) we have seen that the coordinate transformation \(T : V \to \R^n\) defined by \(T(\vx) = [\vx]_{\CB}\) is a linear transformation that is both one-to-one and onto. This allows us to uniquely identify any vector in \(V\) with a vector in \(\R^n\) so that the vector space structure is preserved. In other words, the vector space \(V\) is for all intents and purposes the same as the vector space \(\R^n\text{,}\) except for the way we represent the vectors. This is a very powerful idea in that it shows that any vector space of dimension \(n\) is essentially the same as \(\R^n\text{.}\) When this happens we say that the vectors spaces are isomorphic and call the coordinate transformation an isomorphism.

We this terminology, we summarize the discussion in the following theorem.

It is left for the exercises to show that if \(T: V \to W\) is an isomorphism, then \(T^{-1}: W \to V\) is also an isomorphism. So if there is an isomorphism from a vector space \(V\) to a vector space \(W\text{,}\) then there is an isomorphism from \(W\) to \(V\text{.}\) As a result, we say that \(V\) and \(W\) are isomorphic vector spaces. It is also true that any vector space is isomorphic to itself, and that if \(V\) is isomorphic to \(W\) and \(W\) is isomorphic to \(U\text{,}\) then \(V\) and \(U\) are also isomorphic. The proof of this result is left to the exercises. From this last property we can conclude that any two vector spaces of dimension \(n\) are isomorphic vector spaces. This validates statement we made earlier that the vector space \(\pol_n\) is for all intents and purposes the same as \(\R^{n+1}\text{,}\) since the two spaces are isomorphic. So to understand all finite dimensional vector spaces, it is enough to understand \(\R^n\text{.}\) The next activity provides a little practice with isomorphisms.

Subsection Examples

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

Subsection Summary

Let \(T\) be a linear transformation from a vector space \(V\) to a vector space \(W\text{.}\)

• A function \(T\) from a vector space \(V\) to a vector space \(W\) is a linear transformation if

  1. \(T(\vu + \vv) = T(\vu) + T(\vv)\) for all \(\vu\) and \(\vv\) in \(V\) and

  2. \(T(c\vu) = cT(\vu)\) for all \(\vu\) in \(V\) and all scalars \(c\text{.}\)

• Let \(T\) be a linear transformation from a vector space \(V\) to a vector space \(W\text{.}\) The kernel of \(T\) is the set

  \begin{equation*} \Ker(T) = \{\vx \in V : T(\vx) = \vzero\}\text{.} \end{equation*}

  The kernel of \(T\) is a subspace of \(V\text{.}\)

• Let \(T\) be a linear transformation from a vector space \(V\) to a vector space \(W\text{.}\) The transformation \(T\) is one-to-one if every vector in \(W\) is the image under \(T\) of at most one vector in \(V\text{.}\) A linear transformation \(T\) is one-to-one if and only if \(\Ker(T) = \{\vzero\}\text{.}\)

• Let \(T\) be a linear transformation from a vector space \(V\) to a vector space \(W\text{.}\) The range of \(T\) is the set

  \begin{equation*} \Range(T) = \{T(\vv) : \vv \in V\}\text{.} \end{equation*}

  The range of \(T\) is a subspace of \(W\text{.}\)

• Let \(T\) be a linear transformation from a vector space \(V\) to a vector space \(W\text{.}\) The linear transformation \(T\) is onto if every vector in \(W\) is the image under \(T\) of at least one vector in \(V\text{.}\) The transformation \(T\) is onto if and only if \(\Range(T) = W\text{.}\)

• An isomorphism from a vector space \(V\) to a vector space \(W\) is a linear transformation \(T : V \to W\) that is one-to-one and onto.

Subsection Project: Fractals via Iterated Function Systems

In this project we will see how to use linear transformations to create iterated functions systems to generate fractals. We illustrate the idea with the Sierpinski triangle, an approximate picture of which is shown at left in Figure 37.15.

To make this figure, we need to identify linear transformations that can be put together to produce the Sierpinski triangle.

Project Activity 37.6 contains the information we need to create an iterated function system to produce the Sierpinski triangle. One more step should help us understand the general process.

Project Activity 37.7.

Using the results of Project Activity 37.6, define \(P_{1,i}\) to be \(C_i(P_0)\) for each \(i\text{.}\) That is, \(P_{1,1} = C_1(P_0)\text{,}\) \(P_{1,2} = C_2(P_0)\text{,}\) and \(P_{1,3} = C_3(P_0)\text{.}\) So \(P_{1,i}\) is a triangle half the size of the original translated to the \(i\)th vertex of the original. Let \(P_1 = \bigcup_{i=1}^3 P_{1,i}\text{.}\) That is, \(P_1\) is the union of the shaded triangles in Figure 37.16.

(a)

Apply \(C_1\) from Project Activity 37.6 to \(P_1\text{.}\) What is the resulting figure? Draw a picture to illustrate.

(b)

Apply \(C_2\) from Project Activity 37.6 to \(P_1\text{.}\) What is the resulting figure? Draw a picture to illustrate.

(c)

Apply \(C_3\) from Project Activity 37.6 to \(P_1\text{.}\) What is the resulting figure? Draw a picture to illustrate.

The procedures from Project Activity 37.6 and Project Activity 37.7 can be continued, replacing \(P_0\) with \(P_1\text{,}\) then \(P_2\text{,}\) and so on. In other words, for \(i\) = 1, 2, and 3, let \(P_{2,i} = C_i(P_1)\text{.}\) Then let \(P_2 = \bigcup_{i=1}^3 P_{2,i}\text{.}\) A picture of \(P_2\) is shown at left in Figure 37.17. We can continue this procedure, each time replacing \(P_{j-1}\) with \(P_j\text{.}\) A picture of \(P_9\) is shown at right in Figure 37.17.

If we continue this process, taking the limit as \(i\) approaches infinity, the resulting sequence of sets converges to a fixed set, in this case the famous Sierpinski triangle. So the picture of \(P_9\) in Figure 37.17 is a close approximation of the Sierpinski triangle. This algorithm for building the Sierpinski triangle is called the deterministic algorithm. A Sage cell to illustrate this algorithm for producing approximations to the Sierpinski triangle can be found at faculty.gvsu.edu/schlicks/STriangle_Sage.html.

In general, an iterated function system (IFS) is a finite set \(\{f_1, f_2, \ldots, f_m\}\) of contraction mappings from \(\R^2\) to \(\R^2\text{.}\) If we start with a set \(S_0\text{,}\) and let \(S_1 = \bigcup f_i(S_0)\text{,}\) \(S_2 = \bigcup f_i(S_1)\text{,}\) and so on, then in “nice” cases (we won't concern ourselves with what “nice” means here), the sequence \(S_0\text{,}\) \(S_1\text{,}\) \(S_2\text{,}\) \(\ldots\) converges in some sense to a fixed set. That fixed set is called the attractor of the iterated function system. It is that attractor that is the fractal. It is fascinating to note that our starting set does not matter, the same attractor is obtained no matter which set we use as \(S_0\text{.}\)

One aspect of a fractal is that fractals are self-similar, that is they are made up of constituent pieces that look just like the whole. More specifically, a subset \(S\) of \(\R^2\) is self-similar if it can be expressed in the form

for non-overlapping sets \(S_1\text{,}\) \(S_2\text{,}\) \(\ldots\text{,}\) \(S_k\text{,}\) each of which is congruent to \(S\) by the same scaling factor. So, for example, the Sierpinski triangle is self-similar, made up of three copies of the whole, each contracted by a factor of \(2\text{.}\)

If we have an IFS, then we can determine the attractor by drawing the sequence of sets that the IFS generates. A more interesting problem is, given a self-similar figure, whether we can construct an IFS that has that figure as its attractor.

Project Activity 37.8.

A picture of an emerging Sierpinski carpet is shown at left in Figure 37.18. A Sage cell to illustrate this algorithm for producing approximations to the Sierpinski carpet can be found at faculty.gvsu.edu/schlicks/SCarpet_Sage.html. In this activity we will see how to find an iterated function system that will generate this fractal.

(a)

To create an IFS to generate this fractal, we need to understand how many self-similar pieces make up this figure. Use the image at right in Figure 37.18 to determine how many pieces we need.

(b)

For each of the self-similar pieces identified in part (a), find a linear transformation and a translation that maps the entire figure to the self-similar piece.

Hint.

You could assume that the carpet is embedded in the unit square.

(c)

Test your IFS to make sure that it actually generates the Sierpinski carpet. There are many websites that allow you to do this, one of which is cs.lmu.edu/~ray/notes/ifs/. In this program, the mapping \(f\) defined by

\begin{equation*} f(\vx) = \left[ \begin{array}{cc} a\amp b\\c\amp d \end{array} \right] \vx + \left[ \begin{array}{c} e\\f \end{array} \ \right] \end{equation*}

is represented as the string

\begin{equation*} a \ b \ c \ d \ e \ f\text{.} \end{equation*}

Most programs generally use a different algorithm to create the attractor, plotting points instead of sets. In this algorithm, each contraction mapping is assigned a probability as well (the larger parts of the figure are usually given higher probabilities), so you will enter each contraction mapping in the form

\begin{equation*} a \ b \ c \ d \ e \ f \ p \end{equation*}

where \(p\) is the probability attached to that contraction mapping. As an example, the IFS code for the Sierpinski triangle is

\begin{equation*} \begin{array}{ccccccc} 0.5 \amp 0 \amp 0 \amp 0.5 \amp 0 \amp 0 \amp 0.33 \\ 0.5 \amp 0 \amp 0 \amp 0.5 \amp 1 \amp 0 \amp 0.33 \\ 0.5 \amp 0 \amp 0 \amp 0.5 \amp 0.5 \amp 0.43 \amp 0.33 \end{array} \end{equation*}

The contraction mappings we have used so far only involve contractions and translations. But we do not have to restrict ourselves to just these types of contraction mappings.

Project Activity 37.9.

Consider the fractal represented in Figure 37.19. Find an IFS that generates this fractal. Explain your reasoning.

Check with a fractal generator to ensure that you have an appropriate IFS.

Hint.

Two reflections are involved.

We conclude our construction of fractals with one more example. The contraction mappings in iterated function can also involve rotations.

Project Activity 37.10.

Consider the Lévy Dragon fractal shown at left in Figure 37.20. Find an IFS that generates this fractal. Explain your reasoning.

Check with a fractal generator to ensure that you have an appropriate IFS.

Hint.

Two rotations are involved — think of the fractal as contained in a blue triangle as shown at right in Figure 37.20.

We end this project with a short discussion of fractal dimension. The fractals we have seen are very strange in many ways, one of which is dimension. We have studied the dimensions of subspaces of \(R^n\) — each subspace has an integer dimension that is determined by the number of elements in a basis. Fractals also have a dimension, but the dimension of a fractal is generally not an integer. To try to understand fractal dimension, notice that a line segment is self-similar. We can break up a line segment into 2 non-overlapping line segments of the same length, or 3, or 4, or any number of non-overlapping segments of the same length. A square is slightly different. We can partition a square into 4 non-overlapping squares, or 9 non-overlapping squares, or \(n^2\) non-overlapping squares for any positive integer \(n\) as shown in Figure 37.21.

Similarly, we can break up a cube into \(n^3\) non-overlapping congruent cubes. A line segment lies in a one-dimensional space, a square in a two-dimensional space, and a cube in the three-dimensional space. Notice that these dimensions correspond to the exponent of the number of self-similar pieces with scaling \(n\) into which we can partition the object. We can use this idea of dimension in a way that we can apply to fractals. Let \(d(\text{ object } )\) be the dimension of the object. We can partition a square into \(n^2\) non-overlapping squares, so

Similarly, for the cube we have

We can then take this as our definition of the dimension of a self-similar object, when the scaling factors are all the same (the fern fractal in Figure 37.1 is an example of a fractal generated by an iterated function system in which the scaling factors are not all the same).