Index of imprimitivity = Period of a matrix?

Question

I am learning about the theory of non-negative matrices and trying to connect and reconcile various definitions I came across.

The index of imprimitivity of an irreducible non-negative matrix $\boldsymbol{A}\geq0$ is denoted as $h_{\boldsymbol{A}}$ and defined as the number of its eigenvalues on the spectral circle.

The period of index $i$ of a non-negative $\boldsymbol{A}\geq0$ is defined as $\varpi_{\boldsymbol{A}}(i):=\gcd\{m:\left[\boldsymbol{A}^{m}\right]_{ii}>0,m\in\mathbb{N}\}$. One can show that for an irreducible $\boldsymbol{A}\geq0$ we have $\varpi_{\boldsymbol{A}}(i)=\varpi_{\boldsymbol{A}}(j), \forall i,j$. Therefore, this common value is simply called the period of an irreducible matrix, $\varpi_{\boldsymbol{A}}$.

Question. Is it true that for any irreducible non-negative matrix $\boldsymbol{A}\geq0$ we have $\varpi_{\boldsymbol{A}}=h_{\boldsymbol{A}}$, that is, the period matches the number of dominant eigenvalues? How does one prove that?

I only know that for an irreducible $\boldsymbol{A}\geq0$, we have $\varpi_{\boldsymbol{A}}=1$ ($\boldsymbol{A}$ is aperiodic) iff $h_{\boldsymbol{A}}=1$ ($\boldsymbol{A}$ is primitive) iff $\exists m:\boldsymbol{A}^m>0$ ($\boldsymbol{A}$ is eventually positive). This special case is easier to establish, and my question is about imprimitive non-negative irreducible matrices.

P.S. It looks like the question Period of an irreducible Markov Chain is given by the number of eigenvalues with unit modulus is equivalent to mine, provided one shows that an irreducible non-negative matrix is (diagonally) similar to a Markov matrix. As neither of the questions has been answered, and since my phrasing is slightly more general, I propose not to flag duplicates, at least for now.

Answer 1

The answer to your questions is: Yes

A little bit of background, mainly based on [1, Chapter 3]. Irreducible, nonnegative matrices $A \in \mathbb{R}^{n\times n}$ are often associated with a graph $G(A)$ that has $n$ vertices and two vertices $i$ and $j$ are connected precisely if $[A]_{ij} > 0$. Then, the period of an irreducible matrix (as you define it) is precisely the gcd of the length of all cycles in $G(A)$. A theorem that directly states the connection that you are interested in, is [1, Theorem 3.18]

Theorem 3.18 Let $A$ be a nontrivial irreducible matrix with period $p$ and let $\lambda=\lambda(A)$. Then, there are exacty $p$ Eigenvalues $\mu$ of $A$ for which $|\mu|=\lambda$: those Eigenalues have the form $\lambda \omega^i$, where $\omega$ is a root of order $p$ of unity, and each of those Eigenvalues has algebraic multiplicity $1$.

The authors denote by $\lambda(A)$ the spectral radius of $A$. You might also be interested in [2, Corollary 8.4.7], which proves the statement in one direction.

[1] Marcus, Roth, Siegel - "Introduction to Coding for Constrained Systems", https://personal.math.ubc.ca/~marcus/Handbook/
[2] Horn, Johnson - "Matrix Analysis"

Answer 2

It suffices to prove this when the $A$ is mapped to a stochastic matrix, i.e. divide out the Perron root, and do the diagonal similarity transform here $\rho(B) \leq \rho(|B|)$, where $\rho$ is the spectral radius

The result is a matrix associated with an irreducible Markov chain. Call this stochastic matrix $P$.

Note: when I say a Markov matrix can be written as a direct sum, technically what is meant is that up to graph isomorphism (i.e. permutation similarity) it is direct sum a / direct product / block diagonal. $P^k$ being reducible for some $k$ alway implies block diagonal (as opposed to mere block triangular) since $P^k$ cannot have transient states since $P$ is irreducible (check e.g. $\pi P = \pi=\pi P^k$ and $\pi$ is a positive vector)

