# Fully indecomposable matrices are primitive

How can I show that a fully indecomposable (non negative) matrix $A$ is primitive?

A non negative matrix $A\in\mathbb{R}^n$ is said fully indecomposable if it doesn't exist permutation matrices $P,Q$ such that $$PAQ=\begin{bmatrix}X &0\\Y & Z\end{bmatrix}$$ where $X,Z$ are square matrices.

A non negative matrix is said primitive if there exists an integer $m>0$ such that $A^m$ all entries strictly positive.

• Can you be a little more specific? – Pietro Paparella Apr 16 '18 at 21:28
• Sure, I have just edited. – aleio1 Apr 16 '18 at 22:17

If $A$ is an $n$-by-$n$ matrix with complex entries, then the digraph of $A$, denoted by $\Gamma(A)$, is the directed graph with vertices $V := \{1,\dots,n\}$ and edges $E = \{ (i,j) \mid a_{ij} \ne 0\}$. It is well-known that $A$ is irreducible (i.e.,indecomposable) if and only if $A$ is strongly-connected, i.e., there is a directed path from vertex $i$ to vertex $j$, for every $i$ and $j$ (note that a vertex is considered as strongly connected to itself).
For a strongly directed digraph $\Gamma$, let $k = k(\Gamma)$ be the greatest common divisor of all lengths of all directed cycles of $\Gamma$. Brualdi and Ryser [MR1130611; Combinatorial Matrix Theory] define a matrix $A$ as primitive if $\Gamma(A)$ is irredcible and $k=1$. It is shown (Theorem 3.4.4) that a nonnegative matrix $A$ is primitive if and only if there is a positive integer $N$ such that $A^m$ is positive for every $m \ge N$. Since these properties are equivalent, it suffices to determine the gcd of the cycle-lengths, for which tests are available.