Here's another technique that uses Cayley-Hamilton. We know that A^2 - 3A + 2I = 0, which tells us that A(A-2I) = (A-2I). By induction, we know A^n(A-2I) = (A-2I). Also, since these are all powers of A, this expression commutes: so we also have (A-2I)A^n = A-2I. Now, we know that the columns of A-2I are invariant under A^n, giving the equation (-6a + 2b, -6c + 2d) = (-6, 2) (the other column gives us a scaled copy of this). We can also use (A-2I)A^n = (A-2I) to get (-6a - 15c, 2a + 5c) = (-6, 2) and (-6b - 15d, 2b + 5d) = (-15, 5). We can scale to get the 4 equations 3a - b = 3, 3c - d = -1, 2a + 5c = 2, 2b + 5d = 5. If we add the first, second, and fourth equations we get 3a + b + 3c + 4d = 7. I want to see what the space of possible linear combinations is for this; it can't be all possible linear combinations, as the value of a for example definitely does depend on n. I'll leave it as homework since i should really be studying for my quiz... Edit: The space of possible linear combinations is 3-dimensional, spanned by any 3 of the 4 equations given. This means there is a large family of linear combinations of the entries of A^n that are constant, which i wouldn't have expected but is pretty cool to find out.
I used matrix diagonalization (eigenvalues and eigenvectors) Characteristic equation can be easily found by trace and determinant Inverse of 2x2 matrix also can be easily calculated
I did the diagonalization method and the final exponented matrix comes out to: 6-5k 15-15k 2k-2 6k-5 where k=2^n where n is the exponent on the matrix. So long as you cancel out the ks with your linear combination, it'll always sum to the same thing. This happens because the diagonal matrix, after diagonalization, has a 1 in the top-left; otherwise you'd have only two degrees of freedom.
essentially you worked your way there manually, but from my experience the most useful application of cayley-hamilton is that any matrix function f(A) can be written as a polynomial of degree one less than the dimension of the matrix. in other words A^100=x*I+y*A where x and y are variables to be determined. next we only need to calculate the eigenvalues and plug them into that equation in place of A and get linear equations to solve for x and y. in this case it would look like this: the characteristic polynomial of A is p(x)=x²-3x+2=(x-2)(x-1). so the eigenvalues are x1=1 and x2=2. therefore x1^100=1^100=1=x+y. and x2^100=2^100=x+2y. we can solve for x and y as: y=2^100-1, x=2-2^100. so we can write A^100=(2-2^100)*I+(2^100-1)*A. we don't even need to actually add those matrices up since we can easily read off the individual elements. a=(2-2^100)-4*(2^100-1) b=-15*(2^100-1) c=2*(2^100-1) d=(2-2^100)+7*(2^100-1) the fact that the required combination of matrix elements is special is not even needed for this method. even though you could probably shorten some steps.
if anyone is wondering about this application of Cayley Hamilton(like I was) check the wikipedia page en. wikipedia. org/wiki/Cayley-Hamilton_theorem#Matrix_functions
I know this is partly a joke, but... I kind of think it's not as bad as it might appear, at least considering the 'smart' way to calculate A^100 (exponentiation-by-squaring). A^100 = (A^2)^50 = (((A^2))^2)^25, etc.; you only have to do 8 matrix multiplications if my count is right.
@@iooooooo1Another common way would be to find A^2 then square for A^4, so on to A^8, A^16, A^32, A^64 and then take A^4 * A^32 * A^64. Doesn’t use the cool theorem, but would be useful for other combinations of a, b, c, d. Of course the point of the great video is to highlight the theorem, not this particular problem.
A direct computation is not too hard, either. Just observe that A is diagonisable as A=SMS^(-1), where M = diag(1, 2 and S={{-3,-5},{1,2}}. Substituting this into A^k, all inner S terms cancel, and you'll be left with {{6-5×2^k, 15-15×2^k},{-2+2^(k+1), -5+6×2^k}}, and the rest is trivial.
Instead of guessing the induction hypotheis through integration you can observe that A^n=C_1*\lambda_1^n + C_2*\lambda_2^n, where \lambda_1,2 are roots of characteristic polynomial and C_1 and C_2 you can get fro A^0=I and A^1=A. Essentially HC theorem gives you a recurrence equation and you treat it as such.
You have some linear function on the coefficients in the matrix. Call it L [so L(A+B)=L(A)+L(B), L(cA)=cL(A)] and let z_k = L(A^k). Suppose A is nxn with characteristic polynomial p(x) = x^n+...+a_0. Then 0 = L(p(A)) = z_n + ... + a_0 z_0. This is a recurrence relation. If the eigenvalues of A are distinct, r_1, ..., r_n then the general solution is z_k = b_1 r_1^k + ... + b_n r_n^k for some constants b_1, ..., b_n which can be solved for by computing n values of z_k. (Distinct eigenvalues are important. The vandermonde determinant is lurking here). In this case the eigenvalues are 1 and 2. z_1=7, z_2=7. z_k = b_1 + b_2 * 2^k. Solving gives b_1 = 7, b_2 = 0. So z_k = 7. In particular z_100 = 7.
Did it with strong induction, by defining Sk = 3ak +bk + 3ck +4dk, and having Sk = 7 for all m>=k>=1, found a recursion for a_n, b_n, c_n and d_n, applied applied that in the induction twice with a bit of manipulation and managed to show that Sm+1 = Sm
Wow, the solution steps remind me of my A-level pure maths exam in high school. We were not taught exactly the ??? Theorem but the exam question required us to do substantially all the parts: Find x such that det(A-xI)=0 5:50 Prove A^2-3A+2I=0 7:00 Prove by MI 10:20 Find some nice special value 15:35
So, I tried to check this by hand "generically" - we showed that the expression is 7 for the matrix as given, so I figured I could multiply that matrix by a generic [a, b ; c, d ] matrix and show that the result, in general, was also 7. I tried it twice and it didn't work. The problem turned out to be my order of multiplication - the first times I did [a, b; c, d] * [-4, 15 ; 2, 7]. No workee. Just now I realized what must have been wrong and tried it with [-4, -15 ; 2, 7]*[a, b ; c, d] and that worked like a charm. So, be careful of order of multiplication if you're trying to putz around with this. What I want to know, Michael, is just exactly why you felt right at the outset that this might be an invariant for all powers.
My guess is that it’s because it’s not an obviously simple combination of the entries, so you might suspect that there’s something special about it, and being invariant is one likely candidate.
@@ConManAU Well, yes, but on the other hand that combination of entries had to equal *something* - it turned out to be 7. But I think he must have applied some "meta level analysis" to arrive at that conclusion - not "Ah! It's 7!" but rather "Hmmm, the mere fact that this question has been asked implies there's likely an interesting answer." I mean, if we had some other starting matrix, I could write down the same linear combination and I'd get some integer number. And likely that would not be an invariant. So just the mere fact that a random linear combination equals some random integer just really isn't enough, in an of itself, to indicate anything fun is going on. Just to be clear, I really enjoyed this video - I learned some things.
@@KipIngram For sure, there’s an implication that the person who posed the question constructed it to have a nice answer, and there’s some neat theory behind making it work that could be a video of its own.
i saw the same mistake i was quite confused what happened, had to take out pen and paper to figure it out lol for anyone wondering, mike wrote 2*2^(k+1) + 1 in the orange square, what he meant to do is write 2*2^k + 1 = 2^(k + 1) + 1, because that 2* becomes the +1 in the power
Can you adjust the volume of your videos please? It is really hard to hear you even if the volume is at 100%. There is no problem with any other videos or music. Nice video!
Once the general form of Aⁿ is found, we then notice that 3, 1, 3, 4 has a simple answer for all n, which includes n = 100. I don't think it is more complicated than that. If it were 7, -1, 3, 5 then this would involve very large numbers, as we wouldn't find nice cancellation as we did with 3, 1, 3, 4.
Here's another technique that uses Cayley-Hamilton. We know that A^2 - 3A + 2I = 0, which tells us that A(A-2I) = (A-2I). By induction, we know A^n(A-2I) = (A-2I). Also, since these are all powers of A, this expression commutes: so we also have (A-2I)A^n = A-2I. Now, we know that the columns of A-2I are invariant under A^n, giving the equation (-6a + 2b, -6c + 2d) = (-6, 2) (the other column gives us a scaled copy of this). We can also use (A-2I)A^n = (A-2I) to get (-6a - 15c, 2a + 5c) = (-6, 2) and (-6b - 15d, 2b + 5d) = (-15, 5). We can scale to get the 4 equations 3a - b = 3, 3c - d = -1, 2a + 5c = 2, 2b + 5d = 5. If we add the first, second, and fourth equations we get 3a + b + 3c + 4d = 7.
I want to see what the space of possible linear combinations is for this; it can't be all possible linear combinations, as the value of a for example definitely does depend on n. I'll leave it as homework since i should really be studying for my quiz...
Edit: The space of possible linear combinations is 3-dimensional, spanned by any 3 of the 4 equations given. This means there is a large family of linear combinations of the entries of A^n that are constant, which i wouldn't have expected but is pretty cool to find out.
I used matrix diagonalization (eigenvalues and eigenvectors)
Characteristic equation can be easily found by trace and determinant
Inverse of 2x2 matrix also can be easily calculated
I did the diagonalization method and the final exponented matrix comes out to:
6-5k 15-15k
2k-2 6k-5
where k=2^n where n is the exponent on the matrix. So long as you cancel out the ks with your linear combination, it'll always sum to the same thing. This happens because the diagonal matrix, after diagonalization, has a 1 in the top-left; otherwise you'd have only two degrees of freedom.
You get bonus points for your didactic solution.
Nice alternative to finding the eigenvectors and diagonalising
essentially you worked your way there manually, but from my experience the most useful application of cayley-hamilton is that any matrix function f(A) can be written as a polynomial of degree one less than the dimension of the matrix. in other words A^100=x*I+y*A where x and y are variables to be determined. next we only need to calculate the eigenvalues and plug them into that equation in place of A and get linear equations to solve for x and y. in this case it would look like this:
the characteristic polynomial of A is p(x)=x²-3x+2=(x-2)(x-1). so the eigenvalues are x1=1 and x2=2.
therefore x1^100=1^100=1=x+y. and x2^100=2^100=x+2y.
we can solve for x and y as: y=2^100-1, x=2-2^100.
so we can write A^100=(2-2^100)*I+(2^100-1)*A.
we don't even need to actually add those matrices up since we can easily read off the individual elements.
a=(2-2^100)-4*(2^100-1)
b=-15*(2^100-1)
c=2*(2^100-1)
d=(2-2^100)+7*(2^100-1)
the fact that the required combination of matrix elements is special is not even needed for this method. even though you could probably shorten some steps.
if anyone is wondering about this application of Cayley Hamilton(like I was) check the wikipedia page en. wikipedia. org/wiki/Cayley-Hamilton_theorem#Matrix_functions
17:58 Why bother using all of this when you can just calculate A^100 by hand 🗿
I know this is partly a joke, but... I kind of think it's not as bad as it might appear, at least considering the 'smart' way to calculate A^100 (exponentiation-by-squaring).
A^100 = (A^2)^50 = (((A^2))^2)^25, etc.; you only have to do 8 matrix multiplications if my count is right.
You can do it way simpler. I will post a solution later to that problem.
Worth considering the fact that multiplication on matrices with larger entries takes longer when making the 'optimal method'
Compute A^inf and assume 100 is close to infinity? 🙂
@@iooooooo1Another common way would be to find A^2 then square for A^4, so on to A^8, A^16, A^32, A^64 and then take A^4 * A^32 * A^64. Doesn’t use the cool theorem, but would be useful for other combinations of a, b, c, d. Of course the point of the great video is to highlight the theorem, not this particular problem.
This was a really cool problem that made me look up the Cayley-Hamilton theorem, which is an interesting thing on its own. Thanks!
This was great.
Thank you, professor.
A direct computation is not too hard, either. Just observe that A is diagonisable as A=SMS^(-1), where M = diag(1, 2 and S={{-3,-5},{1,2}}. Substituting this into A^k, all inner S terms cancel, and you'll be left with {{6-5×2^k, 15-15×2^k},{-2+2^(k+1), -5+6×2^k}}, and the rest is trivial.
Instead of guessing the induction hypotheis through integration you can observe that A^n=C_1*\lambda_1^n + C_2*\lambda_2^n, where \lambda_1,2 are roots of characteristic polynomial and C_1 and C_2 you can get fro A^0=I and A^1=A. Essentially HC theorem gives you a recurrence equation and you treat it as such.
He always knows the good place to stop :)
The Cayley Hamilton theorem can also show that for A= {M2x2| tr(A)=-1, det(A)=1}, A^3= I
Which is a result that doesn’t matter, but I think it’s cool.
You have some linear function on the coefficients in the matrix. Call it L [so L(A+B)=L(A)+L(B), L(cA)=cL(A)] and let z_k = L(A^k). Suppose A is nxn with characteristic polynomial p(x) = x^n+...+a_0. Then 0 = L(p(A)) = z_n + ... + a_0 z_0. This is a recurrence relation. If the eigenvalues of A are distinct, r_1, ..., r_n then the general solution is z_k = b_1 r_1^k + ... + b_n r_n^k for some constants b_1, ..., b_n which can be solved for by computing n values of z_k. (Distinct eigenvalues are important. The vandermonde determinant is lurking here).
In this case the eigenvalues are 1 and 2. z_1=7, z_2=7. z_k = b_1 + b_2 * 2^k. Solving gives b_1 = 7, b_2 = 0. So z_k = 7. In particular z_100 = 7.
I haven't calculated eigen values/vectors in a long time. It took me more than I would like to admit:
A = (-4 -15)
( 2 7)
find eigen values
|-4-L -15|
| 2 7-L|
(L-7)(L+4)+30=0
L^2-3L-28+30=0
L^2-3L+2=0
L=(3+-1)/2=1, 2
find eigen vectors
(-5 -15)
( 2 6)
Ev = 1
EV = ( 3)
(-1)
(-6 -15)
( 2 5)
Ev = 2
EV = ( 5)
(-2)
find the other eigen vectors:
( 3 5)^-2 ( 2 5)
(-1 -2) = (-1 -3)
A^100= ( 3 5) * (1 0 ) * ( 2 5)
(-1 -2) (0 2^100) (-1 -3)
( 3 5*2^100) * ( 2 5)
(-1 -2*2^100) (-1 -3)
A^100 = (6-5*2^100 15-15*2^100)
(-2+2*2^100 -5+6*2^100)
18-15*2^100 +15-15*2^100 -6+6*2^100 -20+24*2^100 = 7
I really liked this problem actually. Very fun!
Great problem and solution.
Cool solution!
Did it with strong induction, by defining Sk = 3ak +bk + 3ck +4dk, and having Sk = 7 for all m>=k>=1, found a recursion for a_n, b_n, c_n and d_n, applied applied that in the induction twice with a bit of manipulation and managed to show that Sm+1 = Sm
I had to prove by induction not only that 3 a_k + b_k + 3 c_k + 4 d_k = 7, but also that - 3 a_k + b_k - 9 c_k + 3 d_k = 0.
Doesn't the A^n formula hold for n=0 as well? This would be AA^(-1)=I. This holds with the A^n formula, and also satisfies 3a+...=7.
If I’m not mistaken there was a small error at [13:53] where you put 2*2^(k + 1) when you meant 2*2^k = 2^(k + 1)
I admire this guy soooo much; even if I don't always understand ...
6:26 bless you
Wow, the solution steps remind me of my A-level pure maths exam in high school. We were not taught exactly the ??? Theorem but the exam question required us to do substantially all the parts:
Find x such that det(A-xI)=0 5:50
Prove A^2-3A+2I=0 7:00
Prove by MI 10:20
Find some nice special value 15:35
So, I tried to check this by hand "generically" - we showed that the expression is 7 for the matrix as given, so I figured I could multiply that matrix by a generic [a, b ; c, d ] matrix and show that the result, in general, was also 7. I tried it twice and it didn't work. The problem turned out to be my order of multiplication - the first times I did [a, b; c, d] * [-4, 15 ; 2, 7]. No workee. Just now I realized what must have been wrong and tried it with [-4, -15 ; 2, 7]*[a, b ; c, d] and that worked like a charm. So, be careful of order of multiplication if you're trying to putz around with this.
What I want to know, Michael, is just exactly why you felt right at the outset that this might be an invariant for all powers.
My guess is that it’s because it’s not an obviously simple combination of the entries, so you might suspect that there’s something special about it, and being invariant is one likely candidate.
@@ConManAU Well, yes, but on the other hand that combination of entries had to equal *something* - it turned out to be 7. But I think he must have applied some "meta level analysis" to arrive at that conclusion - not "Ah! It's 7!" but rather "Hmmm, the mere fact that this question has been asked implies there's likely an interesting answer."
I mean, if we had some other starting matrix, I could write down the same linear combination and I'd get some integer number. And likely that would not be an invariant. So just the mere fact that a random linear combination equals some random integer just really isn't enough, in an of itself, to indicate anything fun is going on.
Just to be clear, I really enjoyed this video - I learned some things.
@@KipIngram For sure, there’s an implication that the person who posed the question constructed it to have a nice answer, and there’s some neat theory behind making it work that could be a video of its own.
Very Very interesting sir
13:34 why is there an extra 2? is it a mistake? or no?
A small one.
i saw the same mistake i was quite confused what happened, had to take out pen and paper to figure it out lol
for anyone wondering, mike wrote 2*2^(k+1) + 1 in the orange square, what he meant to do is write 2*2^k + 1 = 2^(k + 1) + 1, because that 2* becomes the +1 in the power
I was falling asleep to this video (on purpose, i like to do that at night) and 6:21 scared me back awake
Hmmm, all good, but it does beg the question, why 7 and why the coefficients 3a + b + 3c + 4d ??? What is the theory behind that?
More often than not these problems are done in reverse. So they start form 7 and come up with a formula which is then associated to a matrix.
Spectacular !!!
Amazing!
Can you adjust the volume of your videos please? It is really hard to hear you even if the volume is at 100%. There is no problem with any other videos or music. Nice video!
I really like the ????? Theorem.
what is the magic for the coefficients 3, 1, 3, 4?
Once the general form of Aⁿ is found, we then notice that 3, 1, 3, 4 has a simple answer for all n, which includes n = 100.
I don't think it is more complicated than that. If it were 7, -1, 3, 5 then this would involve very large numbers, as we wouldn't find nice cancellation as we did with 3, 1, 3, 4.
U CAN DIAGONALIZE TOO ITS EASIER
But can you solve 2+2?????
1 in F3
0 in Z2 x Z2@@aweebthatlovesmath4220
10 in base 4
no
1(mod3)