Archive

Archive for May, 2011

My first logistic bifurcation curve and a bit more

May 27, 2011 5 comments

I don’t know since when, but I desperately want to learn how do I make a logistic bifurcation curve. And now, I finally able to create one. I do not want to forget this ability therefore I post this post, just in case I forget.

Logistic map is one of discrete dynamical systems, represented in the following:

x_{n+1} = \mu x_n (1-x_n).

It is basically a recursive sequence. It looks simple but it is highly not.When \mu \in [0,4] the sequence generated will always be inside the interval [0,4].More specifically, when \mu =2, the sequence converges to a point. When \mu is varied, does the solution still converge to some point?

In fact, when we vary \mu past 3 we have the situation that is best explained through the following figure:

The figure is saying when \mu is just past 3, the sequence is no longer converging to a point. This phenomena is called a period-doubling, as the sequence now tends to alternatingly approaching two points. However, this is the code to create the above figure in Matlab.


clear; clc;
a = 3:0.005:4;  %interval of parameter
x0 = 0.5;       %initial condition
N=500;          %number of iterations
x(1) = x0;      %the first entry is the initial condition
%computation of the orbit
figure(3);hold on;
for i=1:length(a)
for j=2:N
x(j) = a(i)*x(j-1)*(1-x(j-1));
end
y = x(301:end);
plot(a(i),y);
end
hold off
clear

Okay, the fitst task is done. Let us now learn how to make a movie in Matlab. I choose the topic ‘coweb’ as an example. Coweb arises in our topic, which is a discrete dynamical system.

Here is the video

The coweb created in the above movie uses \mu=3.9. This exactly where the chaotic dynamic occurs. Therefore, we do not see any pattern there. The iteration that I used is only 90. However, we already see that the sequence makes such a complicated figure.

The code to create such a video is the following.

clc;clear;
myu = 3.9; %initial parameter
maxiter = 90; %maximum iteration
xo = 0.4; %initial condition
aviobj = avifile ( 'logistik2.avi', 'fps', 3 );%create a file logistik2.avi
x = 0:0.01:1; %range of x data
y1 = myu.*x.*(1-x); %range of y data to graph y=myu(x-x^2)
y2 = x; %range for y data to graph y=x
figure(1);hold on; %open figure window and hold on
axis([0 1.1 0 1.1]) % set the y and x axis
plot(x,y1); %plot the graph of y=myu(x-x^2)
plot(x,y2); %plot the graph of y=x
frame = getframe ( gca ); %command 1 to store what is inside figure 1
aviobj = addframe ( aviobj, frame ); %command 2
xbaru = myu.*xo.*(1-xo);
z2 = 0:0.01:xbaru;
z1 = xo;
plot(z1,z2);
frame = getframe ( gca );
aviobj = addframe ( aviobj, frame );
fprintf('the fixed point is %f',(myu-1)/myu);
for i=2:maxiter
if(xbaru > xo)
y1 = xo:0.01:xbaru;
else
y1 = xbaru:0.01:xo;
end
y2 = xbaru;
plot(y1,y2);
frame = getframe ( gca );
aviobj = addframe ( aviobj, frame );
xo = xbaru;
xbaru = myu.*xo.*(1-xo);
if(xbaru > xo)
y1 = xo:0.01:xbaru;
else
y1 = xbaru:0.01:xo;
end
y2 = xo;
plot(y2,y1);
frame = getframe ( gca );
aviobj = addframe ( aviobj, frame );
end
hold off;
H = (myu-1)/myu;
fprintf('please press any key \n');
aviobj = close ( aviobj );
%pause;
%close all;

However, I really really want to learn how to convert this avi video produced by Matlab to a gif image format. So if anyone know how do I do this please let me know.

(Another) Birthday problem puzzle

May 12, 2011 4 comments

I’d like to discuss one of many birthday problem math puzzles. The complete puzzle and the solution can be found here. But let me write the puzzle as follows.

You and your colleagues know that your boss A’s birthday is one of the following 10 dates:

Mar 4, Mar 5, Mar 8
Jun 4, Jun 7
Sep 1, Sep 5
Dec 1, Dec 2, Dec 8
 
A told you only the month of his birthday, and told your colleague C only the day. After that, you first said: “I don’t know A’s birthday; C doesn’t know it either.” After hearing what you said, C replied: “I didn’t know A’s birthday, but now I know it.” You smiled and said: “Now I know it, too.” After looking at the 10 dates and hearing your comments, your administrative assistant wrote down A’s birthday without asking any questions. So what did the assistant write?

When I first read this puzzle, I am confused. Let me just name the reader/myself  “B” in the puzzle above to avoid more confusion. This puzzle is written in some way that the reader is part of the story. Hence the reader, B, was told the month of A’s birthday but we as the reader do not know the month of A’s birthday. Perhaps it is just a part of puzzle that we have to solve, therefore it might not be a big deal.

