The well-known title is from:
http://mathworld.wolfram.com/ReducibleMatrix.html
The corresponding digraph is strongly connected or the undirected graph is connected.
However, the following paper (which can be easily downloaded)
cluster synchronization and isolated desynchronization in complex networks with symmetries
Please see an example of page 7, where $$B = TAT^{-1},$$ which is shown on p.3 (left column). In this example, $A$ is the adjacency matrix (see (8)). As we know, the adjacency matrix of a connected graph is irreducible.
Here, $B$ is diagonal block form matrix, which violates the theorem above. Before carefully understanding the nontrivial procedure to obtain $B$, is there anything wrong in my understanding and argument?
I did not check the computations of the paper, but $T$ is not a permutation matrix. An irreducible matrix cannot be transformed in a block upper-triangular form by a permutation matrix, but a general base-change can modify the matrix as you want.
An example: any circulant matrix induces a strongly connected graph, but are easily diagonalized by an unitary base-change, and a diagonal is an upper triangular matrix. If $\omega_n$ is a primitive $n$-th root of unity, then $$ C_n = \begin{pmatrix} 0 & 1 & & \\ & \ddots & \ddots &\\ & & \ddots & 1\\ 1 & & & 0 \end{pmatrix}\quad Q_n = \frac 1 {\sqrt n} (\omega_n^{(i-1)(j-1)})_{i,j} \implies C_n = Q_n \begin{pmatrix} 1 & & & \\ & \omega_n & &\\ & & \ddots & \\ & & & \omega_n^{n-1} \end{pmatrix} Q_n^H $$