The definition I am thinking of is

A nonnegative matrix $A$ is said to be reducible if there exists a aprtition of the index set $\{1,2,\dots,n\}$ into nonempty disjoint sets $I_1,I_2$ such that $a_{ij} =0$ whenever $i\in I_1$ and $j\in I_2$

I am wondering if anyone has some intuition on what such matrices look like. Or perhaps some intuition on the structure this puts on matrices.

To me it seems like a reducible matrix is one that has to have a certain number of zeros (at least $(n-1)$ zeros?) and is such that these zeros are, in perhaps a loose sense, asymmetrically located in the matrix. (because if $a_{ij}=0$ then it cant be that $a_{ji}=0$ because then $j\in I_2$ and $j\in I_i$ violating disjointness)

But the above way of thinking about reducible seems too literal.

I found this blog post about reducibility That talks about reducibility in terms of having an invariant non-trivial subspace. I see why this is useful but I don't see how to link this definition to the one I provided

  • 1
    $\begingroup$ Is a block-diagonal matrix intuitive to you? A reducible matrix is one that is block diagonal after conjugation by a permutation matrix, i.e. there exists a permutation matrix $P$ (possibly the identity, of course) such that $PAP^T$ is block diagonal. This conjugation by a permutation matrix basically means that you permute rows and columns in exactly the same way (so you don't scramble up which variable is which between the domain vs. codomain, you just change the order). $\endgroup$ – Ian Oct 5 '18 at 2:00

It means the submatrix $A(I_1,I_2)$ is zero. Alternatively, $A$ is permutationally similar to a block triangular matrix, i.e. $P^{-1}AP=\pmatrix{B&\ast\\ 0&C}$, where $B,C$ are non-empty square matrices of possibly different sizes. (More specifically, $P$ is the permutation matrix such that $P(I_2,\{1,2,\ldots,|I_2|\})$ and $P(I_1,\{(|I_2|+1),\ldots,n\})$ are identity matrices of sizes $|I_2|$ and $|I_1|$ respectively.)

As for the blog entry in the link, at the time of writing, I don't think the author's definition in terms of invariant subspace is correct. For example, every positive matrix $A$ has a positive eigenvector $v$ corresponding to the eigenvalue $\rho(A)$. Hence the linear span of $v$ is always a proper invariant subspace of $\mathbb R^n$. But $A$ is clearly not reducible because it hasn't any zero entry. Since reducibility is a basis-dependent concept (it is not preserved under similarity transform), the author's definition just does not sound right.

By the way, if I remember correctly, $A$ is not required to be nonnegative in Frobenius' original definition, but nowadays, in the context of Perron-Frobenius theorem, nonnegativeness of $A$ is commonly accepted as part of the definition.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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