Linear algebra from Brazil.

[@mikelolis3750]

Would love to see more undergrad olympiad problems covering linear algebra, analysis or pretty much anything not covered by hs olympiads

[@ohgosh5892]

A wonderful journey back to 42. Thanks to Brasil, Douglas Adams, and Michael Penn.

[@aqeel6842]

Always nice seeing a fellow HGTG fan.

[@rodrigodacruzribeiro7190]

Opa, brasileiro acompanhando o seu canal

[@O421]

sempre tem

[@igor7881]

Tamo ai

[@arthurprado1271]

Ssempre!

[@Joao-bv1te]

Eae Rodrigo

[@ricardoaw18]

galera da Unicamp manda um abraço!

[@brandongroth4569]

More college problems! I really enjoyed this one.

[@tahirimathscienceonlinetea4273]

It's a great proof . Indeed,you reminded me when I used to take this class since 2002.Great 👍👍👍

[@jozefmusil7279]

This is absolutely brilliant. You just revised my whole freshman algebra course in this video, and it was highly entertaining to watch. Thank you, I love your channel!

[@edwardlulofs444]

My linear algebra class was 49 years ago, so it was real old review!

[@mstarsup]

19:33 [42, 0; 0, 42], that's 42 x I: the "42 identity", which is the answer to the ultimate question of life, the universe, and everything! Thanks for enlightnening me!

[@alejandrosaldarriaga6061]

Great vid! There is also a solution that doesn't involve computing the eigenvectors : You can show by a quick induction that any power of A has integers on the diagonal and integer multiples of sqrt(5) off the diagonal. Thus, for B=A^n-(m+n^2)A to have only integer entries, it must be diagonal, and therefore have (1 0) and (0 1) as eigenvectors. We can show that for u and v the two eigenvectors of A, they are also eigenvectors of B. If B had distinct eigenvalues, then its eigenspaces would have dimension 1 and u would be on the same line as (1 0) or (0 1), which is not the case. Therefore, B must have one unique eigenvalue which leads to the equation 2^n-(-1)^n=3(m+n^2). The beauty of algebra 😌

[@MathElite]

This channel teaches me about linear algebra since I didn't take it in university love your videos :)

[@QweRinatrtY]

This channel teaches me linear algebra that I failed last semester

[@maxwellsequation4887]

Hey

[@MathElite]

@@maxwellsequation4887 hey

[@ANunes06]

@@QweRinatrtY I *highly* recommend Professor Strang's lectures, available on youtube for free. He LITERALLY re-wrote the textbook on Linear Algebra and presents and extremely insightful geometric approach to learning it. The lectures gloss over the "how do you perform this procedure" part (though it's still there), but it does focus on the conceptual framework. When I hear people are failing LA, it's usually because the class is taught as rote memorization. Here's how you take the determinate, here's how you diagonalize, here's how you find the inverse, here's a bunch of identities to memorize. Have fun. So having this notion that these spaces are all mutually orthogonal, that they describe hyperplanes and families of vectors in those planes, etc can really shore up the "why" behind those "how" answers. Good luck. Math is dope.

[@williamperez-hernandez3968]

For m>=0, the inequality 0

[@goodplacetostop2973]

17:13 Michael’s homework 19:38 Good Place To Stop

[@alnitaka]

It's a good place to stop because the answer to life, the universe, and everything is 42.

[@rbnn]

Just work directly in the eigenspace. A is diagonal with entries 2, -1 and A^2=A+2I. You can then compute the powers of A directly as 2^k,(-1)^k. This is much easier to express in terms of A. In other words, there was no need to compute P and P^{-1} explicitly. It is much easier to leave them uncomputed and you still get the same formula for n and m. All you need is the eigenvalues.

[@youknowwhatsreallysofunny]

42, we meet again.

[@jeanf6295]

You can go faster by using spectral projectors, for : P+Q = Id and -P+2Q = A, P = (2 Id-A)/3 and Q = (Id+A)/3 -1 and 2 being eigenvalues of A, P² = P, Q²=Q and PQ = QP = 0 (you can check this by using the fact that A is a zero of the characteristic polynomial of A). Then A^n = (-1)^n P+2^n Q, you can check that the diagonal elements are integers so you just need to make sure the off diagonal elements are set to zero, that is m+n^2 = (2^n-(-1)^n)/3. For the general case if the eigenvalues of your matrix are a0,a1,a2... then the projector on the associated eingenspace is given by the Lagrange interpolation polynomial applied to A. For instance for the a0 eigenvalue the projector is given by : P0 = (A-a1)...(A-an)/(a0-a1)...(a0-an)

