Is a circulant matrix irreducible?

Question

A circulant matrix $\mathbf{C} \in \mathbb{R}^{n \times n}$ is of the form \begin{equation} \label{circulantmat} \mathbf{C} = \begin{pmatrix} {c_0} & {c_1} & {\dots} & {c_{n-2}} & {c_{n-1}} \\ {c_{n-1}} & {c_0} & {c_1} & {} & {c_{n-2}} \\ {\vdots} & {c_{n-1}} & {c_0} & {\ddots} & {\vdots} \\ {c_2} & {} & {\ddots} & {\ddots} & {c_1} \\ {c_1} & {c_2} & {\dots} & {c_{n-1}} & {c_0} \\ \end{pmatrix}. \end{equation}

In my case, I have that $\mathbf{C}$ has zero entries everywhere except $c_0$, $c_1$ and $c_{n-1}$, which are positive.

I know that $\mathbf{C}$ is irreducible if and only if \begin{equation} (\mathbf{I}_n + \mathbf{C})^{n-1} > 0. \end{equation} Is there a way to show that the above holds?

By intuition, I know that as the non-zero entries of the circulant matrix neighbor each other, the directed graph of the adjacency matrix of $\mathbf{C}$ would be strongly connected, but I want to show this more mathematically.

I have other circulant matrices where more neighboring points are non-zero, which I assume would mean that a similar result would hold.

Answer 1

Your circulant matrix $C = \mathbf I_n + \mathbf C $ can be written in the form $$ C = c_{n-1}P^{-1} + (1+c_0)I + c_1 P. $$ We note that $C^{n-1}$ is positive if and only if $P^{n-1}C^{n-1} = (PC)^{n-1}$ is positive. So, to make things a bit more (notationally) convenient, we consider the matrix $$ PC = c_{n-1}I + (1+c_0)P + c_1 P^2. $$ For each integer $q$, define the set $$ S_q = \{(i,j,k) : i,j,k \in \Bbb Z_{\geq 0},\ i+j+k = n-1, \ j + 2k = q\}. $$ By expanding the product, we can write $$ C^{n-1} = \sum_{q=0}^{n-1} \left(\sum_{(i,j,k) \in S_q} c_{n-1}^i (1 + c_0)^j c_1^k \right)P^q \\ \qquad \qquad \qquad \qquad \qquad \qquad + [\text{non-negative matrix built from higher powers of }P]. $$ We note that for each $q = 1,\dots,n-1$, the set $S_q$ is non-empty (for instance, since we can always find an element with $k = 0$). Thus, the coefficient $\sum_{(i,j,k) \in S_q} c_{n-1}^i (1 + c_0)^j c_1^k$ is necessarily positive, and $\sum_{q=0}^{n-1} \left(\sum_{(i,j,k) \in S_q} c_{n-1}^i (1 + c_0)^j c_1^k \right)P^q$ is a positive circulant matrix.

So, $P^{n-1}C^{n-1}$ is the sum of a positive matrix and a non-negative matrix, which means that it and $C^{n-1}$ are positive.

---

Another approach: show that for $D = \sum_{i=-k}^k d_i P^i$ (with $d_i$ positive), $CD$ is circulant with a positve $\pm(k+1)$th "diagonal". In particular, we can show that $$ CD = \sum_{i=-k-1}^{k-1} c_{n-1}d_{i+1} P^i + \sum_{i=-k}^k c_0 d_i P^i + \sum_{i=-k+1}^{k+1} c_1d_{i-1} P^i. $$ The first term has a positive $-(k+1)$ diagonal, and the third term has a positive $+(k+1)$ diagonal.

With that, we can now inductively conclude that $C^{\lceil (n-1)/2 \rceil}$ will be poisitive.