Margot Gerritsen on "Linear Algebra - the incredible beauty of math"

It's actually delightful to be here

So thanks to for inviting me.

I am a mathematician. And you may not

associate mathematicians with people that

love art.

But I happen to think that mathematics is

the most beautiful thing on earth.

And I want to convince you today that

that's the case.

Now we're going to use a few tricks.

So we're not just going to stare at

equations. I get really a wonderful

feeling inside of me when I stare at a

system of equations. But I'm not expecting

you to have that same sort of feeling.

So what I'd like to do is provide some

color and some illustrations of the

systems of equations.

Now, matrices what are matrices, you know?

Why, as a mathematician, do I love them so

much? Well, let me just give you a little

bit of a feel of the sort of problems I

work on. I'm a computational mathematician

And I really like things to do with fluid

flow. So you give me a fluid, I like to

simulate it. So I've done work on

coastal ocean flows

I've done work on oil and gas flows

I've designed sails for the American cup

For those of you who know about America's

cup Right now. Not for this particular

race but in 2000 and 2003

but in all of these things are eminent

flow I'd like to simulate it.

and to simulate this

we set up a really large system of

equations relating pressures at all

sort of different points in the flow

fields and velocities

and we need to solve it

and ultimately the system of equations

leads to something called a matrix.

I'll show you an example.

But also, because I like matrices so much

In these matrix equations

I can use that same

knowledge to help with example

of the design of a search engine.

Or a recommender system.

And that may sound really funny to you,

but it's exactly the same math

behind it.

And the math behind it,

is this matrix stuff.

Now for some of you,

matrices may actually have to do

with something like this.

Do you recognize that made with

the movie the matrix

which I happen to love.

But has nothing to do with my field.

But if you type in matrices

or you type in matrices for

engineering applications

in Google, you get millions and millions

and millions of hits.

And you can see lots of different

applications, which some how use this

This is just a snap shot

of the images

the first place of images you see

when you type in matrices.

And when you go look at this,

you see matrices come up in

flow mechanics

but also in structural mechanics

you see it come up in social networks

you see it come up in neurology,

biology, so many different application areas

use this matrices.

And so, officialization of them is nice

also because sometimes, when we stare

at a big matrix

which is just a table with numbers,

it's very hard to discern patterns

But sometimes when you start visualizing

them,

you can get a deeper understanding,

also of the underlying math

and the underlying physics.

So, let's start with a little bit of

algebra.

So say, I have four unknowns, that I want

to compute. So this brings

you back to, maybe, high school algebra

If I have four unknowns I want to

compute,

in this case they're called

W, X, Y and Z

We always use these sort of variables

because mathematicians aren't

that creative

alright, so we use things like

X1, X2, X3

and so on, right?

And so if I want to solve for

four unknowns,

I need four constraints.

Four equations

that tell me how they relate to

each other

and here I just made up

four of those

K?

Now one of the things that you see,

is that there is

some empty spots here.

And you also see that there is

this pattern; W, X, Y Z

They are always written in the

same pattern.

Sometime there is a one in front

of it.

1 times W, 1 times X

and sometimes there is nothing.

Which really means there was a zero

in front of it, right?

But as a mathematician,

I look at these, I'm a very organized

person

So I write all of these things in

this particular order.

And I see there are four equations, and

each equation has a bunch of

coefficient corresponding to W.

Bunch corresponding to X,

to Y, and to Z.

And all I really need to remember

for the system, is these coefficients.

Right? As soon as I fix the order,

all I need to remember are these

coefficients.

So what I'm going to do,

is I'm going to re-write this

a little bit.

And I'm going to create,

this table here, which has these

coefficients, now I left out

the zeros.

Now we are also very lazy,

mathematicians.

Zeros, we never write down.

Also, because with these

large systems of equations

that we have to deal with,

say for recommender system

or page rank, or search algorithm

there are many, many many zeros.

So we leave them out.

K?

But, arguably, all that's really

important to me, for this particular

system, whatever that represents;

maybe it's pressure of velocity

relationships in fluid flow,

maybe it's a friend networking

algorithm. I don't really care.

All that's really important

is this table with the numbers

this table, that we call a matrix

K? So that's the matrix.

Now

sometimes we use very simple

visualizations.

Mine is called, Spy Plot.

And all I do

is, you know, I had all these ones

and everywhere a one appears

I simply put a little dot.

K?

So in this case I'm not so interested in

what size these coefficients are,

whether they're one or two or ten

or minus two-hundred.

I don't really care.

I just want to know where there are

non-zeros

because these non-zeros

give me exactly, how these things relate.

If i have a non-zero right here, and a non

zero there, I know that W and Y are an

equation together.

And so, the patterns, of these non zeros

give me information about the system.

Does that make sense?

And so the simplest way,

because again you know the start

is very simple, and not super creative.

In the beginning, we just put a little

dot. And therefore very large systems

of equations we may get things like this.

So this is called, "Spy plot."

So this is just a matrix, with dots

where ever there is a non zero

and you see there are patterns,

now that I can see.

And actually these come from a network

a matrix can also represent a network,

which we'll see in a little bit.

They're Stanford Networks.

This is, I think, uh Standford as a whole

And this was the Internet.

And all the pages in Ero Astro

that we crolled in 2004 to create those

"Spy plots."

And looking at this, I can see

because I know a little bit about how

these were created,

That here are clusters of websites

that are correlated very strongly

so they keep on referring to each other

and internally. And they're not very

much connected to this

so that's central administration.

They only talk to each other.

Not so much to others.

And they can look at this, and they

can discern

organizational structures.

And it's amazing how you can

use these things.

Right?

And of course, some other equations

lead to more interesting patterns.

This is a "spy plot"

Of a particular

equation, or system of equation

that looked at an oil resovoir modeling.

And when look at these particular

patterns, I can say something about

the behavior, not that much

But it's still, you know, resonably

pretty.

And then what I could do,

if the actual non zeros change in size

so some if they're bigger than others

I could give them a color,

depending on the size.

Now we're getting very artsy,

for a mathmatician.

Which is pretty amazing.

And I get things like this.

Now there are many more interesting ways

to do this though, and this is really

what I'd like to show you today.

Is to use graphs.

So we're going to go back

I hope

Yep.

To this matrix.

OK?

Now I want you to focus on, ehm, this

equation here, this equation had W

Plus zero times X

X doesn't play a role

Plus Y times nothing, times Z

Is equal to one.

That's really where that came from

And from this, I know that there is

a connection between W and X.

They're in the same equation.

Right?

W and Y, sorry. W and Y.

I thought you said "Why," so I tried to

explain it again. (Laughter).

Because there is an equation connected.

But W and Y.

So all I'm going to remember now is

that there is that connection.

Now W is here in this location and Y

is in this location. And this non zero

I can see is really connecting

those two together.

So if I say I have a non zero in the

first row and the third column,

I know that W and Y are connected.

If there is a non zero, say, in the

second row and the fourth column

I know that X and Z are connected.

And that's what I am going to do.

So I am just looking at these non zeros

You know, these ones off of the diagonal

The one that's saying W is connected

To itself, but this one

signifies a connection between W and Y

This one between X and Y

And so when I look at those non zeros

I could also write it like this like a

little graph.

Now I see one and three are connected.

The first element, and the third element,

That is the W and the Y.

Now I measure W, X, Y and Z.

One, two, three, four.

And so one and three are connected,

there is another equation that connects

Two with three, and there is an equation

that connects two and four.

And there is an equation that connects

three and four.

These are the connections that I have

between these unknowns.

Now I made it very abstract, right?

Because I had this system of equations

that told me exactly what these equations

were. And I'm just removing that

and say, I'm just interested now in

connections.

What is influenced by what?

If W and Y are in an equation together,

then the size of one influences

the size of the other.

That's all I am interested in now.

