Mathematical Games Hosted by Ed Pegg Jr. [Episode 18: Linear Algebra Magic]

Hello, everyone. I'm Ed Peg, and we'll be starting this very soon. Looks like we accidentally started a minute early. And I'm getting an echo. Okay, This, this might be slightly tricky because I'm getting an echo on my feed, but let's go on with it. Any. Okay. All right, so I'm gonna, just gonna take off my headphones here, so other. I'm not talking to myself. Welcome to mathematical games, episode 18. I'm going to be talking about linear algebra today for this mathematical game series. I've been trying to continue the work of Martin Gardner, who ran mathematical games for Scientific American for, for 25 years. His mathematical Games column was very influential for mathematicians who grew up in the 50s, 60s, 70s and 80s. And I was one of the people who was greatly influenced by Martin Gardner's works. He basically made me really like mathematics and this sense of exploration that there are things that were unknown and unsolved really helped make the whole topic interesting to me. So for, for linear algebra, one of Martin Gardner's famous creations was Dr. Matrix. Irving Joshua Matrix was in many of his columns, doing interesting things with mathematics and also skewering things like numerology and pseudoscience. Usually Dr. Matrix would be set up, taking advantage of people, and Barton would come over and visit to see what Dr. Matrix was up to for a particular column. And he usually did that once a year in his columns. And there's a collected book about. Dr. Matrix is one of the 15 books by Martin Gardner. So, of course, we've got many demonstrations involving linear algebra, and I'll be talking about some of them here. So to kind of prompt this talk, here's a tetrahedron, and I'm rotating it here with my mouse. So what are the pieces of linear algebra involved here? And here's a list that I came up with. We've got a 3D point representation, Mouse, movement vectors, matrix transformations, vector representations, the, the way the coordinates are handled through translations, dot products, cross products, projection. Since we're putting this 3D image onto a 2D screen, normal vectors, very centered coordinates. Since we're moving things around like the cube and whatnot, camera transformations, clipping, interpolation, and then there's a whole process, since I'm talking on a video here, how, how this is all set up and sent to you. We've got digital encoding, error correction, some of which I talked about in the last column, reassembling the data and then converting the data back and forth between sound and everything else. So just with me moving that tetrahedron around and talking about it. There's millions of pieces of linear algebra being used to help do this talk. So may as well start with the simple stuff. What is a vector? And here's some examples. A vector is, goes from a point A to a point B. And we have a representation. And a pair of numbers can represent a vector. So and a norm of a vector is a way of ripping in it so it's equal to one. This is a unit vector here. When one, one of the things with, with physics is just about anything can be represented as a vector. Any sort of movement, a car moving and there's, there's many different types of vectors, rotational vectors, acceleration vectors, movement vectors and whatnot. So much of physics is based on the study of vectors. So we can, let's see, We can take a look at vector addition here. If we have the red and blue vector, we add them together with what's called the tail method, I believe, and you get the purple vector, which is their addition. So vector addition is one of the classic things you learn in linear algebra. But where do the matrices come from? So this is something I mentioned in the last episode with the Kirkman School Girl problem which came out in 1850 and Cayley solved this problem building this matrix like object. And this was done in 1850, which was before the, these letters here are a phenoplane and this item over here is a room square. But Kaylee developed this before either Dino Fano or Thomas Room were born. So this, this is a nice example of somebody else getting credit for what somebody previously had done. So due to this problem, it seems that Sylvester and Cayley worked on other problems that could be solved with grids of numbers. And they developed matrices a little bit later that same year. So it seems like this, this recreational mathematics problem, the Kirkman School Girls problem, led to linear algebra. So here's a sample matrix and here's one of the first paragraphs from Sylvester and Kaylee. For this purpose we must, must commence not with a square, but with an oblong arrangement of terms. And they explored things like determinants and what could be done with them. So Sylvester then later named graphs as seen in graph theory. So here's an example of some of the things they looked at is how determinants could move lines around. Here we, here we show how a transform matrix operates on a square. And you get these different behaviors based on the initial matrix. And if you use more complicated matrices, you get more complicated behaviors. So we can, we can take a vector and change it into A line like so. So any, any vector from the origin leads to a line. And from that we can get the concept of normed lines, where you have a unit vector at the center and a distance. And when you have them combined, you get the norm form of a line, also called a Hessian line. And we can do the same thing with planes. If we have a, a vector, we can change that to a plane. So any plane can be represented with a vector. And this is also called the Hessian form of a plane. So with, with lines and planes, you can do a whole lot. So that's one aspect of linear algebra is representing polyhedra. And from that you can get 3D objects when you combine them together with triangularization. So that goes right into 3D objects in games and whatnot. So here we have the Hessian form of a plane. So we have a function called Hessian plane, where you can get a Hessian form. So once you can draw a line, you can do more things with it. So here's the logo for the Summer Olympics. It looks like sort of a. The face of Marianne. It's also the Olympic torch and also a gold medal. So they wanted to represent a number of things in their logo. But there's also a couple items that are hidden. This, this curve here is done with bezier curves, who were. Which is a joint collaboration between the French mathematician Paul. Oh, I don't know how to say his name, Paul and Pierre, who worked for the French automakers Citroen and Renault. So these curves were developed in France. So this is a very French object here, using French, French mathematics and designed by French designers for the Paris Games. So these are bezier curves. This, this set of, of control points which are numbered here. For example, control point 7 is somewhere here. With these 34 control points, we can do either filled curves or bezier curves, or B spline curves. And let's take a look at one of these. So first we're going to represent a line. We have two points. And if we move the, if we Change the fraction, 0 is just this first point here, and 1 is just the second point. And as we change the fraction, we go from one point to the other. So this is point A times a value plus point B1 minus the value. And this is a standard way of representing points on a line based on two, two points. But with a bezier curve, we can add another point. So we have three points here, and they do the same thing with both lines, but as they change the fraction, they also do A between point between those two points that were generated. And this is the De Castle Zhao algorithm. But don't believe my pronunciation, this guy. We can also add another point here and keep going. We just calculate more lines and so on. So with control points you can make rather elaborate curves that are very natural looking. And this is actually a fairly fast algorithm. SVG uses this quite a bit for, for generating vector based images. And here's a example of the algorithm used to develop one, one piece of the flame. Here are some points that are along it. So that's one thing you can do with these vectors and line representations. We can normalize the vectors and we get points on the unit circle when we, when we normalize them. And then we can move up to the more complicated matrices and you get such things as the, the transpose and the inverse of a matrix. So the, Oh, this is left over from my last time. So this is the, we have the original matrix here, the transpose. We're just basically flipping along an axis and the inverse of a matrix. If we multiply this matrix by that one, we get the identity matrix with ones on the diagonal and zeros elsewhere. We can also do a rotation of a matrix. And here's the representation for the 2D rotation matrix. And from there we can get to A, a 3D rotation where it goes through three angles. And with these three, three angles, that's enough to rotate an object into any orientation. Often two angles is enough, but not always. So they use three angles for the most part. This is, I forget what, what this teapot is called. So once you get two vector rotations, it's basically three 2D rotation matrices interspersed with, with one, such as follows. And when you multiply them all together, you get the, the full 3D rotation matrix. And with that you can get these images showing the result of the rotations. So once you've got these rotation matrices, there's a subset of 12 matrices. And here they are here, these 12 matrices which are known as the tetrahedral group. And with those I can build these, these 12 prisms and join them together and we get this object. We've basically taken one of these prisms and then rotated it by all 12 of these rotation matrices. But I only needed to give data for one of these prisms because the rest is all symmetrical. That's something you can build with Toblerone bars. And after I, after I put this together, the art department thought I should give it to Stephen because he needed a prop for something and, and you use it. And this wound up being A very popular Instagram image. Oh, Utah teapot. That's right. And there's other subsets of the rotation matrices which also make groups, such as the icosahedral group. And here is the icosahedral group here. And A is half the golden ratio, B is half of one over the golden ratio, and C is one half. You've got all these different variations of A, B and C. So this is, this makes 120 matrices. And if you have a polygon such as these here, we can make these objects. So we basically start with one polygon and then we multiply it by the 60 elements of the, of the icosahedral group. Here's the matrix that produces this polygon here. This, this is one of the polygons that uses just the tetrahedral group, which is a subset of the icosahedral group. And there's various polyhedra that are all based on the icosahedral group. The Tricus icotahedron, the compound of 5 tetrahedron, The rhombic hexacontahedron, the Mathematica original spiky from version 1, the cumulated dodecahedron, and the pentagonal hexacontahedron. So these are all developed using the icotahedral group, which is a, a collection of, of matrices based on the golden ratio. So one type of matrix is the, is the permutation matrix. So here's some examples of permutation matrices which basically just move numbers around. So you have a starting Vector such as 1, 2, 3, 4. We can multiply it by this matrix where we can, we can represent this vector down here by this matrix. And when we multiply them together, we get a different permutation. So the permutation matrices are a, make up a group. If you multiply two permutation matrices together, you will get another permutation matrix which, which will produce a closed group. That leads to one useful thing in math, which is sign permutations. Often you want to represent all the permutations of something in a certain way, but you also want to add in signs. So 0, 1, and the golden ratio is one way of representing the I, the vertices of an icosahedron. So here I've got up here three values. The golden ratio, the triben. Yes, Tribonacci ratio. And I forget what this one is. This is a value used in the snub dodecahedron. But for all of these objects, every single Platonic solid and Archimedean solid, there's a simple representation using signed permutations. So basically, you start with a simple set of values and then you get all the signed permutations, which is basically a certain set of permutation matrices. And you get the larger object. And here's pictures of all of these various objects represented as unit spheres all tangent to each other. So we kind, we kind of gain a lot of simplicity. We've got these, these rather complicated objects, but you just say it's signed permutation on these two values and you've pretty much got the object. And we can go up higher, we can, we can look at rotation matrices in four dimensional space. So here's a hypercube being rotated. So this is a projection into 3D space of a four dimensional object, then retranslated into two dimensional space. And we can move up a little bit further to get the unit quaternions. So what are icosians? So basically it's a, a set of unit quaternions. On the definition of quaternions, we start with 2, 000 and 1111. And if you apply plus minus the sign permutations and, and do the taught products with the quaternion set, we get the 24 cell or also called the octoplex. And then if you add 011 over the golden ratio and the golden ratio, you get the Icosians, the 120Ecosians, the centers of the 120 cell or the vertices of the 600 cell. So here's code for setting that up. We can just run that. And these first 24 are the vertices of the 24 cell, which is a self dual object in 4D space. The ECOSYS we, we use the quaternion function and we multiply that by the 120 vectors we've gotten and we can sort them by their conjugates. And here's a random sample of these quaternions. And once you've got the 120 quaternions, we can just build things like the hexacus tricondrahedron based on one polygon. These ICOsians also work as rotation matrices in the space of quaternions. So backing up of that, once you have a series of vectors, it doesn't matter what order you give them in, you always will get to the same spot. So this community commutativity property is useful for simplification. We can also project vectors. For example, projecting this point onto this vector, we get there and then some graphical representation of matrices. We start with the original matrix here. And then when we get the inverse we get this one here. And notice that the dash lines here are, are perpendicular to the vector original vectors. So this dashed blue line is perpendicular here and so on. So that's one property of inverse matrix. This is perpendicular property. Now things get a little bit more complicated. The trace determinant plane of a linear map. Let's see, as we move the point around we get different properties for, For the, For the behavior. And there's a, a map you can make of of where different properties. For example, if the points are on the unit circle, you're on the center. You can also use matrices for calculations. For example, the volume of a tetrahedron is based on a adding ones to each of the coordinates at the bottom and then taking one, six of the determinant of the matrix. So as we change the tetrahedron, we're Basically just this first vertex 666 or 466. We just add a one at the end. We add a one at the end of each coordinate and we get the volume. The circumsphere we can also solve with a determinant. So here I've got four points. And when we just add this vector at the top, we get the equation of the sphere that has those four points. For a conic, if we just take the original XY points, we've got X1, X2, X3, Y1, Y2, Y3. If we just build this matrix, we get the function for the equation going through those five points. We just basically build the matrix and we get the, we get the object that is involved. The nine point cubic is the same. We just build a more complicated matrix and we automatically get the cubic formula that goes through those lines. We can also represent graphs as matrices. If two points are connected in the graph, we mark them with a 1 and if they are not connected they get a 0. So any graph can be represented as a matrix. And you can also do directed graphs based on the direction the vectors go. If, if 1 goes to 2, you'd get a 1, but if 2 did not go back to 1, it would be 0 on the, on the 1, 2 coordinate. So here's a example of linear algebra being used to solve a problem. The Sylvester postage stamp problem. He wanted to know the largest number that could not be made of some combination of 5 and 17 pence stamps. And even though Sylvester developed it and he's remember, if you remember back, Sylvester is the one who developed developed matrices with Halley. But it's named after Frobenius. And the Frobenius number is for this particular one is 63. And we have a little bit of a setup here. If you have say 7x plus 5y, we can represent numbers in a grid and as we move the line. We get different values. And as you move the line you can eliminate different values that do or do not appear. And this is one of the methods used to dissolve the original problem. But the Frobenius method works more easily. Once you get beyond simple matrices. You can have more complicated matrices such as tensors. And here's a demonstration which goes into representing a plane as a tensor. And you can. Oops, not sure why that's. Oh, probably because that was zero. So here's a tensor representation for a plane. In my mind sensors are basically fancy matrices. So we can go to more unusual properties of matrices such as the eigenvalues. So here's a simple looking matrix. However, Realhart and notice when this matrix caused problems in a computer problem computer program, he noticed that the continued fraction had these large values in it. 16 million. And a little bit more experimentation showed it was related to the Ramanujujan number E to the PI times the square root of 163, which is this value here, which is very close to the cube of this number + 744. But this cubic here, if you take the 24th power and subtract 24, it's seemingly equal to the Romanjan number, which should be impossible since this is, this is not a algebraic number. This, this number here is based on a simple polynomial. Now if we extend these, Let's reevaluate this. If we extend these further, we see that these actually diverge after 32 decimal places. But it's bizarre that these two values are so close to each other for 32 decimals. And this is some values behind the monster group and the Leech lattice. There's some very deep math involved with, with, with this matrix and it took about 30 years to fully understand it. That's, that was one of the big projects back in the 1980s. So shifting gears a little bit, we have an orchard problem here. Here we have 11 points that have many lines of three. So this is how 714 lines is three. 15 lines of three. So here's the most lines of three you can get from, from 11 points. But what's a fast way to calculate all the lines? Or putting another way, an extraordinary line is a set of three or more points on a line. So if you're given a set of points, what's the fastest way you can find all the extraordinary lines in that set of points? So I Did a whole bunch of different methods trying to calculate lines quickly. And it turned out that the fastest way by far was using row reduce. So here's, here's the code for find extraordinary lines. And we at the center here it has row reduce. And basically we append ones. For example, here we have 2.60 and 03. If we basically append ones at the end and then do a row reduction, we get a very fast representation for it as a line. And when we gather all those up, the points that have the same line line representation as a row reduction are on the same line. And this works for any dimension as well. So extraordinary lines works in three dimensions, possibly four dimensions, but I haven't tried that. But it's super fast for thousands of points. Just other methods for, for calculating line equations were much, much slower. So that's one bit of, of magic that I didn't expect. But road reduction is, is so optimized now that it's, it's much faster than, than, than other methods. Let's see, we can talk about special types of matrices. A symmetric matrix is, is symmetric along the main diagonal. Skew symmetric is the same, but it has opposite signs. A upper triangular has values on the upper section but zeros elsewhere. And lower triangular is the opposite. The diagonal matrix just has values on the, on the center. I've mentioned identity matrices, but I haven't showed them. Two transpose matrixes. A zero matrix. So these are various types of matrices and there are maybe a hundred different named types of matrices. I do not know all of them. I had a marred matrix. Here's some examples. Here is such that all entries are either plus one or minus one. And any two rows when multiplied together will equal one. I think one. No, it will equal zero. They're mutually orthogonal. And one question is whether these always exist. I give representations up to, I think whatever 4 times 108 is. Up to 432. Now it's, it's believed that these always exist for any matrix matrix with an order of a size that's a multiple of four. But there's a few values such as these here that are still unsolved. And we don't know whether they exist or not. It's believed that they do, but no one's been able to find a representation for them. So that's one of the big unsolved questions in linear algebra and matrix theory. So here's one thing you can do with matrices is find inner products. If we have a, a curve, we can look at the the orbits of the special linear group here, which is a set of two by two matrices. And as we modify them, we get different curves and values. And eventually there's an acting matrix which controls everything. So these can get rather complicated quickly. This is just one example of that. We can also do fractals with matrices. So we have a mapping for points which is based on two matrices. And as we modify the matrices we get different fractals. As shown here. This is this demonstration by Garrett Nelson. Another application for matrices is iterated function systems. So here's an example of a recurrence matrix. And as we change the set of vectors and matrices, we get different behaviors. And that leads to different fractals, such as this object here. Then that leads into Rousey fractals. So here's a set of points and we just basically randomly pick either this value or this value. And then we just keep repeating that based on these pieces of this particular polynomial. Let me make this larger here. This is the super golden ratio here. Let's see if I can make that larger. And it doesn't want to expand immediately. So we can, you can replicate this by using these values here. And we get this Wrigley polygon. And if we just look at powers of the super golden ratio, one of the complex values. Here's, here's. Well, this, this has three. It's X squared plus one equals X to the third. If we look at one of the complex solutions, which is a complex number here it is to the 0th power to the first power, second power, third power, fourth power and negative the second power. If we combine those vertices on the complex plane together, we get in green and back we get one quadrilateral and we also get these two smaller quadrilaterals that split up to make a very good approximation for the original quadrilateral. And that's sort of the same as what's going on here. And if we repeat this as a substitution fractal, we get something that looks exactly like this, which was apparently unknown until a few years ago when I found this simplication. This, this was known. But nobody thought to change this into two quadrilaterals. And the fact that it mapped to the original generating points wasn't known. We can, we can take this particular shape and map it onto itself infinitely to show that the supergolden ratio is equal to the sum of the negative reciprocals of the supergolden ratio starting with two. So this is an example of a Rousey fractal which are still not well understood. We can look at Rousey fractals in three dimensions. And Dieter Steeman has written a number of demonstrations based on these. Let's see what some of these look like. These are examples of Rousey fractals. Let's see if we can get a high order one here. The different colors here make similar shapes. Which, which all equal the larger shape together. So far as I know, no one has gone into these and made simplified forms of these similar to what I did on this previous slide. So if anybody would like to try that as an experiment, take one of the Rousey fractals, which looks very chaotic, and try to simplify it to something very simple. That is a set of four or so polyhedra which, which are similar to the original shape but with a, with pieces moved around. So Rousey fractals are not well studied, but they're all based on particular matrices, usually with a, a characteristic polynomial and a discriminant. The discriminant is the, usually the important part because if, if you have behavior with one particular discriminant, you'll only see that behavior with that particular discriminant. But the polynomial can change. So when I'm looking at these objects, I'll look at the discriminant first. So for example, the super golden ratio and the plastic constant are very often seen in fractals. And also the golden ratio. We can also do such thing as phase portraits with linear algebra. Once you have a, a set of matrices, you can sort of look at what the behavior is as a vector field. And we can also look at group theory objects with, with, with the sporadic groups. There's 26 known sporadic groups. A. There's an explanation for what a, a sporadic group is at the sporadic groups demonstration. But here we have two matrices. This is a zero one matrix, and that's the B matrix. And here's the A matrix. And this, these two matrices together make the M24 group. So we can multiply series of them together such as that. And when you look at all the possible matrices you can get from, from multiplying these two together, it turns out for M24, there's 244 million different matrices that are in that group. And we can look at all of these different ones. Here's the J3 group. And each one of these is produced by two matrices. They get more and more complicated. The F23 group is ternary. That's why it has three colors here and at the start. Here's A and B. Some of them look better than others. For the for the original matrices, for example, here's B and A for the HS group. So the classification of all groups, including all the sporadic groups, was one of the big problems problems in, in mathematics, one of the largest proofs in mathematics. But they went to matrices to represent all of these objects. These are from the, from the Atlas by John Conway. So these are, these are the different groups that are represented in these matrices. So matrices really do a lot. Virtually all computer applications rely on matrices. They're really fast. All large models, from weather to space to special effects to games, all use matrices. Heavily new applications and AI represent rely on data that is carefully structured as matrices or tensors. Almost all mathematical problems can be converted to linear algebra problems. And if you do any sort of programming at all, or just about anything with computers, you're going to have to deal with structured data. So this little simple exercise is showed at the start of just a tetrahedral reader. Moving on. It turns out there's a whole bunch of math that's behind that and I gave a list of some of the objects that are involved and that's what I had. So I'll be glad to answer any questions that people have. You can just post them and I'll be glad to take a look. And if anybody looks at those things like the Rousey fractals and, and comes up with good representations for them, I'll be glad to take a look at those as well. So I'm waiting to see if anybody has questions. And thanks to everybody again for coming to see my talk. All of this, by the way, will be posted on Community probably sometime today or tomorrow. Okay, many thanks everyone, and I will close that here.