However, the big deal is the fact that the solution that I found is different from the solution given. I thought I might get wrong, therefore I look for the solution. What happened was I could not understand the solution. I thought it is just me but it turns out there is someone else who has the same experience.

I would like to modify a little bit of the puzzle in order to make this puzzle a bit clearer, well at least for me.

A’s birthday is one of the following 10 dates:

Mar 4, Mar 5, Mar 8
Jun 4, Jun 7
Sep 1, Sep 5
Dec 1, Dec 2, Dec 8
 
We then have the following conversations between A’s friend.
C said: “I don’t know A’s birthday, but I know only the day (the date) of A’s birthday,”
B said: “Well, I know only the month A’s birthday.”
C said: “Now I know it.”
B said: “Now I know it, too.”

From the information given above, can you tell what is A’s birthday?

Perhaps, this version is better than the previous one. What do you think?

Categories: math puzzle Tags: ,

Notes on diagonalizable linear operators

May 11, 2011 3 comments

Okay, I have a few things in my mind about this topic and I don’t want to lose them tomorrow or the day after. Therefore, I created this note. Hope it is useful to other people as well. Background of this note are as follows:

  1. Suppose A is an n \times n matrix and it is diagonalizable. Therefore, by definition, there is an invertible matrix P and a diagonal matrix D. However, I always forget the relationship between A and D, whether it is D=PAP^{-1} or D=P^{-1}AP. Generally, those two are no different, but we can choose P such that the column vectors of matrix P are the eigenvectors of matrix A, hence we have to know precisely which one it is, otherwise it gets wrong. Until now, when I forget about this, I always derive it and it takes some of my precious time (haha) but now after I have this, I can just open the Internet and look for this note.
  2. Point 1 above talks about diagonalizability of a matrix. But generally, we have a linear operator acting on a general vector field instead. A linear operator is called diagonalizable if there is a basis B such that the matrix representation of this linear operator is a diagonal matrix. It seems for me, diagonalizability of a linear operator and that of a matrix are talking about two different things. One is talking about how to find a basis, while the other is talking about how to find an invertible matrix. However, these two concepts turn out to be the same.

We begin with the following theorem.

Theorem 1 (Coordinate-change matrix)
Let E be a standard basis and B be another basis for an n-dimensional linear space V. Then there is an invertible matrix P such that for every v \in V

P (v)_B=(v)_E.                                                                                                          (1)

Matrix P is called the transition or coordinate-change matrix from the basis B to the basis E. Note that (v)_B and (v)_E are the coordinates of vector v with respect to basis B and E respectively. In fact, the column vectors of matrix P are the coordinates of the basis vectors of B with respect to the standard bases E (i.e. if B=\{ v_1,v_2,\dots,v_n \} then P=[(v_1)_E (v_2)_E \dots (v_n)_E] ).

We won’t prove the theorem as it can be found in any linear algebra textbook. However, using this theorem we can relate the diagonalizability of a linear operator and that of a matrix.Suppose T is a diagonalizable linear operator on an n-dimensional linear space V. Take x \in V then let y be y=T(x). Suppose E is a standard basis in V and B is a basis in V that consists of independent eigenvectors of T.

Then we have the following.

(i) (y)_E = [T(x)]_E = [T]_E (x)_E = A (x)_E, where A is a representation matrix of T with respect to standard basis E.
(ii) (y)_B = [T(x)]_B = [T]_B (x)_B = D (x)_B, where D is a representation matrix of T with respect to basis B. We also know that D is a diagonal matrix.

We want to show that using the theorem 1, D=PAP^{-1} or D=P^{-1}AP. From equation (1) we get:

P (y)_B = (y)_E = A (x)_E = A P (x)_B.

Hence, we have (y)_B = P^{-1}AP (x)_B. While from point (ii) we have (y)_B = D (x)_B. As a conclusion, we have,

D = P^{-1} A P.

We have derived that in fact, D = P^{-1} A P is the right one. We also derived that the invertible matrix P has such a close relationship with the basis B as the column vectors of P are the basis vectors of B, which are the eigenvectors of the linear operator T. This conclude my note.

Academic Recharging

May 6, 2011 Leave a comment

I first hear about this phrase in the Indonesian government of education website. Academic recharging is one of fund application schemes provided to academician who feels bored and sometimes tired doing teaching in their respective university. This scheme is provided to ‘recharge’ them in some way such that they are able to go abroad conducting research with their colleagues overseas. Indonesian government hopes by doing this scheme, lecturer and academician could update their knowledge to the current topics so that Indonesian academic society would not be left behind.