Now vice-versa, if I had a network like

this, a connected graph, maybe

friends. Friend one is connected to

friend three and three is friends with

four but four is not friends with one,

then I could replace that network

with this graph with a matrix.

Right? I could go from one to the

other. But now I'm going to take these

matrices, maybe they come from

fluid mechanics. And I have ten million

columns this way, and I have 10 million

rows this way. This is what we call small

simulation.

So I have a lot, and I'm going to create

a graph out of that. Right?

Now when I look at that graph I can see

these connections, but of course

you immediately say, well I control this

in all sorts of different ways.

You see the same graphs, just drawn

a little differently.

And then the question is, well

which drawing do you prefer?

Which makes it clearest, what the

connections are.

To you.

Just by looking at it, what do you think?

This one?

(Audience) "That one"

Yeah I like this one a lot too.

So then, of course, this is just

with four, right? I just had four

One, two, three and four in connections

Now suppose I have 10 million

With maybe 50 million in connection total

and, and I ask my student, make me

a nice looking graph.

So they can look at it and maybe

discern a little bit of information about

fluid flow.

Right?

So that would be very hard to do, by hand.

So if I had something like this.

And I say, now give me something

that looks very good because now there

are all these overlapping connections.

So then, it's an interesting thing

How do I pull a part this complicated

looking graph and make something

where structures and connections

are much more easy to see.

And that's what I want to show you,

because we can do this. Now you may say

this is a made up example.

What has a messy network like this?

Well let me just show you.

Just one example.

Don't just thought off the web.

I just looked at work by Allera Hall.

And I looked at Saga's from Iceland,

and he published this.

So these are the connections between

various sagas.

Obviously this is very messy.

And I think he should be using

our software.

(Audience Laughter)

Maybe I should send it to him.

So these things happen.

So now the question is,

if I have a bunch of nodes

and I would just place the nodes,

one, two, three, four, all the way

to 10 million

and I have connections between them,

how do I figure out how to pull them

apart and put them on a two

dimensional piece of paper.

So that I have a nice view.

Okay? So how would you do it?

(Audience "grab one and pull?")

Somehow you need - no first of all you

need two nodes that are really

strongly connected to come close

Right? So if node one and two are strongly

connected, maybe because there was

a big non-zero in this matrix then

I want them to be close.

Right? And if one is connected to two

and two to four and four to 17 and

17 to 300, I don't want 1 and 300

to be too close because there is

four degrees of separation.

Right? So the question is, how do I do

that?

So we have these nodes, and

we have these lines connecting them.

K? Now what we're going to do is

two things. Each of these lines will

imagine it's a spring.

So when we pull things apart,

they pull back.

Right? And the size of the spring -

the strength of the spring, Guess what?

That's determined by what?

By the strength of that Non-zero.

Right? OK, that's nice. But what would

happen if I did this?

If I had all of these nodes and I

put springs on them, and let them go.

What would happen if I didn't do anything

else?

Would they (shooo)? All get together?

I don't want that either.

I don't want them all to cluster,

so they're not allowed to get too close.

So how can I make things - I need some

kind of repelling force. So when they get

too close, they're not allowed to.

So what do I do?

I give every node an electric charge.

So that they repel each other.

K? So now I have a whole network of

balls attached to springs,

the springs have stiffness, the balls

have an electric charge.

And I let the whole thing drop on the

floor.

Because I want it two dimensional, right?

And I let this thing organize itself.

So it comes to an equilibrium shape.

That's always minimizing some sort of

energy.

Right?

It's beautiful, these systems do this

automatically.

And I just let them organize themselves.

So it would look something like this.

We start with this,

we let it drop,

and now it becomes this.

So it's exactly that same configuration.

Now here we've cheated a little,

how big you make that electric charge

and how big you make the strength of

the springs.

That determines what stuff you get out.

So afterward, we need a lot of changing

to make it look beautiful.

K so this looks really easy.

But some of the pictures I'm going to

show you took a long, long time to create.

Because there was a lot of

twiggling. Put a little

bit more spring strength here.

And more repulsive charge there.

But when you look at this it's beautiful

structure. And it shows you very naturally

these clusters and when you stare at

these structures

you can really get some information

about the underlying system.

No matter where this comes from.

Now let me show you some

really beautiful examples.

In much larger systems than this.

This is a financial portfolio

optimization.

So this is one of the matrices you

would have come up in one of the

simulations or computer programs you

would have in financial portfolio

optimizations. This looks much better

than what you would imagine. From the

2008 problems.

Right?

How did we know that this was behind it.

This one, is another type of program

that we often have in optimization.

Called "prodredic(sp?)" programming.

It's the matrix from one of those

simulations, here is the close up.

So they're very intricate things.

These are just two dimensional

patterns. But of course, it looks a little

bit three dimensional.

You can also do these things in 3D

but it is much harder to vision.

This one, is from electrical engineering

It's a circuit simulation.

So we also call this the porcupine.

And this is a close up

It's not a super high resolution image,

but it gives you an idea.

This is another linear programming problem

That comes from some sort of optimization

problem. And I forgot which one this is.

And this color is often the strength of

connection. You can also use it in also

different ways.

And my friend, Tim, who created this,

uses colors so the pictures look really

nice. (audience laughter).

So we can play with these colors because

there is lots of different ways to color

this.

I have to admit, this is pretty nice.

I'll show you some others.

This one, is part of my field, it's

a matrix of an ocean, of shallow water.

So where the depth of the water is much

less than the width of the area.

Now, this doesn't nearly look as nice.

But the matrix that comes out

is very unstructured, but still,

it almost has the same feel to it as

water. That's of course why we made it

green and blue.

Now this is a close-up.

This one is another linear programming

problem. It's my favorite. It has quite

beautiful structures.

And this one is actually a social network

Which we have labeled, the poppy.

And here, where you see poppies

of flowers, they're really clusters

of friends.

They are strongly connected friend

networks, within this large social

network. So you can have a lot of fun

with this. Right?

We played with something else as well.

And I brought a poster.

Because Allison was going to show her

beautiful work, so I wanted to show

that we also do nice things.

Here is my artwork.

Sometimes I ask people, what are they

looking at, and they say I'm looking at

some sort of network or graph. But

this is the LCSH.

Library of Congress Subject headers.

So this is the library system that we use

in almost all libraries of the world

And what you are looking at are

library main categories, and their sub

categories, and how everything

is linked together.

Now the LCSH asked us in 2005, me

and a group of my students, to help

them understand the structure.

So here are cataloggers who have

worked on this categorizing

for decades. But they have never seen it,

they just put it the data. So we

used exactly the same kind of program

that you just saw. We call it the galaxy.

I will make sure they get the link

so they can play with it. You

can go in and zoom in and click on

the node and it will jump up

and show connected notes, and this

is a way to browse. What is also really

funny here, is you see this whole mess

in the middle, because it is very strongly

interconnected stuff, we but in words

where the connections were strongest

But the library also used it to find

lazy cataloggers. Because look at this,

we call this a Supernova. This is

Japanese Antiquites. And it has one main

category, and a whole bunch of sub

categories. But the catalogger did

not interconnect the sub-catagories.

So we have Japanese Antiquities,

and 140 things attached to it,

but how they related, he or she did

not relate it. So the library can look

at it and say, we really should do

something about this. Because the more

messy it looks, the better it is for

browsing purposes. But we just

thought it was a beautiful picture.

This took a long, long time to create,

we had to think about the colors,

and how the nodes.

And now we are looking at ways

to put this in 3D, so you can

truly fly through the galaxy.

And you can do the same with

Wikipedia, and other networks that you

have. You can say let's go on a flight

through my social network.

And you can see who is stronger connected

than you are. Anyway it is a lot of fun

to play with. So I'll make sure you have

this link, and I'll take any questions you

may have.