Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How does one show a matrix is irreducible and reducible? Please explain and an example would be great as well.

I know that a matrix is reducible if and only if it can be placed into block upper-triangular form. How do you find block upper-triangular form?

share|cite|improve this question
5  
Maybe you can remind us --- what does irreducible mean, in the context of matrices? what does reducible mean? – Gerry Myerson Feb 27 '13 at 2:01

A square matrix is reducible iff the associated directed graph has smaller strongly connected components. So you may use a strong component algorithm to solve your problem.

share|cite|improve this answer
1  
Please what is an associated directed graph of a matrix? – npisinp Apr 11 '14 at 14:04
2  
@npisinp Let the matrix in question be $A$ and let $B=(b_{ij})$ be the matrix such that $b_{ij}=1$ if $a_{ij}\ne0$, and $b_{ij}=0$ if $a_{ij}=0$. Then $B$ is the adjacency matrix of a directed graph, and $A$ is reducible iff this directed graph has proper strongly connected components. – user1551 Apr 13 '14 at 12:23

The best place to look is this wiki link. To add to the other answer, another equivalent condition is that for every index $[i,j]$, there should be a $m$ such that $(A^m)_{ij}>0$ which is naturally satisfied if the matrix entries are all positive. If it is non-negative, then one needs to check other things.

share|cite|improve this answer
    
In my opinion this answer is a bit broad, because the provided wiki link links to a theorem that uses the irreducibilty of a Matrix. That is, there is no algorithm outlined to solve the reduciblity question. – kiltek Dec 3 '14 at 9:46

There is another simple criterion for the irreducibility of a matrix with non negative entries. Such an $n\times n$-matrix $A$ is irreducible if and only if all entries of $$\sum\limits_{i=0}^{n}A^i$$ are greater then 0.

Since i do not have a reference, i will briefly sketch a proof: Using the definition, that $A$ is irreducible iff for all indices $i,j$ there is an exponent $e_{i,j}$, such that entry $[A^{e_{i,j}}]_{ij}$ is positive (where $[C]_{ij}$ denotes the entry at $i,j$ of a matrix $C$).

Let $B$ be the matrix obtained from $A$ by replacing all non zero entries by 1.

(1) Show that $A$ is irreducible iff B is irreducible.

(2) Show that $\sum\limits_{i=0}^{n}A^i$ has only positive entries iff this is true for $\sum\limits_{i=0}^{n}B^i$.

(3) Let $G$ be the directed graph with vertices $\{1,2,\ldots,n\}$, where there is an edge from $i$ to $j$ iff $b_{ij}>0$. Show, by induction on $m$, that the entry of $[B^m]_{ij}$ corresponds to the number of directed paths from $i$ to $j$.

According to (3), for $m\in\mathbb{N}$ the number of directed paths from $i$ to $j$ of length at most $m$ is $\left[\sum\limits_{k=0}^mB^k\right]_{ij}$. Now the claim follows form the following equivalences: $$\begin{array}{rl} &\text{$B$ is an irreducible matrix.}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$, there is a directed path in $G$ from $i$ to $j$.}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$, there is a directed path in $G$ from $i$ to $j$ of length at most $n$}\\ &\text{(note that this graph has exactly $n$ vertices).}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$ holds $\left[\sum\limits_{k=0}^{n}B^k\right]_{ij}>0$.} \end{array}$$

share|cite|improve this answer
    
Could you site the reference which gives this result ? – Shailesh Mar 18 at 22:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.