But I have found my way of academic recharging. And I give many thanks to ICTP and MIT. Courses that are provided by ICTP and MIT have been recorded and have been available online. I don’t know since when this happens but for me it is great. I can update my knowledge with some new information that I have never learned before.

After downloaded a video, I can watch the course that I am interested. When I don’t understand a thing, I can just pause and google them. I can pause anytime I want when some students knocking my door. I strongly recommended this way of learning to my colleagues and my students as this is much as fun as watching movie.

Here are some references that you might like.

  1. http:// http://www.ictp.tv
  2. http://ocw.mit.edu/courses/audio-video-courses/
  3. http://www.youtube.com/user/MIT
  4. http://www.khanacademy.org/

Rope burning logic puzzle (just slightly more generalised)

May 2, 2011 6 comments

Many seem to know already the famous rope burning puzzle. When we google it, there will be infinitely many websites discussing this puzzle. However, I try to (kind of) generalise this puzzle a little bit and relate this puzzle to understand the difference between axioms, theorems, lemmas and corollaries that are often used in mathematics articles.

Here is the puzzle: There are two ropes and one lighter. Each rope has special properties.

  1. If we light one end of the rope, it will take exactly one hour to completely burn out.
  2. The density of the rope is not uniform, which means that burning half the rope would not take half an hour.
  3. Those two ropes are not identical, they aren’t the same density nor the same length nor the same width.

The question is how do we measure exactly 45 minutes using those two ropes.

We shall not discuss the answer here, instead I would like to give some logical consequences of those rules given in the properties of the rope. Those three properties are called axioms in mathematics article. They are not to be proven. We have to believed them, we have to accept it.

The first consequence is summarized in the following lemma (which is a small relatively easy consequence of the axioms).

Lemma 1
If we burn both ends of the rope, the rope will take 30 minutes to be completely burned

This lemma is very useful and it is used in solving the puzzle. It seems obvious but we can’t just take it for granted. Anyway, here is the proof.

Proof:
Let us prove this by a contradiction. Assume it would take x minutes by burning both ends of the rope until it is completely burned. Assume x \neq 30. Let us consider the case where x > 30.  At first (t=0) the rope is burned at both ends and after x minutes the rope would be gone. However, after 30 minutes there is still a segment of the rope that hasn’t been burned yet. See the figure below.

And now, let us consider if at first the rope is burned only at one end. It would take then 30 minutes until the segment AB is completely burned and it would take another 30 minutes to completely burn the segment CD. A contradiction, as it would need more than one hour to completely burned out the rope. The case where x < 30 can be proven similarly. QED

The next consequence is summarized in the theorem below. Theorem usually used to give a significant consequence of the three axioms given above. The theorem tells us that the solution of the puzzle exists.

Theorem 2
There is such a way to measure 45 minutes using only two ropes

Proof: Burn both ends of the first rope and burn one end of the second rope. According to lemma 1, it will take 30 minutes to completely burn out the first rope. The next step is to burn the other end of the second rope, therefore it will take 15 minutes to burn out the second rope if we apply lemma 1 once more to the second rope which has 30 minutes remaining rope.  QED.

The puzzle stops here, but our discussion does not. I would like to discuss if we have n ropes then how many minutes we can measure accurately. It turns out this problem is an immediate consequence of the last theorem.

Corollary 3
Suppose there are n ropes that satisfy the properties given in the beginning of this section, then there is such a way to measure exactly (60 - 60/2^n) minutes.

Proof:
This can be shown by inductively applying theorem 2 n times to n ropes.

The next results given below are dealing with only one rope. As given in the Lemma 1, we can measure exactly 30 minutes with using only one rope. However, there are various ways how we measure exactly 30 minutes. I won’t present the proofs here as it’s just fun to figure it all ourselves.

Lemma 4
Let us take the rope that has special properties given above. Cut the rope into two pieces and burn both ends of the first piece and then burn both ends of the second piece. It takes exactly 30 minutes until the rope is completely burned.

Lemma 5
Let’s take the rope that has special properties given above. Cut the rope into n pieces. Burn both ends of the first piece and then burn both ends of the second piece and so on until the last piece. It takes exactly 30 minutes until all the pieces of the rope are completely burned.

All the results above are resulted from burning the end of the rope. We are now asking ourselves what do we get if we burn the rope somewhere in the middle. Logically, the fire will spread in two directions. Depending on the density of the rope, one end of the rope will be caught by the fire first.

Lemma 6
Let’s take the rope that has special properties given above. Burn the rope at one point in the middle. Once one end of the rope is caught by the fire, burn the other end of the rope. It takes exactly 30 minutes until the rope is completely burned.

Of all results presented above, with using only one rope, we can measure exactly 30 and 60 minutes. But I would like to ask whether there is any other time that we can measure using only one rope.

Categories: math puzzle, Teachings Tags: