Mixing
Recurrence relation with a matrix?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let $ mathbfM = beginbmatrix 2 & 1 \ 1 & 2 endbmatrix$ and $mathbfX_n = beginbmatrixx_n \ y_n endbmatrix$. Solve $displaystyle mathbfX_n+1 = mathbfMX_n$ for $n ge 0$ with the i.c. $x_0 =2, y_0 = 0$.
I'm not sure how to solve this. My idea is to write this as $mathbfX_n+k =mathbfM^k mathbfX_n$ for $k ge 0$. But it's not clear how I'd get the solution from that, after I've gone through the calculation?
linear-algebra recurrence-relations
asked Jul 29 at 8:46
Nebulae
505
add a comment |Â
up vote
0
down vote
favorite
Let $ mathbfM = beginbmatrix 2 & 1 \ 1 & 2 endbmatrix$ and $mathbfX_n = beginbmatrixx_n \ y_n endbmatrix$. Solve $displaystyle mathbfX_n+1 = mathbfMX_n$ for $n ge 0$ with the i.c. $x_0 =2, y_0 = 0$.
I'm not sure how to solve this. My idea is to write this as $mathbfX_n+k =mathbfM^k mathbfX_n$ for $k ge 0$. But it's not clear how I'd get the solution from that, after I've gone through the calculation?
linear-algebra recurrence-relations
asked Jul 29 at 8:46
Nebulae
505
You need to diagonalize $mathbf M$.
– joriki
Jul 29 at 8:48
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $ mathbfM = beginbmatrix 2 & 1 \ 1 & 2 endbmatrix$ and $mathbfX_n = beginbmatrixx_n \ y_n endbmatrix$. Solve $displaystyle mathbfX_n+1 = mathbfMX_n$ for $n ge 0$ with the i.c. $x_0 =2, y_0 = 0$.
I'm not sure how to solve this. My idea is to write this as $mathbfX_n+k =mathbfM^k mathbfX_n$ for $k ge 0$. But it's not clear how I'd get the solution from that, after I've gone through the calculation?
linear-algebra recurrence-relations
asked Jul 29 at 8:46
Nebulae
505
Let $ mathbfM = beginbmatrix 2 & 1 \ 1 & 2 endbmatrix$ and $mathbfX_n = beginbmatrixx_n \ y_n endbmatrix$. Solve $displaystyle mathbfX_n+1 = mathbfMX_n$ for $n ge 0$ with the i.c. $x_0 =2, y_0 = 0$.
I'm not sure how to solve this. My idea is to write this as $mathbfX_n+k =mathbfM^k mathbfX_n$ for $k ge 0$. But it's not clear how I'd get the solution from that, after I've gone through the calculation?
linear-algebra recurrence-relations
asked Jul 29 at 8:46
Nebulae
505
edited Jul 29 at 9:04
asked Jul 29 at 8:46
Nebulae
505
asked Jul 29 at 8:46
Nebulae
505
asked Jul 29 at 8:46
Nebulae
505
505
You need to diagonalize $mathbf M$.
– joriki
Jul 29 at 8:48
add a comment |Â
You need to diagonalize $mathbf M$.
– joriki
Jul 29 at 8:48
You need to diagonalize $mathbf M$.
– joriki
Jul 29 at 8:48
You need to diagonalize $mathbf M$.
– joriki
Jul 29 at 8:48
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
accepted
If you diagonalize the matrix,
$$M=PDP^-1$$ and
$$M^n=PDP^-1PDP^-1cdots PDP^-1=PD^nP^-1$$
so that the $n^th $ power of a diagonal matrix is the diagonal made of the $n^th$ powers.
Depending on the values of the Eigenvalues, the diagonal elements converge to zero or diverge to infinity (and $1$ remains and $-1$ alternates).
But in this exercise, all of this is useless as the initial conditions are null.
answered Jul 29 at 9:02
Yves Daoust
110k665203
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
1
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
add a comment |Â
up vote
2
down vote
Hint: Take a good look at that initial condition. What is $mathbf X_1$?
answered Jul 29 at 8:48
Arthur
98.4k793174
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
add a comment |Â
up vote
0
down vote
Alt. hint (without matrix powers): Â the recurrence relations can be written as:
$$
beginalign
begincases
x_n+1=2 x_n + y_n \
y_n+1=x_n + 2y_n
endcases
endalign
$$
Subtracting the two equalities gives $,x_n+1-y_n+1=x_n-y_n,$, which telescopes to:
$$x_n-y_n=x_n-1-y_n-1=ldots=x_0-y_0=C$$
Thus $,y_n=x_n-C,$, and substituting back into the first relation gives the simple recurrence in $,x_n,$:
$$
x_n+1=2x_n+(x_n-C) quadiffquad x_n+1=3x_n - C
$$
answered Jul 29 at 18:11
dxiv
53.8k64796
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
If you diagonalize the matrix,
$$M=PDP^-1$$ and
$$M^n=PDP^-1PDP^-1cdots PDP^-1=PD^nP^-1$$
so that the $n^th $ power of a diagonal matrix is the diagonal made of the $n^th$ powers.
Depending on the values of the Eigenvalues, the diagonal elements converge to zero or diverge to infinity (and $1$ remains and $-1$ alternates).
But in this exercise, all of this is useless as the initial conditions are null.
answered Jul 29 at 9:02
Yves Daoust
110k665203
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
1
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
add a comment |Â
up vote
2
down vote
accepted
If you diagonalize the matrix,
$$M=PDP^-1$$ and
$$M^n=PDP^-1PDP^-1cdots PDP^-1=PD^nP^-1$$
so that the $n^th $ power of a diagonal matrix is the diagonal made of the $n^th$ powers.
Depending on the values of the Eigenvalues, the diagonal elements converge to zero or diverge to infinity (and $1$ remains and $-1$ alternates).
But in this exercise, all of this is useless as the initial conditions are null.
answered Jul 29 at 9:02
Yves Daoust
110k665203
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
1
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
If you diagonalize the matrix,
$$M=PDP^-1$$ and
$$M^n=PDP^-1PDP^-1cdots PDP^-1=PD^nP^-1$$
so that the $n^th $ power of a diagonal matrix is the diagonal made of the $n^th$ powers.
Depending on the values of the Eigenvalues, the diagonal elements converge to zero or diverge to infinity (and $1$ remains and $-1$ alternates).
But in this exercise, all of this is useless as the initial conditions are null.
answered Jul 29 at 9:02
Yves Daoust
110k665203
If you diagonalize the matrix,
$$M=PDP^-1$$ and
$$M^n=PDP^-1PDP^-1cdots PDP^-1=PD^nP^-1$$
so that the $n^th $ power of a diagonal matrix is the diagonal made of the $n^th$ powers.
Depending on the values of the Eigenvalues, the diagonal elements converge to zero or diverge to infinity (and $1$ remains and $-1$ alternates).
But in this exercise, all of this is useless as the initial conditions are null.
answered Jul 29 at 9:02
Yves Daoust
110k665203
answered Jul 29 at 9:02
Yves Daoust
110k665203
answered Jul 29 at 9:02
Yves Daoust
110k665203
answered Jul 29 at 9:02
Yves Daoust
110k665203
110k665203
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
1
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
add a comment |Â
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
1
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
I got the initial condition wrong. Also I thought it was $M = P^-1DP$? Thanks. So after I find $M^kX_n $, I let $k=0$?
– Nebulae
Jul 29 at 9:05
1
1
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
@Farthing: no, $X_n=M^nX_0$.
– Yves Daoust
Jul 29 at 9:10
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
In general does $PDP^-1 = P^-1DP$?
– Nebulae
Jul 29 at 9:19
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
@Farthing: consider $Q=P^-1$.
– Yves Daoust
Jul 29 at 9:21
add a comment |Â
up vote
2
down vote
Hint: Take a good look at that initial condition. What is $mathbf X_1$?
answered Jul 29 at 8:48
Arthur
98.4k793174
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
add a comment |Â
up vote
2
down vote
Hint: Take a good look at that initial condition. What is $mathbf X_1$?
answered Jul 29 at 8:48
Arthur
98.4k793174
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Hint: Take a good look at that initial condition. What is $mathbf X_1$?
answered Jul 29 at 8:48
Arthur
98.4k793174
Hint: Take a good look at that initial condition. What is $mathbf X_1$?
answered Jul 29 at 8:48
Arthur
98.4k793174
answered Jul 29 at 8:48
Arthur
98.4k793174
answered Jul 29 at 8:48
Arthur
98.4k793174
answered Jul 29 at 8:48
Arthur
98.4k793174
98.4k793174
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
add a comment |Â
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
I'm sorry I typed the initial condition wrong.
– Nebulae
Jul 29 at 9:04
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
@Farthing Well, then. Diagonalisation it is. Or you could try to first solve the initial value problem $M_0=M, M_n=MM_n-1$. Whichever you think is easiest.
– Arthur
Jul 29 at 9:10
add a comment |Â
up vote
0
down vote
Alt. hint (without matrix powers): Â the recurrence relations can be written as:
$$
beginalign
begincases
x_n+1=2 x_n + y_n \
y_n+1=x_n + 2y_n
endcases
endalign
$$
Subtracting the two equalities gives $,x_n+1-y_n+1=x_n-y_n,$, which telescopes to:
$$x_n-y_n=x_n-1-y_n-1=ldots=x_0-y_0=C$$
Thus $,y_n=x_n-C,$, and substituting back into the first relation gives the simple recurrence in $,x_n,$:
$$
x_n+1=2x_n+(x_n-C) quadiffquad x_n+1=3x_n - C
$$
answered Jul 29 at 18:11
dxiv
53.8k64796
add a comment |Â
up vote
0
down vote
Alt. hint (without matrix powers): Â the recurrence relations can be written as:
$$
beginalign
begincases
x_n+1=2 x_n + y_n \
y_n+1=x_n + 2y_n
endcases
endalign
$$
Subtracting the two equalities gives $,x_n+1-y_n+1=x_n-y_n,$, which telescopes to:
$$x_n-y_n=x_n-1-y_n-1=ldots=x_0-y_0=C$$
Thus $,y_n=x_n-C,$, and substituting back into the first relation gives the simple recurrence in $,x_n,$:
$$
x_n+1=2x_n+(x_n-C) quadiffquad x_n+1=3x_n - C
$$
answered Jul 29 at 18:11
dxiv
53.8k64796
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Alt. hint (without matrix powers): Â the recurrence relations can be written as:
$$
beginalign
begincases
x_n+1=2 x_n + y_n \
y_n+1=x_n + 2y_n
endcases
endalign
$$
Subtracting the two equalities gives $,x_n+1-y_n+1=x_n-y_n,$, which telescopes to:
$$x_n-y_n=x_n-1-y_n-1=ldots=x_0-y_0=C$$
Thus $,y_n=x_n-C,$, and substituting back into the first relation gives the simple recurrence in $,x_n,$:
$$
x_n+1=2x_n+(x_n-C) quadiffquad x_n+1=3x_n - C
$$
answered Jul 29 at 18:11
dxiv
53.8k64796
Alt. hint (without matrix powers): Â the recurrence relations can be written as:
$$
beginalign
begincases
x_n+1=2 x_n + y_n \
y_n+1=x_n + 2y_n
endcases
endalign
$$
Subtracting the two equalities gives $,x_n+1-y_n+1=x_n-y_n,$, which telescopes to:
$$x_n-y_n=x_n-1-y_n-1=ldots=x_0-y_0=C$$
Thus $,y_n=x_n-C,$, and substituting back into the first relation gives the simple recurrence in $,x_n,$:
$$
x_n+1=2x_n+(x_n-C) quadiffquad x_n+1=3x_n - C
$$
answered Jul 29 at 18:11
dxiv
53.8k64796
answered Jul 29 at 18:11
dxiv
53.8k64796
answered Jul 29 at 18:11
dxiv
53.8k64796
answered Jul 29 at 18:11
dxiv
53.8k64796
53.8k64796
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865902%2frecurrence-relation-with-a-matrix%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You need to diagonalize $mathbf M$.
– joriki
Jul 29 at 8:48