Listen: Mathematician Elizabeth Drellich Explains a Story of Animation and Algebra
Listen: Visiting Assistant Professor Elizabeth Drellich Explains Splines: A Story of Animation and Algebra
In this talk, Visiting Professor of Mathematics and Statistics Elizabeth Drellich, who has been teaching at Swarthmore for three years and currently teaches probability and combinatorial math, gives an introduction into splines, and how concept that started centuries ago with shipbuilders has become a powerful algebraic tool.
Drellich explains that the surface of your model car or your favorite Pixar character’s face is made up of a collection of polynomials that fit together smoothly called a spline. These splines are models, but they are also algebraic objects that can be added and multiplied. Some splines contain deep information about the structure of groups and algebraic varieties.
Drellich's talk was part of the Math/Stat Colloquium series, held every Tuesday in the Science Center 199.
Audio transcript:
Speaker 1: ... Elizabeth Drellich is here, she's been here for three years. And she's going to be giving a talk today so she's teaching probability and combinatorial math, she's teaching all of algebra, [inaudible] next semester. She got her Bachelors in Mathematics and International Affairs at George Washington and then [inaudible] UMass Amherst, while she was there she taught at Smith a little bit. Then she was teaching at University of North Texas when we stole her away and brought her to Swarthmore. So she will be speaking on "Splines, From Animation to Algebra".
Elizabeth D: Cool. Okay. So, splines. This little creature right here is the starfish from Finding Nemo. Hello! So, hopefully by the end of this talk, or really by the end of the first third you will know why that picture is here.
But I want to start with some history. So, if I told you I'm going to hand you a spline, what you might think, as I hand you, is a piece of bendy, bendy wood. And the reason you might want a piece of bendy, bendy wood is so that you can bend this piece of wood into any curved shape you want. So this picture right here? This is actually fairly big, this is the side of a guitar being shaped into the correct shape. So we have this bendy strip of wood creating a smooth curve that's connecting these important points that you want your guitar to encompass.
Alright, so a little bit of history. This idea of using bendy pieces of wood to model or make things that need to hit certain points, is actually a really old technique. This is a picture of a, a drawing in a book from 1711. Which is a shipbuilder's assistant, how to build ships.
So what this is demonstrating, all of these curves are places where you would want a nice smooth curve. You'll want a bendy piece of wood, and you would like all of those bendy pieces of wood to line up nicely so that your ship doesn't have any holes in it. So it doesn't sink. That would be a pretty big bummer. And you would start with small bendy pieces of wood, to make a model. So you know before you employ all of these hundreds of people and years of labor, to make your ship, that it's actually going to float.
So the next thing I want to show you. I should have gotten it quicker. Is this picture here. Now this is an animation done by Pixar, or I think Disney Pixar, and what do you notice about this hand here? What do you observe? Does it look perfect?
audience: No.
Elizabeth D: No. If you saw it you'd be like, "Well, it's a little bit rough". But, next picture, is how we can improve this hand and smooth it out. So when these Disney Pixar animators are creating this they might start with a picture that looks like this and then smooth it out, create smooth curves, that turn it into this picture.
So I want to zoom in on what the real difference between those two pictures is. That first picture had a lot of points, and they were glued together nicely, they met at important points, they all lined up. If you make out of that is like a glove or a shell, there wouldn't be holes in it. But there are these really sharp edges between where the planes meet. So, this is actually a picture of this [inaudible] polynomial. So you have the purple plane, and the green plane, the blue plane and the red plane. I believe. And if I wanted to smooth that all out, I might enhance my polynomials.
And now this picture, instead of planes, we have these quadratic equations. We still have that the function is zero on that negative one to zero, negative one to zero square. The purple part. And we actually still have all four corners at the same point. But what's happened is that we've smoothed out all of those edges. So instead of having these really sharp meetings of two planes, we have nice smooth curves. You can go continuously from the purple to the green. You can go continuously from the green to the red, from the red to the blue, from the blue to the purple. And in fact, it's hard to see in this picture, but it's also nice and smooth at zero zero here. You can go continuously in any of the four directions.
Okay. So I want to talk about some of the algebra here. So we're going to simplify this picture down to functions of one variable. And the first picture, the first hand, the first set of four planes. Although it's sort of like this picture, we had a piece [inaudible] defined function, like h. And we have f of x and g of x and they meet nicely, at a point. So f of a equals g of a. But, they're kind of sharp where they meet there. So what sort of condition could we add to say, "We don't just want them to meet up, we don't just want there to be no holes in our ship, we want it to be somewhat fluid dynamic". Right? We do not want to have sharp edges.
What sort of mathematical constraint could I add, in addition to f of a equals g of a. And this is a question for you, you're all paying attention [crosstalk]. Yeah?
audience: [inaudible]
Elizabeth D: Yeah, if I added the constraint that f prime of a also must equal g prime of a, instead of just f of a equaling g of a. Well then I would get something, oh, wrong way, like this. So adding that second constraint means that now they're not just going to meet sharply, they're going to meet smoothly. So we've gone from that first hand to that second hand picture by adding this, basically calculus, constraint.
Okay. So, so far we've seen some animation, we've seen some functions, what does this mean algebraically?
[inaudible]
They had to be equal, fa, f of a has equaled g of a. Then, algebraically I can write that condition as the rule that x minus a has to divide the difference between the two functions. So that may not be super intuitive and I want to remind everyone of how we can expand out polynomials. You take the Taylor Expansion of f of a. So were going to make the not unreasonable assumption that f of s equals it's Taylor Extension at a. And then you can say that f of x is going to be f of a plus f prime of a over one times x minus a plus f double prime of a [inaudible] times a squared. And we just get these terms expanding out forever. And if we do exactly the same thing for g of x, so assumption number two is that g of x also equals it's Taylor Expansion at a. Well then what happens if we subtract g from f? If they happen to be equal, these first two terms here? They disappear.
And then we have exactly our algebraic constraint that x minus a shows up in every subsequent term. What do you do if I wanted to add that the derivatives also match.? This is a a question for you guys again. What would happen to the difference of the Taylor Series?
Yes, [inaudible]
audience: x minus a squared is affected?
Elizabeth D: Yeah. If f of a and g of a are equal and f prime of a equals g prime of a, then there's going to be an x minus a squared in every single term of this expansion. So, if I don't just want that they meet, I want that they meet smoothly, to the [inaudible] derivative, or to the nth derivative, all the way up. I need to add this constraint that x minus a to the n divides f of x minus g of x. So I've taken this physical or technological idea that we need these curves to meet smoothly, and I've turned it into something purely algebraic. Okay, so we've got this condition that x minus a to the n, we divide f of x minus g of x. I don't want to just go back to meeting at the first derivative, smoothly, and meeting at the point. So just x minus a squared divides x minus g of x.
And we don't usually think about polynomials dividing other polynomials, or dividing Taylor Expansion. So what does that really mean to divide f of x minus g of x? Or we can think of it as there exists some other polynomial, h of x. Such that h of x times x minus a squared is equal to that difference.
If we can't have a rational function we need an actual polynomial if we want these to all be polynomials. So, can I see a show of hands, who has taken Math 67?
Okay. That's a good population. Those of you who have not taken Math 67, I'll be teaching it next semester so [inaudible] and you can check [inaudible] in about 30 seconds. So, what might we use to describe all of the polynomials in the set h of x for some function, h of x times x minus a squared. All of the functions we can get in that form. Daniel?
Daniel: The ideal generated by x minus a squared?
Elizabeth D: Yeah. So, one way to write this, I'm going to move over to the chalkboard, is that if I write something like x minus a quantity squared, I can ask for all of the functions. Infinite set of functions that are generated by that. And that means we have the set of all things that look like h of x times s minus a squared such that h of x is a polynomial. And I've denoted that by the r join x, right there.
So, if you haven't had Math 67 yet, you can just skip that line because all three of these conditions are completely equivalent. The idea that x minus a squared divides the difference is the same as saying there exists some polynomial h with that property, which is the same as saying that there difference is in that ideal.
So now we get to our algebraic question. So I am not an engineer, I am not an animator. Although those are super fun things that I would love to delve in. I'm more of an algebraist. So the question I want to ask with these is, is it possible to assign not one solution but all solutions. Can we find all pairs, f of x, g of x, with the property that we care about. And you can think about property as being any one of these three, they're all equivalent.
So, do you want to give me a particular [inaudible]
audience: Ah, sure four times x minus a squared.
Elizabeth D: Okay. four times x minus a squared comma zero. Can you give me a whole bunch more solutions? So how would you rephrase that to give me a whole bunch more solutions?
audience: Now we can multiply both members of that set by any real number.
Elizabeth D: Yeah. We can have any real number, like a. No, we've already used a, b times x minus a squared and zero, that's going to work. Is anything else going to work?
We'll leave that as a thought, if you get distracted or want to work on a project. There are more pairs that will work for this example. But I want to go to an example that is both simultaneously harder and easier. So, instead of talking about polynomials I'm going to transform this question into not polynomials but just pairs or triplets. So, if I give you a graph that has a and b and I label the edge connecting a and b with something called i, what I am trying to convey to you with this symbol, is that a minus b is in the set i, the same way we had f of x minus g of x was in the ideal generated by x minus a squared.
So here is a triangle. And we are going to work together to answer the question, what are all the triples; a, b, and c, with the property that a minus b is a multiple of five, b minus c is a multiple of seven, and a minus c is a multiple of three. So I'm actually going to give you a few seconds to write down, come up was some examples, and then we're going to start collecting some examples. We're going to make a collection on the board over here.
If you have a triple raise your hand I'm going to put it on the board. Daniel?
Daniel: The, for a to b you can just use five, for b to c you can use seven, and then for a to c that would be, I guess, could you do ... Oh, do you want it to be an actual triangle or can it just be-
Elizabeth D: ... I want values a, b and c. They'll have that property.
Daniel: I see [crosstalk]
Elizabeth D: The property that a minus b is a multiple of 5, b minus c is a multiple of seven, and a minus c is a multiple of three. [inaudible] do you have an example?
audience: [inaudible]
Elizabeth D: Okay, can you say that a little bit louder for me?
audience: 105?
Elizabeth D: 105.
audience: 210.
Elizabeth D: 210.
audience: 315.
Elizabeth D: 315. Okay. So, can anyone confirm that these in fact are the differences we need? Well, the difference between this one and this one; a minus c is 210, multiple of seven, multiple of three, multiple of five, it's a multiple of all of them. There we have 105, that's definitely a multiple of 5, here we have 105 again, another multiple of seven. Daniel, do you have another one?
Daniel: Yeah, so a minus b or, sorry, a ... so you can have a being something that is say, I guess a two.
Elizabeth D: Okay, is two.
Daniel: And then b would be seven-
Elizabeth D: ... b is seven.
Daniel: And c could be 14?
Elizabeth D: Does 14 work up here? Yeah, 12, seven, and five all have the right property.
Yeah?
audience: What about one, one, one-
Elizabeth D: One, one, one! Yeah. If we label them all one we get exactly the property we want. And we all laughed but actually this is really important. Because this way of labeling, this function from the vertices to the integers, this is so important that we're going to call it the trivial spline. So you know when something in one of your algebra is called the trivial vector space, or you have, you know, all sorts of things that we call "the trivial blank". That means they're actually really, really important. Even though they're something like one, one, one.
Anything else? Is there any way we can get another labeling? Another spline on this triangle? Maybe from some of these. Okay, zero, ten, and three. I like that one.
audience: If we take any one of these and just add a constant to each of the three parentheses it's going to keep all the [crosstalk]-
Elizabeth D: ... So what if I add a constant to each vertex? It's going to keep the differences the same. So I could do three plus my constant, 10 plus my constant, zero plus my constant. You can always add a constant to all of the vertices. What else could I do? Add them together. I could add two of these splines together. I could take this one and this one and add them together and get 329, 217, and 107. Those are still going to have the same property that the difference between these two is a multiple of three. The difference between these two is a multiple of seven, and the difference between these two is a multiple of five. Is there anything else I could do?
One more thing? Yeah?
audience: You can multiply them.
Elizabeth D: Multiply them in what sense?
audience: By an integer.
Elizabeth D: I could multiple them by an integer. I can say, multiply this one by two, and get 28, 14, and four. Okay, so we've now identified a whole bunch of splines on this triangle and we have all these rules for getting more. So I'm going to write down what we're allowed to do so far.
So we can add two splines, two of these algebraic splines. We can multiply by a constant, and multiply every term by a constant. And this one right here, where we added a constant to each term, do we need to specify that as a different role?
No, because I could get this by multiplying the one, one, one, our super important, super boring, trivial spline. By the constant c to get c, c, c, and then adding them together. Okay. So, we have this set of objects that we can add together and we can multiply by any integer. What do we call a set of objects like that? Anyone who's finished 67 might have this word floating around in the back of their head. Professors?
professor 1: [crosstalk] you don't need 67.
Elizabeth D: What?
professor 1: You don't need 67.
professor 2: It's in the vector space?
Elizabeth D: Ahh. There was a conjecture from the professors. That this might be a vector space. Does anyone disagree with your honored professors? That this is a vector space.
audience: I think 'cause the, your, our [inaudible] are like things ... The constants are the integers. So, it's not a vector space, it is a module.
Elizabeth D: It's not a vector space. It is a module. So [crosstalk] a vector space is a modular work field. And we are not over [crosstalk] field so we can only [crosstalk]-
professor 1: I forgot that you're doing all over c. We're just generalizing with you. [crosstalk]
Elizabeth D: So it seems, the set of splines, our triangle, this particular triangle, maybe any triangle, we'll see. Is a z module. It's like a vector space, but we can't divide by integer. How special do you guys think that this particular triangle is? Is this really special?
audience: No.
Elizabeth D: No, [crosstalk] this isn't special at all. In fact, this is so incredibly not special that we don't even need to have integers. Right? We had an over z at top. Well, if I have any brain I can set up the same definition. I can take a graph, I can label the edges by ideals, and I can ask what vertex labels have the property I care about. But the difference between a and b is in the ideal labeling the edge connecting them. So I'm going to do a little pause for a pretty picture and show you my absolute favorite spline.
This is my favorite spline. Algebraic spline. And I love this spline so much that I 3D printed it. So pass it around gently, these are expensive. In terms of time, though not money. So I'm going to send one this way, Hi! And I'm going to send the other one this way. The orange one is on the screen. And what you can't see on the 3D printed version, but you can see on the slide, is that I've got six different colors, and the colors represent different edge labels, different ideals. So all of the pink edges are labeled by the same ideal. All of the green edges the labeled by the same ideal. And they're actually all parallel.
And if I compute all possible splines, as edge labeled graph, I'm gonna get a module that actually happens to be the cohomology of a certain algebraic varieties. So that's the cohomology of the [inaudible] for the three people who [inaudible] about that. Everyone else, [inaudible] and I would love to tell you everything about it. But there's something else going on in this comment. Which is that the splines on this edge of the graph form a rank 24 module.
What do I mean by rank 24? And this comes back to the comment of is this the vector space or is this a module? We don't have a vector space, we might not have a basis. But it's still possible that we have a generating set. So when I say a rank 24 module, I mean that there is a collection of 24 labelings on the vertices that respect these constraints, given by the colors, that will generate using only these operations. Adding and multiplying by a constant, will generate all possible splines.
So that question I asked, several slides ago, can we find all possible pairs with the property we care about? Well, for this spline here, for this edge label graph, I would need to tell you explicitly, 24 labelings on, as it's going around you can count 24 vertices, in order to get all of them.
I want to come back to this triangle. Because triangle only has three vertices. And right now we've got one, two, three, four, five, six splines up on the board. And we know how to make a whole bunch more splines out of these six, right? Multiply by a constant, we can add them. Do we need all of them in order to generate all of the splines? And can we generate all splines on this triangle with these six? Maybe there's something hiding that we don't yet have. So is there any spline here that might definitely need to be in our generating set?
Yeah?
audience: The trivial-
Elizabeth D: ... The trivial spline. If I wanted a generating set I really, really want this trivial spline to be in it. Do I need this spline here? Do I need my three plus c, 10 plus c, and zero? Can I erase something to simplify it? What if I just had three, 10, and zero? Right. If I have these two I can get a lot of splines. Can I get all of the splines? Can anyone think of a spline, a labeling on these three vertices, that you cannot get taking a multiple of this, plus a multiple of this? Yeah, Thomas?
Thomas: The other one right over there-
Elizabeth D: ... The other one right over here.
Thomas: Two, seven, fourteen.
audience: The other direction?
Thomas: Yeah, yeah, yeah.
Elizabeth D: Two, seven, and fourteen. Yeah. Right? You would need, for the difference here, to be ten, or seven, which it is, but the difference here to be ten, which it is definitely not. You might want to take these three as a possible candidate for a generating set. But actually I'm going to replace this first one with one that is maybe even clearer. And I'm going to replace this one as well. And show you my favorite generating set. Because it's hard to come up with these and prove that they generate. So I definitely needed the trivial spline. The next one, I'm going to have five and twelve. And the last one I'm going to put two zeros and a twenty.
So, my question to you, I just erased a whole bunch of splines. Can you make those splines that I just erased, that none of you wrote down, so none of you know what they are, as z linear combinations of these three? If you add two times this one, to this one, you're going to get the two, seven, fourteen. You multiple by large numbers you'll eventually get some of the other ones.
Okay. So my claim, and I'm not going to prove this but I am going to kind of hand wave it at you, is that these three splines make a generating set for that triangle. So the triangle, the collection of all splines on the triangle, is a z module of rank three.
Now, what might we need to know that we have actually a generating set and that we cannot remove any of these? So I know we said this isn't a vector space, and this isn't a basis, but maybe we can use some of those skills. Anyone notice anything? About the properties of these three? So, if we were trying to find a basis what two properties would we need? We would need ... Yeah?
audience: It cannot all be a linear combination of other components.
Elizabeth D: None of these can be a linear combination or perhaps a z linear combination of other elements. Anything else?
audience: It spans the whole collection.
Elizabeth D: It has to span the whole collection. Is that what you were going to say as well? We'd have to prove that it spans the whole collection. What of those is easier to prove than the other? Which one is going to be easier to prove about this set? Linear independence, or spanning? Yeah. Why is linear independence easier? What have we built in to this example? We have a whole tone of zeroes. Right? This one in the middle has no zeros in it. This one have a zero at the bottom, this one has zero, zero and then a non-zero at the top.
So we have this built-in upper triangularity, so there's no way that any of these could be a linear combination of the others. They are z linearly independent. And in fact they're just linearly independent if you allow your field to be r or c.
So, triangle was rank three. And what I'm claiming is that we answered the question for the triangle. What are all of the splines on the triangle? Well they're anything you can get as a z linear combination of those three splines.
So we have our first theorem. Which is that the collection of algebraic splines on an edge labeled graph is going to be an r module. And I've got an extra word in the title, I've put a constraint on there that my ring r has to be commuted. Multiplication has to work that whenever I have a times b I also have b times a. You can always multiply it in either direction.
There's one more thing we did not discover about how to turn a collection of splines that you already have into a new spline. So I'm going to make this claim that the collection of algebraic splines, on an edge label graph, is not just a module, it's also a ring. So what does that mean I can do with two splines? What special properties does a ring have? Daniel?
Daniel: You can multiply them?
Elizabeth D: I can multiply them. I can take two splines and I can multiply them together. How would I really want to do that? Can you multiply it in any sort of cross-producty way? We're not going to do anything fancy like that at all. All I'm going to say is that if you have an edge, it looks like a and b, whose difference is in that set, that ideal. And I have another one, c and d. Well by multiplying b times d and a times c, ac and bd is also going to have the same property, as long as my ring is commuted. As long as I can multiply in one direction and in the opposite direction, then I'll always be equal. Okay.
So that's a pretty big restriction. As a mathematician what do you think my next question is going to be? This works for any commutative ring. What about non commutative rings? How can I still have these properties, which of these hold, if my ring is not like the integers but it doesn't have ... it's not like integers which can multiply in either direction, its more like some other types of things that multiply that don't commute. That you can't rearrange the order.
Who can think of an example of a ring, collection of things, that you can't change the order of multiplication? You can hear people whispering it. I know it's late in the afternoon. I saw a hand at the back.
audience: Matrices?
Elizabeth D: Matrices. Matrices don't commute. You may multiply one matrix times another matrix. You cannot change the order. So this summer, myself and three students; Dimitri, Charles, and Gabrielle, who [inaudible] College. Dimitri and Charles are Senior and Sophomore respectively. We are working on this problem and we started with the idea of matrices. What happens if you define things exactly the same way. Make a graph, label some ideals. But maybe your ideals, and all of your vertex labels have to be matrices. They can't just be integers, and they can't just be polynomials. Polynomials also commute.
Well we've got exactly the same idea. If we have a graph, and we have edge labels, there's no reason we can't ask a question such as, what matrices, I'm going to put them in the same order, a and b, have the property that a minus b is equal to sub matrix p times, for example, one, two, zero, zero.
So, what two by two matrices, a and b, have this problem? Well, if I change this, if I ask what matrices a minus b have, the property that there are some two by two matrix. That p times one, one, zero, one is equal to their difference. Is anyone, can anyone think of any two matrices that would work for the second example? [inaudible]
audience: Three, three, zero, three and two, two, zero, two.
Elizabeth D: Okay, three, three, zero, three and two, two, zero, two would work because then I would get the identity times this. Is there anything special about this matrix? The terminate is not zero. So what can we do with this matrix?
audience: [crosstalk] Invert it.
Elizabeth D: We can invert it. For, in fact, any pair of matrices, a and b. Any pair a and b will have this property. That there exists another matrix p, such that p times one, one, zero, one is equal to their difference. But that's not true in this first case. Sometimes we are going to have the right property and sometimes we're not. So those same two examples of ... three, three, zero three, minus two, two, zero, two, one, one, zero, one. Is there any matrix p, any two by two matrix, that you can multiply, one, two, zero, zero by p to get one, one, zero, one? Is it possible? Well we have a question about this matrix. What do we know about this one already? What important property does it have that let us do what we did before?
audience: [crosstalk] It's invertible.
Elizabeth D: It's invertible. This one's invertible. What about this one? It's not invertible. Can I take a non-invertible matrix, hit it with another matrix, and get something invertible? No. I've lost that information forever. Now, we've got a little bit of time left and now that I've gotten your brain thinking a little about some of the weirdness that comes out of ... when you take away commutativity, I want you to go back to those two big theorems we had. The two big theorems were that the ring of splines, the ring of solutions ... er, the set of splines, the set of solutions, is a module. That theorem stays true. But no longer can we multiply them.
Once we lose that commutativity, things start to break. There is one theorem that kind of broke open this field of algebraic splines. So instead of having actual curves, imagine we're looking at the algebra specifically. It's a theorem by Lauren Rose who's a professor at Bard. And it says if you have an n cycle, like that three cycle, that triangle we had, labeled by ideals and integers, then the collection of splines is going to be a z module of rake n. You're going to have the same number in your middle generating set as you have vertices.
In fact this can be extended and was extended by a collection of students at Smith College about five years ago. To not just cycles and n vertices, but any connected graph on n vertices. It's still going to have rank and.
audience: When n is the number-
Elizabeth D: ... When n is the number of vertices. Yes. rank n when n is the number of vertices. Thank you Linda.
So, does that hold when we don't have integers anymore? Well the answer is no. So one of the things that the four of us proved this summer, is that if you want a non commutative ring then you can build an edge labeling on a graph to result in any rank. You can build an edge labeled graph that only has the trivial spline. Rank one. You can build an edge label graph that only has two splines in it's generating set. You could have one that has n for every vertex. One generates it for every vertex.
And you can also go bigger. Once we are no longer in the integers, which are our principal ideal domain, then your ideals no longer have to be principled, they no longer have to be even finitely generated.
The second thing we proved this summer, is that if you do look at ideals that are principally generated, does that mean we can only have one thing that we can write, It's all the multiples of that one thing that happen to intersect at zero. Then if we label all the edges of our n cycle with ideals that only intersect at zero, we lose exactly one dimension in our module. We go from something that is ranked n on n vertices to something that is ranked n minus one. And it doesn't matter how we choose those labels.
Last thing I want to show you, is this picture which is really just a spline on a negative two to one and negative two to one. So this shape, as weird and cool as it looks, is only made up of these pieces of degree two. Now you can think of this in the algebraic picture, with the graph, as having nine vertices, nine regions, that have to line up on the boundaries. On y equals zero, y equals negative one, x equals zero and x equals negative one. So we've got this nice smooth shape using only simple polynomials.
So, this is bringing our whole story back from non commutative craziness into point of animation and drawing curves. So thank you for your participation, I know I dragged a lot of answers out of you today, and, yeah-
