What is an "indecomposable" matrix?

Solution 1:

See this entry in Planet Math: Fully Indecomposable Matrix.

See also Special matrices: scroll to "Decomposable". You'll find what it means to be decomposable, partly decomposable, and fully indecomposable.

Note: The term irreducible is usually used instead of indecomposable.

Wikipedia: "...a matrix is irreducible if it is not similar via a permutation to a block upper triangular matrix (that has more than one block of positive size)."
(Replacing non-zero entries in the matrix by one, and viewing the matrix as the adjacency matrix of a directed graph, the matrix is irreducible if and only if the digraph is irreducible.)

PlanetMath: reducible matrix
"An $n\times n$ matrix $A$ is said to be a reducible matrix *if and only if* for some permutation matrix $P$, the matrix $P^TAP$ is block upper triangular matrix."
If a square matrix is not reducible, it is said to be an irreducible matrix.

Solution 2:

An $n \times n$ matrix $A$ is reducible if there is a permutation matrix $P$ so that

$$PAP^T=\begin{bmatrix}B&C\\0&D\end{bmatrix}$$

where $B$ and $D$ are square. Equivalently, $A$ is reducible if it has a $k \times (n-k)$ zero submatrix with disjoint column and row indices.

If $A$ is not reducible, it is irreducible.

On the other hand, $A$ is partly decomposable if there are permutation matrices $P$ and $Q$ so that

$$PAQ=\begin{bmatrix}B&C\\0&D\end{bmatrix}$$

where $B$ and $D$ are square. Equivalently, $A$ is partly decomposable if it has a $k \times (n-k)$ zero submatrix.

If $A$ is not partly decomposable, it is fully indecomposable (or sometimes totally indecomposable).

Every fully indecomposable matrix is irreducible, but the converse is false in general.

Brualdi and Ryser's Combinatorial Matrix Theory provides the following comment on this terminology:

One may wonder why the adverbs "partly" and "fully" are being used here. The reason is that the terminology "decomposable" and "indecomposable" is sometimes used in place of "reducible" and "irreducible." A reducible matrix of order $n$ also has a $k$ by $n-k$ zero submatrix for some integer $k$ but the row indices and column indices of the zero submatrix are disjoint sets. Thus reducibility is a more severe restriction on a matrix than that of part decomposability.

Indecomposable almost always means irreducible rather than fully indecomposable, but most authors, as with Brualdi and Ryser above, prefer to stick to irreducible and fully indecomposable, avoiding indecomposable.

Solution 3:

We shall call two matrices $A$ and $В$ permutation equivalent, or p-equivalent, if there exist permutation matrices $P$ and $Q$ such that $A=PBQ$.

An $n\times n$ nonnegative matrix is said to be partly decomposable if it contains an $s \times \left(n - s\right)$ zero submatrix. In other words, a matrix is partly decomposable if it is p-equivalent to a matrix of the form

$$\left[\begin{matrix} X & Y\\ 0 & Z \end{matrix}\right]$$

where $X$ and $Z$ are square. If an $n\times n$ nonnegative matrix contains no $s \times(n - s)$ zero submatrix, it is said to be fully indecomposable.