Mathematics - 2021-09-09

Euler 2

03:04

shintuku

03:50

Suppose $y = \phi(x)$ is an implicit function of $y$ for $f:\mathbb{R}^2 \to \mathbb{R}$

any way to think geometrically about the fact that $\frac{\partial \phi}{\partial x} (a) = -\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y}} (\langle a, \phi(a)\rangle)$?

copper.hat

04:24

@shintuku If $f$ was linear (affine) what would the formula be?

I just came across an old answer of mine that contained egregious errors. Very annoying.

shintuku

e.g., if the graph of $f$ was a plane?

copper.hat

Suppose $f:\mathbb{R}^2 \to \mathbb{R}$ was linear. Then it must be of the form $f(x,y) = ax+by$. What would $\phi$ be then?

Note that ${\partial f(x,y) \over \partial x} = a$ and similarly for the other.

Koro

I think that "steadily increasing" and "monotonically increasing" mean the same thing. Am I right in saying that?

shintuku

we'd get $y = \frac{-ax}{b}$

copper.hat

The term steadily increasing is a bit ambiguous, monotonically increasing has a (reasonably) well defined mathematical meaning.

@shintuku That should give some geometric perspective...

Koro

04:31

@copper.hat Hi copper! I didn't know that steadily was ambiguous. :(

shintuku

hm, i'll continue meditating on it, thanks

Koro

@shin: I think some gradient should turn out to be perpendicular to some level set, if I am not mistaken.

copper.hat

@Koro I would think it ambiguous in a mathematical context. I could be mistaken too.

Koro

I checked my book again, steadily increasing/decreasing is defined exactly as one would define monotonically increasing/decreasing so both are the same. :)

copper.hat

I have never seen the term steadily increasing used in a mathematical context.

Ted Shifrin

04:39

I agree with @copper.

Most likely this is not a serious mathematics text.

Koro's comment about the gradient of $f$ being orthogonal to $f(x,y)=c$ is the whole point. What then is the slope of the curve at a point?

Other than that, the rigorous argument for the formula is just chain rule.

This is, in fact, part of the implicit function theorem.

copper.hat

@shintuku The main point of the linear function is to note that $\phi'(y) =- { { \partial f(x,y) \over \partial x} \over { \partial f(x,y) \over \partial y} }$.

shintuku

@TedShifrin right, this is to prove the properties of the gradient on level curves denoted by the implicit function. i'm just wondering how come someone would get the idea that it is an application of the chain rule

@copper.hat i'm working on that idea, trying to do plane visualizations hehe

copper.hat

because $f(\phi(y),y) = 0$.

while the proof is a little detailed, the idea is straightforward. Just approximate by linear and solve.

Ted Shifrin

Actually, it’s $y=\phi(x)$ here, isn’t it?

The chain rule proof appears several times in my videos.

copper.hat

Ah sorry, I goofed.

Ted Shifrin

04:45

If you know about directional derivatives, this is a horrid way to understand the gradient.

Most multivariable treatments are very poor.

shintuku

hm, you do have some videos on the implicit function theorem, i'll recheck those. thanks for the reference

copper.hat

The implicit function theorem has a cute application (in appropriate context, of course) to showing differentiability of the solutions of an ode.

shintuku

btw, were you suggesting understanding it through directional derivatives instead? @TedShifrin

Ted Shifrin

Absolutely.

shintuku

hm, how would that go? (if you have time of course, and if it's covered in the lectures i'm going through them atm)

Ted Shifrin

04:53

Yes, the lecture on the gradient explains it all. If you want rigor, go back to actual definitions of differentiability.

shintuku

alright, thanks!

Koro

05:08

@copper.hat In the text A course on Pure Mathematics by GH Hardy, the term is used :)

Ted Shifrin

05:25

Almost A century old …

Koro

yes :)

copper.hat

A lot of stuff has improved since then.

Koro

steadily increasing sounds cool though :)

Kumar Shuvam

06:27

Hi!

If I have a diagonal matrix of order n, let's say what should be the maximum possible number of zeroes in it?

@robjohn Sorry professor, it has been killing me for a while. I know it should be n^2- n but let's say if it is zero matrices then it should be n^2 right? Why don't we take the worst-case possible i.e. considering zero matrix?

robjohn

@KumarShuvam what do you mean "order n"?

Kumar Shuvam

I mean n*n matrix

robjohn

is that "rank n"?

Kumar Shuvam

no It is n by n matrix

robjohn

well, if it really means "$n\times n$", then there are at most $n^2$ zeros. If it means "rank $n$", then there are at most $n^2-n$

Kumar Shuvam

06:34

What is rank professor?

robjohn

your text has not mentioned the rank of a matrix?

Rank (linear algebra)

In linear algebra, the rank of a matrix A is the dimension of the vector space generated (or spanned) by its columns. This corresponds to the maximal number of linearly independent columns of A. This, in turn, is identical to the dimension of the vector space spanned by its rows. Rank is thus a measure of the "nondegenerateness" of the system of linear equations and linear transformation encoded by A. There are multiple equivalent definitions of rank. A matrix's rank is one of its most fundamental characteristics. The rank is commonly denoted by rank(A) or rk(A); sometimes the parentheses are not...

Kumar Shuvam

No!

robjohn

If the matrix is invertible its rank is the same as each dimension

so an invertible $n\times n$ matrix has rank $n$

Kumar Shuvam

Oh! I understand it now :)

Thank you professor :)

SmokenSieEinBitteChebaHitBits

I'm implementing arrow code now

Will post screenshots when it's working

Mircea

06:46

Hey everyone!

SmokenSieEinBitteChebaHitBits

@Mircea hey homie!

^_^

Mircea

I have a quick question and I was hoping someone in here could help

SmokenSieEinBitteChebaHitBits

let me guess, it's about math

Mircea

indeed it is lol

SmokenSieEinBitteChebaHitBits

You've got major math addiction issues, and you need help getting your fix

shoot

Mircea

06:48

Do you guys know which of these grows faster?
C^O(n^2) or n^O(n)

you got me lol

where C is a constant, like 2

SmokenSieEinBitteChebaHitBits

@Mircea are you looking for proof?

of one or the other

Mircea

not really

one or the other

SmokenSieEinBitteChebaHitBits

Then just plot them using desmos

Mircea

I was hoping someone in here had some intuition that would spare me the numerical calculations:-)

SmokenSieEinBitteChebaHitBits

The crossing point of the functions will depend upon the three constants involved

Intuitively the one on the right grows faster

Mircea

06:50

really it's (2n-3)^O(n) vs 4^O(n^2)

SmokenSieEinBitteChebaHitBits

Let $C \gt 1$

Now let $D$ be the constant of $O(n^2)$

And $E$ the constant of $O(n)$

So you want to prove that for some $n \gt 0$, you have $C^{D n^2} \lt n^{En}$

Take the $\log_C$ of both sides

Mircea

for all n greater than some N actually

SmokenSieEinBitteChebaHitBits

Well I think that would follow after you just show that one such exists

Mircea

alright

SmokenSieEinBitteChebaHitBits

That gives you: $\iff Dn^2 \lt En \log_C(n)$

Because $\log_C$ is increasing

and thus order preserving

Apparently then the one on the left grows faster

since the one on the right is $O(n \log n)$

and the one on the left is $O(n^2)$

Mircea

06:57

hmm, yeah

SmokenSieEinBitteChebaHitBits

Counter intuitively it seems (to me)

Did that help you?

Mircea

yes, actually! I think this is the result I was hoping for :)

and yeah, good idea taking log on both sides

SmokenSieEinBitteChebaHitBits

Well also make sure you graphically plot an example for $C, D,E = 2$

Mircea

I will do!

SmokenSieEinBitteChebaHitBits

To double check the argument

Mircea

06:58

yeah, thanks!

SmokenSieEinBitteChebaHitBits

You're welcome, mon

