Нерозкладна матриця

Нерозкладна матриця — невід'ємна матриця яку перестановкою рядків і стовпців не можна привести до блочного трикутного вигляду. Нерозкладні матриці є деяким узагальненням додатних матриць, для яких зберігаються властивості теореми Перрона — Фробеніуса.

Означення

Квадратна матриця A розмірності n з невід'ємними елементами називається розкладною якщо вона задовольняє такі еквівалентні умови:

Існує така підмножина $S\subset \{1,2,\ldots ,n\},$ що виконуються рівності: $a_{ij}=0\quad \forall i\in S,j\notin S$
Деякою перестановкою рядків і стовпців матрицю можна привести до вигляду:

PAP^{-1}={\begin{bmatrix}B&0\\C&D\end{bmatrix}}

де B і D — деякі квадратні матриці, 0 — нуль-матриця, P — матриця перестановки.

Якщо такої множини індексів S не існує (і матрицю не можна привести до вказаного виду), то матриця називається нерозкладною.

Іншими еквівалентними означеннями нерозкладних матриць є:

Для будь-яких цілих чисел (i, j) таких що $1\leqslant i,j\leqslant n$ існує число $1\leqslant k\leqslant n,$ що виконується: $(A^{k})_{ij}>0$
Нехай введено орієнтований граф вершини якого відповідають рядкам і стовпцям матриці і від вершини i до вершини j дуга йде тоді і тільки тоді, коли $a_{ij}>0.$ Тоді матриця A є нерозкладною тоді і тільки тоді, коли відповідний граф є сильно зв'язаним.