Reducible Matrix

\( \renewcommand{\vec}[1]{\boldsymbol{#1}} \DeclareMathOperator*{\E}{\mathbb{E}} \DeclareMathOperator*{\Var}{\mathrm{Var}} \DeclareMathOperator*{\Cov}{\mathrm{Cov}} \DeclareMathOperator*{\argmin}{\mathrm{arg\,min\;}} \DeclareMathOperator*{\argmax}{\mathrm{arg\,max\;}} \def\ZZ{{\mathbb Z}} \def\NN{{\mathbb N}} \def\RR{{\mathbb R}} \def\CC{{\mathbb C}} \def\QQ{{\mathbb Q}} \def\FF{{\mathbb FF}} \def\EE{{\mathbb E}} \newcommand{\tr}{{\rm tr}} \newcommand{\sign}{{\rm sign}} \newcommand{\1}{𝟙} \newcommand{\inprod}[2]{\left\langle #1, #2 \right\rangle} \newcommand{\set}[1]{\left\{#1\right\}} \require{physics} \)

1 Definition #

A square \(n \times n\) matrix \(A\) is called reducible if the indices \(1,2, \dots ,n\) can be divided into two disjoint nonempty sets \(i_1, i_2, \dots , i_{\mu}\) and \(j_1, j_2, \dots , j_{\nu}\) (with \(\mu+\nu=n\) such that:

\[A_{i_{\alpha}, j_{\beta}}=0\]

for \(\alpha=1,2, \dots ,\mu\) and \(\beta = 1,2, \dots , \nu\).

A matrix is reducible if and only if it can be placed into block upper-triangular form by simultaneous row/column permutations. In addition, a matrix is reducible if and only if its associated digraph is not strongly connected.

A square matrix that is not reducible is said to be irreducible.

2 Reference #

Links to this note