From: Steffen Boerm
Newsgroups: sci.math
Subject: Re: matrix
Date: Tue, 24 Nov 1998 09:31:30 +0100
Michiel wrote:
> When is a matrix irreducible?
> Does irreducibility imply non-degenerate eigenvalues?
Consider the graph G(A) of a matrix A\in\bbbr^{n\times n}:
G(A) = (V, E)
with V={1,...,n}
and (i, j)\in E iff A_{ij}<> 0
An index i is connected to an index j, if there exists a
path in G(A) from i to j.
A is called irreducible if every index is connected to
every other index.
If A is irreducible with only non-negative entries, the
Perron-Frobenius theorem states that the spectral radius
of A is a single eigenvalue of A with a positive eigenvector.
Best regards,
cu, Steffen 8-)
--
Steffen Boerm
EMail: sbo@numerik.uni-kiel.de
WWW: http://www.numerik.uni-kiel.de/~sbo/
==============================================================================
From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Newsgroups: sci.math
Subject: Re: matrix
Date: 24 Nov 1998 16:51:26 -0500
In article <365A6EE2.3CB9@numerik.uni-kiel.de>,
Steffen Boerm wrote:
:Michiel wrote:
:
:> When is a matrix irreducible?
:> Does irreducibility imply non-degenerate eigenvalues?
:
:Consider the graph G(A) of a matrix A\in\bbbr^{n\times n}:
:
: G(A) = (V, E)
:
: with V={1,...,n}
: and (i, j)\in E iff A_{ij}<> 0
:
:An index i is connected to an index j, if there exists a
:path in G(A) from i to j.
:
:A is called irreducible if every index is connected to
:every other index.
:
:If A is irreducible with only non-negative entries, the
:Perron-Frobenius theorem states that the spectral radius
:of A is a single eigenvalue of A with a positive eigenvector.
:
(Typo: a simple eigenvalue)
This does not prevent other eigenvalues from having the same absolute
value as the spectral radius; if there are such eigenvalues, they will be
the vertices of a regular polygon centered at 0.
Other tests for irreducibility: an n-by-n matrix A is irreducible iff
(1) there exists a permutation matrix P such that P^T * A * P is
"reduced", which means of the form
[ B C ]
[ 0 D ]
where B, D are square matrices, and 0 stands for a (rectangular or
square) zero matrix.
(2) (I + abs(A))^n has all entries positive,
(3) (k*I - abs(A))^(-1) has all entries positive for at least one
positive value of k.
One of candidates for k can be any number greater than your favorite
matrix norm of abs(A).
Moreover, in case of irreducibility, (k*I - abs(A))^(-1) will have all
entries positive for all k greater than the spectral radius of abs(A).
You can find out more in R.S. Varga's book "Matrix Iterative Analysis",
Prentice Hall.
Good luck, ZVK(Slavek).
==============================================================================
From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: matrix
Date: 25 Nov 1998 00:07:02 GMT
In article <365A6EE2.3CB9@numerik.uni-kiel.de>, Steffen Boerm writes:
|> Michiel wrote:
|> > When is a matrix irreducible?
|> > Does irreducibility imply non-degenerate eigenvalues?
|> Consider the graph G(A) of a matrix A\in\bbbr^{n\times n}:
|> G(A) = (V, E)
|> with V={1,...,n}
|> and (i, j)\in E iff A_{ij}<> 0
|> An index i is connected to an index j, if there exists a
|> path in G(A) from i to j.
|> A is called irreducible if every index is connected to
|> every other index.
|> If A is irreducible with only non-negative entries, the
|> Perron-Frobenius theorem states that the spectral radius
|> of A is a single eigenvalue of A with a positive eigenvector.
On the other hand, there may be multiple eigenvalues inside the
spectral radius. For example, the irreducible matrix
[ 2 1 1 ]
[ 1 2 1 ]
[ 1 1 2 ]
has a double eigenvalue of 1 in addition to the single eigenvalue 4.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2