Fight the power

user27286

Hello @robjohn Lend me some of your intelligence.

Actually if all of the people in this room lend half of their intelligence to me, I would be quite decent.

Mircea

haha

SmokenSieEinBitteChebaHitBits

@Mircea are you studying algorithms or analytic NT?

Mircea

well, I was trying to prove a combinatorial conjecture of one of my professors

disprove*

and I think I just succeded :-)

SmokenSieEinBitteChebaHitBits

07:02

Nice

What's the conjecture?

Is it to do with graph theory?

Mircea

His conjecture was that you can turn a full binary tree with leaves numbered from 1 to n to any other full binary tree with leaves from 1 to n using only tree rotations and swaps in O(n) time

and I turned this into a grapg theory problem by noticing that if every tree is a node then it has exactly degree 2n-3

SmokenSieEinBitteChebaHitBits

What do they mean by "turn a full binary tree with ... into another one"?

Mircea

O(n) steps, sorry

where each step is either a tree rotation, or swapping one node's left and right subtrees

SmokenSieEinBitteChebaHitBits

Does this binary tree contain numbers?

Mircea

only in the leaves

you can think of it as combining all numbers from 1 to n via some binary operation

SmokenSieEinBitteChebaHitBits

07:06

So since it's a full tree, it looks just like a perfect pyramid?

Mircea

that is associative and commutative\

sorry, I meant full as in each node has either 2 or 0 children

SmokenSieEinBitteChebaHitBits

I c

Mircea

it's actually better to think of this in terms of ways to combine n terms via this one binary operation

and each step is applying commutativity once or associativity once

and the conjecture is that you can turn any such term into an equivalent term in O(n) steps, where a step is either an application of a commutativity law or one of an assoc law

SmokenSieEinBitteChebaHitBits

Okay, so take trivial tree with 1 node

clearly the conjecture is true for that case

1 leaf node

Mircea

yeah, but for suffficiently large n it breaks down it seems

if you represent all such trees with n numbered leaves by a node in a huge graph then each node will have degree n-1+n-2

because you have n-1 internal nodes that you can swap at, and n-2 internal edges that you can rotate the tree along

SmokenSieEinBitteChebaHitBits

07:11

Welp, I'm confused, back to coding

Mircea

sorry, I guess I made things harder

SmokenSieEinBitteChebaHitBits

No, you did good. I just am not very well versed in your area

Mircea

a whiteboard would certainly help :-)

SmokenSieEinBitteChebaHitBits

yes, like ziteboard

Mircea

fair enough

SmokenSieEinBitteChebaHitBits

07:12

online

Mircea

what's that?

SmokenSieEinBitteChebaHitBits

You know how there are a ton of collaborative drawing tools, ziteboard is one of the nicer, simpler, working ones

Use q.uiver.app for CD's

but has no collaborative invite feature

Mircea

app.ziteboard.com/team/410959f7-cd9a-4637-8ca7-07614aa1dde9

here are the 2 operations you can do on the trees

SmokenSieEinBitteChebaHitBits

@Mircea

youtube.com/channel/UCkwSzrP8pr2uN4Mu04ktipg/videos

It's the one called Abstract Spacecraft

Mircea

I was half expecting a rick roll

SmokenSieEinBitteChebaHitBits

07:24

Did a lot of work on it today so it's a lot further than that feature wise

Started arrow code today as well, which is really adapting old code to new project since I wrote bezier arrow code before with all the auto positioned text and control points posititing nicely along node sides

Mircea

nice, looks interesting

I'm not sure what's supposed to happen though

SmokenSieEinBitteChebaHitBits

Well, you'll see when it's all done

and released

Lots to code on it

Mircea

haha, goodluck

SmokenSieEinBitteChebaHitBits

basically allows you to peruse CD's (commutative diagrams) and math definitions in general

Mircea

interesting. Can you let me know when it's done?

SmokenSieEinBitteChebaHitBits

07:26

It's a spacecraft for viewing math abstractly

