Let $A$ be a matrix which is irreducible, so there exists no permutation matrix $P$ such that $P^{T}AP$ is upper block triangular. Let $B$ a matrix for which $A_{ij}\leq B_{ij} \leq 0$ for $i \neq j$ and $0<A_{ii}<B_{ii}$. How can I show that $B$ is irreducible as well?


1 Answer 1


This is not true. Consider, e.g., $$ A=\pmatrix{1&-1\\-1&1}\quad\text{and}\quad B=\pmatrix{2&0\\0&2}. $$ Both $A$ and $B$ satisfy the given conditions but $B$ is reducible.

It would be true if you replaced "$A_{ij}\leq B_{ij}\leq 0$ for $i\neq j$" by "$B_{ij}\leq A_{ij}\leq 0$ for $i\neq j$". This is easy: the only way how to make an irreducible matrix reducible is to set some off-diagonal entries to zero.

  • $\begingroup$ So matrix $B$ isn't a M-matrix? (M-matrix is a K-matrix which is irreducible) $\endgroup$ Nov 9, 2015 at 16:30
  • $\begingroup$ @RoosJansen A matrix does not need to be irreducible to be an M-matrix. (I'm not really sure what is a K-matrix.) Usually, an M-matrix is a Z-matrix which does satisfy one of these conditions. $\endgroup$ Nov 9, 2015 at 16:39
  • $\begingroup$ Thanks! Do you have a hint to proof that B is a M-matrix? (because I thought K-matrix+irreducible implies M-matrix, where a K-matrix is a Z-matrix with diagonal elements bigger than 0) $\endgroup$ Nov 9, 2015 at 16:43
  • $\begingroup$ @RoosJansen If $A$ is real symmetric, then "being an M-matrix" and "being positive definite" are equivalent terms. There are lots of K-matrices which are symmetric but not positive definite (take a symmetric K-matrix with "large" negative off-diagonal entries like $A=\pmatrix{1&-2\\-2&1}$ is a K-matrix, irreducible, but not an M-matrix). $\endgroup$ Nov 9, 2015 at 16:53
  • $\begingroup$ @RoosJansen Otherwise, taking an M-matrix $A$ and making its off-diagonals "less negative" and the diagonal "more positive" most likely won't change the "M-matricity" of the result. You might ask a new question on that if you like. $\endgroup$ Nov 9, 2015 at 16:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .