89 Zombie Math—Decomposing 5 0 5 い ) Figure 9.3. A 3D graph (a), with noise (b), that is reduced (c) using the SVD. singular values seen in Figure 9.4. L00king at the 可 0t , we see a steep drop- 0 in values beginning at the seventh largest singular value. That drop-off is the signal 0fa ん t0 choose. We'II take ん = 8 and construct the rank 8 matr1X approximation with the SVD. Now, we 可 ot the rank 8 matnx approximation as seen ⅲ Figure 9.3 (c). The noise is reduced, though we d0 not entirely regain the image in Figure 9.3 (a). This technique is used when you may know there is noise but don't know where or hOW much. SO, having improvement in the data like that seen in Figures 9.3 (c) and (b) can be important. The blurrmg 0f the lmage that occurred in compresslon aidS in reducing n01Se. 10 35 40 45 50 15 20 25 30 Figure 9.4. Singular values ofthe matrix containing the data graphed in Figure 9.3

20 When Life is Linear Figure 3.6. Noah on the Davidson college campus and in the Museum of Math- ematics. Ph0tographs courtesy 0f Davidson College and the NationaI Museum of Mathematics. 3.5 Leaving Through a P0 「 This same idea can be used for another visual effect. This time, let's start with the image in Figure 3.6 (a) 0f the Davidson C011ege campus and end with the image in (b)located at the Museum 0f Mathematics. What visual effect can a convex combination have on Noah WhO iS standing in bOth pictures? Before reading further, guess what happens if we visualize the matnx ル for ル = 伐 / 十 ( 1 (a)Xwherearangesfrom0t0 1. ln Figures 3.6 (a) and (b), Noah is placed in the same location in both lmages. SO, this time the background fades om one image t0 the 0ther. ln Figures 3.7 (a) and (b) we see the image ル fora = 0.25 and 0.6 , respectively. Figu re 3.7. Noah in stages of teleporting om the Davidson college campus to the Museum of Mathematics. Photogr 叩 hs courtesy of the National Museum of Mathematics and Davidson College.

49 lt's 日 ementary, My Dear Watson Figure 6.5. げ we zero the values below the main diagonal, as done in Gaussian elimination, on an image Of Abraham Lincoln, d0 we get the image in (b) or (c)? image again. This elementary row operation has bnghtened Mona Lisa's eyes as seen in Figure 6.4 (a). ⅲ contrast, let's leave rows 320 t0 420 the same and multiply all other rows by 0.5. This darker image is seen in Figure 6.4 (c). 6.1.3 Substitute Lincoln Now, let's 0k at replacing a row by adding it t0 a multiple 0f another row. TO keep things visual, let's work with the image 0f Abraham laincoln in Figure 6.5 (a). F0110wing the steps 0f Gaussian elimination, we'll place a zero in the first element Of every row but the first. Then, we turn tO the second column and place a zero ln every row except the first tWO rows. This process IS continued for every row until zeros are placed in every element under the main diagonal Of the matr1X. NOW comes a question, would this result in the image in Figures 6.5 (b) or (c)? N0te, a black pixel corresponds to a 0 in the matr1X. The matnces that produced Figures 6.5 (b) or (c) both have zeros in all elements below their main diagonals. When using Gauss1an elimination tO solve a linear system, we would back substitute at this stage. Depending on your intuition with Gaussian elimination, you may have guessed (b) or (c). While the process does produce zeros ⅲ all elements belOW the main diagonal, in most cases the nonzero elements in the row a ト 0 change. Earlier ⅲ this chapter, we had a linear system om the problem posed in the ノⅲ z ん〃 g & la ん″ , 6 9 4 0 1 ー っ ~ っ 4 っ 0 ーっ 0 っ一

19 Sum Matrices (b) Figure 3.5. Mikayla ⅲ the Museum of Mathematics (a), made invisible (b), and in stages 0f becoming invisible (c) and (d). Ph0togr 叩 hs courtesy 0f the National Museum ofMathematics. We will make Mikayla, as seen in Figure 3.5 (a), disappear in the National Museum 0f Mathematics in New York City. How do we place such a hex on Mikayla? The tnck is letting the beginning matr1X X be Figure 3.5 (a) and the final matrix, / , be Figure 3.5 (b). Then, we visualize the image corresponding to the matr1X ル = 伐 / 十 い一 a)X, for differmg values of 伐 . We start with 伐 = 0 , which corresponds toN=X. Then,aisincrementedt00.1,S0ル=伐/ 十 (1 ー伐 ) X = 0.1 / 十 0.9X. We continue to increment 伐 until 伐 = 1 at which point ル = 伐 / 十 い一 a)X = Y. What's happening? Consider a pixel that has the same value in Figures 3.5 (a) and (b). Then x リ = ノ , where ノ and 盟 . / denote elements in X and / that appear ⅲ row / and column ノ . Remember 〃リ = 伐 ) ク / 十 ( 1 ー伐 ) x リ 伐を / 十い一伐 ) x リ = /. SO, the pixel stays the same. For a pixel that is part of Mikayla in 3.5 (a) and the museum in 3.5 (b), then 佐 / progressively contains more Of a contrlbution from / as 伐 mcreases. For example, Figure 3.5 (c) and (d) are formed with 伐 = 0.25 and 0.6 , respectively.

