If a matrix is irreducible, based on the following definition

A matrix is reducible if there are two disjoint sets of indexes $I,J$ with $|I|=\mu$, $|J|=\nu$, $\mu+\nu=n$ such that for every $(i,j)\in I\times J$ we have $a_{ij}=0$

then is this equivalent to saying that the matrix graph is connected?

I found this result but it seems it is only one direction.

  • 3
    $\begingroup$ ...that the graph is strongly connected (since we talk about directed graphs). $\endgroup$ – Artem Jul 11 '14 at 23:05
  • $\begingroup$ @Artem Thank you. If the matrix is symmetric does this simplify things? Does symmetry cause this to reduce to connectivity? $\endgroup$ – jonem Jul 11 '14 at 23:08
  • 2
    $\begingroup$ Yes, if the matrix is symmetric we can talk about simply about connectivity. $\endgroup$ – Artem Jul 11 '14 at 23:16

For an undirected graph $G$: for each partition $\{I,J\}$ of the vertices of $G$ we check if there are no edges between vertices in $I$ and vertices in $J$.

If $G$ is disconnected, then $\{I,J\}$ can be found (choose $I$ as the vertices in one connected component). Conversely, if $\{I,J\}$ can be found, then there are no edges between $I$ and $J$ and $G$ is disconnected.

For the adjacency matrix $A=(a_{ij})$, if $\{I,J\}$ can be found then subgraph formed by the rows indexed by $I$ and the columns indexed by $J$ form an all-$0$ submatrix.

This means that, $A$ has the block structure $$\begin{array}{|c|c|} \hline A_I & 0 \\ \hline 0 & A_J \\ \hline \end{array}$$ where the rows and columns are indexed by the indices in $I$ then $J$.

In the directed case, we instead have no edges directed from a vertex in $I$ to a vertex in $J$. So we can find $\{I,J\}$ if $G$ is not strongly connected (take $I$ to be the vertices in one strongly connected component).


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.