Irreducible matrix

from Wikipedia, the free encyclopedia

Irreducibility of matrices is a concept of linear algebra that is closely related to graph theory . Put simply, a is matrix irreducible if its rows and columns can not be permuted so that the matrix is transferred to the lower block triangular shape.

In addition to applications in graph theory, the concept of irreducibility is used in the theory of positive eigenvalues ​​and vectors, see for example Perron-Frobenius' theorem .

definition

A matrix is said to be reducible if there is a permutation matrix such that

It is made with and the other block matrices dimensioned accordingly appropriate. If this rearrangement is not possible, the matrix is ​​called irreducible .

Potency and irreducibility

If all entries of the matrix are nonnegative and if the main diagonal is really positive, then the irreducibility of is equivalent to the fact that a number exists for which

holds, that is, all entries of the matrix power are positive. The statement that a matrix is irreducible is somewhat weaker if it holds and there exists such that is.

A matrix with non-negative entries is irreducible if and only if there is a number for each index pair so that the entry of is positive.

use

Irreducible matrices play a role for the existence of eigenvectors and the dimension of the associated eigenspace, see Perron-Frobenius theorem . Furthermore, there is a close connection to graph theory : The adjacency matrix of a directed graph is irreducible if and only if the graph is strongly connected . Furthermore , if it is irreducible, then it is also irreducible. In addition, the irreducibility of a stochastic matrix is equivalent to the irreducibility of the Markov chain , which is described by the stochastic matrix.

example

The adjacency graph of the matrix . There is no path from node 3 to node 2, so the graph is not
strongly connected .

As an example, consider the following matrix:

The transposed matrix is

This means that the matrix has the required triangular block shape and is therefore reducible.

Web links

literature

Individual evidence

  1. Peter Knabner, Wolf Barth: Lineare Algebra. Basics and Applications . Springer Spectrum, 2013, p. 842 .