72 When Life is Linear Figure 8.2. An originalimage is repeatedly scaled via a linear transformation. This matrlx's only eigenvalue is え , and any 2D column matrrx is an elgenvec- tor. Figure 8.2 shows the effect of repeatedly applying this transformation with え = 1 / 3 ⅲ (a) and with え = ー 1 / 3 ⅲ (b).ln both figures, we have placed the onginalimage and the images produced by three applications 0f this transformatlon on top Of each other. Knowing the values of え , can you determine which 0f the four images ⅲ (a) and in (b) is the starting image? 8.3 Finding G「0 叩 ies Clustermg is a powerfultool in data mining that sorts data into groups called c / ″、セパ . Which athletes are similar, which customers might buy similar products, or what movles are similar are all possible topics Of clusterlng. There are many ways to cluster data and the type of question you ask and data you analyze often influences which clustenng method you will use.ln this section, we'll cluster undirected graphs using elgenvectors. We'Il see how eigenvectors play a ro 厄 in clustenng by partitioning the undirected graph in Figure 8.3. A graph is a collection 0f vertices and edges. The vertices ⅲ this graph are the circles labeled 1 t0 7. Edges exist between pairs Of vertices. This graph is undirected since the edges have no

What Are the Chances? もお . バ 気し、驫、缸龕。↓ 103 Figu re 10.7. Sierpifiski's triangle created with the chaos game visualized after 5 000 (a), 20 , 000 (b), and 80 , 000 (c) steps. the new vector, then one step Ofour game 燔 captured in = [ 0 T , P2 = [ 0 ()]T,andI)3= where p randomly chosen from 店 Sierpinski's triangle forms after an infinite number Of iterations but there comes a point after which a larger number Of iterations no longer produces visible differences. Such changes are only perceived after zooming into regions. TO see this visually, Figures 10.7 (a), (b), and (c) are this process after 5 000 , 20 , 000 , and 80 , 000 iterations. 、 Ve can also represent the chaos game as レ 2 0 0 1 / 2 where p randomly chosen t0 be PI, P2, or P3. T(V) is a new point that we graph since it is part 0f the fractal. Then, we let v equal T(v) and perform the transformation again. This looping produces the fractal. This formula becomes more versatile when we add another term: COS 〃 レ 2 0 0 1 / 2 ー Sin() COS 0 Let's set 〃 t0 5 degrees. This produces the image in Figure 川 .8 (a). An interesting vanation is tO keep 〃 at 0 degrees when either points 2 or 3 are chosen ⅲ the chaos game. げ point 1 is chosen, then we use 〃 equalto 5 degrees. This produces the image in Figure 川 .8 (b).

When Life is Linear 3.3 BIending Space lnspired by a histonc speech by President J0hn F. Kennedy, let's use linear algebra tO visually capture a moment ⅲ time that committed the United States tO a national space program. ln the speech, the president stated, 、 'We go intO space because whatever mankind must undertake, free men must fully share. " Soon after, he made the resounding challenge, ツ believe that this nation should commit itself t0 achieving the goal, before this decade IS out, Of landing a man on the moon and returning him safely tO the Earth. ' By the end of the decade, what might have seemed like a distant dream in his speech became reality with the APOIIO 1 1 mission to the moon. We start with images of President Kennedy giving that address before a 」 0 ⅲ t session Of Congress in 1961 and Buzz Aldnn standing on the moon as seen ⅲ Figures 3.3 (a) and (b). Using Ph0toshop,I cut the astronaut out 0f Figure 3.3 (b) and placed him on a black background as seen in Figure 3.3 (c). My goalis to blend the two images into a new image. The choice of a black background ⅲ Figure 3.3 (c) is due to the grayscale value of black pixels, which is zero.ln a moment, we'll discuss the implication of a black background mo 代 . Let ノ and B denote the matrrces containing the grayscale information of JFK and Buzz Aldrin, respectively. To create the blend, we let 図 伐ノ十 ( 1 ー伐 ) 召 , where 月 becomes the blended image. lfa = 0.5 then 図 has equal contrlbutions om each picture. I used 伐 = 0.7 tO create Figure 3.3 (d), which created each pixel with 70 % of the value om image of JFK and 30 % from the image ofthe astronaut. This resulted in the image ofJFK being more defined and prominent than that Ofthe astronaut. Let's return a moment to the clipped image of Buzz Aldrm in Figure 3.3 (c) as opposed to (b). Had I used the unclipped image, the surface of the moon would have been visible, albeit faintly, in the blended image. NOt including this was my artistic choice. Let's also ok at the decision of having a black background, rather than using another color like white. Again, a black grayscale pixel has a value 0f 0. If 〃 is the value 0f a pixel in the image of JFK and the pixel in the same location is black in clipped image 0f Buzz Aldrin, then the value 0f the pixel in the blended image is 夜〃 , which equals 0.7 〃 . We know this results in a slightly darker image of JFK giving his speech. SupposeI had placed AIdnn on a white background. What result would you anticipate?

