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