2
$\begingroup$

The incidence matrix below is primitive (the graph is strongly connected) thus it is irreducible. However, this matrix looks reducible (using $P = I_n$) ?! What am I missing?

[A is called reducible if, subject to some permutation of the rows and the same permutation of the columns, A can be written in upper triangular block form, i.e. $$PAP^{-1} =\begin{bmatrix} B &C \\0 &D\end{bmatrix}$$]

enter image description here

$\endgroup$
1
$\begingroup$

Indeed, the given matrix is irreducible. Your claim is correct that if a matrix is reducible, then it can be written in the form (after some reordering of the states): $$A' = \begin{pmatrix} B & C\\ \color{blue}{\mathbf{0}} & D \end{pmatrix}.$$

But notice that $B$ and $D$ must be square blocks! Apparently, you think that the blue block represents the zero block above: $$\begin{pmatrix} 0 & 1 & * & * & * \\ 0 & 0 & * & * & *\\ 1 & 0 & * & * & *\\ \color{blue} 0 & \color{blue} 0 & * & * & *\\ \color{blue} 0 & \color{blue} 0 & * & * & * \end{pmatrix} $$ But the block above the blue block is not square!

$\endgroup$

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.