When Life is Linear Figure 3.4. A linear blend ofimages ofa cub and adult ⅱ on. using the images 0f a cub and adult lion in Figures 2.2 (a) and (b). l'll create a blended image column by column. ln the blended image, a column 0f pixels equals the value 0f the pixels in the same column 0f the image a ん十 ( 1 ー伐 )C, where ん and C are the images of the adult lion and cub, respectively. We'll take 伐 = ー on the far 厄代 and 伐 = 0 on the far nght. The resulting image can be seen in Figure 3.4. NOte the different ways we've used one mathematical method. a moment, we will use a convex combination tO create even mo 代 effects. ThiS connects tO an important point about the field and study ofmathematics. The boundarles ofmathematics Often widen through one mathematician building 0 仕 the work of another. lsaac Newton, a founder of calculus, stated, "lf I have seen further than others, it is by standing on the shoulders 0f giants. " One idea can clear the path tO another. 、 Me see this ⅲ this chapter as the idea Ofa convex combination allows a varlety ofapplications. As you think about the ideas Of this section and continue tO 代 ad, be mindful of your thoughts and ideas. 、 Mhat comes tO mind? Can you use these ideas tO see further and in Other directions? 3.4 LinearIy lnvisible NOW that we've learned how to do a convex combination let's learn to cast a hex or spell with it! Our mag1C wand will be our convex combination.

Entering the Matrix Figure 2.2. lmages ofa lion cub (a), adult lion (b), and composite images (c). Photo of lion cub by Sharon Sipple, (www.flickr.com/photos/ssipple/1468 引 0248 レ ) , and photo of adult lion Steve Martin, (www.flickr.com/ph0tos/p0kerbrit/141542728 ロ / ) , CC BY 2.0 (creativecommons.org/licenses/by/2.0). TO see this, let's take the image oflion cub and adult lion seen in Figure 2.2 (a) and (b). Can you figure out how ー produced the images in Figure 2.2 (c)? Take a moment and consider it before reading on. The images in Figure 2.2 (c) were created by randomly choosing a pixel location in the image Of the lion cub. Then, a random size Of a submatnx was chosen. Then each Of the submatnces Of the chosen with its upper righthand corner at the chosen pixel location were swapped between the images 0f the cub and adult lion. D0ing this several times formed the composite images ⅲ Figure 2.2 (c).

79 Stretch and Shrink 5 0 -0 0 5 0 5 一 5 0 一 5 0 LO 0 【 0 20 ー 1 5 ー 10 ー 5 0 5 10 15 20 Figure 8.9. POints in Figure 8.7 rotated (a). The first and second prmcipal compo- nents (b). ー 20 ー 15 ー 10 ー 5 0 5 10 15 20 This vector, indeed, passes through the data at the same spot as the x-aXIS in the data in Figure 8.7. Our eigenvectors indicate the amount Of varlance ofthe data in that direction. SO, the eigenvector with the highest elgenvalue is the pnncipal component. The second eigenvector is perpendicular tO the first and reframes the data in a new coordinate system as seen in Fig- ure 8.9 (b). One ofthe biggest advantages Ofthis methOd is in dimensron reduction. S11PP0se we rotate the ellipse into 3D as seen in Figure 8.10. The data is still two dimensionalin nature. lt has length and width but no height which is why it all lies in a plane, which is drawn with a dotted line in Figure 8.10. For this type of data, we will find three eigenvectors but one 0f them will have an eigenvalue Of zero indicating the data actually is tWO dimensional. Figure 8.10. A 2D ellipse rotated in 3D.