\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{???.??} %Здесь автор определяет УДК своей работы
\def\mscs{??X??} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\numberwithin{equation}{section}
%-------------------------------------------------
\theoremstyle{plain}
\newtheorem{theorem}{Теорема}
\newtheorem{lemma}{Лемма}%[section]
\newtheorem{propos}{Предложение}
\newtheorem{property}{Свойство}
\newtheorem{corollary}{Следствие}

%-------------------------------------------------
\theoremstyle{definition}
\newtheorem{definition}{Определение}
% \newtheorem{proof}{Доказательство}\def\theproof{}
\newtheorem{remark}{Замечание}
\newtheorem{primer}{Пример}
\newtheorem{notation}{Обозначение}
%-------------------------------------------------
\def\Re{\operatorname{Re}}
\def\Im{\operatorname{Im}}
\def\const{\mathrm{const}}
\def\RR{\mathbb R}
\def\CC{\mathbb C}
\def\NN{\mathbb N}
\def\RS{\mathfrak R}
\def\bz{\mathbf z}
\def\sH{\mathscr H}
\def\HH{\mathscr H}
\def\mro{\widehat\rho}
%-------------------------------
%\oddsidemargin=0pt

\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК    512.643 \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}%\hphantom{aaaaaaaaaaaaaaaaaaaaa\;}
     	 \hspace{\fill}{\rm\small MSC\ \ 15B48  \hspace{-4mm}}
  }%\vbox
}

\sloppy

\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc Цепные свойства полугрупп неотрицательных матриц]{\large Цепные свойства полугрупп неотрицательных матриц}
\author[Ю.А. Альпин, А.Э. Гутерман, Е.Р. Шафеев]{\bf \large \textsc{Ю.А. Альпин, А.Э. Гутерман, Е.Р. Шафеев}}
%\protect\orcidicon{тут видимо должно быть doi автора. в шаблоне как ниже}\\
%\author[А.Э. Гутерман]{\bf \large \textsc{А.Э. Гутерман}}
% \protect\orcidicon{0000-0001-8827-2630}\\ 
%\author[Е.Р. Шафеев]{{\bf \large \textsc{Е.Р. Шафеев}}%\protect\orcidicon{0000-0001-8827-2630}\\
%\textit{Представлено} \textsc{А.Э. Гутерманом}
%\textit{(заполняется редактором)}
%}%
\address[Ю.А. Альпин]{Yuri Abdullovich Alpin  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Gogol st. 9, ap. 1, 
\newline\hphantom{iii} 420015 Kazan, Russia
}%
\address[А.Э. Гутерман]{Alexander Emilevich Guterman  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Department of Mathematics, Bar-Ilan University, 
	\newline\hphantom{iii}  5290002 Ramat Gan, Israel
}%
\address[Е.Р. Шафеев]{Eugenii Rinatovich Shafeev   % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Department of Mathematics and Mechanics,  Moscow State University, 
	\newline\hphantom{iii} 119991 Moscow, Russia
}


\email{\textcolor{blue}{yurialpin016@gmail.com, alexander.guterman@biu.ac.il, shafeev.ev@yandex.ru}
}%

\thanks{\sc Alpin Yu.A., Guterman A.E., Shafeev E.R.,
Chainable sets of nonnegative matrices}
\thanks{\copyright \ 2023 }
%\thanks{\rm Работа поддержана РФФИ (грант 03-01-11111)}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:}  Теорема Протасова --- Войнова о комбинаторной структуре полугрупп неотрицательных матриц расширяет известный результат Фробениуса о канонической форме неприводимой неотрицательной матрицы.  Настоящая работа посвящена обобщению теоремы Протасова --- Войнова  на необязательно   неприводимые полугруппы матриц. Для этого на основе цепных свойства неотрицательных матриц введено расширение понятий индекса импримитивности и канонического разбиения.   
 
\medskip

 

The theorem by Protasov and Voinov on the combinatorial structure of semigroups of nonnegative matrices extends a   well-known result of Frobenius on the canonical form of an irreducible nonnegative matrix. We   generalize  the Protasov --- Voinov theorem to not necessarily irreducible semigroups of matrices. For this purpose, an extensions of the concepts of imprimitivity index and canonical partition are introduced which are based on the chain properties of non-negative matrices.
%A combinatorial extension of the concepts of imprimitivity index and canonical partition is proposed. A generalization of the Protasov--Voinov theorem to the class of semigroups of matrices without zero rows and columns is obtained.
\medskip

\noindent{\bf Keywords:} неотрицательные матрицы, цепные матрицы, цепной индекс 
\\
non-negative matrices, chainable matrices, chainable index 
\end{quote}

\bigskip

\section{Введение}	 
	
Согласно известной теореме Фробениуса любая неотрицательная неприводимая матрица  либо примитивна, либо
преобразованием перестановочного подобия приводится к так называемой форме Фробениуса  (см., например~\cite{Gant}).  

В работе \cite{PV}  Протасов и Войнов доказали обобщение теоремы Фробениуса на неприводимые полугруппы неотрицательных матриц. 
Для этого они  предложили полугрупповые аналоги определений неприводимой и примитивной матрицы 
и сформулировали важную теорему о строении неприводимых полугрупп неотрицательных матриц \cite[теорема~1]{PV}, см. также теорему~\ref{PV}  в разделе~6, которая %. Теорема Протасова --- Войнова  
описывает комбинаторную структуру неприводимой полугруппы неотрицательных матриц без нулевых строк и столбцов. Ключевым понятием теоремы является понятие индекса
импримитивности полугруппы. 
	
	Основным результатом данной работы является обобщение теоремы Протасова --- Войнова. Мы используем понятия потенциально цепной матрицы и индекса несолидарности, которые, соответственно, являются естественными расширениями понятий примитивной матрицы и индекса импримитивности и показываем, см. теорему \ref{tsep_pg1}, что любая полугруппа матриц без нулевых строк или столбцов, без дополнительного предположения о ее неприводимости, также обладает специальной комбинаторной структурой, зависящей от ее индекса несолидарности. %  Доказана следующая теорема:
	В теореме  \ref{Fr} доказано, что для неприводимой полугруппы разбиение на классы солидарности совпадает с разбиением на классы совместимости. Это показывает, 
	%Из теоремы \ref{Fr} следует, 
	что теорема \ref{tsep_pg1} является
	естественным обобщением теоремы Протасова--Войнова. Неформально говоря, она показывает, что удается спасти из  теоремы Протасова--Войнова, если отказаться от требования неприводимости, оставив лишь необременительное предположение об отсутствии нулевых строк или столбцов в матрицах. 
	
	Цепные матрицы были впервые рассмотрены в \cite{HM}, где изучалась их структура и алгебраические свойства. Позднее цепные и потенциально цепные матрицы, а также цепной ранг,  рассматривались в работах \cite{chain1} и~\cite{AGSh}.
	
	В параграфе 2 вводятся основные определения и формулируются базовые утверждения. В параграфе 3 формулируется   теорема об оценке цепного ранга произведения двух матриц и исследуется случай равенства в приведенном неравенстве.  Параграф 4 описывает в терминах цепного ранга 
	матрицы, действующие на классах солидарности как перестановки.
	В параграфе 5 для полугрупп матриц вводятся новые определения и доказывается основная теорема этой работы.  В шестом параграфе мы соотносим полученный результат с известными фактами о неприводимых матрицах и с теоремой Протасова --- Войнова.
	
  \section{ О цепном ранге}

Множество прямоугольных неотрицательных матриц без нулевых строк и столбцов обозначется символом $\mathbb{P}$, а  символом $\mathbb{P}_n$ ---  подмножество $\mathbb{P}$, состоящее из  матриц порядка $n$.  Пусть дана $(n\times m)$-матрица $A\in\mathbb{P}$.
Говорят, что $i$-ая и  $j$-ая строки $A$ \textit{пересекаются}, если они имеют положительные элементы в некотором общем столбце.
Обозначим множество индексов $\{1,2,\ldots,n\}$  через~$\textbf{n}$.

Со всякой  $n\times m$ матрицей $A\in\mathbb{P}$ связаны следующие  бинарные отношения на множестве $\textbf{n}$.    
\begin{definition}\label{sovm} 
Индексы  $i$ и  $j$  совместимы  матрицей $A$ ($A$-совместимы), если
$i$-ая и  $j$-ая строки $A$ пересекаются. \end{definition} 
\begin{definition}\label{solidar}
Индексы  $i$ и  $j$  солидарны  в матрице $A$ ($A$-солидарны), если существует такая последовательность индексов 
%\begin{equation}\label{w_hat}
$	i=i_1,i_2, \ldots,i_s=j,$
%\end{equation}
что строки с  номерами  $i_k, i_{k+1}$ совместимы  матрицей $A$ при $k=1,\ldots,{s-1}$. \end{definition} 

Отношение  $A$-солидарности индексов является, очевидно,  отношением эквивалентности на $\textbf{n}$. 

На языке матрицы $A$ определение \ref{solidar} означает следующее:
\begin{propos}\label{Asolidar} Индексы $i,j\in \textbf{n}$ солидарны в матрице $A$ тогда и только тогда, когда при некотором показателе $s$ справедливо неравенство:
$$(AA^T)^s_{ij}>0.$$
\end{propos}
\proof
	Индексы $i_1$ и $i_2$ совместимы   матрицей $A$ тогда и только тогда, когда $(AA^T)_{i_1 i_2} > 0$. В свою очередь, последовательность из определения \ref{solidar} существует тогда и только тогда, когда найдутся такие индексы $i_2,\ldots i_{s-1}$, что
	
	\begin{equation}
		(AA^T)_{i_1, i_2} (AA^T)_{i_2, i_3} \ldots (AA^T)_{i_{s-1}, i_s} > 0,\end{equation} 
	Существование такой последовательности индексов по определению матричного произведения эквивалентно условию $(AA^T)_{i_1, i_s}^s > 0$.
\endproof
\begin{definition}\label{d_tsep} Матрица $A\in\mathbb{P}$ размера $n\times m$ называется цепной, если любые индексы $i,j\in \textbf{n}$ солидарны в $A$, т.е. $(AA^T)^s_{ij}>0$ при некотором~$s$.\end{definition}
 \begin{definition}\label{tsep_r} 	Цепным рангом  $n\times m$ матрицы $A\in\mathbb{P}$ называется число классов $A$-солидарности и обозначается $\mathrm{crk}A$.\end{definition}

Из определения \ref{tsep_r} видно, что цепной ранг $n\times m$ матрицы $A\in\mathbb{P}$ лежит в следующих границах: $1\leq\mathrm{crk}A\leq n$. При этом $\mathrm{crk}(A)=1$
только если  $A$ --- цепная матрица (теорема 2.1 из \cite{chain1}). Максимальное значение $\mathrm{crk}A=n$ достигается, если в $A$ нет пересекающихся строк, последнее же имеет место в точности тогда, когда в каждом столбце $A$ есть ровно один положительный элемент.  В этом случае в $A$ всего $m$ положительных элементов. Обозначим через $r_i$ число положительных элементов $i$-й
строки. Ясно, что
$r_1+\cdots+r_n=m.$
Это равенство возможно лишь при $n\leq m$, а если $m=n$, то при
$r_1=\cdots=r_n=1.$ Сформулируем это полезное утверждение отдельно (другое его доказательство см. в \cite[лемма~3.7]{AGSh}):

\begin{propos}\label{vgr} Если $A\in\mathbb{P}_n$, то  $\mathrm{crk}A=n$  тогда и только тогда, когда матрица $A$ содержит ровно один положительный элемент в каждой строке и каждом столбце, т.е. является мономиальной матрицей.
\end{propos}

Согласно теореме 3.1 из \cite{chain1} цепной ранг произведения прямоугольных неотрицательных матриц  удовлетворяет неравенству
\begin{equation}\label{osn_crk}\mathrm{crk}(AB)\leq\min(\mathrm{crk}A,\mathrm{crk}B).\end{equation}
     	
 Напомним (см. напр. \cite{chain1}), что
со всякой неотрицательной $n\times m$ матрицей $A$ связан  \textit{ассоциированный} оператор ${A}$, отображающий множество~$2^\textbf{n}$ в множество~$2^\textbf{m}$ и определяемый формулой
\begin{equation}\label{n-m} \alpha\mapsto\alpha A=\{j|(A)_{ij}>0,i\in\alpha\}.\end{equation}
Как видно из \eqref{n-m}, множество $\alpha A$ состоит из номеров столбцов матрицы  $A$, имеющих положительные элементы в строках с номерами из  $\alpha$.

Для полноты определения будем считать, что $\varnothing A=\varnothing$.


\begin{lemma}\label{bijection} Оператор $A: 2^\textbf{n} \to 2^\textbf{m}$, ассоциированный с  $n\times m$  матрицей $A\in\mathbb{P}$, обладает следующими свойствами:

1) $\alpha\neq\varnothing \ \Rightarrow \alpha A\neq\varnothing$, т.е. непустые множества отображаются в непустые;

2) для любого $j\in\textbf{m}$ существует такое подмножество
$\alpha$, что  $j\in\alpha A$.
\end{lemma}
\proof Первое утверждение следует из того, что в матрице $A$ нет нулевых строк, а второе --- из отсутствия в $A$ нулевых столбцов.
\endproof
 
 Из определения отношения солидарности и леммы \ref{bijection}  вытекает следующее описание нецепной матрицы.

\begin{propos}\label{netsep} Пусть даны матрица $A\in\mathbb{P}$ и соответствующие ей классы солидарности $\alpha_1, \ldots, \alpha_r$ $(r\geq2)$. Тогда при  $s=1,\ldots,r$

1) на пересечении строк с номерами из множества $\alpha_s$ и столбцов с номерами из множества  $\alpha_sA$
стоит цепная подматрица, обозначим её $A^{ch}_s$.
 
2) в строках с номерами из $\alpha_s$ и столбцах с номерами из $\alpha_sA$ все элементы, не принадлежащие $A^{ch}_s$, равны нулю.
\end{propos}

\section{Равенство
$\mathrm{crk}(AB)=\mathrm{crk}(A) =\mathrm{crk}(B)$} 

\begin{lemma}\label{partitionLemma}	Пусть дана цепная матрица с $n$ строками. При любом разбиении множества 
$\mathbf{n} = \{1, \ldots , n\}$ для любого класса $\pi_1$
 разбиения найдётся такой класс  $\pi_2, \pi_1 \ne  \pi_2$,
 что некоторая строка с номером из  класса $\pi_1$
 пересекается с некоторой строкой с номером из  класса~$  \pi_2$.
\end{lemma}
\begin{proof} Предположим противное. Тогда существует такое
		 разбиение множества $\mathbf{n}$, что строки некоторого класса %, скажем, $\alpha$,  
не пересекаются со строками, не принадлежащими %$\alpha$.
этому классу. Ясно, что такая матрица не может быть цепной. 
		\end{proof}
	 \begin{theorem}\label{A=AB} Даны $n\times m$ матрица $A$ и $m\times p$ матрица $B$ из $\mathbb{P}$. Пусть цепной ранг матриц  $A,B$ одинаков и  равен $r\geq 2$. Дано разбиение множества $\textbf{n}$ на классы $A$-солидарности:
   \begin{equation}\label{rA=rAB1}\alpha=(\alpha_1, \ \alpha_2, \ \ldots, \ \alpha_r),\end{equation}
  а также  разбиение множества $\textbf{m}$ на классы $B$-солидарности:
\begin{equation}\label{rA=rAB2}\beta=(\beta_1, \ \beta_2, \ \ldots, \ \beta_r).\end{equation}

Равенство $\mathrm{crk}(AB)=r$
    имеет место тогда и только тогда, когда для каждого класса $\beta_j$ найдётся единственный класс $\alpha_i$, такой, что $\alpha_iA=\beta_j$,  или, другими словами, когда разбиение \eqref{rA=rAB2} совпадает с разбиением 
		\begin{equation}\label{rA=rAB3} \alpha_1A, \ \alpha_2A, \ \ldots, \ \alpha_rA. \end{equation}
		с точностью до порядка элементов.
   \end{theorem} 
    \proof  Без уменьшения общности можно считать, что матрица $A$ разбита на горизонтальные полосы в соответствии с классами \eqref{rA=rAB1}:
   \begin{equation}\label{gor}A=\begin{pmatrix}
  A_1\\
  A_2\\
  \vdots\\
  A_r\\
  \end{pmatrix}.\end{equation}
 Действительно, этого можно добиться,  умножив  $A$ слева на подходящую матрицу перестановки. Цепной ранг  $A$ при этом не меняется.  Согласно предложению \ref{netsep} матрица $A_s$ содержит цепную подматрицу $A^{ch}_s$, расположенную в столбцах с номерами из класса $\alpha_sA$, а все другие её элементы равны нулю.
  Множества
 \begin{equation}\label{beta1}\beta_1B, \ \beta_2B, \ \ldots, \ \beta_rB\end{equation} 
 определяют  разбиение  матрицы $B$ на вертикальные подматрицы. Матрица, составленная из столбцов с номерами из $\beta_tB$, обозначается через  $B_t$.
  Без уменьшения общности можно считать, что эти вертикальные подматрицы образуют сплошные полосы, расположенные в порядке \eqref{beta1}:
  \begin{equation}\label{vert}B=\begin{pmatrix}
B_1 | B_2 | \ \ldots \  |B_r\\
\end{pmatrix}.\end{equation}
  Такого вида  можно добиться,  умножив матрицу  $B$ справа на подходящую матрицу перестановки. Цепной ранг $B$ при этом не меняется. По предложению \ref{netsep} матрица $B_t$ содержит цепную подматрицу $B^{ch}_t$, расположенную в строках с номерами из класса $\beta_t$, а прочие её элементы равны нулю.
    
  Матрицы  $A$ и $B$ можно перемножить поблочно:
  \begin{equation}\label{AcdotB}AB=\begin{pmatrix}
   A_1\\
   A_2\\
   \vdots\\
  A_r\\
   \end{pmatrix}\begin{pmatrix}
   B_1 | B_2 | \ \ldots \  |B_r\\
   \end{pmatrix}=\begin{pmatrix}
  A_1B_1 &A_1B_2& \ldots &A_1B_r\\
  A_2B_1 & A_2B_2& \ldots &A_2B_r\\
  \cdot & \cdot& \cdot &\cdot\\
  A_rB_1 & A_rB_2& \ldots &A_rB_r\\
  \end{pmatrix}.\end{equation}
 
 Предположим, что условие теоремы выполнено, т.е. для всякого класса $\beta_t$ найдётся единственный класс
$\alpha_s$, такой, что $\alpha_sA=\beta_t$. Тогда
$$
A_sB_t=\left\{\begin{array}{l}A^{ch}_sB^{ch}_t,\text{\ если } \alpha_sA=\beta_t;\\\ 0 \ \text{ в противном случае.}\end{array}\right.
$$

Таким образом, матрица   \eqref{AcdotB} имеет блочно-мономиальный вид: в каждой блочной строке и каждом блочном столбце есть ровно один ненулевой, причём цепной, блок.   Цепной  ранг такой матрицы равен $r$.

\medskip

 Предположим, что условие теоремы не выполнено. 
 Это условие (относящееся к двум разбиениям одного конечного множества) можно пересказать такими словами: каждый класс $\beta_j$ содержится в одном из классов $\alpha_iA$. Невыполнение условия означает, что элементы  некоторого класса $\beta_k$
 из \eqref{rA=rAB2} распределены по некоторым классам разбиения \eqref{rA=rAB3}, обозначим их
$$\alpha_{j_1}A \ \ldots, \ \alpha_{j_h}A.$$
Это значит, что класс $\beta_k$ разбит на подклассы

 \begin{equation}\label{b_cap_a}\beta_k\cap(\alpha_{j_1}A), \ \ldots, \ \beta_k\cap(\alpha_{j_h}A).\end{equation}

Соответственно, матрица $B_k$ разбивается на горизонтальные подматрицы, отвечающие подклассам \eqref{b_cap_a}. То же происходит с цепной подматрицей $B^{ch}_k$ матрицы $B_k$, расположенной в  строках с номерами из $\beta_k$.  По лемме \ref{partitionLemma} для  подкласса  $\beta_k\cap\alpha_{j_1}A$ найдётся такой подкласс  $\beta_k\cap\alpha_{j_g}A$, что
некоторые строки с номерами из этих двух подклассов  пересекаются. Пусть  пересекаются строки с номерами $$u\in\beta_k\cap\alpha_{j_1}A,  \ v\in\beta_k\cap\alpha_{j_g}A.$$ Пусть также через $p\in\alpha_{j_1}$ и $q\in\alpha_{j_g}$ обозначены номера строк матрицы $A$, содержащих элементы $(A)_{pu}>0, (A)_{qv}>0$.
 
Умножая $p$-ю строку матрицы $A$ на матрицу $B$, получим $p$-ю строку матрицы $AB$. В эту строку в качестве слагаемого с положительным коэффициентом $(A)_{pu}$ входит $u$-я строка $B$. Соответственно, в $q$-ю строку матрицы $AB$
  в качестве слагаемого с положительным коэффициентом $(A)_{qv}$ входит $v$-я строка~$B$.
Следовательно $p$-я и $q$-я строки $AB$ пересекаются по тому же столбцу, по которому пересекаются $u$-я и $v$-я строки матрицы $B$.  В результате для матрицы $AB$  справедливо:
   
   а) индексы из $\alpha_{j_1}$   солидарны, поскольку они солидарны в $A$, по той же причине солидарны индексы из $\alpha_{j_g}$ (см. \cite[лемма 3.1]{chain1});
   
   б) строка  $p\in\alpha_{j_1}$ пересекается со строкой $q\in\alpha_{j_g}$.
   
   Из свойств а) и б) вытекает, что классы $\alpha_{j_1}$ и $\alpha_{j_g}$ входят в один класс $AB$-солидарности, следовательно, число классов $AB$-солидарности меньше числа классов $A$-солидарности, т.е. $\mathrm{crk}(AB)<\mathrm{crk}(A)$.
\endproof

\section{Равенство
$\mathrm{crk}(A^2)=\mathrm{crk}(A)$} 


\begin{definition}\label{kak_perest} Пусть дана матрица $A\in\mathbb{P}_n$. Дано также некоторое разбиение $\alpha_1, \ \alpha_2, \ \ldots, \ \alpha_r$
 множества $\textbf{n}$. Следуя  \cite{PV}, будем говорить, что   \textit{матрица $A$ действует на классах разбиения как перестановка}, если для каждого класса $\alpha_j$ найдётся единственный класс $\alpha_i$, такой, что $\alpha_iA=\alpha_j$. \end{definition}

		\begin{primer}
			Рассмотрим разбиение $\alpha_1 = \{1,2\}, \alpha_2 = \{3\}$ и матрицу $$M = \begin{pmatrix}
				0 & 0 & 1\\
				0 & 0 & 1\\
				1 & 1 & 0\\
			\end{pmatrix}.$$
			Как легко видеть, $\alpha_1 M = \alpha_2, \alpha_2 M = \alpha_1$. Это значит, что $M$ действует на классах данного разбиения как перестановка.
		\end{primer}
Индекс $j$ будем называть $A$-\textit{последователем} индекса $i$, если $(A)_{ij}>0$.
\begin{lemma}\label{kak_per} Матрица $A\in\mathbb{P}_n$ действует на классах  разбиения $\alpha_1, \alpha_2,  \ldots, \alpha_r $
 множества $\textbf{n}$ как перестановка, если для любых $i,j\in \textbf{n}$, лежащих в разных классах разбиения, их $A$-последователи тоже лежат
в разных классах  разбиения.
\end{lemma}
\proof Выберем в каждом классе разбиения по одному представителю:
$$i_1\in\alpha_1, \ldots, i_r\in\alpha_r.$$
Пусть $j_s$ --- $A$-последователь индекса $i_s$, $s=1,\ldots, r$.
Согласно условию леммы,  $A$-последователи  лежат в попарно различных классах разбиения. Это значит, что есть такая перестановка $\sigma$ на множестве $\{1,\ldots, r\}$, что
\begin{equation}\label{Aposl} j_1\in \alpha_{\sigma(1)}, \ldots, j_r\in \alpha_{\sigma(r)}.\end{equation}
 %Т.е. $$(A)_{i_1j_1}>0, \ldots, (A)_{i_rj_r}>0.$$
 Докажем, что если $j_s\in\alpha_{\sigma(s)}$, то \textit{все} $A$-последователи индекса $i_s$ лежат в $\alpha_{\sigma(s)}$, т.е.
$\alpha_sA\subseteq\alpha_{\sigma(s)}$. Предположим противное: некоторый $A$-последователь индекса $i_s$, например, индекс $k$, лежит в $\alpha_{\sigma(t)}, t\neq s$. Но имеем также $j_t\in \alpha_{\sigma(t)}$. Выходит, что $A$-последователи
индексов $i_s$ и $i_t$, принадлежащих  разным классам разбиения $\alpha$, лежат в одном классе $\alpha_{\sigma(t)}$. Это противоречит условию леммы. Итак, мы доказали, что
$\alpha_sA\subseteq\alpha_{\sigma(s)}$, $s=1,\ldots, r$. Из того, что $A$ --- матрица без нулевых столбцов, следует, что все вложения являются на самом деле равенствами:
$$\alpha_sA=\alpha_{\sigma(s)}, \ s=1,\ldots, r.$$
\endproof

\begin{lemma}\label{ik-jl} Пусть матрица $A\in\mathbb{P}_n$ действует на классах некоторого разбиения $ \ \alpha_1, \alpha_2,  \ldots,  \alpha_r \ $
 множества $\textbf{n}$ как перестановка.  Тогда
матрица $A$ перестановочно подобна блочно-мономиальной матрице блочного порядка $r$. %Заметим, что ненулевые блоки матрицы $PAP^T$ не имеют нулевых строк и столбцов.
\end{lemma}
\proof Пусть матрица $P$ переставляет строки $A$ так, чтобы первые позиции заняли строки с номерами из $\alpha_1$, затем следовали строки с номерами из $\alpha_2$ и т.д. Тогда $PAP^T$ --- блочно-мономиальная матрица блочного порядка~$r$. 
\endproof
 \begin{corollary}\label{A=AA} Для матрицы $A\in\mathbb{P}_n$
равенство 
\begin{equation}\label{A=2A} \mathrm{crk}A^2=\mathrm{crk}A\end{equation}
 имеет место тогда и только тогда, когда  выполнены следующие два условия:

1) матрица $A$ действует на классах солидарности как перестановка,

2) матрица $A$ перестановочно подобна блочно-мономиальной матрице блочного порядка $r=\mathrm{crk}A$,  в которой
все ненулевые блоки --- цепные матрицы.
\end{corollary}
\proof Пусть равенство \eqref{A=2A} выполнено, тогда 
свойство 1) доказывается применением теоремы \ref{A=AB} к случаю $A=B$.
Свойство  2) доказывается применением леммы \ref{ik-jl}, причём утверждение относительно ненулевых блоков вытекает из следующих соображений. Цепной ранг блочно-мономиальной матрицы равен, очевидно,  сумме цепных рангов ненулевых блоков. Так как число  ненулевых блоков равно $r=\mathrm{crk}A$, то цепные ранги всех ненулевых блоков равны единице, т.е. эти блоки --- цепные матрицы.

Пусть условия 1) и 2)  выполнены. Квадрат блочно-мономиальной матрицы с цепными блоками является
блочно-мономиальной матрицей, каждый ненулевой блок  которой равен произведению двух цепных блоков исходной матрицы в силу чего и сам является цепной матрицей. Очевидно, что $\mathrm{crk}A^2=\mathrm{crk}A$.
\endproof
 \section{Цепные свойства полугрупп}

 Вначале приведём  определения, которые обобщают на полугруппы определения \ref{sovm} и \ref{solidar}.
\begin{definition}\label{Psovm}(\cite{AA2014})
Индексы  $i,j\in \textbf{n}$  \textit{совместимы} полугруппой $\mathcal{P}\subseteq\mathbb{P}_n$, если они совместимы  некоторой матрицей $A\in\mathcal{P}$.
 \end{definition}
\begin{definition}\label{Psolidar}
Индексы  $i$ и  $j$  \textit{солидарны}  в полугруппе $\mathcal{P}\subseteq\mathbb{P}_n$, если существует последовательность индексов 
\begin{equation}\label{w_hat5}i=i_1,i_2, \ldots,i_s=j,\end{equation}
в которой соседние индексы $i_k, i_{k+1}$ совместимы полугруппой $\mathcal{P}$, т.е. совместимы некоторой матрицей  $A_k\in\mathcal{P}$ \ $(k=1,\ldots,s-1)$. 
\end{definition} 
Отношение солидарности индексов в $\mathcal{P}$ является, очевидно, отношением эквивалентности на $\textbf{n}$.

\begin{lemma}\label{A=B=AB=BA} Пусть для матриц $A,B\in\mathbb{P}_n$ \begin{equation}\label{cr_Ak1}\mathrm{crk}(A)=\mathrm{crk}(A^2)=\mathrm{crk}(B)=\mathrm{crk}(B^2)=\mathrm{crk}(AB)=r\geq2.\end{equation}
Тогда 

1) разбиение на классы солидарности для матриц $A$ и $B$ является одинаковым, причём на этих классах матрицы $A$ и $B$ действуют как перестановки;

2) матрицы $A$ и $B$ одним преобразованием перестановочного подобия приводятся к блочно-мономиальному виду блочного порядка $r$, причём все ненулевые блоки являются цепными матрицами.
\end{lemma} 
\proof Рассмотрим разбиения множества $\textbf{n}$ 
\begin{equation}\label{rA=rAB1bis}\alpha_1, \ \alpha_2, \ \ldots, \ \alpha_r\end{equation}
 \begin{equation}\label{rA=rAB3bis} \alpha_1A, \ \alpha_2A, \ \ldots, \ \alpha_r A, \end{equation}
\begin{equation}\label{rA=rAB2bis}\beta_1, \ \beta_2, \ \ldots, \ \beta_r,\end{equation}
\begin{equation}\label{rA=rAB4}\beta_1B, \ \beta_2B, \ \ldots, \ \beta_r B.\end{equation}
Здесь \eqref{rA=rAB1bis} и \eqref{rA=rAB2bis} --- классы солидарности для матриц $A$ и $B$. При условии \eqref{cr_Ak1}
указанные четыре разбиения
совпадают (т.е. отличаются лишь порядком перечисления членов).
Действительно, разбиения \eqref{rA=rAB1bis} и \eqref{rA=rAB3bis}, а также
\eqref{rA=rAB2bis} и \eqref{rA=rAB4}, совпадают по следствию \ref{A=AA} (с.\pageref{A=AA}); совпадение \eqref{rA=rAB3bis} и \eqref{rA=rAB2bis} вытекает из теоремы  \ref{A=AB} (с.\pageref{A=AB}).

Поскольку  матрицы $A$ и $B$ определяют  одно и то же разбиение множества $\textbf{n}$ на классы солидарности, то можно выбрать одно перестановочное подобие (способом, описанным в доказательстве леммы \ref{ik-jl}), приводящее эти матрицы к блочно-мономиальному виду. В этих матрицах, согласно лемме \ref{ik-jl}, ненулевые блоки являются цепными матрицами.
\endproof

 Пусть $I(\mathcal{P})$ --- множество матриц полугруппы $\mathcal{P}\subseteq\mathbb{P}_n$, имеющих минимальный цепной ранг:
\begin{equation}\label{min_crk}
I(\mathcal{P})=\{A\in \mathcal{P} \ | \ \mathrm{crk}(A)= \min\limits_{M\in\mathcal{P}}\mathrm{crk}(M)\}.\end{equation}

 Из \eqref{osn_crk} следует, что $I(\mathcal{P})$ --- (двусторонний) идеал в $\mathcal{P}$.

\begin{corollary}\label{I} Для  матриц идеала $I(\mathcal{P})$ классы солидарности одинаковы.
\end{corollary}
\proof Нетрудно видеть, что для любых $A,B\in I(\mathcal{P})$ выполняются условия леммы \ref{A=B=AB=BA}. Следовательно, если для какой-нибудь матрицы $A\in I(\mathcal{P})$ известны классы  солидарности, то они являются классами  солидарности для любой из
 матриц идеала $I(\mathcal{P})$.\endproof

  \begin{lemma}\label{A-AB} \cite[лемма 2]{AA2014} Пусть для матриц $A$, $B$ из $\mathbb{P}$ существует произведение $AB$.  Если индексы $i$ и $j$ совместимы матрицей $A$, то они совместимы и матрицей $AB$.
\end{lemma}
\proof  Пусть $(A)_{ik}>0,(A)_{jk}>0, (B)_{kl}>0$. Отсюда $$(AB)_{il}\geq (A)_{ik} (B)_{kl}>0, \ (AB)_{jl}\geq (A)_{jk} (B)_{kl}>0.$$
 \endproof
\begin{lemma}\label{I_razb} Индексы $i,j\in \textbf{n}$ совместимы полугруппой $\mathcal{P}$ тогда и только тогда, когда они совместимы  (любой) матрицей, принадлежащей идеалу $I(\mathcal{P})$.\end{lemma}
\proof  Согласно следствию \ref{I} достаточно доказать, что индексы $i,j$ совместимы какой-нибудь матрицей из $I(\mathcal{P})$. Пусть индексы $i,j\in \textbf{n}$ совместимы матрицей $B\in \mathcal{P}$. В силу леммы \ref{A-AB}  при $C\in I(\mathcal{P})$ они совместимы матрицей $BC\in I(\mathcal{P})$. 

Обратное утверждение очевидно.
\endproof

\begin{theorem}\label{podhod_0}   Индексы $i,j\in \textbf{n}$ солидарны в $\mathcal{P}$ тогда и только тогда, когда они солидарны в (любой) матрице, принадлежащей идеалу $I(\mathcal{P})$.  \end{theorem}
\proof  Пусть индексы $i,j$ солидарны в $\mathcal{P}$. Тогда в последовательности \eqref{w_hat5} соседние индексы совместимы полугруппой $\mathcal{P}$ и по лемме \ref{I_razb} они  $A$-солидарны при любой $A\in I(\mathcal{P})$. Поскольку солидарность индексов есть транзитивное отношение, то индексы $i,j$ тоже $A$-солидарны.

 Обратное утверждение очевидно.
\endproof


\begin{definition}\label{nesolA} Индексом несолидарности полугруппы $\mathcal{P}\subseteq\mathbb{P}_n$ называется максимальное число $r=r(\mathcal{P})$ индексов, любые два из которых несолидарны в  $\mathcal{P}$. Другими словами, индекс $r(\mathcal{P})$ равен числу классов $\mathcal{P}$-солидарности. 
\end{definition}

По теореме \ref{podhod_0} классы солидарности полугруппы $\mathcal{P}$ совпадают с классами солидарности любой из матриц идеала $I(\mathcal{P})$. Отсюда и из описания \eqref{min_crk} идеала $I(\mathcal{P})$ следует, что индекс несолидарности полугруппы $\mathcal{P}\subseteq\mathbb{P}_n$ равен наименьшему из цепных рангов матриц полугруппы: \begin{equation}\label{nesol=min}r(\mathcal{P})=\min\limits_{A\in\mathcal{P}}\mathrm{crk}(A).\end{equation}


 \begin{theorem}\label{tsep_pg1} Пусть дана  полугруппа  $\mathcal{P}$  матриц с индексом несолидарности, равным $r$, в множестве $n\times n$-матриц без нулевых строк или столбцов.
	
	1. Если $r=1$, то  полугруппа $\mathcal{P}$ цепная (т.е. содержит цепную матрицу).
	
	2. Если $r\geq2$, то все матрицы полугруппы $\mathcal{P}$ действуют на классах солидарности как перестановки.
	Все матрицы полугруппы $\mathcal{P}$  одним преобразованием перестановочного подобия приводятся к блочно-мономиальному виду блочного порядка $r$. Преобразованная полугруппа содержит матрицы, в которых все ненулевые блоки являются цепными матрицами.\end{theorem}

\proof%[Доказательство теоремы \ref{tsep_pg1}]
 1. Утверждение  немедленно следует из \eqref{nesol=min}.

2. По лемме \ref{A=B=AB=BA}  все матрицы идеала $I(\mathcal{P})$ действуют на классах солидарности как перестановки и одним преобразованием перестановочного подобия приводятся к блочно-мономиальному виду блочного порядка $r$ с цепными ненулевыми блоками. 

Теперь докажем, что не только матрицы из $I(\mathcal{P})$, но любая матрица  $A\in\mathcal{P}$ действует  на классах солидарности как перестановка. Согласно лемме \ref{kak_per} достаточно доказать, что $A$-последователи несолидарных индексов несолидарны. Предположим противное: для несолидарных индексов  $i$ и $j$ имеем $(A)_{ik}>0, (A)_{jl}>0$, но  индексы $k$ и $l$  солидарны. Тогда, если $B\in I(\mathcal{P})$ и $(B)_{ks}>0,(B)_{lt}>0$, то $s$ и $t$ солидарны. Для матрицы $AB\in I(\mathcal{P})$ и индексов $i$ и $j$ имеем:
$$(AB)_{is}\geq (A)_{ik}(B)_{ks}>0, (AB)_{jt}\geq (A)_{jl}(B)_{lt}>0,$$
следовательно, индексы $i$ и $j$, как имеющие солидарных последователей,   должны быть солидарными.
Пришли к противоречию. 
\endproof	


\section{Связь теоремы Протасова--Войнова и теоремы \ref{tsep_pg1}} 

Напомним, что по одному из эквивалентных определений неотрицательная  матрица $A$ порядка  $n$  называется неприводимой, если для любых индексов $i,j$ из
	множества $\textbf{n}=\{1,\ldots,n\}$ существует такой показатель $l$, что $(i,j)$-элемент матрицы $A^l$ положителен.
Из теории Перрона--Фробениуса неотрицательных матриц известно, что спектральный радиус $\rho(A)$  неприводимой матрицы $A$ является её простым собственным значением. Количество $r=r(A)$ собственных значений, равных $\rho(A)$ по модулю, называется индексом импримитивности неприводимой матрицы. При $r=1$  матрица является примитивной, а если $r>1$, то импримитивной. 
Комбинаторная (т. е. определяемая расположением положительных элементов) характеристика примитивной матрицы состоит в том, что некоторая её степень является положительной матрицей. По известной теореме Фробениуса неприводимая матрица либо примитивна, либо
преобразованием перестановочного подобия приводится к так называемой форме Фробениуса:
 \begin{equation}\label{Frob}A=\left(%
 \begin{array}{cccc}
 0 & A_{12} & \ldots & 0 \\
 \cdot & \cdot & \cdot & \cdot \\
 0 & 0 & \ldots &  A_{r-1,r}  \\
 A_{r1} & 0 & \ldots & 0 \\
 \end{array}%
 \right),\end{equation}
 причём в матрице  $A^r=\mathrm{diag}(A_{11}^{(r)},A_{22}^{(r)},\ldots, A_{rr}^{(r)})$
 диагональные блоки  примитивны (см., например~\cite[гл. 8, пар. 2]{Gant}).  

 В работе \cite{PV}  Протасов и Войнов доказали обобщение теоремы Фробениуса на полугруппы неотрицательных матриц. При этом использовались следующие полугрупповые аналоги определений неприводимой и примитивной матрицы.
 Полугруппа $\mathcal{P}$ неотрицательных матриц порядка  $n$  называется неприводимой,
 если для любых $i,j\in \textbf{n}$ в $\mathcal{P}$ найдётся матрица с
 положительным $(i,j)$-элементом. Легко видеть, что неприводимость неотрицательной матрицы $A$ эквивалентна неприводимости полугруппы $\langle A\rangle$.
Полугруппа называется примитивной, если она содержит хотя бы одну положительную матрицу. Неприводимые полугруппы, не являющиеся примитивными, называются импримитивными. 

Теорема Протасова--Войнова (\cite{PV}) описывает комбинаторную структуру неприводимой полугруппы неотрицательных матриц без нулевых строк и столбцов. Ключевым понятием теоремы является понятие индекса
импримитивности полугруппы. Мы приведём соответствующее определение и теорему в формулировке, несколько отличающейся от оригинальной, но более удобной в контексте данной работы.

\begin{definition}\label{Def1}
Индексом импримитивности полугруппы $\mathcal{P}\subseteq\mathbb{P}_n$ называется наибольшее число $r$, такое, что существуют  $r$ индексов, любые два из которых не совместимы полугруппой $\mathcal{P}$. 
\end{definition}
\begin{theorem}\label{PV} (\cite[теорема 1]{PV}) Пусть $\mathcal{P}\subseteq\mathbb{P}_n$
неприводимая полугруппа с индексом импримитивности $r$. Если $r=1$, то полугруппа  $\mathcal{P}$ содержит положительную матрицу.

Если  $r\geq 2$, то существует единственное разбиение множества $\textbf{n}$ на $r$ классов, на котором все матрицы полугруппы действуют как перестановки. Это разбиение называется \textit{каноническим}.

Все матрицы полугруппы $\mathcal{P}$  одним преобразованием перестановочного подобия приводятся к блочно-мономиальному виду блочного порядка $r$. Преобразованная полугруппа содержит матрицы, в которых все ненулевые блоки положительны.
\end{theorem}

Для дальнейшего существенно то, что каноническое разбиение допускает описание в терминах совместимости:
\begin{theorem}\label{th2}(\cite{AA2019})
Для  неприводимой полугруппы  $\mathcal{P}\subseteq\mathbb{P}_n$  разбиение множества  $\textbf{n}$
на классы совместимости является каноническим разбиением.
\end{theorem}
\begin{theorem}\label{poln} Разбиение множества $\textbf{n}$ на классы солидарности является подразбиением любого разбиения, 
на котором матрицы полугруппы $\mathcal{P}\subseteq\mathbb{P}_n$  действуют как перестановки.
 \end{theorem}
\proof
 Пусть на  разбиении  $\pi$    матрицы полугруппы $\mathcal{P}$  действуют как перестановки. Предположим, что
индексы  $i$ и  $j$  солидарны  в полугруппе $\mathcal{P}$. Тогда, согласно определению \ref{Psolidar},
 существует такая последовательность индексов 
\begin{equation}\label{w_hat_2}i=i_1,i_2, \ldots,i_s=j,\end{equation}
что индексы $i_k, i_{k+1}$ совместимы некоторой матрицей $A_k\in\mathcal{P}, \  k=1,\ldots,s-1$. 
Индексы, лежащие  в разных $\pi$-классах, не
совместимы, очевидно, никакой матрицей из  $\mathcal{P}$. Другими словами, индексы, совместимые  матрицей из $\mathcal{P}$, необходимо лежат в одном $\pi$-классе. Отсюда следует, что любые два соседних индекса в последовательности \eqref{w_hat_2}  лежат в одном $\pi$-классе, а потому солидарные индексы $i$ и  $j$ лежат в том же $\pi$-классе. Это значит, что разбиение на классы солидарности является подразбиением разбиения $\pi$.
\endproof
\begin{theorem}\label{Fr} Для неприводимой полугруппы   $\mathcal{P}\subseteq\mathbb{P}_n$  разбиение на классы солидарности совпадает с разбиением на классы совместимости. 
\end{theorem}
\proof
 1) По теореме \ref{poln} разбиение на классы $\mathcal{P}$-солидарности является подразбиением разбиения на классы $\mathcal{P}$-совместимости, т.е.  $\mathcal{P}$-солидарные индексы $\mathcal{P}$-совместимы. 
2) Из определения \ref{Psolidar} видно, что  $\mathcal{P}$-совместимые индексы $\mathcal{P}$-солидарны.
Из 1) и 2) следует утверждение теоремы.
\endproof
В силу теоремы \ref{Fr} индекс несолидарности неприводимой полугруппы   $\mathcal{P}\subseteq\mathbb{P}_n$ совпадает с её индексом импримитивности. В частности,
индекс несолидарности неприводимой матрицы $A\in\mathbb{P}_n$ равен её индексу импримитивности.

Применим полученные результаты к полугруппе $\langle A\rangle$, порождённой единственной матрицей $A\in\mathbb{P}_n$. Из неравенства \eqref{osn_crk} следует цепочка неравенств
\begin{equation}\label{menee} \mathrm{crk} A\geq \mathrm{crk} A^2\geq \cdots \geq\mathrm{crk} A^k\geq\mathrm{crk} A^{k+1}\geq\cdots 
\end{equation}
причём имеет место теорема
\begin{theorem}\label{Ak+1=Ak} (\cite{AGSh}, теор. 3.5)
Если
$\mathrm{crk}A^{k+1}=\mathrm{crk}A^k$, то $\mathrm{crk}A^{k+t}=\mathrm{crk}A^k$ для всех $t\in \mathbb{N}$.
 \end{theorem}
Обозначим через $\varkappa$ минимальный показатель, при котором  в цепочке неравенств  \eqref{menee} имеет место равенство $\mathrm{crk}A^{\varkappa+1}=\mathrm{crk}A^\varkappa$.
\begin{propos}\label{<n}  $\varkappa\leq n-1$. 
\end{propos}
\proof Вначале отметим очевидное: $\varkappa\leq n$. Допустим, что $\varkappa=n$. Это равенство возможно только если $\mathrm{crk}A=n$, следовательно, по предложению \ref{vgr},  $A$ --- мономиальная матрица. Множество мономиальных матриц замкнуто относительно умножения, поэтому $\mathrm{crk}A^k=n$ при $k=1,2,\ldots$ Но в этом случае $\varkappa=1$. Ввиду полученного противоречия получаем $\varkappa\leq n-1$.
\endproof
Из предложения \ref{<n} следует, что матрица $A^{n-1}$ принадлежит
идеалу $I(\langle A\rangle)$. Учитывая это, из теоремы \ref{podhod_0} выводим:
\begin{corollary}\label{podhod_00} Пусть $A\in\mathbb{P}_n$. Индексы $i,j\in \textbf{n}$ солидарны в полугруппе $\langle A\rangle$ тогда и только тогда, когда они солидарны в матрице $A^{n-1}$.
  \end{corollary}
 Индекс несолидарности  полугруппы $\langle A\rangle$ обозначим символом $r(A)$.
Тогда утверждение следствия \ref{podhod_00} можно записать в виде равенства 
\begin{equation}\label{r=crk} r(A)=\mathrm{crk}A^{n-1}.
\end{equation}
 
\begin{theorem}\label{1matrix} Пусть $A\in\mathbb{P}_n$.

1. Если $r(A)=1$, то $A$ --- потенциально цепная матрица, а именно, матрицы $A^k$, $k\geq n-1$, являются цепными матрицами.

2. Если $r=r(A)\geq2$, то матрица $A$  преобразованием перестановочного подобия приводится к блочно-мономиальному виду блочного порядка $r$. В матрицах $A^k$, $k\geq n-1$, ненулевые блоки являются цепными матрицами.
\end{theorem}

 Предположим, что  матрица $A$ неприводима. По теореме \ref{Fr} классы солидарности полугруппы $\langle A\rangle$ совпадают с классами совместимости. Если $r(A)=1$, т.е. любые два индекса совместимы, то $A$ --- примитивная матрица, см. \cite[предложение 6.1]{chain1}. Теперь пусть $r=r(A)\geq2$. Тогда классы
 совместимости образуют так называемое циклическое разбиение множества $n$. Это значит, что существует нумерация классов  совместимости:
 $ \ \alpha_1, \alpha_2, \ldots, \alpha_r, \ $
при которой $\alpha_1A=\alpha_2, \alpha_2A=\alpha_3, \ldots, \alpha_rA=\alpha_1$. Этой нумерации соответствует форма \eqref{Frob}. Таким образом, в  неприводимом случае блочно-мономиальная форма из теоремы \ref{1matrix} превращается в форму Фробениуса.
Подробный вывод формы Фробениуса с помощью отношения совместимости см. в \cite{A2015}.


\section*{Благодарности}

Авторы благодарны Владимиру Протасову за интересные обсуждения.

\bigskip
\begin{thebibliography}{9}

     \bibitem{A2015}Yu.A. Alpin, \textit{Nonnegative matrices} ---  Kazan. Fed. University, 2015.
     \bibitem{AA2019}  Al'pin Yu. A., Al'pina V.S. \href{https://doi.org/10.1134/S0001434619050183}{\it A New Proof of the Protasov-Voynov Theorem on Semigroups of Nonnegative Matrices} ---  Math Notes \textbf{105}, 805–811 (2019).
     \bibitem{AA2014} Yu.A. Alpin,  V.S. Alpina,
     \href{https://doi.org/10.1007/s10958-015-2390-9}{Combinatorial Properties of Entire Semigroups of Nonnegative Matrices}  J Math Sci \textbf{207}, 674–685 (2015).
     \bibitem{chain1} Yu.A. Alpin,  I.V. Bashkin, \textit{Nonnegative chainable matrices} --- Computational methods and algorithms. Part XXXIII, Zap. Nauchn. Sem. POMI, \textbf{496}, POMI, St. Petersburg, 5–25, (2020). Translation in J. Math. Sci.
     (N.Y.) \textbf{255}, no. 3, 217–230 (2021).  
     \bibitem{AGSh} Yu.A. Alpin, A.E. Guterman, E.R. Shafeev \href{https://doi.org/10.1007/s10958-023-06443-9}{\it An upper bound for the chainable index} --- J Math Sci \textbf{272}, 487–495, (2023).
     \bibitem{Gant} F.R. Gantmacher, \textit{The theory of matrices} --- Nauka, 1967.
      \bibitem{HM} J. Hartfiel, J. Maxson,  \href{https://doi.org/10.1016/0012-365X(75)90049-7}{The chainable matrix, a special combinatorial matrix.} --- Discrete Math., \textbf{12} (1975), 245-256.
     \bibitem{PV} V.Yu. Protasov, A.S. Voynov, \href{https://doi.org/10.1016/j.laa.2012.02.029}{Sets of nonnegative matrices
          without positive products.} --- Linear Algebra Appl., \textbf{437}, 749-765 (2012).
     
     \end{thebibliography}
% \begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).


% \bibitem{1} D.G. Northcott,
% \href{https://doi.org/10.1017/CBO9780511565908}{\it Ideal Theory}, Cambridge University Press, Cambridge, 1953.

% \bibitem{2} I.I. Ivanov,
% \href{https://doi.org/10.1002/cpa.20282}{\it Some properties of commutative algebras}, Siberian Electronic
% Mathematical Reports, {\bf 1} (2004), 142--143.

% \bibitem{3} A.V. Tetenov, M. Samuel, D.A. Vauilin,
% \href{https://doi.org/10.21538/0134-4889-2017-23-4-281-291}{\it On dendrites generated by polyhedral systems and their ramification points}, Trudy Inst. Mat. Mekh. UrO RAN, \textbf{23}:4 (2017), 281--291.

% \end{thebibliography}
\end{document}
