From: Steffen Boerm <sbo@numerik.uni-kiel.de>
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  <sbo@numerik.uni-kiel.de> 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 <sbo@numerik.uni-kiel.de> 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