@Mircea send an email to fruitfulapproach (google)

Mircea

just send me an email at osebe2 (at) illinois (dot) edu

SmokenSieEinBitteChebaHitBits

and I'll keep a list or you could just star the repository on github

Mircea

gotcha

SmokenSieEinBitteChebaHitBits

Do you have a github account?

Mircea

yeah, MirceaS

SmokenSieEinBitteChebaHitBits

07:27

Okay, let me post link here

github.com/enjoysmath/abstract-spacecraft

That's the code, description is old though

Mircea

I'll keep an eye on it :)

I gtg now

SmokenSieEinBitteChebaHitBits

K, star the repo!

Mircea

see ya later\

SmokenSieEinBitteChebaHitBits

I like stars ...

Mircea

will do

lol

SmokenSieEinBitteChebaHitBits

07:28

L8er tater

Mircea

that's cause you are one

;)

SmokenSieEinBitteChebaHitBits

Coolio

shintuku

@Koro hey Koro, earlier you said that, if $y = \phi(x)$ is an implicit function of $y$ for $f:\mathbb{R}^2 \to \mathbb{R}$, the fact $\frac{\partial \phi}{\partial x}(a) = -\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y}}(\langle a, \phi(x)\rangle)$ was related to the property of gradients being orthogonal to level sets

how come that fact reminded you of that?

SmokenSieEinBitteChebaHitBits

Probably because of determinant

ad - bc = 0

shintuku

hm.. sorry if this is obvious, but why is the determinant involved here?

SmokenSieEinBitteChebaHitBits

07:36

Is the fraction $(\partial f/\partial x)/(\partial f/\partial y)$ a fraction?

If so, bring the denominator to the left

and you get the form AD - BC for appropriate assigments of the variables

@shintuku

shintuku

hm, $\frac{\partial f}{\partial y}(\langle a, \phi(x)\rangle) \frac{\partial \phi}{\partial x}(a) - \frac{\partial f}{\partial x}(\langle a, \phi(x) \rangle = 0$ does look like a determinant

but, does this have any conceptual relationship with the gradient and level curves?

again sorry if this is obvious

SmokenSieEinBitteChebaHitBits

My mistake, I thought there were some relation with orthogonality

and 2D det

If you convert the dot product into a determinant maybe...

then dot product of two 2-3D vectors is zero iff the vectors are orthogonal

So <a,b>.<d,-c> = ad - bc

What is $\phi(x)$ defined as?

shintuku

it is the implicit function of $y$ defined $y = \phi(x)$ from $f:\mathbb{R}^2 \to \mathbb{R}$

SmokenSieEinBitteChebaHitBits

How do $f, \phi$ relate in this context?

shintuku

by virtue of the implicit function theorem, $f$ satisfies the properties for $\phi$ to be the implicit function of $y$. so visually speaking the graph of $\phi$ looks like $f = 0$

Koro

08:13

@shin: $f(x,y)=c$ is a level set of f. Gradient of f =0 so $1.f_x +f_y y’ =0$ which gives $y’=-\frac{f_x}{f_y}$

robjohn

08:27

$0=\mathrm{d}f=\frac{\partial f}{\partial x}\mathrm{d}x+\frac{\partial f}{\partial x}\mathrm{d}y$ so $\frac{\mathrm{d}y}{\mathrm{d}x}=-\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y}}$

another take

love_sodam

One problem I saw today is to compute $147^{247}\bmod 347$ by an application of Egyptian multiplication method

Ancient Egyptian multiplication

In mathematics, ancient Egyptian multiplication (also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication), one of two multiplication methods used by scribes, is a systematic method for multiplying two numbers that does not require the multiplication table, only the ability to multiply and divide by 2, and to add. It decomposes one of the multiplicands (preferably the smaller) into a sum of powers of two and creates a table of doublings of the second multiplicand. This method may be called mediation and duplation, where mediation means halving...

Here's how they did. Basically factorize the number and add up

Using this, any bright ideas to compute that?

Leaky Nun