| View previous topic :: View next topic |
| Author |
Message |
mhasoba
Guest
|
 Posted: Tue Oct 28, 2008 6:24 pm Post subject: eigenvalue monotonicity |
 |
|
Dear all,
I was hoping that somebody could provide me with some insights into
the following problem.
Given a real matrix A and its non-negative counterpart, |A| (wherein
all the matrix entries have been replaced by their absolute values),
it is known that rho(A) <= rho(|A|) (e.g., theorem 8.1.18 in Horn and
Johnson, 1985), where given a nxn matrix X, rho(X) is its spectral
radius (absolute value of the eigenvalue with largest magnitude).
However, can it be shown possibly under certain restrictions on A,
that rho(A) increases (possibly monotonically) with rho(|A|)?
Many thanks in advance!
Mhasoba |
|
| |
|
 Back to top |
Robert Israel
Guest
|
| Posted: Wed Oct 29, 2008 4:51 am Post subject: Re: eigenvalue monotonicity |
|
|
mhasoba <mhasoba@gmail.com> writes:
[quote]Dear all,
I was hoping that somebody could provide me with some insights into
the following problem.
Given a real matrix A and its non-negative counterpart, |A| (wherein
all the matrix entries have been replaced by their absolute values),
it is known that rho(A) <= rho(|A|) (e.g., theorem 8.1.18 in Horn and
Johnson, 1985), where given a nxn matrix X, rho(X) is its spectral
radius (absolute value of the eigenvalue with largest magnitude).
However, can it be shown possibly under certain restrictions on A,
that rho(A) increases (possibly monotonically) with rho(|A|)?
[/quote]
Certainly some conditions are needed. For example, consider the 2 x 2
family
[ 1 t ]
A = [ -t -1 ]
where rho(|A|) = 1 + |t| while rho(A) = |sqrt(1-t^2)|
= sqrt(1-t^2) for |t| <= 1, sqrt(t^2 - 1) for |t| >= 1.
Thus e.g. as t goes from 0 to 1, rho(|A|) increases while
rho(A) decreases, while as t goes from 1 to +infty both increase.
What sort of restrictions did you have in mind?
--
Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada |
|
| |
|
| Back to top |
mhasoba
Guest
|
| Posted: Wed Oct 29, 2008 5:21 pm Post subject: Re: eigenvalue monotonicity |
|
|
On Oct 28, 6:51 pm, Robert Israel
<isr...@math.MyUniversitysInitials.ca> wrote:
[quote]mhasoba <mhas...@gmail.com> writes:
Dear all,
I was hoping that somebody could provide me with some insights into
the following problem.
Given a real matrix A and its non-negative counterpart, |A| (wherein
all the matrix entries have been replaced by their absolute values),
it is known that rho(A) <= rho(|A|) (e.g., theorem 8.1.18 in Horn and
Johnson, 1985), where given a nxn matrix X, rho(X) is its spectral
radius (absolute value of the eigenvalue with largest magnitude).
However, can it be shown possibly under certain restrictions on A,
that rho(A) increases (possibly monotonically) with rho(|A|)?
Certainly some conditions are needed. For example, consider the 2 x 2
family
[ 1 t ]
A = [ -t -1 ]
where rho(|A|) = 1 + |t| while rho(A) = |sqrt(1-t^2)|
= sqrt(1-t^2) for |t| <= 1, sqrt(t^2 - 1) for |t| >= 1.
Thus e.g. as t goes from 0 to 1, rho(|A|) increases while
rho(A) decreases, while as t goes from 1 to +infty both increase.
What sort of restrictions did you have in mind?
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
[/quote]
The type of matrices I am dealing with are share the following
characteristics:
(1) structurally symmetry (A_ij ~= 0 iff A_ji ~= 0).
(2) diagonal elements are all zero.
(3) The matrix entries are not necessarily < 1.
Based upon numerical simulations, I find that across a large enough
range of rho(|A|), rho(A) does increase monotonically (actually,
linearly). The numerical simulations were performed by varying the
magnitudes of the matrix entries (at random), while keeping the sign
and sparsity structure constant. The type of sign and sparsity
structure do not affect the overall result.
mhasoba |
|
| |
|
| Back to top |
Robert Israel
Guest
|
| Posted: Thu Oct 30, 2008 7:11 am Post subject: Re: eigenvalue monotonicity |
|
|
mhasoba <mhasoba@gmail.com> writes:
[quote]On Oct 28, 6:51=A0pm, Robert Israel
isr...@math.MyUniversitysInitials.ca> wrote:
mhasoba <mhas...@gmail.com> writes:
Dear all,
I was hoping that somebody could provide me with some insights into
the following problem.
Given a real matrix A and its non-negative counterpart, |A| (wherein
all the matrix entries have been replaced by their absolute values),
it is known that rho(A) <=3D rho(|A|) (e.g., theorem 8.1.18 in Horn and
Johnson, 1985), where given a nxn matrix X, rho(X) is its spectral
radius (absolute value of the eigenvalue with largest magnitude).
However, can it be shown possibly under certain restrictions on A,
that rho(A) increases (possibly monotonically) with rho(|A|)?
Certainly some conditions are needed. =A0For example, consider the 2 x 2
family
=A0 =A0 [ 1 =A0 t ]
A =3D [ -t -1 ]
where rho(|A|) =3D 1 + |t| while rho(A) =3D |sqrt(1-t^2)|
=3D sqrt(1-t^2) for |t| <=3D 1, sqrt(t^2 - 1) for |t| >=3D 1.
Thus e.g. as t goes from 0 to 1, rho(|A|) increases while
rho(A) decreases, while as t goes from 1 to +infty both increase.
What sort of restrictions did you have in mind?
--
Robert Israel =A0 =A0 =A0 =A0 =A0 =A0
=A0isr...@math.MyUniversitysInitial=
s.ca
Department of Mathematics =A0 =A0 =A0 =A0http://www.math.ubc.ca/~israel
University of British Columbia =A0 =A0 =A0 =A0 =A0 =A0Vancouver, BC,
Cana=
da
The type of matrices I am dealing with are share the following
characteristics:
(1) structurally symmetry (A_ij ~=3D 0 iff A_ji ~=3D 0).
(2) diagonal elements are all zero.
(3) The matrix entries are not necessarily < 1.
Based upon numerical simulations, I find that across a large enough
range of rho(|A|), rho(A) does increase monotonically (actually,
linearly). The numerical simulations were performed by varying the
magnitudes of the matrix entries (at random), while keeping the sign
and sparsity structure constant. The type of sign and sparsity
structure do not affect the overall result.
[/quote]
OK, try a 3 x 3 example:
[ 0 -1 t ]
A = [ 1 0 t ]
[ 1 1 0 ]
Eigenvalues of A are 0 and (+/-) sqrt(-1+2 a), so rho(A) = sqrt(|-1+2a|).
Eigenvalues of |A| are -1 and 1/2 (+/-) sqrt(1+8|a|), so
rho(|A|) = 1/2 + 1/2 sqrt(1+8|a|). As a increases from 0, rho(|A|) increases
but rho(A) first decreases (to 0 at a = 1/2) and then increases.
--
Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada |
|
| |
|
| Back to top |
mhasoba
Guest
|
| Posted: Sat Nov 01, 2008 12:49 pm Post subject: Re: eigenvalue monotonicity |
|
|
On Oct 29, 9:11 pm, Robert Israel
<isr...@math.MyUniversitysInitials.ca> wrote:
[quote]mhasoba<mhas...@gmail.com> writes:
On Oct 28, 6:51=A0pm, Robert Israel
isr...@math.MyUniversitysInitials.ca> wrote:
mhasoba<mhas...@gmail.com> writes:
Dear all,
I was hoping that somebody could provide me with some insights into
the following problem.
Given a real matrix A and its non-negative counterpart, |A| (wherein
all the matrix entries have been replaced by their absolute values),
it is known that rho(A) <=3D rho(|A|) (e.g., theorem 8.1.18 in Horn and
Johnson, 1985), where given a nxn matrix X, rho(X) is its spectral
radius (absolute value of the eigenvalue with largest magnitude).
However, can it be shown possibly under certain restrictions on A,
that rho(A) increases (possibly monotonically) with rho(|A|)?
Certainly some conditions are needed. =A0For example, consider the 2 x 2
family
=A0 =A0 [ 1 =A0 t ]
A =3D [ -t -1 ]
where rho(|A|) =3D 1 + |t| while rho(A) =3D |sqrt(1-t^2)|
=3D sqrt(1-t^2) for |t| <=3D 1, sqrt(t^2 - 1) for |t| >=3D 1.
Thus e.g. as t goes from 0 to 1, rho(|A|) increases while
rho(A) decreases, while as t goes from 1 to +infty both increase.
What sort of restrictions did you have in mind?
--
Robert Israel =A0 =A0 =A0 =A0 =A0 =A0
=A0isr...@math.MyUniversitysInitial> > s.ca
Department of Mathematics =A0 =A0 =A0 =A0http://www.math.ubc.ca/~israel
University of British Columbia =A0 =A0 =A0 =A0 =A0 =A0Vancouver, BC,
Cana> > da
The type of matrices I am dealing with are share the following
characteristics:
(1) structurally symmetry (A_ij ~=3D 0 iff A_ji ~=3D 0).
(2) diagonal elements are all zero.
(3) The matrix entries are not necessarily < 1.
Based upon numerical simulations, I find that across a large enough
range of rho(|A|), rho(A) does increase monotonically (actually,
linearly). The numerical simulations were performed by varying the
magnitudes of the matrix entries (at random), while keeping the sign
and sparsity structure constant. The type of sign and sparsity
structure do not affect the overall result.
OK, try a 3 x 3 example:
[ 0 -1 t ]
A = [ 1 0 t ]
[ 1 1 0 ]
Eigenvalues of A are 0 and (+/-) sqrt(-1+2 a), so rho(A) = sqrt(|-1+2a|).
Eigenvalues of |A| are -1 and 1/2 (+/-) sqrt(1+8|a|), so
rho(|A|) = 1/2 + 1/2 sqrt(1+8|a|). As a increases from 0, rho(|A|) increases
but rho(A) first decreases (to 0 at a = 1/2) and then increases.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
[/quote]
Yes, this is a good counterexample. I am going to try and determine
which sign structures determine monotonicity. |
|
| |
|
| Back to top |
Peter Spellucci
Guest
|
| Posted: Sat Nov 01, 2008 4:39 pm Post subject: Re: eigenvalue monotonicity |
|
|
In article <4ac2b347-7fae-487e-891b-05967e2d8f4f@k36g2000pri.googlegroups.com>,
mhasoba <mhasoba@gmail.com> writes:
[quote]On Oct 29, 9:11=A0pm, Robert Israel
isr...@math.MyUniversitysInitials.ca> wrote:
[/quote]
snip
[quote]OK, try a 3 x 3 example:
[ 0 -1 t ]
A = [ 1 0 t ]
[ 1 1 0 ]
Eigenvalues of A are 0 and (+/-) sqrt(-1+2 a), so rho(A) =3D sqrt(|-1+2a|=
).
Eigenvalues of |A| are -1 and 1/2 (+/-) sqrt(1+8|a|), so
rho(|A|) =3D 1/2 + 1/2 sqrt(1+8|a|). =A0As a increases from 0, rho(|A|) i=
ncreases
but rho(A) first decreases (to 0 at a =3D 1/2) and then increases.
[/quote]
snip
[quote]Yes, this is a good counterexample. I am going to try and determine
which sign structures determine monotonicity.
[/quote]
you wrote in your experiments yuo consistently observed the
monotonicity you are behind: maybe it is this:
if
DA(_(ij) has the same sign as A_(ij) for all i,j
A is diagonalizable (random matrices _are_ diagonalizable, ususally)
the perturbation is so small that the eigenvector to the
dominant eigenvalue doesn>t change sign in any of its components:
then
(obviously) rho(abs(A)) <= rho(abs(A+DA))
and
rho(A) <= rho(A+DA) due to the fact that the Rayleighquotinet of
A+DA (with the eigenvector to the dominant eigenvalue of A) increases
and rho(A+DA) can be expressed as a Rayleigh quotient (and in the hermitian case
is the max of this)
hth
peter |
|
| |
|
| Back to top |
|
