Spectral radius of the product of two matrices
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let us define the following matrix multiplication:
$$C=AB$$
where $B$ is a block diagonal matrix with $N$ blocks, $B_1$, $B_2$,..., $B_N$, each of dimensions $M times M$. I know that $B_k = I_M - mu R_k$ with $R_k$ equals to a hermitian matrix and $mu$ equal to some positive constant. Moreover, I know that the the entries of the matrix $A$ are non-negative real numbers. I also know that the matrix $A$ is right stochastic, i.e., the sum of the elements in each row equals one. Can I say that the spectral radius of C is smaller than one for some values of $mu$? If so, can I determine the range of values of $mu$ under which the spectral radius of $C$ is smaller than one?
matrices norm spectral-radius
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
asked Feb 20 '16 at 12:30
user316165
62
add a comment |Â
up vote
1
down vote
favorite
Let us define the following matrix multiplication:
$$C=AB$$
where $B$ is a block diagonal matrix with $N$ blocks, $B_1$, $B_2$,..., $B_N$, each of dimensions $M times M$. I know that $B_k = I_M - mu R_k$ with $R_k$ equals to a hermitian matrix and $mu$ equal to some positive constant. Moreover, I know that the the entries of the matrix $A$ are non-negative real numbers. I also know that the matrix $A$ is right stochastic, i.e., the sum of the elements in each row equals one. Can I say that the spectral radius of C is smaller than one for some values of $mu$? If so, can I determine the range of values of $mu$ under which the spectral radius of $C$ is smaller than one?
matrices norm spectral-radius
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
asked Feb 20 '16 at 12:30
user316165
62
Since $I$ is also Hermitian, can't you just say that $B_k$ is Hermitian? Given a Hermitian matrix $B$, you can compute $X = I-B$, which is also Hermitian, and call $X$ by the name $R_k$, so simply saying $B_k$ is Hermitian is the same as saying it has the form you specified.
– John Hughes
Feb 20 '16 at 15:00
True. You are right $X=I-B$ is hermitian. Does this help to have an answer? Thanks!
– user316165
Feb 20 '16 at 15:09
No idea. But it does simplify the question, which is sometimes a good start. And it makes user1551's counterexample no longer work in general, because the matrix $B$ produced by that answer is generally not Hermitian.
– John Hughes
Feb 20 '16 at 15:34
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let us define the following matrix multiplication:
$$C=AB$$
where $B$ is a block diagonal matrix with $N$ blocks, $B_1$, $B_2$,..., $B_N$, each of dimensions $M times M$. I know that $B_k = I_M - mu R_k$ with $R_k$ equals to a hermitian matrix and $mu$ equal to some positive constant. Moreover, I know that the the entries of the matrix $A$ are non-negative real numbers. I also know that the matrix $A$ is right stochastic, i.e., the sum of the elements in each row equals one. Can I say that the spectral radius of C is smaller than one for some values of $mu$? If so, can I determine the range of values of $mu$ under which the spectral radius of $C$ is smaller than one?
matrices norm spectral-radius
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
asked Feb 20 '16 at 12:30
user316165
62
Let us define the following matrix multiplication:
$$C=AB$$
where $B$ is a block diagonal matrix with $N$ blocks, $B_1$, $B_2$,..., $B_N$, each of dimensions $M times M$. I know that $B_k = I_M - mu R_k$ with $R_k$ equals to a hermitian matrix and $mu$ equal to some positive constant. Moreover, I know that the the entries of the matrix $A$ are non-negative real numbers. I also know that the matrix $A$ is right stochastic, i.e., the sum of the elements in each row equals one. Can I say that the spectral radius of C is smaller than one for some values of $mu$? If so, can I determine the range of values of $mu$ under which the spectral radius of $C$ is smaller than one?
matrices norm spectral-radius
matrices norm spectral-radius
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
asked Feb 20 '16 at 12:30
user316165
62
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
asked Feb 20 '16 at 12:30
user316165
62
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
edited May 21 at 11:29
Rodrigo de Azevedo
12.7k41751
12.7k41751
asked Feb 20 '16 at 12:30
user316165
62
asked Feb 20 '16 at 12:30
user316165
62
asked Feb 20 '16 at 12:30
user316165
62
62
Since $I$ is also Hermitian, can't you just say that $B_k$ is Hermitian? Given a Hermitian matrix $B$, you can compute $X = I-B$, which is also Hermitian, and call $X$ by the name $R_k$, so simply saying $B_k$ is Hermitian is the same as saying it has the form you specified.
– John Hughes
Feb 20 '16 at 15:00
True. You are right $X=I-B$ is hermitian. Does this help to have an answer? Thanks!
– user316165
Feb 20 '16 at 15:09
No idea. But it does simplify the question, which is sometimes a good start. And it makes user1551's counterexample no longer work in general, because the matrix $B$ produced by that answer is generally not Hermitian.
– John Hughes
Feb 20 '16 at 15:34
add a comment |Â
Since $I$ is also Hermitian, can't you just say that $B_k$ is Hermitian? Given a Hermitian matrix $B$, you can compute $X = I-B$, which is also Hermitian, and call $X$ by the name $R_k$, so simply saying $B_k$ is Hermitian is the same as saying it has the form you specified.
– John Hughes
Feb 20 '16 at 15:00
True. You are right $X=I-B$ is hermitian. Does this help to have an answer? Thanks!
– user316165
Feb 20 '16 at 15:09
No idea. But it does simplify the question, which is sometimes a good start. And it makes user1551's counterexample no longer work in general, because the matrix $B$ produced by that answer is generally not Hermitian.
– John Hughes
Feb 20 '16 at 15:34
Since $I$ is also Hermitian, can't you just say that $B_k$ is Hermitian? Given a Hermitian matrix $B$, you can compute $X = I-B$, which is also Hermitian, and call $X$ by the name $R_k$, so simply saying $B_k$ is Hermitian is the same as saying it has the form you specified.
– John Hughes
Feb 20 '16 at 15:00
Since $I$ is also Hermitian, can't you just say that $B_k$ is Hermitian? Given a Hermitian matrix $B$, you can compute $X = I-B$, which is also Hermitian, and call $X$ by the name $R_k$, so simply saying $B_k$ is Hermitian is the same as saying it has the form you specified.
– John Hughes
Feb 20 '16 at 15:00
True. You are right $X=I-B$ is hermitian. Does this help to have an answer? Thanks!
– user316165
Feb 20 '16 at 15:09
True. You are right $X=I-B$ is hermitian. Does this help to have an answer? Thanks!
– user316165
Feb 20 '16 at 15:09
No idea. But it does simplify the question, which is sometimes a good start. And it makes user1551's counterexample no longer work in general, because the matrix $B$ produced by that answer is generally not Hermitian.
– John Hughes
Feb 20 '16 at 15:34
No idea. But it does simplify the question, which is sometimes a good start. And it makes user1551's counterexample no longer work in general, because the matrix $B$ produced by that answer is generally not Hermitian.
– John Hughes
Feb 20 '16 at 15:34
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
No. Consider
$$
B =
beginbmatrix
1 & 0 \
0 & 1
endbmatrix,\
A =
beginbmatrix
-10 & 9 \
9 & -10
endbmatrix
$$
The determinant of $AB$ is $19$, so at least one of the two eigenvalues must be larger than $1$. (They're real because $AB$ is symmetric.)
If you also know that all entries in $A$ are positive, then I suspect that it might be true, but don't have a proof offhand.
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
1
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
add a comment |Â
up vote
0
down vote
The answer is no in general. Suppose $A$ is stochastic but not doubly stochastic. Then its operator norm (i.e. the largest singular value) is strictly greater than $1$. Let $A=USV^T$ be its singular value decomposition. Let $0<frac1_2<epsilon<1$ and define $B=epsilon VU^T$. Then $B$ itself is a big $ntimes n$ block matrix whose operator norm is equal to $epsilon<1$. Yet the spectral radius of $AB=epsilon USU^T$ is $epsilon|A|_2$, which is greater than $1$.
By extending the above construction, we can construct counterexamples such that both $A$ and $B$ are block diagonal and they have identical partitions. Therefore, by continuity, there exist counterexample where the $A$ is entrywise nonzero but $B$ is genuinely/properly block-diagonal as well.
answered Feb 20 '16 at 13:17
user1551
67.2k565123
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
No. Consider
$$
B =
beginbmatrix
1 & 0 \
0 & 1
endbmatrix,\
A =
beginbmatrix
-10 & 9 \
9 & -10
endbmatrix
$$
The determinant of $AB$ is $19$, so at least one of the two eigenvalues must be larger than $1$. (They're real because $AB$ is symmetric.)
If you also know that all entries in $A$ are positive, then I suspect that it might be true, but don't have a proof offhand.
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
1
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
add a comment |Â
up vote
0
down vote
No. Consider
$$
B =
beginbmatrix
1 & 0 \
0 & 1
endbmatrix,\
A =
beginbmatrix
-10 & 9 \
9 & -10
endbmatrix
$$
The determinant of $AB$ is $19$, so at least one of the two eigenvalues must be larger than $1$. (They're real because $AB$ is symmetric.)
If you also know that all entries in $A$ are positive, then I suspect that it might be true, but don't have a proof offhand.
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
1
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
add a comment |Â
up vote
0
down vote
up vote
0
down vote
No. Consider
$$
B =
beginbmatrix
1 & 0 \
0 & 1
endbmatrix,\
A =
beginbmatrix
-10 & 9 \
9 & -10
endbmatrix
$$
The determinant of $AB$ is $19$, so at least one of the two eigenvalues must be larger than $1$. (They're real because $AB$ is symmetric.)
If you also know that all entries in $A$ are positive, then I suspect that it might be true, but don't have a proof offhand.
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
No. Consider
$$
B =
beginbmatrix
1 & 0 \
0 & 1
endbmatrix,\
A =
beginbmatrix
-10 & 9 \
9 & -10
endbmatrix
$$
The determinant of $AB$ is $19$, so at least one of the two eigenvalues must be larger than $1$. (They're real because $AB$ is symmetric.)
If you also know that all entries in $A$ are positive, then I suspect that it might be true, but don't have a proof offhand.
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
answered Feb 20 '16 at 12:46
John Hughes
59.9k23987
59.9k23987
1
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
add a comment |Â
1
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
1
1
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
I would like to specify that the entries of A are nonnegative real numbers. In that case, your counterexample is not valid. Any idea if we know this about A?
– user316165
Feb 20 '16 at 12:50
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
Are you the person asking the question? If you want to add a constraint, by all means do so! If you mean "Did my textbook author mean this?", that's not a question I can really answer, although many people would require nonnegative entries in a matrix before calling it stochastic.
– John Hughes
Feb 20 '16 at 13:20
add a comment |Â
up vote
0
down vote
The answer is no in general. Suppose $A$ is stochastic but not doubly stochastic. Then its operator norm (i.e. the largest singular value) is strictly greater than $1$. Let $A=USV^T$ be its singular value decomposition. Let $0<frac1_2<epsilon<1$ and define $B=epsilon VU^T$. Then $B$ itself is a big $ntimes n$ block matrix whose operator norm is equal to $epsilon<1$. Yet the spectral radius of $AB=epsilon USU^T$ is $epsilon|A|_2$, which is greater than $1$.
By extending the above construction, we can construct counterexamples such that both $A$ and $B$ are block diagonal and they have identical partitions. Therefore, by continuity, there exist counterexample where the $A$ is entrywise nonzero but $B$ is genuinely/properly block-diagonal as well.
answered Feb 20 '16 at 13:17
user1551
67.2k565123
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
add a comment |Â
up vote
0
down vote
The answer is no in general. Suppose $A$ is stochastic but not doubly stochastic. Then its operator norm (i.e. the largest singular value) is strictly greater than $1$. Let $A=USV^T$ be its singular value decomposition. Let $0<frac1_2<epsilon<1$ and define $B=epsilon VU^T$. Then $B$ itself is a big $ntimes n$ block matrix whose operator norm is equal to $epsilon<1$. Yet the spectral radius of $AB=epsilon USU^T$ is $epsilon|A|_2$, which is greater than $1$.
By extending the above construction, we can construct counterexamples such that both $A$ and $B$ are block diagonal and they have identical partitions. Therefore, by continuity, there exist counterexample where the $A$ is entrywise nonzero but $B$ is genuinely/properly block-diagonal as well.
answered Feb 20 '16 at 13:17
user1551
67.2k565123
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The answer is no in general. Suppose $A$ is stochastic but not doubly stochastic. Then its operator norm (i.e. the largest singular value) is strictly greater than $1$. Let $A=USV^T$ be its singular value decomposition. Let $0<frac1_2<epsilon<1$ and define $B=epsilon VU^T$. Then $B$ itself is a big $ntimes n$ block matrix whose operator norm is equal to $epsilon<1$. Yet the spectral radius of $AB=epsilon USU^T$ is $epsilon|A|_2$, which is greater than $1$.
By extending the above construction, we can construct counterexamples such that both $A$ and $B$ are block diagonal and they have identical partitions. Therefore, by continuity, there exist counterexample where the $A$ is entrywise nonzero but $B$ is genuinely/properly block-diagonal as well.
answered Feb 20 '16 at 13:17
user1551
67.2k565123
The answer is no in general. Suppose $A$ is stochastic but not doubly stochastic. Then its operator norm (i.e. the largest singular value) is strictly greater than $1$. Let $A=USV^T$ be its singular value decomposition. Let $0<frac1_2<epsilon<1$ and define $B=epsilon VU^T$. Then $B$ itself is a big $ntimes n$ block matrix whose operator norm is equal to $epsilon<1$. Yet the spectral radius of $AB=epsilon USU^T$ is $epsilon|A|_2$, which is greater than $1$.
By extending the above construction, we can construct counterexamples such that both $A$ and $B$ are block diagonal and they have identical partitions. Therefore, by continuity, there exist counterexample where the $A$ is entrywise nonzero but $B$ is genuinely/properly block-diagonal as well.
answered Feb 20 '16 at 13:17
user1551
67.2k565123
answered Feb 20 '16 at 13:17
user1551
67.2k565123
answered Feb 20 '16 at 13:17
user1551
67.2k565123
answered Feb 20 '16 at 13:17
user1551
67.2k565123
67.2k565123
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
add a comment |Â
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
In particular for $A = beginbmatrix 0 & 1 \ 0 & 1endbmatrix, B = beginbmatrix s & -s \ s & sendbmatrix$, where $s = c sqrt2/2$, we get eigenvalues $csqrt2$ and $0$ for $AB$. In this case, the 2-norm of $B$ is $c$, so picking any value of $c$ like $0.8$ provides a numerical example.
– John Hughes
Feb 20 '16 at 13:40
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%2f1664097%2fspectral-radius-of-the-product-of-two-matrices%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
Since $I$ is also Hermitian, can't you just say that $B_k$ is Hermitian? Given a Hermitian matrix $B$, you can compute $X = I-B$, which is also Hermitian, and call $X$ by the name $R_k$, so simply saying $B_k$ is Hermitian is the same as saying it has the form you specified.
– John Hughes
Feb 20 '16 at 15:00
True. You are right $X=I-B$ is hermitian. Does this help to have an answer? Thanks!
– user316165
Feb 20 '16 at 15:09
No idea. But it does simplify the question, which is sometimes a good start. And it makes user1551's counterexample no longer work in general, because the matrix $B$ produced by that answer is generally not Hermitian.
– John Hughes
Feb 20 '16 at 15:34