Mixing
How to write out the elements of a matrix that has been taken to the $n$th power.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am attempting to write an explicit formula for the individual elements of a matrix that has been exponentiated to the $n$th power. Let $P$ be an $ntimes n$ matrix and let $p_ij^(n)$ be the $(i,j)$th entry of the matrix $P^n$. How can I write out an explicit formula for $p_ij^(n)$?
I know that $$p_ij^(2) = sum_k=1^n p_ikp_kj$$
and I'm fairly sure that
$$p_ij^(3) = sum_r=1^n p_rjleft(sum_k=1^n p_ikp_kjright) = sum_r=1^n sum_k=1^np_rjp_ikp_kj$$
But even with this, I'm struggling to generalize for arbitrary $n$. Any help would be appreciated.
matrices
asked Jul 30 at 3:56
BSplitter
419115
add a comment |Â
up vote
1
down vote
favorite
I am attempting to write an explicit formula for the individual elements of a matrix that has been exponentiated to the $n$th power. Let $P$ be an $ntimes n$ matrix and let $p_ij^(n)$ be the $(i,j)$th entry of the matrix $P^n$. How can I write out an explicit formula for $p_ij^(n)$?
I know that $$p_ij^(2) = sum_k=1^n p_ikp_kj$$
and I'm fairly sure that
$$p_ij^(3) = sum_r=1^n p_rjleft(sum_k=1^n p_ikp_kjright) = sum_r=1^n sum_k=1^np_rjp_ikp_kj$$
But even with this, I'm struggling to generalize for arbitrary $n$. Any help would be appreciated.
matrices
asked Jul 30 at 3:56
BSplitter
419115
Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables.
– coffeemath
Jul 30 at 4:01
So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly?
– BSplitter
Jul 30 at 4:06
Is the matrix diagonizable?
– RHowe
Jul 30 at 4:25
@Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one.
– BSplitter
Jul 30 at 4:34
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am attempting to write an explicit formula for the individual elements of a matrix that has been exponentiated to the $n$th power. Let $P$ be an $ntimes n$ matrix and let $p_ij^(n)$ be the $(i,j)$th entry of the matrix $P^n$. How can I write out an explicit formula for $p_ij^(n)$?
I know that $$p_ij^(2) = sum_k=1^n p_ikp_kj$$
and I'm fairly sure that
$$p_ij^(3) = sum_r=1^n p_rjleft(sum_k=1^n p_ikp_kjright) = sum_r=1^n sum_k=1^np_rjp_ikp_kj$$
But even with this, I'm struggling to generalize for arbitrary $n$. Any help would be appreciated.
matrices
asked Jul 30 at 3:56
BSplitter
419115
I am attempting to write an explicit formula for the individual elements of a matrix that has been exponentiated to the $n$th power. Let $P$ be an $ntimes n$ matrix and let $p_ij^(n)$ be the $(i,j)$th entry of the matrix $P^n$. How can I write out an explicit formula for $p_ij^(n)$?
I know that $$p_ij^(2) = sum_k=1^n p_ikp_kj$$
and I'm fairly sure that
$$p_ij^(3) = sum_r=1^n p_rjleft(sum_k=1^n p_ikp_kjright) = sum_r=1^n sum_k=1^np_rjp_ikp_kj$$
But even with this, I'm struggling to generalize for arbitrary $n$. Any help would be appreciated.
matrices
asked Jul 30 at 3:56
BSplitter
419115
asked Jul 30 at 3:56
BSplitter
419115
asked Jul 30 at 3:56
BSplitter
419115
asked Jul 30 at 3:56
BSplitter
419115
419115
Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables.
– coffeemath
Jul 30 at 4:01
So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly?
– BSplitter
Jul 30 at 4:06
Is the matrix diagonizable?
– RHowe
Jul 30 at 4:25
@Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one.
– BSplitter
Jul 30 at 4:34
add a comment |Â
Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables.
– coffeemath
Jul 30 at 4:01
So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly?
– BSplitter
Jul 30 at 4:06
Is the matrix diagonizable?
– RHowe
Jul 30 at 4:25
@Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one.
– BSplitter
Jul 30 at 4:34
Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables.
– coffeemath
Jul 30 at 4:01
Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables.
– coffeemath
Jul 30 at 4:01
So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly?
– BSplitter
Jul 30 at 4:06
So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly?
– BSplitter
Jul 30 at 4:06
Is the matrix diagonizable?
– RHowe
Jul 30 at 4:25
Is the matrix diagonizable?
– RHowe
Jul 30 at 4:25
@Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one.
– BSplitter
Jul 30 at 4:34
@Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one.
– BSplitter
Jul 30 at 4:34
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
You have to use more indices to express the entry of $P^n$.
To be more precise for any matrix $P$ with entries $P_ij$, the entries of the matrix $P^n$, given by $(P^n)_ij$ are given by :
$$
(P^n)_ij = sum_a_1,a_2,...,a_n-1 = 1^n P_ia_1P_a_1a_2ldots P_a_n-2a_n-1P_a_n-1j
$$
so the number of indices changes with the power. This formula can easily proved by induction, as you saw for the case $n=2$ to $n=3$ by substitution.
Note that the problem of having $n-1$ summations is solved by iterating over a different set that contains all the possible types of indices : this is why we can combine $a_1,...,a_n-1$ into one summation.
Furthermore, a very similar formula applies for the product of $n$ matrices in an admissible order (number of columns of left matrix equals number of rows of the right matrix). More precisely , if $A_i$, $i=1,...,n$ are $c_i times d_i$ matrices such that $c_i+1 = d_i$ for all $i=1,...,n-1$, then the product $prod A_i$ will have entries given by a similar summation, which I leave you to figure out, where each $a_i$ in the index set will not vary from $1$ to $n$, but something else. The expression for entries of the power is a special case of this formula, which can also be proved by induction.
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
add a comment |Â
up vote
0
down vote
If your matrix is diagonalizable then we have, $A in mathbbC^n times n $
$$ A = V Lambda V^*$$
$$ A^n = VLambda^n V^* $$
now matrix multiplication is
$$ (AB)_ik = sum_k=1^n a_ijb_jk $$
then we have
$$ ((AB)C))_il = sum_k=1^p sum_j=1^n a_ijb_jk c_kl $$
$$ (A)_il^c = sum_k=1^p sum_j=1^n v_ij lambda_jk^cv_kl^t$$
now all $ lambda^c $ is the entries exponentiatied.
answered Jul 30 at 4:42
RHowe
915715
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
You have to use more indices to express the entry of $P^n$.
To be more precise for any matrix $P$ with entries $P_ij$, the entries of the matrix $P^n$, given by $(P^n)_ij$ are given by :
$$
(P^n)_ij = sum_a_1,a_2,...,a_n-1 = 1^n P_ia_1P_a_1a_2ldots P_a_n-2a_n-1P_a_n-1j
$$
so the number of indices changes with the power. This formula can easily proved by induction, as you saw for the case $n=2$ to $n=3$ by substitution.
Note that the problem of having $n-1$ summations is solved by iterating over a different set that contains all the possible types of indices : this is why we can combine $a_1,...,a_n-1$ into one summation.
Furthermore, a very similar formula applies for the product of $n$ matrices in an admissible order (number of columns of left matrix equals number of rows of the right matrix). More precisely , if $A_i$, $i=1,...,n$ are $c_i times d_i$ matrices such that $c_i+1 = d_i$ for all $i=1,...,n-1$, then the product $prod A_i$ will have entries given by a similar summation, which I leave you to figure out, where each $a_i$ in the index set will not vary from $1$ to $n$, but something else. The expression for entries of the power is a special case of this formula, which can also be proved by induction.
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
add a comment |Â
up vote
1
down vote
accepted
You have to use more indices to express the entry of $P^n$.
To be more precise for any matrix $P$ with entries $P_ij$, the entries of the matrix $P^n$, given by $(P^n)_ij$ are given by :
$$
(P^n)_ij = sum_a_1,a_2,...,a_n-1 = 1^n P_ia_1P_a_1a_2ldots P_a_n-2a_n-1P_a_n-1j
$$
so the number of indices changes with the power. This formula can easily proved by induction, as you saw for the case $n=2$ to $n=3$ by substitution.
Note that the problem of having $n-1$ summations is solved by iterating over a different set that contains all the possible types of indices : this is why we can combine $a_1,...,a_n-1$ into one summation.
Furthermore, a very similar formula applies for the product of $n$ matrices in an admissible order (number of columns of left matrix equals number of rows of the right matrix). More precisely , if $A_i$, $i=1,...,n$ are $c_i times d_i$ matrices such that $c_i+1 = d_i$ for all $i=1,...,n-1$, then the product $prod A_i$ will have entries given by a similar summation, which I leave you to figure out, where each $a_i$ in the index set will not vary from $1$ to $n$, but something else. The expression for entries of the power is a special case of this formula, which can also be proved by induction.
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You have to use more indices to express the entry of $P^n$.
To be more precise for any matrix $P$ with entries $P_ij$, the entries of the matrix $P^n$, given by $(P^n)_ij$ are given by :
$$
(P^n)_ij = sum_a_1,a_2,...,a_n-1 = 1^n P_ia_1P_a_1a_2ldots P_a_n-2a_n-1P_a_n-1j
$$
so the number of indices changes with the power. This formula can easily proved by induction, as you saw for the case $n=2$ to $n=3$ by substitution.
Note that the problem of having $n-1$ summations is solved by iterating over a different set that contains all the possible types of indices : this is why we can combine $a_1,...,a_n-1$ into one summation.
Furthermore, a very similar formula applies for the product of $n$ matrices in an admissible order (number of columns of left matrix equals number of rows of the right matrix). More precisely , if $A_i$, $i=1,...,n$ are $c_i times d_i$ matrices such that $c_i+1 = d_i$ for all $i=1,...,n-1$, then the product $prod A_i$ will have entries given by a similar summation, which I leave you to figure out, where each $a_i$ in the index set will not vary from $1$ to $n$, but something else. The expression for entries of the power is a special case of this formula, which can also be proved by induction.
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
You have to use more indices to express the entry of $P^n$.
To be more precise for any matrix $P$ with entries $P_ij$, the entries of the matrix $P^n$, given by $(P^n)_ij$ are given by :
$$
(P^n)_ij = sum_a_1,a_2,...,a_n-1 = 1^n P_ia_1P_a_1a_2ldots P_a_n-2a_n-1P_a_n-1j
$$
so the number of indices changes with the power. This formula can easily proved by induction, as you saw for the case $n=2$ to $n=3$ by substitution.
Note that the problem of having $n-1$ summations is solved by iterating over a different set that contains all the possible types of indices : this is why we can combine $a_1,...,a_n-1$ into one summation.
Furthermore, a very similar formula applies for the product of $n$ matrices in an admissible order (number of columns of left matrix equals number of rows of the right matrix). More precisely , if $A_i$, $i=1,...,n$ are $c_i times d_i$ matrices such that $c_i+1 = d_i$ for all $i=1,...,n-1$, then the product $prod A_i$ will have entries given by a similar summation, which I leave you to figure out, where each $a_i$ in the index set will not vary from $1$ to $n$, but something else. The expression for entries of the power is a special case of this formula, which can also be proved by induction.
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
edited Jul 30 at 4:20
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
answered Jul 30 at 4:14
ðÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
31.7k22463
31.7k22463
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
add a comment |Â
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Is my formula for $p_ij^(3)$ incorrect, then? Should it instead be $sum_r=1^n sum_k=1^n p_rjp_ikp_kr$?
– BSplitter
Jul 30 at 4:21
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
Yes, what you have written now is correct, and the earlier one was wrong.
– Ã°ÑÂтþý òіûûð þûþф üÑÂûûñÑÂрó
Jul 30 at 8:23
add a comment |Â
up vote
0
down vote
If your matrix is diagonalizable then we have, $A in mathbbC^n times n $
$$ A = V Lambda V^*$$
$$ A^n = VLambda^n V^* $$
now matrix multiplication is
$$ (AB)_ik = sum_k=1^n a_ijb_jk $$
then we have
$$ ((AB)C))_il = sum_k=1^p sum_j=1^n a_ijb_jk c_kl $$
$$ (A)_il^c = sum_k=1^p sum_j=1^n v_ij lambda_jk^cv_kl^t$$
now all $ lambda^c $ is the entries exponentiatied.
answered Jul 30 at 4:42
RHowe
915715
add a comment |Â
up vote
0
down vote
If your matrix is diagonalizable then we have, $A in mathbbC^n times n $
$$ A = V Lambda V^*$$
$$ A^n = VLambda^n V^* $$
now matrix multiplication is
$$ (AB)_ik = sum_k=1^n a_ijb_jk $$
then we have
$$ ((AB)C))_il = sum_k=1^p sum_j=1^n a_ijb_jk c_kl $$
$$ (A)_il^c = sum_k=1^p sum_j=1^n v_ij lambda_jk^cv_kl^t$$
now all $ lambda^c $ is the entries exponentiatied.
answered Jul 30 at 4:42
RHowe
915715
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If your matrix is diagonalizable then we have, $A in mathbbC^n times n $
$$ A = V Lambda V^*$$
$$ A^n = VLambda^n V^* $$
now matrix multiplication is
$$ (AB)_ik = sum_k=1^n a_ijb_jk $$
then we have
$$ ((AB)C))_il = sum_k=1^p sum_j=1^n a_ijb_jk c_kl $$
$$ (A)_il^c = sum_k=1^p sum_j=1^n v_ij lambda_jk^cv_kl^t$$
now all $ lambda^c $ is the entries exponentiatied.
answered Jul 30 at 4:42
RHowe
915715
If your matrix is diagonalizable then we have, $A in mathbbC^n times n $
$$ A = V Lambda V^*$$
$$ A^n = VLambda^n V^* $$
now matrix multiplication is
$$ (AB)_ik = sum_k=1^n a_ijb_jk $$
then we have
$$ ((AB)C))_il = sum_k=1^p sum_j=1^n a_ijb_jk c_kl $$
$$ (A)_il^c = sum_k=1^p sum_j=1^n v_ij lambda_jk^cv_kl^t$$
now all $ lambda^c $ is the entries exponentiatied.
answered Jul 30 at 4:42
RHowe
915715
edited Jul 30 at 17:54
answered Jul 30 at 4:42
RHowe
915715
answered Jul 30 at 4:42
RHowe
915715
answered Jul 30 at 4:42
RHowe
915715
915715
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%2f2866648%2fhow-to-write-out-the-elements-of-a-matrix-that-has-been-taken-to-the-nth-power%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
Your approach is right. For $n$th power you need $n-1$ intermediate index name as you've done in he third power case with 2 intermediate variables.
– coffeemath
Jul 30 at 4:01
So I can see that I would have $n-1$ summations, but would be the arguments of those summations, exactly?
– BSplitter
Jul 30 at 4:06
Is the matrix diagonizable?
– RHowe
Jul 30 at 4:25
@Geronimo I'm not sure. I believe so, but I'd have to study up on diagonalizability again. The matrices I'm concerned about are irreducible transition matrices used in Markov chains, so each row should sum to one.
– BSplitter
Jul 30 at 4:34