[@ianloree2784]

Now I know what to look forward to next year!

[@jamesyeung3286]

Come to brazil

[@demenion3521]

since calculating the matrix-power took more than half of the video, i would recommend using the cayley-hamilton-algorithm for arbitrary matrix functions. that doesn't require the calculation of eigenvectors or matrix products

[@erikr007]

Yes, just find a recurrence for A^n = a_n A + b_n and observe the growth of a_n.

[@bsmith6276]

Sure, but in the context of an undergraduate math competition problem with a 2x2 matrix it makes more sense to do the diagonalization method which is a standard topic in an introductory linear algebra course.

[@demenion3521]

@@bsmith6276 that is true, i guess. but never hurts learning new methods to solve problems more easily :D

[@goodplacetostop2973]

HOMEWORK : Let k be the answer to this homework. The probability that an integer chosen uniformly at random from {1,2,...,k} is a multiple of 11 can be written as a/b for relatively prime positive integers a and b. Compute 100a + b. SOURCE : 2021 HMMT - Guts Round

[@reshmikuntichandra4535]

Which problem are you pointing out by saying "this" problem?

[@goodplacetostop2973]

@@reshmikuntichandra4535 « This » problem is the homework itself.

[@claudio9991]

Answer: k

[@goodplacetostop2973]

@@claudio9991 Technically the truth but that would be zero point during the tournament 😂

[@aadfg0]

If k is divisible by 11, the answer is 1/11, making k=101, contradiction. So we may write k=11a+b, 0 a = 9b = 90 -> k = 1000, which works. As a-9b b ≥ 1.5a for the 2nd option. This also means 7 > 20/3 ≥ 2b/3 ≥ a, so 6≥a≥1. Let a' = a/d, b' = b/d. Then c(11a+b) = (9b-a) -> (9-c)b = (11c+1)a -> (9-c)b' = (11c+1)a'. If c = 9, then a' = 0, so no solutions. Else, 10 ≥ b ≥ b' ≥ (11c+1)/(9-c), so c = 8, 7, 6, 5 don't work. On the other hand, 6≥a≥d=10-c, so c≥4, implying c = 4 -> d = 6 -> a = 6, a' = 1, b' = (11c+1)/(9-c) a' = 9. But then b = db' = 54 > 10, contradiction. Thus, we have shown only k = 1000 works without assuming the answer is unique.

[@ericzeisel3522]

platypus :a(z)b(w): I am stumped

[@hrs7305]

Wow never really knew there was a UG MO , more content like this please

[@mrmanning6098]

This problem makes one hell of a first impression. I'll give it a shot, but I am intimidated.

[@mrmanning6098]

1.5 hours later... and I've settled on (m,n) being either (0,1) or (-6,7) I really hope the video's solution is more elegant than mine. There is NO way I'm typing this one out Edit after watching: Yeaaahhhhh my solution was very similar to Michael's. I'm a little bummed there was no way around doing the 7 cases for n, but glad that I didn't waste my time grinding it out.

[@xCorvus7x]

Nice result for n=7.

[@nikitakipriyanov7260]

1:08 I don't see why it's surprising. Fibonacci sequence is comprised by the integer numbers, however we can also calculate it as (linear combinations of) powers of an irrational number, a golden ratio. I'd rather expect something like that. All in all, n=1, m=0 or n=7, m=-6 are the only solutions. If there were no requirement |m|≤n, there could be infinite number of solutions, with any n≥1 and with m = (2^n-(-1)^n)/3 - n². It's the 2^n vs n² game restricts our set. I easily proved the divisibility by 3 by induction (so that m is integer for any n≥1).

[@samuelbam3748]

16:33 i know it's a little bit late, but i found a way to get to this equation for m without many computation (in fact we only have to compute the eigenvalues of A). For this we define the polynomial f(A) := A^n - (m+n^2) A and assume that f(A) has only integer entries. We will now argue, that f(A) has diagonal form. Notice that A is of the form ( a, b*sqrt(5) // c*sqrt(5), d) where a,b,c,d are integers. If we consider all matrices of this form. We call the set of all such matrices M. M is closed over addition, matrix multiplication and scalar multiplication when the scalar is an integer (so this set is a Z-algebra). For addition and scalar multiplication this is clear. For the matrix multiplication we consider two matrices: ( a_1 , b_1*sqrt(5) // c_1*sqrt(5), d_1 ) * ( a_2 , b_2*sqrt(5) // c_2*sqrt(5), d_2 ) = ( a_1*a_2 + 5*b_1*c_2, (a_1*b_2 + b_1*d_2)*sqrt(5) // (c_1*a_2 + d_1*c_2)*sqrt(5), 5*c_1*c_2 + d_1*d_2 ) which is a element of M. In particular f(A) is a element of M. Because all the entries of f(A) must also be integers, f(A) must have diagonal form. (This may seem more complicated than just calculating everything, but if you already know a little bit about algebras over rings, then this is very natural.) Now we will consider the eigenvalues of A. Just as in the video we calculate the eigenvalues (so i will skip this part). The eigenvalues of A are -1 and 2. Now let v_1 and v_2 be eigenvectors of the eigenvalue -1 and 2 respectively. We don't actually need to calculate these eigenvalues. The only important thing is, that they are not (1,0)^T nor (0,1)^T. (This can be easily done, by "computing" A*(0,1)^T and A*(1,0)^T to show that they aren't eigenvectors of A.) By a basic property of matrix polynomials, we now that f(-1) and f(2) are eigenvalues of f(A) with eigenvectors v_1 and v_2 respectively. But since we know, that f(A) has diagonal form, the vectors (1,0)^T and (0,1)^T must also be eigenvectors of f(A). But now we have four pairwise linear independent eigenvectors (0,1), (1,0), v_1 and v_2. Because f(A) is a 2x2-matrix, this can only happen if they are all eigenvectors of the same eigenvalue. We now that at least two of them must be the same because f(A) has maximal 2 distinct eigenvalues. Now the eigenspace of this eigenvalue has dimension 2, so all vector in R^2 are in the eigenspace and f(A) has only 1 eigenvalue. We now that f(-1) and f(2) are both eigenvalues of f(A) and that f(A) has only one eigenvalue, thus f(-1) = f(2). This yelds: (-1)^n + (m+n^2) = 2^n - 2*(m+n^2) => m = (2^n)/3 - ((-1)^n)/3 - n^2 The rest of the solution would be the same as the video.

[@AmaymonF]

É Brasil porra!

[@Mateus-gd4if]

Thanks for the video

[@giladu.6551]

Woo a linear algebra problem! I was able to solve this one, that's so cool!

[@NaHBrO733]

17:13 the left one is odd and the right one is even

[@mushfiqurrahman_8971]

Hey Michael.I have a little question.This math problem was given in the "Bangladesh Mathematical Olympiad-BDMO 2021" Regional round. The problem is:Four non-negative integers (a1,a2,a3,a4) sum to 101010. No carry is performed while adding these numbers. How many ways can you choose (a1,a2,a3,a4,)? Hope you'll help :")

[@wesleydeng71]

@17:14 should switch the odd and even formulas.

[@idjles]

42!

[@goodplacetostop2973]

1405006117752879898543142606244511569936384000000000

[@luizhenriquebinharaarantes9901]

Quem ousa nos invocar

[@wellingtonbalmant5965]

We do this on quantum mechanics to elevated to n a operator.

[@TheJara123]

Please finish ramanujan series...please...

[@saydainsheikh3123]

This problem was so smooth

[@romajimamulo]

Huh, I solved it differently after diagonalizing, as you can factor on the left a P out, then factor P inverse from the right, and ask what the diagonals have to be for the product to be all integers, then what M and N get you those diagonals

[@patrickpablo217]

I'd love to see more of that

[@exatizandoaulas7856]

Slv do Brasil maicao da caneta :0

[@guzztavofc]

ao mesmo tempo em que eu odiava fazer todo esse trabalho em álgebra eu gostava porque saber fazer me fazia parecer inteligente

[@wowZhenek]

The other 2 (top left and bottom right) parts of the final matrix are kinda unreasonably omitted in the solution. Technically the value there could end up being a non-integer, but luckily it was an integer in the end.

[@wolffang21burgers]

Can be considered homework to prove that these are always integers. Hint: Factor out 1/3 and work modulo 3

[@selenamertvykh6481]

They're not omitted. (0, 1) and (-6, 7) are the candidate pairs, both of which give integer matrices when checked, which he did. He just skipped the computation.

[@krisbrandenberger544]

@ 17:23, the signs of 1 should be reversed.

[@cabra500]

Aí sim hein Maicão, essa aí foi pica

[@KaiqueSantos-xe1xu]

Kkkkkkkk

[@fhffhff]

(6 -7√5) (2√5 -1)

[@hans-juergenbrasch3683]

Or just use A^2=A+2I where I is the identity matrix, i.e. (2A-I)^2=9I

[@sergiokorochinsky49]

Both equations are true, but... where do they come from? Do you mind explain a bit?

[@hans-juergenbrasch3683]

For the first one either direct calculation or use A^2=trace(A)A-det(A)I and for the second one just multiply by 4 succeeded by a quadratic extension.

[@martinschulz6832]

17:13 He confused the signs of 1 in the nominator in the even and odd case.

[@tomatrix7525]

This is great

[@jagmarz]

16:23 (-1)^(n+1) = -(-1)^n but I had to watch a couple times to notice what happened.

[@goodplacetostart9099]

Bom lugar para começar em 0:01 ;)

[@ricardoaw18]

As always, awesome video Michael!

[@jerikogormantara444]

Question : at 14:13 why we must have that expression equals to zero? i think if it is equal to sqrt(5) that would be an integer too?

[@user-yv1qs7sy9d]

Yes, you are almost right. But notice that all the terms in the parentheses are rational, while sqrt(5) is irrational. Therefore, the expression cannot be equal to sqrt(5).

[@wowZhenek]

can't get an irrational number from the sum of rationals

[@jerikogormantara444]

ahh i see XD Thankyou for the comments

[@deyomash]

What if the off diagonal terms are equal to sqrt5. Then sqrt 5 times sqrt 5 is 1. Which is allowed. Or.. what if they are 1/sqrt5. Then off diag is 1. Which is also fine? Havemt calculated it through whether those are new slns or not thouhh.

[@wolffang21burgers]

The inside of the brackets is rational

[@deyomash]

@@wolffang21burgers yeah man thanks :)

[@arthurguilherme7685]

Cadê os BR's???

[@kevinmartin7760]

That (0 0) column added while calculating the eigenvectors didn't seem to do much.

[@ObviousLump]

he augmented the 0-vector to his matrix to find the eigenvectors, it's just another way of doing the simultaneous equations - the column didn't appear to do much precisely because it was (0,0) so when he was adding a bunch of multiples of 0 together, he keeps getting 0

[@nathanisbored]

he used it at 7:35 to create the equation with 0 on the right side.

[@blackhole3407]

And thats a good place

[@thgmansur]

...to stop :)

[@joaovictor-dp3rf]

Who else is bad at math but click on the video because it said Brazil?

[@verbumtech]

Eu sou um homem simples: vejo Brasil no título, então clico.

[@gymarcelo2822]

falou em Brazil?

[@sjp6839]

This went right over my head. I watched it till the end and understood nothing

[@user-mn9lj6to4i]

m = -3 if n=2????? If n=2, then m = -7/3

[@ulysses_grant]

Linear algebra from Brazil: 1 + 1 = 3. Welcome to Brazil.

[@luizhenriquebinharaarantes9901]

Welcome to Brazil. Rules: there are no rules

[@ulysses_grant]

@@luizhenriquebinharaarantes9901 Rules: HUE.

[@lksclaudino]

Essa questão é da IMO ou OBM? Saudações!

[@viniciusdionizio4807]

OBM, 2º fase de 2016 mais precisamente

[@lksclaudino]

@@viniciusdionizio4807 tks

[@kristianwichmann9996]

Surprise 42

[@joaopimentel6380]

#XUPAIME

[@lksclaudino]

Pq

[@zemyaso]

I hate matrices, I learned them but never learned where to use them and they are pretty complicated, idek how they came up with the rules

[@patrickpablo217]

Oh man, you are missing out. They are the best. Lots of places to use them. A bunch of problems students typically solve a different way can be solved more simply with matrices. Also just great fun in their own right. Even just 2x2 real entried matrices can model real numbers, complex numbers, dual numbers, and split-complex numbers. They give linear transformations of the plane (rotations, reflection, shear, etc). It just goes on and on.

[@OuroborosVengeance]

I think he doesnt like teaching linear algebra as much as he enjoys teaching some other subjects. Thats my impression

[@tutordave]

Well of course the answer is 42. Everyone knows that.

[@nathanisbored]

Geez this seems like a miserable problem