---

OP has already stated that the aperiodic case is understood--so that is taken for granted. Note: aperiodicity is necessarily equivalent to there being only one eigenvalue on the unit circle. Thus this proof starts only with the coarse association that $\geq 2$ eigenvalues on the unit circle for irreducible $P$ is equivalent to $P$ having some period $\geq 2$.

Let $P$ a stochastic matrix with index of imprimitivity $=r\geq 2$. This means there are $r$ eigenvalues on the unit circle, only one of which $=1$ since $A$ is irreducible. The boundedness of $P$ (using e.g. Frobenius norm or operator 2 norm) implies these eigenvalues are all necessarily semi-simple (why?) and we'll prove they are in fact simple, forming a complete set of $r$th roots of unity. For expediency, we write out the Jordan Form

$P = S\pmatrix{D_r & \mathbf 0\\\mathbf 0&J}S^{-1}$ where $D_r$ is a $r\times r$ diagonal matrix containing the eigenvalues on the unit circle and $J$ contains Jordan blocks associated with eigenvalues strictly inside the unit circle. We now put this aside for a bit and prove some lemmas.

Lemma 1:
Let $P$ be an irreducible $n\times n$ stochastic matrix with period $\geq 2$. Then $\text{trace}\big(P\big)=0$.

(The $n=1$ case trivially has trace one and is trivially aperiodic hence excluded). For $n\geq 2$, by stochasticity we know $\text{trace}\big(P\big)\geq 0$, so suppose for contradiction that $\text{trace}\big(P\big)\gt 0$. Then $P$ has exactly one $\lambda = 1$ (Perron root) and at least one other eigenvalue $\omega\neq 1$ which is on the unit circle (if no $\omega$ exists, then $\lim_{k\to\infty}P^k$ exists and $P$ is aperiodic). Further $\text{trace}\big(P\big)\gt 0\implies$ at least one diagonal of $P$ that is positive, i.e. some $p_{j,j}\gt 0$. Then by applying (reverse) triangle inequality to row $j$ we see $\big(\omega I - P\big)$ is weakly diagonally dominant and irreducible, hence by Taussky's refinement of Gerschgorin Discs $\det\big(\omega I - P\big)\neq 0$ and $\omega$ is not an eigenvalue, a contradiction. This proves the lemma.

(I gave a proof of Taussky's refinement under "optional second", here: Prove that this block matrix is positive definite .)

Lemma 2:
all eigenvalues on the unit circle for irreducible $P$ are roots of unity (i.e. each satisfies $\lambda^k=1$ for some positive integer $k$).

If $P$ is aperiodic then the result is immediate. Suppose $P$ is periodic. We do this via strong induction on $n$. The (Base) $2\times 2$ case: $P$ is stochastic and trace zero hence $P= \pmatrix{0 & 1\\1&0}$

Inductive case:
We know $\text{trace}\big(P\big) =0$ but $\text{trace}\big(P^k\big) \gt 0$ for some minimal $k\in \big\{2,3,...,n\big\}$. Note: $\text{trace}\big(P^k\big) \lt 0$ is impossible, and $\text{trace}\big(P^k\big) = 0$ for all $1\leq k \leq n$ powers implies $P$ is nilpotent which contradicts irreducibility. Thus using the above minimal $k$, via Lemma 1 we know $P^k$ is reducible and/or aperiodic. The former case explicitly says $P^k$ is reducible and we show it must be in the latter case as well. If $P^k$ is aperiodic, all eigenvalues on the unit circle $=1$ which implies $\omega^k=1$ for some $\omega \neq 1$, and by Perron-Frobenius Theory $P^k$ is thus reducible into a collection of irreducible stochastic matrices, each of which has a single eigenvalue on the unit circle if aperiodic, and for period $\geq 2$ we may apply our induction hypothesis. Thus each eigenvalue on the unit circle is a $k_i$th root of unity so $k':=k_1\cdot k_2\cdot ... \cdot k_r$ and they all satisfy $x^{k'}-1=0$.

