1
$\begingroup$

Let $A\in\mathbb{R}^{n\times n}$ be a non-negative and irreducible matrix. Consider $B:=AA^\top$. It can be proved (I can post a proof if needed) that the following condition is necessary and sufficient to have $B$ primitive:

C. There exists no way to rename the states in such a way that there exist $0\leq p < q < r \leq n$ such that $V$ can be split in $V_1=\{1,\dots,p\}$ (if $p>0$ and $V_1=\emptyset$ otherwise), $V_2=\left\{p+1,\dots,q\right\}, V_3=\left\{q+1,\dots,r\right\}$ and $V_4=\left\{r+1,\dots,n\right\}$ (if $r<n$ and $V_4=\emptyset$ otherwise), and such that according to this partition matrix $A$ (relative to the new relabelling) has the following sparsity pattern ($\star$ denotes an entry that can take a nonzero value): \begin{equation*} A = \begin{array}{c@{\!\!\!}} \left[ \begin{array}[c]{ccc|ccc|ccc|ccc} \star & \cdots & \star & 0 & \cdots & 0 &\star& \cdots & \star & 0& \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ \star & \cdots & \star & 0 & \cdots & 0 &\star& \cdots & \star & 0& \cdots & 0 \\ \hline \star & \cdots & \star & 0 & \cdots & 0 &\star& \cdots & \star & 0& \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ \star & \cdots & \star & 0 & \cdots & 0 &\star& \cdots & \star & 0& \cdots & 0 \\ \hline 0 & \cdots & 0 & \star & \cdots & \star & 0& \cdots & 0 & \star& \cdots & \star \\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 0 & \cdots & 0 & \star & \cdots & \star & 0& \cdots & 0 & \star& \cdots & \star \\ \hline 0 & \cdots & 0 & \star & \cdots & \star & 0& \cdots & 0 & \star& \cdots & \star \\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ 0 & \cdots & 0 & \star & \cdots & \star & 0& \cdots & 0 & \star& \cdots & \star \\ \end{array} \right] & \begin{array}[c]{@{}l@{\,}l} \left. \begin{array}{c} \vphantom{0} \\ \vphantom{\vdots} \\ \vphantom{0} \end{array} \right\} & \text{$V_1$} \\ \left. \begin{array}{c} \vphantom{0} \\ \vphantom{\vdots} \\ \vphantom{0} \end{array} \right\} & \text{$V_2$} \\ \left. \begin{array}{c} \vphantom{0} \\ \vphantom{\vdots} \\ \vphantom{0} \end{array} \right\} & \text{$V_3$} \\ \left. \begin{array}{c} \vphantom{0} \\ \vphantom{\vdots} \\ \vphantom{0} \end{array} \right\} & \text{$V_4$} \end{array} \end{array} \end{equation*}

Looking at $A$ as an adjacency matrix of a graph, we have that if there exists a partition of $V$ such that the nodes of $V_1$ communicate only with those of $V_1$ and $V_2$, those of $V_2$ only communicate with those of $V_3$ and $V_4$, those of $V_3$ communicate only with those of $V_1$ and $V_2$ and those of $V_4$ communicate only with those of $V_3$ and $V_4$, condition C is not met (note that $V_1$ and $V_4 $ are not necessarily present, while $V_2$ and $V_3$ are always present since $A$ is irreducible).

Here is my question: Have graphs whose adjacency matrices satisfy condition C been studied in the literature? If so, do such graphs have a name? Any answer/comment would be highly appreciated. Thank you.

$\endgroup$
  • $\begingroup$ When you speak of "graphs", do you consider directed or undirected ones? I guess directed? $\endgroup$ – M.U. Jan 14 '16 at 17:51
  • $\begingroup$ Yes, I mean directed graphs. $\endgroup$ – Ludwig Jan 14 '16 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.