Calculate the product $A^{10}v$ where $A$ is a $2 times 2$ matrix and $v$ is a vector $[4 ; 4]^T$ [duplicate]
0
$begingroup$
This question already has an answer here:
Finding a 2x2 Matrix raised to the power of 1000
6 answers
Following on from the title, can someone suggest how to proceed with this one.
$$A=begin{bmatrix}1&1\4&1end{bmatrix}$$
and
$$v = [4 ; 4]^T?$$
linear-algebra matrix-equations
edited Jan 3 at 20:18
A.Γ.
22.9k32656
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
$endgroup$
marked as duplicate by amd, stressed out, Namaste linear-algebra
Users with the linear-algebra badge can single-handedly close linear-algebra questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 3 at 20:22
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
0
$begingroup$
This question already has an answer here:
Finding a 2x2 Matrix raised to the power of 1000
6 answers
Following on from the title, can someone suggest how to proceed with this one.
$$A=begin{bmatrix}1&1\4&1end{bmatrix}$$
and
$$v = [4 ; 4]^T?$$
linear-algebra matrix-equations
edited Jan 3 at 20:18
A.Γ.
22.9k32656
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
$endgroup$
marked as duplicate by amd, stressed out, Namaste linear-algebra
Users with the linear-algebra badge can single-handedly close linear-algebra questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 3 at 20:22
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
One way could be to multiply $A$ by itself nine times then by $v$ from the right. It is pretty straightforward.
$endgroup$
– A.Γ.
Jan 3 at 20:15
add a comment |
0
0
0
$begingroup$
This question already has an answer here:
Finding a 2x2 Matrix raised to the power of 1000
6 answers
Following on from the title, can someone suggest how to proceed with this one.
$$A=begin{bmatrix}1&1\4&1end{bmatrix}$$
and
$$v = [4 ; 4]^T?$$
linear-algebra matrix-equations
edited Jan 3 at 20:18
A.Γ.
22.9k32656
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
$endgroup$
This question already has an answer here:
Finding a 2x2 Matrix raised to the power of 1000
6 answers
Following on from the title, can someone suggest how to proceed with this one.
$$A=begin{bmatrix}1&1\4&1end{bmatrix}$$
and
$$v = [4 ; 4]^T?$$
This question already has an answer here:
Finding a 2x2 Matrix raised to the power of 1000
6 answers
linear-algebra matrix-equations
linear-algebra matrix-equations
edited Jan 3 at 20:18
A.Γ.
22.9k32656
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
edited Jan 3 at 20:18
A.Γ.
22.9k32656
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
edited Jan 3 at 20:18
A.Γ.
22.9k32656
edited Jan 3 at 20:18
A.Γ.
22.9k32656
edited Jan 3 at 20:18
A.Γ.
22.9k32656
22.9k32656
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
asked Jan 3 at 20:11
RocketKangarooRocketKangaroo
334
334
marked as duplicate by amd, stressed out, Namaste linear-algebra
Users with the linear-algebra badge can single-handedly close linear-algebra questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 3 at 20:22
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by amd, stressed out, Namaste linear-algebra
Users with the linear-algebra badge can single-handedly close linear-algebra questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 3 at 20:22
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
One way could be to multiply $A$ by itself nine times then by $v$ from the right. It is pretty straightforward.
$endgroup$
– A.Γ.
Jan 3 at 20:15
add a comment |
$begingroup$
One way could be to multiply $A$ by itself nine times then by $v$ from the right. It is pretty straightforward.
$endgroup$
– A.Γ.
Jan 3 at 20:15
$begingroup$
One way could be to multiply $A$ by itself nine times then by $v$ from the right. It is pretty straightforward.
$endgroup$
– A.Γ.
Jan 3 at 20:15
$begingroup$
One way could be to multiply $A$ by itself nine times then by $v$ from the right. It is pretty straightforward.
$endgroup$
– A.Γ.
Jan 3 at 20:15
add a comment |
1 Answer
1
active
oldest
votes
2
$begingroup$
You can
calculate $Av$, and then apply $A$ to the result nine times;
or, since the eigenvalues of $A$ are distinct, $A$ is diagonalizable: there exist $P$ invertible and $D$ diagonal with $A=PDP^{-1}$. Then $A^{10}=PD^{10}P^{-1}$, where $D^{10}$ is very easy since it's diagonal.
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
$endgroup$
2
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
1
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
1
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
1
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
1
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
|
show 10 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
2
$begingroup$
You can
calculate $Av$, and then apply $A$ to the result nine times;
or, since the eigenvalues of $A$ are distinct, $A$ is diagonalizable: there exist $P$ invertible and $D$ diagonal with $A=PDP^{-1}$. Then $A^{10}=PD^{10}P^{-1}$, where $D^{10}$ is very easy since it's diagonal.
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
$endgroup$
2
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
1
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
1
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
1
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
1
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
|
show 10 more comments
2
$begingroup$
You can
calculate $Av$, and then apply $A$ to the result nine times;
or, since the eigenvalues of $A$ are distinct, $A$ is diagonalizable: there exist $P$ invertible and $D$ diagonal with $A=PDP^{-1}$. Then $A^{10}=PD^{10}P^{-1}$, where $D^{10}$ is very easy since it's diagonal.
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
$endgroup$
2
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
1
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
1
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
1
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
1
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
|
show 10 more comments
2
2
2
$begingroup$
You can
calculate $Av$, and then apply $A$ to the result nine times;
or, since the eigenvalues of $A$ are distinct, $A$ is diagonalizable: there exist $P$ invertible and $D$ diagonal with $A=PDP^{-1}$. Then $A^{10}=PD^{10}P^{-1}$, where $D^{10}$ is very easy since it's diagonal.
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
$endgroup$
You can
calculate $Av$, and then apply $A$ to the result nine times;
or, since the eigenvalues of $A$ are distinct, $A$ is diagonalizable: there exist $P$ invertible and $D$ diagonal with $A=PDP^{-1}$. Then $A^{10}=PD^{10}P^{-1}$, where $D^{10}$ is very easy since it's diagonal.
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
answered Jan 3 at 20:17
Martin ArgeramiMartin Argerami
129k1184185
129k1184185
2
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
1
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
1
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
1
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
1
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
|
show 10 more comments
2
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
1
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
1
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
1
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
1
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
2
2
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
$begingroup$
That sounds very inefficient. Each time you multiply two $2times 2$ matrices you are doing 8 products and four sums; so to calculate $A^{10}$ you are doing $9times 8+2=74$ products and $9times 4+1=37$ sums, whereas if you apply $A$ to $v$ and keep doing it, each time you are doing 2 products and one sum, for a total of $10times 2=20$ products and $10times 1=10$ sums.
$endgroup$
– Martin Argerami
Jan 3 at 20:22
1
1
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
$begingroup$
In general, yes. But at this stage, with the 10th power, when you compare with finding the two eigenvalues, two corresponding eigenvectors, then inverting the matrix with the eigenvectors and columns, and then doing the two products in $PD^{10}P^{-1}$, "brute force" is probably less or similar work. It won't as soon as you increase powers.
$endgroup$
– Martin Argerami
Jan 3 at 20:30
1
1
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
$begingroup$
Yes, you are right. Contrary to what @stressedout seems to think, algorithms are not my thing :D
$endgroup$
– Martin Argerami
Jan 3 at 20:34
1
1
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
$begingroup$
If you compute $A^2$ and then $A^4=(A^2)^2$, you can then compute $A^2v$ followed by $A^4(A^2v)$ followed by $A^4(A^4(A^2v))$, with a total of $8+8+4+4+4=28$ multiplications and $4+4+4+2+2=14$ additions.
$endgroup$
– Barry Cipra
Jan 3 at 20:39
1
1
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
$begingroup$
I love how everyone is calculating the number of additions and multiplications necessary to solve this like it is actually an important problem. :P @Martin I never thought algorithms were your thing. But I said that I should never design them. :D
$endgroup$
– stressed out
Jan 3 at 20:42
|
show 10 more comments
$begingroup$
One way could be to multiply $A$ by itself nine times then by $v$ from the right. It is pretty straightforward.
$endgroup$
– A.Γ.
Jan 3 at 20:15