Lemma 3:
Now consider the projection: $T = S\pmatrix{I_r & \mathbf 0\\\mathbf 0&\mathbf 0}S^{-1}$. Then
$M:=TP=PT= S\pmatrix{D_r & \mathbf 0\\ \mathbf 0&\mathbf 0}S^{-1}$
is a stochastic matrix.

Note that $T= \lim_{s\to \infty} \big(P^{k'}\big)^s$
which is a stochastic matrix and the product of two stochastic matrices is a stochastic matrix

Lemma 4:
$0 \leq \text{trace}\big(M^k\big) = \text{trace}\big(D_r^k\big)\leq r$

$M$ is a stochastic matrix hence $0\leq \text{trace}\big(M^k\big)$ and $\text{trace}\big(M^k\big) = \text{trace}\big(D_r^k\big)$ since $M$ and $D_r$ have the same non-zero eigenvalues.

By triangle inequality
$\text{trace}\big(M^k\big) =\text{trace}\big(D_r^k\big) = \big \vert \text{trace}\big(D_r^k\big) \big \vert \leq \sum_{k=1}^r \vert d_{i,i}\vert^k = r$ with equality iff $D_r^k = I$.

Lemma 5 (using character theory):
(i) $\text{trace}\big(M^k\big) \in \big\{0,r\big\}$ for all $k$ and (ii) all non-zero eigenvalues of $M$ are distinct.

Let $G$ be the cyclic group generated by $D_r$. Since this is already a matrix group then we may call $G'$ a representation of $G$ via what amounts to the identity homomorphism. I.e. $G'$ is a (faithful) $r$-dimensional representation of a finite abelian matrix group, $G$. Being abelian all irreducible representations are $1$-dimensional and the number of irreducible representations $=\vert G \vert$. The character associated with $G'$, $\chi$, may be written as
$\chi = \eta_1 \cdot\chi_1+\eta_2\cdot \chi_2 + ... + \eta_{\vert G \vert}\cdot \chi_{\vert G \vert}= 1\cdot \chi_1+\eta_2 \cdot\chi_2 + ... + \eta_{\vert G \vert} \cdot\chi_{\vert G \vert}$
where $\eta_j \in \mathbb N$ (inclusive of zero). (In terms of notation, page 319 of Artin's Algebra 1st edition could be useful here.)

We know the multiplicity of eigenvalue 1 for $G'$ (the trivial representation) is $1$. Using the standard inner product for characters we have
$1=\langle \chi_1, \chi \rangle= \frac{1}{\vert G \vert}\sum_{k=1}^{\vert G\vert}1 \cdot \text{trace}\big(D_r^k\big)$

re-scaling by $r$ we have
$r= \frac{1}{\vert G \vert}\sum_{k=1}^{\vert G\vert}r \cdot \text{trace}\big(D_r^k\big)$
$\geq \frac{1}{\vert G \vert}\sum_{k=1}^{\vert G\vert} \text{trace}\big(D_r^k\big)\cdot \text{trace}\big(D_r^k\big)=\langle \chi, \chi\rangle = \eta_1^2+\eta_2^2 + ... + \eta_{\vert G \vert}^2$
$\geq \sum_{j=1}^{\vert G\vert} \eta_j=r$
The first inequality comes from the prior lemma and is met with equality iff $\text{trace}\big(D_r^k\big) \in \big\{0,r\big\}$ for all $k$ and the second inequality comes from the fact that $\eta_j \in \mathbb N$ and is met with equality iff all $\eta_j \in \big\{0,1\big\}$ i.e. if all eigenvalues of $D_r$ are distinct.

Since both inequalities are met with equality we conclude that all eigenvalues are distinct and $\text{trace}\big(M^k\big) \in \big\{0,r\big\}$ for all $k$

Lemma 6:
$D_r$ consists of a complete set of $r$th roots of unity.

Since $M$ is similar to $\pmatrix{D_r & \mathbf 0\\ \mathbf 0&\mathbf 0}$ and all eigenvalues of $D_r$ are distinct, we know $M$ has minimal polynomial

$M^{r+1} + c_r M^r + c_{r-1}M^{r-1}+ ...+c_1 M=\mathbf 0$
i.e. $M^{r+1}$ is written uniquely as linear combination of $\big\{M^r, M^{r-1}, ..., M\big\}$. Put differently, $\big\{M^r, M^{r-1}, ..., M\big\}$ provides a basis for powers of $M$. Since $\text{trace}\big(M^k\big)\gt 0$ for some $k$ ($M$ is not nilpotent), the above basis in combination with the Lemma $5$ implies
$\text{trace}\big(M^k\big)=r$ for some $k\in \big\{1,2,...,r\big\}$

Lemma $4$ tells us that $\text{trace}\big(M^k\big)=r\implies D_r^k = I_r \implies$ all eigenvalues of $D_r$ are $k$th roots of unity. However for $k \in \big\{1,2,...,r-1\big\}$ there are $\lt r$ distinct kth roots of unity and all eigenvalues of $D_r$ are distinct by the lemma 5 $\implies \text{trace}\big(M^k\big)=0 $ for $k \in \big\{1,2,...,r-1\big\}\implies \text{trace}\big(M^r\big)=r\implies D_r$ consists of a complete set of $r$th roots of unity.

Corollary:
$\text{trace}\big(M^k\big) = 0$ if $k\% r \neq 0$ (i.e. when $k$ is not a multiple of $r$)
$\text{trace}\big(M^k\big) = r$ when $k\% r = 0$ (i.e. when $k$ is a multiple of $r$)

main problem:
Suppose some diagonal element of $P^k$ is positive, then $\text{trace}\big(P^k\big)\gt 0$, and $P^k$ is reducible by the argument in Lemma 2 (in the induction case). So $P^k$ is a direct sum of $m=m_0+m_1$ irreducibles, where $m_0$ of those have period $p_i\geq 2$ each having trace zero by lemma 1, thus $\text{trace}\big(P^k\big)= $ sum of traces of $m_1$ aperiodic irreducibles (each having a single eigenvalue with modulus 1, i.e. the Perron root).
define $T':= \lim_{t\to \infty}\Big(\big(P^k\big)^{k^{''}}\Big)^t$
where mimicking before, $k^{''}$ is chosen to send all unit modulus eigenvalues of $\big(P^k\big)$ to 1.

When we apply $T'$, we get $\big(T'P^k\big)$ is still a direct sum of $m = m_0+m_1$ irreducibles
i.e. taking a power of $\big(P^k\big)$ respects the block diagonal structure it has (up to graph isomorphism) and this necessarily holds in limits as well. When we examine an arbitrary block of $\big(P^k\big)$ we see that $T'$ kills all subdominant spectra but acts as the identity on roots of unity hence periodicity ($m_0$) and aperiodicity ($m_1$) is preserved.

but $T'=S\pmatrix{I_r & \mathbf 0\\ \mathbf 0&\mathbf 0}S^{-1}=T$ thus

$T'P^k= TP^k = \big(TP\big)^k=M^k$ so
$ \text{trace}\big(M^k\big)=m_1\gt 0\implies k$ is a multiple of $r$ by the preceding corollary. Finally $J^k\to \mathbf 0$ means $\big\vert \text{trace}\big(M^{r\cdot t}\big)- \text{trace}\big(P^{r\cdot t}\big)\big\vert\lt \epsilon$ for any $\epsilon \gt 0$ for $t$ large enough, in particular after selecting $t$ we have $\text{trace}\big(P^{r\cdot t}\big)\gt 0$ and $\text{trace}\big(P^{r\cdot {(t+1)}}\big)\gt 0$ thus $r$ is the GCD. We have established a bijection that $r$ eigenvalues on the unit circle for $P$ implies period $r$ for arbitrary integer $r\geq 2$ and this completes the proof.