# Row graphs of Toeplitz matrices††thanks: This work was partially supported
by Science Research Center Program through the National Research Foundation of
Korea(NRF) Grant funded by the Korean Government (MSIP)(NRF-2016R1A5A1008055).
G.-S. Cheon was partially supported by the NRF-2019R1A2C1007518. Bumtle Kang
was partially supported by the NRF-2021R1C1C2014187. S.-R. Kim was partially
supported by the Korea government (MSIP) (NRF-2017R1E1A1A03070489).

Gi-Sang Cheona,b, Bumtle Kangb, Suh-Ryung Kimb,c, and Homoon Ryub,c
a Department of Mathematics, Sungkyunkwan University, Suwon 16419, Rep. of
Korea
b Applied Algebra and Optimization Research Center, Sungkyunkwan University,
Suwon 16419, Rep. of Korea
c Department of Mathematics Education, Seoul National University,
Seoul 08826, Rep. of Korea
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

In this paper, we study row graphs of Toeplitz matrices. The notion of row
graphs was introduced by Greenberg et al. in 1984 and is closely related to
the notion of competition graphs, which has been extensively studied since
Cohen had introduced it in 1968.

To understand the structure of the row graphs of Toeplitz matrices, which seem
to be quite complicated, we have begun with Toeplitz matrices whose row graphs
are triangle-free. We could show that if the row graph $G$ of a Toeplitz
matrix $T$ is triangle-free, then $T$ has the maximum row sum at most $2$.
Furthermore, it turns out that $G$ is a disjoint union of paths and cycles
whose lengths cannot vary that much in such a case. Then we study
$(0,1)$-Toeplitz matrices whose row graphs have only path components, only
cycle components, and a cycle component of specific length, respectively. In
particular, we completely characterize a $(0,1)$-Toeplitz matrix whose row
graph is a cycle.

Keywords: Toeplitz matrix, row graph, competition graph, triangle-free graph,
cycle components

##  1 Introduction

The support of a matrix $A$ is the $(0,1)$-matrix with the $(i,j)$-entry equal
to $1$ if the $(i,j)$-entry of $A$ is nonzero, and equal to $0$, otherwise.
The digraph of a square matrix is the digraph whose adjacency matrix is the
support of the matrix If a square matrix $A$ is symmetric, then the arc set of
its digraph is symmetric and we consider the graph of $A$, instead of the
digraph of $A$, which is obtained from the digraph of $A$ by replacing each
directed cycle of length $2$ with an edge.

A Toeplitz matrix of order $n$ is an $n\times n$ matrix, $T=(t_{ij})$ where
$t_{ij}=a_{i-j}$ for all $i,j=1,\ldots,n$, i.e. a matrix of the form

$\displaystyle T=\left(\begin{array}[]{cccc}a_{0}&b_{1}&\cdots&b_{n-1}\\\
a_{1}&a_{0}&\ddots&\vdots\\\ \vdots&\ddots&\ddots&b_{1}\\\
a_{n-1}&\cdots&a_{1}&a_{0}\end{array}\right),\quad b_{i}=a_{-i}.$ (5)

Toeplitz matrices have been investigated by many authors with wide application
in various fields of pure and applied mathematics. For example, the matrices
often appear in discrete differential or integral equations, physical data-
processing, orthogonal polynomials, stationary processes, and moment problems,
see [6, 10, 11] and references there in. Recently, the primitivity and the
exponents of $(0,1)$-Toeplitz matrices have been studied in [12].

In this paper, we study the “row graphs” of $(0,1)$-Toeplitz matrices and
obtain some interesting results. Given a $(0,1)$ boolean matrix $A$, a graph
$G$ is called the row graph of $A$ and denoted by ${\rm RG}(A)$ if the rows of
$A$ are the vertices of $G$, and two vertices are adjacent in $G$ if and only
if their corresponding rows have a nonzero entry in the same column of $A$.
This notion was studied by Greenberg [7]. As a matter of fact, ${\rm RG}(A)$
is the “competition graph” of the digraph of $A$, which was introduced by
Cohen [3] in 1968 associated with the study of ecosystems. Given a digraph
$D$, the competition graph of $D$ has $V(D)$ as its vertex set and an edge
$uv$ if and only if there are arcs $u\to w$ and $v\to w$ for some vertex $w$
in $D$ (see Figure 1 for an illustration). The notion of competition graphs
and its variants have been extensively studied since Cohen introduced it.

Most digraphs dealt in studying competition graphs have none of loops,
multiple edges. Equivalently, the adjacency matrices of those digraphs are
$(0,1)$-matrices with the zero main diagonal and not both $(i,j)$-entry and
$(j,i)$-entry $1$. In this vein, we technically consider the family
${\mathcal{T}}$ of $(0,1)$-Toeplitz matrices $T=(t_{i,j})_{n}$ satisfying the
following conditions:

  * (i)

$t_{i,i}=0$ for all $i\in[n]$;

  * (ii)

If $t_{i,j}=1$, then $t_{j,i}=0$.

If we describe the row graph $G$ of a $(0,1)$-Toeplitz matrix $(t_{i,j})_{n}$
more precisely,

$V(G)=[n]$

and $i$ and $j$ are adjacent in $G$ if and only if $t_{i,k}=t_{j,k}=1$ for
some $k\in[n]$.

If a graph $G$ is the row graph of $T$ for some $T\in\mathcal{T}$, then we
call $G$ a Toeplitz-row graph. Unless otherwise mentioned, we mean by a
$(0,1)$-Toeplitz matrix a matrix in ${\mathcal{T}}$.

Given a $(0,1)$ boolean matrix $A$, we denote by ${\mathcal{C}}(A)$ the
adjacency matrix of ${\rm RG}(A)$, that is, the $(i,j)$-entry of
$\mathcal{C}(A)$ equals

$\begin{cases}1&\mbox{if $i\neq j$ and the inner product of the $i$th row and
the $j$th row of $A$ is $1$;}\\\ 0&\mbox{otherwise.}\end{cases}$

We may regard ${\mathcal{C}}$ as an operator on the set of all $n\times n$
boolean matrices.

${0}$${0}$${1}$${0}$${0}$${1}$${1}$${0}$${0}$${1}$${0}$${0}$${0}$${1}$${0}$${0}$${1}$${0}$${1}$${0}$${1}$${0}$${0}$${1}$${0}$${1}$${0}$${1}$${0}$${0}$${0}$${0}$${1}$${0}$${1}$${0}$$\left(\vbox{\hrule
height=43.06433pt,depth=43.06433pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=43.06433pt,depth=43.06433pt,width=0.0pt}\right)$$T=$

$1$$6$$2$$5$$3$$4$${\rm RG}(T)=:G$

${0}$${0}$${0}$${1}$${0}$${1}$${0}$${0}$${0}$${1}$${1}$${0}$${0}$${0}$${0}$${0}$${1}$${1}$${1}$${1}$${0}$${0}$${0}$${1}$${0}$${1}$${1}$${0}$${0}$${0}$${1}$${0}$${1}$${1}$${0}$${0}$$\left(\vbox{\hrule
height=43.06433pt,depth=43.06433pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=43.06433pt,depth=43.06433pt,width=0.0pt}\right)$$A(G)=$

Figure 1: A Toeplitz matrix $T=T_{6}\langle 1,3;2,5\rangle$, the row graph $G$
of $T$, and the adjacency matrix $A(G)$ of $G$

In Section 2, we study triangle-free Toeplitz-row graphs. We first derive
equalities involving integers belonging to $\alpha$ or $\beta$ as the
condition for two vertices being adjacent in the row graph of a Toeplitz
matrix $T_{n}\langle\alpha;\beta\rangle$ (Theorem 2.1). We show that if the
row graph of a Toeplitz matrix $T$ is triangle-free, then $T$ belongs to
${\mathcal{T}}_{\leq 2}$ where ${\mathcal{T}}_{\leq 2}$ denotes the set of
Toeplitz matrices with the maximum row sum at most $2$. By the way, if
$T\in{\mathcal{T}}_{\leq 2}$, then ${\rm RG}(T)$ is a disjoint union of cycles
and paths and therefore a triangle-free Toeplitz row graph is a disjoint union
of paths and cycles. Based on these observations we came up with the following
research question:

Is every disjoint union of cycles and paths a triangle-free Toeplitz-row
graph?

The answer turns out to be no. As a matter of fact, the lengths of paths or
cycles in a triangle-free Toeplitz row graph cannot be much different (Theorem
2.10). We give a necessary and sufficient condition for a Toeplitz matrix
belonging to ${\mathcal{T}}_{\leq 2}$ (Theorem 2.7), which plays an important
role throughout Sections 2. We characterize a Toeplitz matrix
$T_{n}(\alpha,\beta)\in{\mathcal{T}}_{\leq 2}$ with $|\alpha|=|\beta|=2$ whose
row graph is triangle-free (Theorem 2.8) and the connected triangle-free
Toeplitz-row graphs (Theorem 2.14).

Section 3 focuses on $(0,1)$-Toeplitz matrices whose row graphs consist of
only path components, only cycle components, and a cycle component with
specific length, respectively. We first give a sufficient condition for a
$(0,1)$-Toeplitz matrix to have the row graph consisting of only path
components (Proposition 3.3). Then we show that, given integers $4\leq m\leq
n$ except a few cases, there is a Toeplitz matrix of order $n$ whose row graph
contains a cycle component of length $m$ (Theorem 3.5). We completely
characterize the Toeplitz matrices $T_{n}\langle\alpha;\beta\rangle$ with
$|\alpha|=2$ and $|\beta|=1$ whose row graph contains a cycle (Theorem 3.9).
We give a sufficient condition for the row graph of a Toeplitz matrix
consisting of only cycle components and figure out the length of cycles
(Proposition 3.12 and Theorem 3.15). Finally, we completely characterize a
Toeplitz matrix whose row graph is a cycle (Theorem 3.14).

##  2 Triangle-free Toeplitz-row graphs

Since Toeplitz matrices are completely determined by their first column and
first row, we begin by assuming that there are $k_{1}$ ones in the first
column and $k_{2}$ ones in the first row of $T$ ($k_{1}$ or $k_{2}$ may be $0$
but not both), and $t_{i+1,1}=1$ for $i=i_{1},\ldots,i_{k_{1}}$ if $k_{1}\geq
1$ and $t_{1,j+1}=1$ for $j=j_{1},\ldots,j_{k_{2}}$ if $k_{2}\geq 1$. Denote
by $\alpha=\\{i_{1},\ldots,i_{k_{1}}\\}$ if $k_{1}\geq 1$ and
$\beta=\\{j_{1},\ldots,j_{k_{2}}\\}$ if $k_{2}\geq 1$ the sets of such row and
column indices in increasing order. If $k_{1}=0$ (resp. $k_{2}=0$), then
$\alpha=\emptyset$ (resp. $\beta=\emptyset$). By definition, clearly $\alpha$
and $\beta$ are disjoint subsets of $[n-1]$. Recall that the lower shift
matrix $L$ of order $n$ is the $(0,1)$-matrix with ones only on the
subdiagonal, and zeroes elsewhere. For example, the $4\times 4$ lower shift
matrix is

$\displaystyle L=\left(\begin{array}[]{cccc}0&0&0&0\\\ 1&0&0&0\\\ 0&1&0&0\\\
0&0&1&0\end{array}\right).$

Thus it follows from (5) that $T$ can be expressed in terms of $L$ and
$U=L^{T}$ as follows:

$T=\sum_{m=1}^{k_{1}}L^{i_{m}}+\sum_{m=1}^{k_{2}}U^{j_{m}}$ (7)

(if $k_{1}=0$ or $k_{2}=0$, then the corresponding summands are regarded as
zero matrices). For convenience, we denote $T$ by
$T_{n}\langle\alpha;\beta\rangle$ or $T_{n}\langle
i_{1},\ldots,i_{k_{1}};j_{1},\ldots,j_{k_{2}}\rangle$ when we need to specify
the elements of $\alpha,\beta$. Especially, if $\alpha=\beta$, then
$T_{n}\langle\alpha;\beta\rangle$ is a $(0,1)$-symmetric Toeplitz matrix with
zero diagonal and we denote it by $ST_{n}\langle\alpha\rangle$.

We note that $T_{n}\langle\alpha;\beta\rangle=PT_{n}\langle\beta;\alpha\rangle
P^{T}$ for the permutation matrix $P=[p_{i,j}]$ where $p_{i,j}=1$ if and only
if $i+j=n+1$. Thus the row graph of $T_{n}\langle\alpha;\beta\rangle$ and that
of $T_{n}\langle\beta;\alpha\rangle$ are isomorphic. Accordingly, we may
assume $i_{1}<j_{1}$ for a $(0,1)$-Toeplitz matrix $T_{n}\langle
i_{1},\ldots,i_{k_{1}};j_{1},\ldots,j_{k_{2}}\rangle$ without loss of
generality.

######  Theorem 2.1.

Let $T=T_{n}\langle\alpha;\beta\rangle$ and take integers $i$ and $j$ in $[n]$
with $i<j$. Then $i$ and $j$ are adjacent in ${\rm RG}(T)$ if and only if one
of the following is true:

$\displaystyle j-i=$ $\displaystyle i_{t}-i_{s}$ for some
$i_{s}\in\alpha\cap[i-1]$ and $i_{t}\in\alpha\cap[j-1]$ with $s<t$; (8)
$\displaystyle j-i=$ $\displaystyle j_{q}-j_{p}$ for some
$j_{q}\in\beta\cap[n-i]$ and $j_{p}\in\beta\cap[n-j]$ with $p<q$; (9)
$\displaystyle j-i=$ $\displaystyle i_{t}+j_{q}$ for some $i_{t}\in\alpha$ and
$j_{q}\in\beta$. (10)

###### Proof.

Let $T=[t_{i,j}]$ and $G={\rm RG}(T)$. Suppose that $i$ and $j$ are adjacent
in $G$. Then, by definition, there exists $k\in[n]$ such that $t_{i,k}=1$ and
$t_{j,k}=1$. We consider the following three cases: (i) $1\leq k<i$; (ii)
$i<k<j$; (iii) $j<k\leq n$. We let

$i-k=i_{s},\quad j-k=i_{t},\quad k-i=j_{q},\quad\mbox{and}\quad k-j=j_{p}.$

In Case (i), $i_{s}\in\alpha\cap[i-1]$, $i_{t}\in\alpha\cap[j-1]$, and
$j-i=i_{t}-i_{s}$; in Case (ii), $j_{q}\in\beta$, $i_{t}\in\alpha$, and
$j-i=i_{t}+j_{p}$; in Case (iii), $j_{q}\in\beta\cap[n-i]$,
$j_{p}\in\beta\cap[n-j]$, and $j-i=j_{p}-j_{q}$.

We show the converse.

Case 1. $j-i=i_{t}-i_{s}$ for some $i_{s}\in\alpha\cap[i-1]$ and
$i_{t}\in\alpha\cap[j-1]$. Then $t_{i_{s}+1,1}=t_{i_{t}+1,1}=1$. Since
$i_{s}\leq i-1$, we have $i-i_{s}\geq 1$ and $t_{i,i-i_{s}}=1$. Similarly,
$t_{j,j-i_{t}}=1$. By the case assumption, $i-i_{s}=j-i_{t}$, so $i$ and $j$
are adjacent in $G$.

Case 2. $j-i=j_{q}-j_{p}$ for some $j_{q}\in\beta\cap[n-i]$ and
$j_{p}\in\beta\cap[n-j]$. Then $t_{1,j_{p}+1}=t_{1,j_{q}+1}=1$. Since
$j_{q}\leq n-i$, we have $i+j_{q}\leq n$ and $t_{i,i+j_{q}}=1$. Similarly,
$t_{j,j+j_{p}}=1$. By the case assumption, $i+j_{q}=j+j_{p}$, so $i$ and $j$
are adjacent in $G$.

Case 3. $j-i=i_{t}+j_{q}$ for some $i_{t}\in\alpha$ and $j_{q}\in\beta$. Then
$t_{1,j_{q}+1}=t_{i_{t}+1,1}=1$. Therefore $t_{i,i+j_{q}}=t_{j,j-i_{s}}=1$. By
the case assumption, $i+j_{q}=j-i_{s}$, so $i$ and $j$ are adjacent in $G$. ∎

######  Proposition 2.2.

For any Toeplitz matrix of order $n$, the $\ell$th row sum equals the
$(n-\ell+1)$st column sum for any $\ell\in[n]$.

###### Proof.

Let $T=T_{n}\langle\alpha;\beta\rangle$. Take $\ell\in[n]$ and let

$M_{1}=\\{\ell-i_{s}\in[n]\mid i_{s}\in\alpha\\}\quad\mbox{and}\quad
M_{2}=\\{\ell+j_{t}\in[n]\mid j_{t}\in\beta\\}.$

Then the nonzero columns in the $\ell$th row is a disjoint union of $M_{1}$
and $M_{2}$. Now we let

$N_{1}=\\{p\in[n]\mid p-i_{s}=n-\ell+1,i_{s}\in\alpha\\}\quad\mbox{and}\quad
N_{2}=\\{p\in[n]\mid p+j_{t}=n-\ell+1,j_{t}\in\beta\\}.$

Then the nonzero entries on $n-\ell+1$st column is a disjoint union of $N_{1}$
and $N_{2}$.

We claim that for each $i=1,2$ and $p\in[n]$, $x\in M_{i}$ if and only if
$n-p+1\in N_{i}$ as follows:

$p\in M_{1}$ (resp. $p\in M_{2}$)
---
$\Leftrightarrow$ $p=\ell-i_{s}$ for some $i_{s}\in\alpha$ (resp.
$p=\ell+j_{t}$ for some $j_{t}\in\beta$)
$\Leftrightarrow$ $n-p+1=n-\ell+1+i_{s}$ for some $i_{s}\in\alpha$ (resp.
$n-p+1=n-\ell+1-j_{t}$ for some $j_{t}\in\beta$ )
$\Leftrightarrow$ $(n-p+1)-i_{s}=n-\ell+1$ for some $i_{s}\in\alpha$ (resp.
$(n-p+1)+j_{t}=n-\ell+1$ for some $j_{t}\in\beta$ )
$\Leftrightarrow$ $n-p+1\in N_{1}$ (resp. $n-p+1\in N_{2}$).

Thus $|M_{1}\cup M_{2}|=|N_{1}\cup N_{2}|$ and this completes the proof. ∎

######  Corollary 2.3.

The maximum row sum and the maximum column sum of a Toeplitz matrix are the
same.

######  Corollary 2.4.

If the row graph of a Toeplitz matrix $T$ is triangle-free, then the maximum
row sum of $T$ is at most two.

###### Proof.

Suppose that a triangle-free graph $G$ is the row graph of a Toeplitz matrix
$T$. Then, by the definition of row graph, the maximum column sum is at most
two. Thus, by Corollary 2.3, the maximum row sum of $T$ is at most two. ∎

In [9], it is shown that if $D$ has maximum indegree and maximum outdegree at
most $2$, then its competition graph is a disjoint union of cycles and paths.
In other words, if a Toeplitz matrix $T$ belongs to ${\mathcal{T}}_{\leq 2}$,
then ${\rm RG}(T)$ is a disjoint union of cycles and paths.

######  Corollary 2.5.

If $T$ is a Toeplitz matrix with the maximum row sum at most $2$, then the row
graph of $T$ is a disjoint union of cycles and paths.

Thus, by Corollaries 2.4 and 2.5, we obtain the following corollary.

######  Corollary 2.6.

A triangle-free Toeplitz-row graph is a disjoint union of cycles and paths.

Let ${\mathcal{G}}_{\leq 2}$ be the set of graphs with degree at most $2$,
that is, the set of graphs each of which is a disjoint union of cycles and
paths. Then Corollary 2.6 may be restated as follows:

$\\{G\mid G={\rm RG}(T)\text{ for some $T\in{\mathcal{T}}$ and }G\text{ is
triangle-free}\\}\subseteq{\mathcal{G}}_{\leq 2}.$

In the rest of this section, we will examine disjoint union of cycles and
paths that are row graphs of Toeplitz matrices. By Corollaries 2.4 and 2.5, we
only need take a look at Toeplitz matrices in ${\mathcal{T}}_{\leq 2}$. We can
easily check that if $T_{n}\langle\alpha;\beta\rangle\in{\mathcal{T}}_{\leq
2}$, then $\alpha\leq 2$ and $\beta\leq 2$. However, the following matrix
shows that the converse is not true;

$\displaystyle T_{7}\langle
1,3;2,5\rangle=\left(\begin{array}[]{ccccccc}0&0&1&0&0&1&0\\\ 1&0&0&1&0&0&1\\\
0&1&0&0&1&0&0\\\ 1&0&1&0&0&1&0\\\ 0&1&0&1&0&0&1\\\ 0&0&1&0&1&0&0\\\
0&0&0&1&0&1&0\end{array}\right).$

Based on the observation, we present a necessary and sufficient condition for
a Toeplitz matrix $T=T_{n}\langle\alpha;\beta\rangle$ belonging to
${\mathcal{T}}_{\leq 2}$ when $\alpha\neq\emptyset$ and $\beta\neq\emptyset$,
which will play a key role in studying triangle-free Toeplitz-row graphs. We
can easily check that $T=T_{n}\langle\alpha;\beta\rangle$ belongs to
${\mathcal{T}}_{\leq 2}$ if one of $\alpha$ and $\beta$ is the empty set and
the other set has order at most $2$.

######  Theorem 2.7.

Let $T=T_{n}\langle i_{1},\ldots,i_{k_{1}};j_{1},\ldots,j_{k_{2}}\rangle$
where $k_{1},k_{2}\geq 1$. Then the maximum row sum of $T$ is at most $2$ if
and only if the following property holds:

  * $(\star)$

$k_{1},k_{2}\leq 2$, and especially if $k_{2}=2$, then $i_{1}+j_{2}\geq n$ and
if $k_{1}=2$, then $i_{2}+j_{1}\geq n$.

###### Proof.

We first show the ‘if’ part. To reach a contradiction, suppose that the row
sum of the $u$th row is at least $3$ for some $u\in[n]$. Then there are
$\\{v_{1},v_{2},v_{3}\\}\subset[n]$ such that the entries $(u,v_{1})$,
$(u,v_{2})$, and $(u,v_{3})$ of $T$ is $1$. By the definition of Toeplitz
matrix, for each $i=1,2,3$, either

$u-v_{i}\in\alpha$ (11)

or

$v_{i}-u\in\beta.$ (12)

Since $k_{1},k_{2}\leq 2$, exactly two of $v_{1},v_{2},v_{3}$ satisfy (11) or
exactly two of $v_{1},v_{2},v_{3}$ satisfy (12). We may assume the former so
that $u-v_{1}=i_{1}$, $u-v_{2}=i_{2}$, and $v_{3}-u\in\beta$. Then
$v_{3}-v_{2}\geq i_{2}+j_{1}\geq n$, which is impossible since
$\\{v_{2},v_{3}\\}\subseteq[n]$. Thus the maximum row sum of $T$ is at most
$2$.

Now we show the contrapositive of the ‘only if’ part. We can easily see that
the $n$th row sum and the $1$st row sum are $k_{1}$ and $k_{2}$, respectively.
Therefore $k_{1},k_{2}\leq 2$. If $k_{2}=2$ and $i_{1}+j_{2}<n$, then the
entries $(n-j_{2},n-i_{1}-j_{2})$, $(n-j_{2},n+j_{1}-j_{2})$, and
$(n-j_{2},n)$ equal $1$ and so the $(n-j_{2})$th row sum is at least $3$. A
similar argument can be applied for the case $k_{1}=2$ and $i_{2}+j_{1}<n$. ∎

We characterize a Toeplitz matrix $T_{n}(\alpha,\beta)\in{\mathcal{T}}_{\leq
2}$ with $|\alpha|=|\beta|=2$ whose row graph is triangle-free.

######  Theorem 2.8.

Let $T=T_{n}\langle i_{1},i_{2};j_{1},j_{2}\rangle$ with $i_{1}+j_{2}\geq n$
and $i_{2}+j_{1}\geq n$. Then ${\rm RG}(T)$ contains a triangle if and only if
one of the following holds:

  * (i)

$2i_{2}=3i_{1}+j_{1}$ and $n>2i_{1}+j_{1}$;

  * (ii)

$2j_{2}=i_{1}+3j_{1}$ and $n>i_{1}+2j_{1}$;

  * (iii)

$i_{2}=3i_{1}+2j_{1}$;

  * (iv)

$j_{2}=2i_{1}+3j_{1}$;

  * (v)

$i_{2}+j_{2}=2(i_{1}+j_{1})$.

###### Proof.

We first show the ‘if’ part. We can check that for each cases (i), (ii),
(iii), (iv), and (v), $\\{1+i_{1},1+i_{2},1+2i_{2}-i_{1}\\}$,
$\\{1,1+j_{2}-j_{1},1+2j_{2}-2j_{1}\\}$,
$\\{1+i_{1},1+2i_{1}+j_{1},1+3i_{1}+2j_{1}\\}$,
$\\{1,1+i_{1}+j_{1},1+2i_{1}+2j_{1}\\}$, and
$\\{1,1+j_{2}-j_{1},1+i_{2}+j_{2}-(i_{1}+j_{1})\\}$ is a triangle of ${\rm
RG}(T)$, respectively.

Now we show the ‘only if’ part. Suppose that there is a triangle $uvw$ of
${\rm RG}(T)$ with $u<v<w$. Then
$\\{v-u,w-v,w-u\\}\subset\\{i_{1}+j_{1},j_{2}-j_{1},i_{2}-i_{1}\\}$ by the
hypothesis and Theorem 2.1. Suppose that $\\{w-v,v-u\\}$ is either
$\\{i_{1}+j_{1},i_{2}-i_{1}\\}$ or $\\{i_{1}+j_{1},j_{2}-j_{1}\\}$. Then
$w-u=i_{2}+j_{1}\geq n$ or $w-u=i_{1}+j_{2}\geq n$, which is impossible.
Suppose that $\\{w-v,v-u\\}=\\{i_{2}-i_{1}\\}$ and $w-u=j_{2}-j_{1}$. Then, by
Theorem 2.1, $u>i_{1}$ and $w+j_{1}\leq n$. However,
$w+j_{1}=u+j_{2}>i_{1}+j_{2}\geq n$ and we reach a contradiction. Similarly,
we can show that the case $\\{w-v,v-u\\}=\\{j_{2}-j_{1}\\}$ and
$w-u=i_{2}-i_{1}$ cannot happen either.

Then the following are the only possible remaining cases since
$w-u=(w-v)+(v-u)$:

  * (1)

$\\{w-v,v-u\\}=\\{i_{2}-i_{1}\\}$ and $w-u=i_{1}+j_{1}$;

  * (2)

$\\{w-v,v-u\\}=\\{j_{2}-j_{1}\\}$ and $w-u=i_{1}+j_{1}$;

  * (3)

$\\{w-v,v-u\\}=\\{i_{1}+j_{1}\\}$ and $w-u=i_{2}-i_{1}$;

  * (4)

$\\{w-v,v-u\\}=\\{i_{1}+j_{1}\\}$ and $w-u=j_{2}-j_{1}$;

  * (5)

$\\{w-v,v-u\\}=\\{i_{2}-i_{1},j_{2}-j_{1}\\}$ and $w-u=i_{1}+j_{1}$.

In the case (1), since $u>i_{1}$, $n\geq w=u+i_{1}+j_{1}>2i_{1}+j_{1}$.
Moreover, since $w-u=(w-v)+(v-u)$, $2i_{2}=3i_{1}+j_{1}$. In the case (2),
since $w+j_{1}\leq n$, $n\geq w+j_{1}=u+i_{1}+2j_{1}>i_{1}+2j_{1}$. In
addition, $2j_{2}=i_{1}+3j_{1}$. In the case (3), since $u>i_{1}$, $n\geq
w=u+2(i_{1}+j_{1})>3i_{1}+2j_{1}$. In the case (4), since $w+j_{1}\leq n$,
$n\geq w+j_{1}\geq u+2(i_{1}+j_{1})+j_{1}>2i_{1}+3j_{1}$.

Furthermore, in the case (3), $i_{2}=3i_{1}+2j_{1}$ and
$n>3i_{1}+2j_{1}=i_{2}$; in the case (4) $j_{2}=2i_{1}+3j_{1}$ and
$n>2i_{1}+3j_{1}=j_{2}$. By the definition of Toeplitz graph,
$n>\max\\{i_{2},j_{2}\\}$, so there is no restriction on $n$ in cases (3) and
(4). Finally, we have $i_{2}+j_{2}=2(i_{1}+j_{1})$ in the case (5). Hence we
obtain the desired result. ∎

To find out the exact number of cycles or paths, we need the following lemma.

######  Lemma 2.9.

Take $T=T_{n}\langle
i_{1},\ldots,i_{k_{1}};j_{1},\ldots,j_{k_{2}}\rangle\in{\mathcal{T}}_{\leq 2}$
with $k_{1},k_{2}\geq 1$ and let $G$ be the row graph of $T$. Then the
following are true:

  * (a)

If $v_{1}v_{2}\cdots v_{\ell}$ is a path in $G$ for an integer $\ell\geq 2$,
then $(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ is also a path in $G$ if
$v_{i}\notin\\{1,1+i_{1}\\}$ for any $i\in[\ell]$.

  * (b)

If $v_{1}v_{2}\cdots v_{\ell}$ is a path component in $G$ for an integer
$\ell\geq 2$ with $v_{i}\notin\\{1,1+i_{1}\\}$ for each $i\in[\ell]$ and

$\\{v_{1},v_{\ell}\\}\cap\\{n-i_{2}+i_{1}+1,n-j_{2}+1,n-j_{1}+1,n-(i_{1}+j_{1})+1\\}=\emptyset,$
(13)

then $(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ is also a path component in $G$
(if $|\alpha|=1$, then we ignore $i_{2}$ and if $|\beta|=1$, then we ignore
$j_{2}$).

  * (c)

If $v_{1}v_{2}\cdots v_{\ell}v_{1}$ is a cycle in $G$ for an integer $\ell\geq
2$, then $(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)(v_{1}-1)$ is also a cycle in
$G$ if $v_{i}\notin\\{1,1+i_{1}\\}$ for any $i\in[\ell]$.

###### Proof.

By Theorems 2.1 and 2.7, vertices $x$ and $y$ with $y>x$ are adjacent if and
only if one of the following is true:

  * (i)

$y-x=i_{2}-i_{1}$, $i_{1}\leq x-1$, and $i_{2}\leq y-1$;

  * (ii)

$y-x=j_{2}-j_{1}$, $j_{2}\leq n-x$, and $j_{1}\leq n-y$;

  * (iii)

$y-x=i_{1}+j_{1}$

(if $k_{1}=1$ (resp. $k_{2}=1$), then we ignore the term $i_{2}-i_{1}$ (resp.
$j_{2}-j_{1}$)).

Suppose that $v_{1}v_{2}\cdots v_{\ell}$ is a path in $G$. To show (a),
suppose that $S\cap\\{1,1+i_{1}\\}=\emptyset$. Fix $k\in[\ell-1]$ and
$x_{k}=\min\\{v_{k+1},v_{k}\\}$ and $y_{k}=\max\\{v_{k+1},v_{k}\\}$. Since
$x_{k}\neq 1$ by the hypothesis, $1\leq x_{k}-1\leq y_{k}-1$. Since $x_{k}$
and $y_{k}$ are adjacent, one of (i), (ii), (iii) for $x=x_{k}$ and $y=y_{k}$
is true.

In the case (i), $i_{1}+1\leq x_{k}-1$ since $x_{k}\neq 1+i_{1}$. Thus
$i_{1}\leq(x_{k}-1)-1$. Since $i_{1}-x_{k}=i_{2}-y_{k}$,
$i_{2}\leq(y_{k}-1)-1$. In the case (ii), $j_{2}<n-(x_{k}-1)$ and
$j_{1}<n-(y_{k}-1)$. Thus $x_{k}-1$ and $y_{k}-1$ are adjacent in $G$. Since
$k$ was arbitrarily chosen, we may conclude that $v_{i}-1$ and $v_{i+1}-1$ are
adjacent in $G$ for all $i\in[\ell-1]$. Consequently, we have shown that
$(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ is also a path in $G$.

To show (b), suppose $v_{1}v_{2}\cdots v_{\ell}$ is a path component in $G$
for an integer $\ell\geq 2$ with $v_{i}\notin\\{1,1+i_{1}\\}$ for any
$i\in[\ell]$ and satisfying (13). Then
$Q:=(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ is a path by (a). Suppose, to the
contrary, $(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ is not a path component. Then
$Q$ is extendded to a longer path by Theorem 2.7. We consider the case in
which there is a vertex $v\neq v_{\ell-1}-1$ which is adjacent to $v_{\ell}-1$
in $G$. Let

$x=\min\\{v,v_{\ell}-1\\}\quad\mbox{and}\quad y=\max\\{v,v_{\ell}-1\\}.$

Since $x$ and $y$ are adjacent, one of (i), (ii), (iii) is true.

Suppose $v+1>n$. Since $v$ is a vertex in $G$, $v=n=y$. Then either (i) or
(iii) is true. Thus either $v_{\ell}-1=n-(i_{1}+j_{1})$ or
$v_{\ell}-1=n-i_{2}+i_{1}$, which contradicts (13).

Now, suppose that $v+1\leq n$. Noting $y-x=(y+1)-(x+1)$, we know that $v+1$
and $v_{\ell}$ are adjacent in the case (iii). In the case (ii),
$y-x=i_{2}-i_{1}$, $i_{1}\leq x-1<x$, and $i_{2}\leq y-1<y$. Thus $v+1$ and
$v_{\ell}$ are adjacent in $G$ and we reach a contradiction. In the case (i),
$y-x=j_{2}-j_{1}$, $j_{2}\leq n-x$, and $j_{1}\leq n-y$. Since
$v_{\ell}-1\not\in\\{n-j_{1},n-j_{2}\\}$ by (13), $j_{2}\leq n-(x+1)$ or
$j_{1}\leq n-(y+1)$. Since $y-x=j_{2}-j_{1}$, $j_{2}\leq n-(x+1)$ and
$j_{1}\leq n-(y+1)$. Thus $v+1$ and $v_{\ell}$ are adjacent in $G$ and we
reach a contradiction.

By a similar argument, one can show that there is no vertex except $v_{2}-1$
that is adjacent to $v_{1}-1$ in $G$. Hence,
$(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ is a path component in $G$ and (b) is
valid.

To show (c), suppose $v_{1}v_{2}\cdots v_{\ell}v_{1}$ is a cycle in $G$. By
(a), $(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)$ and $(v_{\ell}-1)(v_{1}-1)$ are
paths in $G$. Therefore $(v_{1}-1)(v_{2}-1)\cdots(v_{\ell}-1)(v_{1}-1)$ is
also a cycle in $G$. ∎

######  Theorem 2.10.

Let $G$ be a triangle-free Toeplitz-row graph. Then the following are true:

  * (a)

There are no three cycle of different lengths in $G$.

  * (b)

There are no seven paths of different lengths in $G$.

###### Proof.

Since $G$ is triangle-free, $G$ is the row graph of a Toeplitz matrix
$T_{n}\langle i_{1},\ldots,i_{k_{1}};j_{1},\ldots,j_{k_{2}}\rangle$ satisfying
($\star$) by Theorem 2.7.

To show (a) by contradiction, suppose that there are cycles
$C_{1},C_{2},C_{3}$ of different lengths in $G$. Then, by Lemma 2.9(c), there
exist cycles $C_{1}^{*},C_{2}^{*},C_{3}^{*}$ in $G$ such that $C_{i}^{*}$ has
same length as $C_{i}$ for each $i=1,2,3$ and each of
$C_{1}^{*},C_{2}^{*},C_{3}^{*}$ contains a vertex $1$ or $1+j_{1}$. By the
pigeonhole principle, a vertex $1$ or $1+i_{1}$ is on two of cycles, which is
a contradiction as $C_{1}$, $C_{2}$, $C_{3}$ are components of $G$ by
Corollary 2.6. Thus (a) is true.

To prove (b) by contradiction, suppose that there are path components
$P_{1},P_{2},\ldots,P_{7}$ of different lengths in $G$. Then there exist path
components $P_{1}^{*},P_{2}^{*},\ldots,P_{7}^{*}$ in $G$ such that $P_{i}^{*}$
has same length as $P_{i}$ for each $i=1,\ldots,7$ and each of
$P_{1}^{*},P_{2}^{*}\ldots,P_{7}^{*}$ contains one of the vertices
$1,1+i_{1},n-i_{2}+i_{1}+1,n-j_{2}+1,n-j_{1}+1,n-i_{1}-j_{1}+1$ by Lemma
2.9(b) (if $k_{1}=1$ (resp. $k_{2}=1$), ignore $n-j_{2}+1$ (resp.
$n-i_{2}+i_{1}+1$)). By the pigeonhole principle, at least one of the vertices
$1,1+i_{1},n-i_{2}+i_{1}+1,n-j_{2}+1,n-j_{1}+1,n-i_{1}-j_{1}+1$ is in two path
components which is a contradiction (if $k_{1}=1$ (resp. $k_{2}=1$), ignore
$n-j_{2}+1$ (resp. $n-i_{2}+i_{1}+1$)). ∎

######  Corollary 2.11.

Any graph containing three cycles of different lengths or seven path
components of different lengths is not a Toeplitz-row graph.

Now we characterize triangle-free Toeplitz-row graphs without isolated
vertices.

######  Lemma 2.12.

Any Toeplitz-row graph of order $n\leq 4$ has an isolated vertex.

###### Proof.

Clearly, if $n=2$, then the row graph of a Toeplitz matrix is edgeless. To the
contrary, suppose that $G:={\rm RG}(T)$ has no isolated vertex for some
$T=T_{n}\langle\alpha;\beta\rangle$ with $n\in\\{3,4\\}$. Since the vertices
$1$ and $n$ have degree at least one, $t_{1,k}=t_{n,\ell}=1$ for some
$k,\ell\in[n]$ and so $n-\ell\in\alpha$ and $k-1\in\beta$. Thus $k_{1}\geq 1$
and $k_{2}\geq 1$. We let $\alpha=\\{i_{1},\ldots,i_{k_{1}}\\}$ and
$\beta=\\{j_{1},\ldots,j_{k_{2}}\\}$. Then $k_{1}+k_{2}\leq n-1\leq 3$, so
$k_{1}=1$ or $k_{2}=1$. We first consider the case $k_{1}=1$. Then $k_{2}\leq
2$ and no two adjacent vertices in $G$ satisfy Theorem 2.1(8) . Since $G$ has
no isolated vertex, the vertex $n$ is adjacent to some vertex $u$ for some
$1\leq u<n$. Obviously, $u$ and $n$ do not satisfy Theorem 2.1(9), so
$n-u=i_{1}+j_{t}$ for some $t\in\\{1,2\\}$. Since $u<n\leq 4$, $n-u\leq 3$ and
so $i_{1}+j_{t}\leq 3$. Since we assumed $i_{1}<j_{1}$ throughout this paper,
$(i_{1},j_{1})=(1,2)$ and if there exists $j_{2}$, then $j_{2}=3$. Then all
the entries of $T$ are zero except $t_{2,1}=\cdots=t_{n,n-1}=1$,
$t_{1,3}=\cdots=t_{n,n-2}=1$, and $t_{1,4}=\cdots=t_{n,n-3}=0$ or $1$ depend
upon the existence of $j_{2}$. Thus $t_{3,j}=0$ except $j=2$. Yet, $t_{i,2}=0$
except $i=3$, so the vertex $3$ is isolated in $G$ and we reach a
contradiction. Thus $k_{1}=2$ and $k_{2}=1$. Then no two adjacent vertices
satisfy Theorem 2.1(9). Since the vertex $1$ has degree at least one, $1$ and
a vertex $v$ are adjacent for some $2\leq v\leq n$. Since $1$ and $v$ do not
satisfy Theorem 2.1(8), $v-1=i_{s}+j_{1}$ for some $s\in\\{1,2\\}$. Since we
assume $i_{1}<j_{1}$ throughout this paper, $i_{s}+j_{1}\geq 3$, so $n=v=4$
and $i_{s}+j_{1}=3$. Then $k_{1}=1$ and $(i_{1},j_{1})=(1,2)$, which leads to
a contradiction as above. ∎

######  Proposition 2.13.

A path or a cycle of order $n$ is a Toeplitz-row graph if and only if $n\geq
5$.

###### Proof.

The ‘only if’ part immediately follows from Lemma 2.12.

To prove the ‘if’ part, suppose $n\geq 5$. Let $T_{1}=T_{n}\langle
1,2;n-2\rangle$ (see Figure 2 for an illustration). Then, for each
$i=2,\ldots,n-1$, the $(i,i-1)$-entry and the $(i+1,i-1)$-entry of $T_{1}$ are
$1$, so the vertices $i$ and $i+1$ are adjacent in ${\rm RG}(T_{1})$.
Moreover, the $(1,n-1)$-entry and $(n,n-1)$-entry are $1$, so the vertices $1$
and $n$ are adjacent. Thus ${\rm RG}(T_{1})$ contains a path of order $n$ and
so, by Corollary 2.6, ${\rm RG}(T_{1})$ is a path of order $n$.

To show a cycle of length $n$ is a Toeplitz-row graph, consider
$T_{2}=T_{n}\langle 1,2;n-2,n-1\rangle$ (see Figure 2). Then, by the above
argument, $2,3,\ldots,n,1$ is the sequence of a path in ${\rm RG}(T_{2})$.
Since the $(1,n)$-entry and $(2,n)$-entry are $1$, the vertices $1$ and $2$
are adjacent. Thus ${\rm RG}(T_{2})$ contains a cycle of length $n$ and so, by
Corollary 2.6, ${\rm RG}(T_{2})$ is a cycle of length $n$. ∎

$\displaystyle T_{1}=\left(\begin{array}[]{cccccc}0&0&0&0&1&0\\\
1&0&0&0&0&1\\\ 1&1&0&0&0&0\\\ 0&1&1&0&0&0\\\ 0&0&1&1&0&0\\\
0&0&0&1&1&0\end{array}\right)$

$\displaystyle T_{2}=\left(\begin{array}[]{cccccc}0&0&0&0&1&1\\\
1&0&0&0&0&1\\\ 1&1&0&0&0&0\\\ 0&1&1&0&0&0\\\ 0&0&1&1&0&0\\\
0&0&0&1&1&0\end{array}\right)$

Figure 2: Toeplitz matrices $T_{1}=T_{6}\langle 1,2;4\rangle$ and
$T_{2}=T_{6}\langle 1,2;4,5\rangle$

Now we are ready to give a characterization of connected triangle-free
Toeplitz-row graphs.

######  Theorem 2.14.

A Toeplitz-row graph of order $n$ is connected and triangle-free if and only
if $n\geq 5$ and it is a path or a cycle of order $n$.

###### Proof.

The ‘if’ part is valid by the ‘if’ part of Proposition 2.13. The ‘only if’
part is true by Lemma 2.12 and the ‘only if’ of Proposition 2.13. ∎

##  3 Toeplitz matrices in ${\mathcal{T}}_{\leq 2}$ whose row graph contains a
cycle

In the previous section, we showed that

$\\{G\mid G={\rm RG}(T)\text{ for some $T\in{\mathcal{T}}$ and }G\text{ is
triangle-free}\\}\subseteq{\mathcal{G}}_{\leq 2}.$

In this section, we study

${\mathcal{T}_{\leq 2}^{\star}}:=\\{T\in{\mathcal{T}_{\leq 2}}\mid{\rm
RG}(T)\text{ contains a cycle}\\}.$

From Corollary 2.5, we know that the row graph of a Toeplitz matrix
$T\in{\mathcal{T}}_{\leq 2}$ is a disjoint union of paths and cycles.
Therefore $T_{\leq 2}\setminus{\mathcal{T}_{\leq 2}^{\star}}$ is a set of
Toeplitz matrix with maximum row sum at most $2$ whose row graph is a disjoint
union of path components.

We first present a specialized version of Theorem 2.1 for a matrix in
${\mathcal{T}}_{\leq 2}$.

######  Lemma 3.1.

Let $T=T_{n}\langle i_{1},i_{2};j_{1},i_{2}\rangle$ be a Toeplitz matrix in
${\mathcal{T}}_{\leq 2}$. Then two vertices $u$ and $v$ with $u<v$ are
adjacent in the row graph of $T$ if and only if one of the following is true:

  * (i)

$1\leq u\leq n-j_{2}$ and $v=u+j_{2}-j_{1}$;

  * (ii)

$i_{1}+1\leq u\leq n-i_{2}+i_{1}$ and $v=u+i_{2}-i_{1}$;

  * (iii)

$1\leq u\leq n-j_{1}-i_{1}$ and $v=u+i_{1}+j_{1}$.

###### Proof.

Suppose that $u$ and $v$ are adjacent. Then, by Theorem 2.1,
$v-u\in\\{j_{2}-j_{1},i_{2}+i_{1},i_{1}+j_{1},i_{1}+j_{2},i_{2}+j_{1},i_{2}+j_{2}\\}$.
If $v=u+j_{2}-j_{1}$, then $1\leq u\leq n-j_{2}$ by (9) of the same theorem.
Suppose $v=u+i_{2}-i_{1}$. Then $i_{1}\leq u-1$ by (8), so $i_{1}+1\leq u$.
Moreover, $u+i_{2}-i_{1}\leq n$ and so $u\leq n-i_{2}+i_{1}$. If
$v=u+i_{1}+j_{1}$, then $u+i_{1}+j_{1}=v\leq n$ and so $1\leq u\leq
n-j_{1}-i_{1}$. The converse is obviously true by Theorem 2.1. ∎

###  3.1 Toeplitz matrices in ${\mathcal{T}}_{\leq 2}^{\star}$

We first give a sufficient condition for a Toeplitz matrix belonging to
$T_{\leq 2}\setminus{\mathcal{T}_{\leq 2}^{\star}}$. A matrix is called
acyclic if its digraph does not contain a directed cycle. Using the following
lemma, we show that $T\in T_{\leq 2}\setminus{\mathcal{T}_{\leq 2}^{\star}}$
if $T$ is acyclic.

######  Lemma 3.2 ([12]).

Let $T=T_{n}\langle i_{1},\ldots,i_{k_{1}};j_{1},\ldots,j_{k_{2}}\rangle$.
Then the digraph of $T$ contains a directed cycle $C_{s,t}$ of length
$\frac{i_{s}+j_{t}}{\gcd(i_{s},j_{t})}$ for each $s\in[k_{1}]$ and
$t\in[k_{2}]$ such that $i_{s}+j_{t}\leq n$.

######  Proposition 3.3.

Let $T$ be an acyclic Toeplitz matrix in ${\mathcal{T}}_{\leq 2}$. Then the
row graph of $T$ consists of only path components.

###### Proof.

Let $G={\rm RG}(T)$. By Theorem 2.7, $T=T_{n}\langle\alpha;\beta\rangle$ with
$|\alpha|\leq 2$ and $|\beta|\leq 2$. Moreover, since $T$ is acyclic,
$i_{1}+j_{1}>n$ by Lemma 3.2 and so Lemma 3.1(iii) cannot happen. If
$|\alpha|=|\beta|=1$, then none of (i) and (ii) of Lemma 3.1 can happen and so
$G$ is an empty graph. Suppose that $|\alpha|=2$ or $|\beta|=2$. Then, since
(iii) of Lemma 3.1 cannot happen, the edge set of $G$ equals $E_{1}$ if
$|\alpha|=2$ and $|\beta|=1$; $E_{2}$ if $|\alpha|=1$ and $|\beta|=2$;
$E_{1}\cup E_{2}$ if $|\alpha|=|\beta|=2$ where

$E_{1}=\\{\\{i,i-i_{1}+i_{2}\\}\mid 1\leq i\leq n-i_{2}\\}\mbox{ and
}E_{2}=\\{\\{j,j-j_{1}+j_{2}\\}\mid 1+j_{1}\leq j\leq n+j_{1}-j_{2}\\}.$

Suppose, to the contrary, that the subgraph $G[E_{1}]$ of $G$ induced by
$E_{1}$ contains a cycle $C:=v_{0}v_{1}\ldots v_{\ell-1}v_{0}$ (we identify
$v_{\ell}$ with $v_{0}$) for some integer $\ell\geq 3$. Then
$|v_{i+1}-v_{i}|=i_{2}-i_{1}$ for all $i\in\\{0,1,\ldots,\ell-1\\}$. Since $C$
is closed, there is $i\in\\{0,1,\ldots,\ell-1\\}$ such that $v_{i-1}<v_{i}$
and $v_{i}>v_{i+1}$. Then

$v_{i}-v_{i+1}=|v_{i+1}-v_{i}|=|v_{i}-v_{i-1}|=v_{i}-v_{i-1},$

which implies $v_{i-1}=v_{i+1}$. Since $\ell\geq 3$, we have reached a
contradiction. By a similar argument, we may show that $G[E_{2}]$ does not
contain a cycle. Therefore the statement is true if either $|\alpha|=2$ and
$|\beta|=1$ or $|\alpha|=1$ and $|\beta|=2$.

Suppose that $|\alpha|=|\beta|=2$. Since $i_{2}+j_{1}>i_{1}+j_{1}>n$, $E_{1}$
and $E_{2}$ are disjoint. Moreover, the largest $n-i_{1}$ among the ends of
the edges in $E_{1}$ is less than the smallest $j_{1}$ among the ends of the
edges in $E_{2}$. Thus, if a cycle is contained in $G$, then it must be
contained in $G[E_{1}]$ or in $G[E_{2}]$. Since we have shown that $G[E_{1}]$
and $G[E_{2}]$ are disjoint unions of paths, the statement is valid. ∎

Now, it is interesting to find out which matrix in ${\mathcal{T}_{\leq
2}^{\star}}$ has a its row graph containing a cycle component. First of all,
we will claim that for any integers $4\leq m\leq n$ except a few cases, there
exists a Toeplitz matrix of order $n$ in ${\mathcal{T}_{\leq 2}^{\star}}$
whose row graph contains a cycle component of length $m$.

######  Lemma 3.4.

Let $T=T_{n}\langle i_{1},i_{2};j_{1},j_{2}\rangle$. If there exists integers
$1\leq k\leq\frac{n-1-i_{1}}{i_{2}-i_{1}}$ and
$1\leq\ell\leq\frac{n-1-j_{1}}{j_{2}-j_{1}}$ such that

$i_{1}+j_{1}=k(i_{2}-i_{1})+\ell(j_{2}-j_{1}),$

then the row graph of $T$ contains a cycle of length $k+\ell+1$.

###### Proof.

Let $s=i_{2}-i_{1}$ and $t=j_{2}-j_{1}$ and suppose that there exists integers
$1\leq k\leq\frac{n-1-i_{1}}{s}$ and $1\leq\ell\leq\frac{n-1-j_{1}}{t}$. Then
$i_{1}+ks\leq n-1$ and $j_{1}+\ell t\leq n-1$. By adding them, we have
$i_{1}+j_{1}+ks+\ell t\leq 2(n-1)$. From this and the equality
$i_{1}+j_{1}=ks+\ell t$, we obtain the inequality

$i_{1}+j_{1}=ks+\ell t\leq n-1,$ (14)

i.e. $1+ks\leq n-\ell t$. Therefore $\\{1+ks,2+ks,\ldots,n-\ell
t\\}\neq\emptyset$ and so $\\{1+ks-j_{1},2+ks-j_{1},\ldots,n-\ell
t-j_{1}\\}\neq\emptyset$. Since $i_{1}+ks\leq n-1$,

$(n-(i_{1}+j_{1}))-(1+ks-j_{1})=n-1-(i_{1}+ks)\geq 0$

and so $1+ks-j_{1}\leq n-(i_{1}+j_{1})$. Since $n-\ell t-j_{1}\geq 1$, there
is an integer $p\in\\{1,2,\ldots,n-(i_{1}+j_{1})\\}\cap\\{1+ks-j_{1},2+ks-
j_{1},\ldots,n-\ell t-j_{1}\\}$. Then

$1\leq p\leq n-(i_{1}+j_{1})$ (15)

and

$1+ks-j_{1}\leq p\leq n-\ell t-j_{1}$ (16)

Let $W=\\{p,p+t,\ldots,p+\ell t,p+\ell t+s,\ldots,p+\ell t+ks\\}$. Then, by
(14) and (15),

$1\leq p<p+t<\cdots<p+\ell t+s<\cdots<p+\ell t+ks=p+(i_{1}+j_{1})<n.$

Therefore $W\subset[n]$. Now, by (16),

$(p+qt)+j_{1}\leq p+\ell t+j_{1}\leq n$

for each $q\in[\ell]$. Thus $p+(q-1)t$ and $p+qt$ are adjacent for
$q\in[\ell]$ by Lemma 3.1(i). On the other hand, by (16),

$(p+\ell t+(q-1)s)-i_{1}\geq(1+ks-j_{1})+\ell t-i_{1}=1$

for each $q\in[k]$. Thus, by Lemma 3.1(ii), $p+\ell t+(q-1)s$ and $p+\ell
t+qs$ are adjacent for each $q\in[k]$. Finally, $(p+ks+\ell t)-p=i_{1}+j_{1}$,
so $p$ and $p+ks+\ell t$ are adjacent in ${\rm RG}(T)$ by the same lemma.
Hence the subgraph of ${\rm RG}(T)$ induced by $W$ is a cycle of length
$k+\ell+1$. ∎

######  Theorem 3.5.

For every integers $m$ and $n$ such that $4\leq m\leq n$ and
$(m,n)\notin\\{(4,4),(4,5),(6,8)\\}$, there exists a Toeplitz matrix of order
$n$ in ${\mathcal{T}_{\leq 2}}$ whose row graph contains a cycle component of
length $m$.

###### Proof.

For integers $m$ and $n$ with $4\leq m\leq n$ and
$(m,n)\notin\\{(4,4),(4,5),(6,8)\\}$, we let

$T=\begin{cases}T_{n}\langle n-m+1,n-m+2;m-2,n-1\rangle&\mbox{if $n<2m-4$;}\\\
T_{n}\langle 3,5;2m-8,2m-7\rangle&\mbox{if $n=2m-4$ and $m\geq 7$;}\\\
T_{6}\langle 1,4;3,5\rangle&\mbox{if $n=6$ and $m=5$;}\\\ T_{n}\langle
2,4;2m-6,2m-5\rangle&\mbox{if $n=2m-3$ and $m\geq 6$;}\\\ T_{7}\langle
1,5;4,6\rangle&\mbox{if $n=7$ and $m=5$;}\\\ T_{n}\langle
m-2,n-1;n-m+1,n-m+2\rangle&\mbox{if $n>2m-3$.}\end{cases}$

We first show that $T$ is well-defined in each case. From the hypothesis
$4\leq m\leq n$, it immediately follows that each of $n-m+1$, $n-m+2$, $m-2$,
and $n-1$ is a positive integer. In the case $n=2m-4$ and $n=2m-3$, $2m-8>0$
and $2m-6>0$ since $m\geq 7$ and $m\geq 6$, respectively.

In addition, $n-m+1<n-m+2<m-2<n-1$ if $n<2m-4$, and $m-2<n-m+1<n-m+2<n-1$ if
$n>2m-3$. It is easy to check that the four parameters for the cases $n=2m-4$
and $n=2m-3$ given above are distinct and arranged to fulfil the conditions
which we imposed on a Toeplitz matrix. Furthermore, by using Theorem 2.7, we
can easily check that $T$ in each case belongs to $\mathcal{T}_{\leq 2}$.

Now, we let $k=m-2$ and $\ell=1$ if $n<2m-3$; $k=m-5$ and $\ell=5$ if $n=2m-4$
and $m\geq 7$; $k=m-4$ and $\ell=4$ if $n=2m-3$ and $m\geq 6$; $k=1$ and
$\ell=m-2$ if $n>2m-3$. Then the integers $k$ and $\ell$ satisfy the
inequalities and the equality given in Lemma 3.4. Thus $T$ contains a cycle of
length $m$ for $4\leq m\leq n$ except
$(m,n)\in\\{(4,4),(4,5),(5,6),(5,7),(6,8)\\}$. We may check that $152631$ and
$162731$ are $5$-cycles in ${\rm RG}(T)$ for $(m,n)=(5,6)$ and $(m,n)=(5,7)$,
respectively. Since $T\in\mathcal{T}_{\leq 2}$, an $m$-cycle is a component of
${\rm RG}(T)$ by Corollary 2.5. ∎

Among the matrices in $\mathcal{T}_{\leq 2}$ is of the form $T_{n}\langle
i_{1},i_{2};j_{1}\rangle$ or $T_{n}\langle i_{1};j_{1},j_{2}\rangle$, we may
identify the matrices whose row graphs contain a cycle component. We need the
following lemmas.

######  Lemma 3.6.

Let $G$ be the graph of a symmetric Toeplitz matrix $ST_{n}\langle
u_{1},\ldots,u_{k}\rangle$ with $\gcd(u_{1},\ldots,u_{k})=d\geq 2$. In
addition, let $G_{i}$ be the subgraph of $G$ induced by the vertex set
$\\{v\in V(G)\mid v\equiv i\pmod{d}\\}$ for each integer $1\leq i\leq d$ and
$r$ be an integer such that $r\equiv n\pmod{d}$ and $1\leq r\leq d$. Then, for
each integer $1\leq i\leq d$, $G_{i}$ is isomorphic to the graph $H_{i}$ of a
symmetric Toeplitz matrix $T_{i}$ where

$\displaystyle T_{i}=\begin{cases}ST_{\lceil n/d\rceil}\langle
u_{1}/d,\ldots,u_{k}/d\rangle&\mbox{ if }1\leq i\leq r;\\\ ST_{\lceil
n/d\rceil-1}\langle u_{1}/d,\ldots,u_{k}/d\rangle&\mbox{ if }r+1\leq i\leq
d.\end{cases}$

In addition, there is no edge joining a vertex in $G_{i}$ and a vertex in
$G_{j}$ if $i\neq j$.

###### Proof.

Take two adjacent vertices $x$ and $y$ in $G$. Then the $(x,y)$-entry of a
symmetric Toeplitz matrix $ST_{n}\langle u_{1},\ldots,u_{k}\rangle$ is $1$, so
$|x-y|\in\\{u_{1},\ldots,u_{k}\\}$, Therefore $x\equiv y\pmod{d}$ by the
hypothesis. Thus there is no edge joining a vertex in $G_{i}$ and a vertex in
$G_{j}$ if $i\neq j$ by the definition of $G_{i}$. In addition, each of
$G_{1},\ldots,G_{r}$ has $\lceil n/d\rceil$ vertices and each of
$G_{r+1},\ldots,G_{d}$ has $\lceil n/d\rceil-1$ vertices. Take $i\in[r]$ and
define a map $\varphi_{i}:V(G_{i})\to V(H_{i})$ sending $i+d\ell$ to $i+\ell$
(each element in $V(G_{i})$ is in the form of $i+d\ell$ for an integer
$\ell$). Then it is obvious that $\varphi_{i}$ is a bijection. Now,

$x$ and $y$ are adjacent in $G_{i}$
---
$\Leftrightarrow$ $|x-y|\in\\{u_{1},\ldots,u_{k}\\}$
$\Leftrightarrow$
$\left|(x-y)/d\right|\in\left\\{u_{1}/d,\ldots,u_{k}/d\right\\}$
$\Leftrightarrow$
$|\varphi_{i}(x)-\varphi_{(}y)|\in\left\\{u_{1}/d,\ldots,u_{k}/d\right\\}$
$\Leftrightarrow$ $\varphi_{i}(x)$ and $\varphi_{i}(y)$ are adjacent in
$T_{\lceil n/d\rceil}\langle u_{1}/d,\ldots,u_{k}/d\rangle$.

Thus $G_{i}\cong H_{i}$. By a similar argument, we may show that $G_{i}\cong
H_{i}$ for $i\in\\{r+1,\ldots,d\\}$. ∎

######  Lemma 3.7.

Let $G$ be the graph of a symmetric Toeplitz matrix $ST_{n}\langle
u_{1},u_{2}\rangle$ and let $d=\gcd(u_{1},u_{2})\geq 2$. In addition, let
$G_{i}$ be the subgraph of $G$ induced by the vertex set $\\{v\in V(G)\mid
v\equiv i\pmod{d}\\}$ for each $i=1,2,\ldots,d$ and $r$ be an integer such
that $r\equiv n\pmod{d}$ and $1\leq r\leq d$. Suppose that $n\leq
u_{1}+u_{2}\leq d\lceil n/d\rceil$. Then $G_{i}$ is a cycle for each
$i=1,2,\ldots,r$.

###### Proof.

Fix $i\in[r]$. By Lemma 3.6, $G_{i}$ is the graph of $ST_{\lceil
n/d\rceil}\langle u_{1}/d,u_{2}/d\rangle$. By the hypothesis,

$\frac{n}{d}\leq\frac{u_{1}+u_{2}}{d}\leq\left\lceil\frac{n}{d}\right\rceil,$

so $(u_{1}+u_{2})/d=\lceil n/d\rceil$. Therefore, by Lemma 3.13, there is a
cycle $C_{i}$ of length $\lceil n/d\rceil$ in $G_{i}$. Thus $C_{i}$ is a
Hamilton cycle of $G_{i}$. Take any vertex $v$ in $G_{i}$. Then each neighbor
of $v$ belongs to $\\{v+u_{2},v+u_{1},v-u_{2},v-u_{1}\\}$. Since
$u_{2}+u_{1}\geq n$ and $(v+u_{2})-(v-u_{1})=u_{1}+u_{2}\geq n$, at most one
of $v+u_{2}$ and $v-u_{1}$ can be a vertex of $G$. For the same reason, at
most one of $v+u_{1}$ and $v-u_{2}$ can be a vertex of $G$. Thus the degree of
$v$ is at most two. Since $v$ was arbitrarily chosen, each vertex in $G_{i}$
has degree at most $2$. Therefore $C_{i}$ itself is $G_{i}$. ∎

######  Lemma 3.8.

Let $G$ be the graph of a symmetric Toeplitz matrix $ST_{n}\langle
u_{1},u_{2}\rangle$ where $\gcd(u_{1},u_{2})=1$. If $u_{1}+u_{2}>n$, then $G$
is acyclic.

###### Proof.

Suppose, to the contrary, that $u_{1}+u_{2}>n$ and $G$ contains a cycle
$v_{1}v_{2}\cdots v_{\ell}v_{1}$. Fix $i\in[\ell]$. Then
$|v_{i+1}-v_{i}|=u_{1}$ or $u_{2}$ (we identify $v_{\ell+1}$ and $v_{\ell+2}$
with $v_{1}$ and $v_{2}$, respectively). Suppose that $v_{i+1}-v_{i}=\pm
u_{1}$. If $v_{i+2}-v_{i+1}=\mp u_{1}$, then $v_{i+2}-v_{i}=0$, a
contradiction. If $v_{i+2}-v_{i+1}=\pm u_{2}$, then
$|v_{i+2}-v_{i}|=u_{1}+u_{2}>n$, a contradiction again. Thus, if
$v_{i+1}-v_{i}=\pm u_{1}$, then $v_{i+2}-v_{i+1}=\pm u_{1}$ or $\mp u_{2}$. By
a similar argument, we may show that if $v_{i+1}-v_{i}=\pm u_{2}$, then
$v_{i+2}-v_{i+1}=\mp u_{1}$ or $\pm u_{2}$. Therefore
$v_{i+1}-v_{i}\in\\{u_{1},-u_{2}\\}$ for each $i\in[\ell]$ or
$v_{i+1}-v_{i}\in\\{-u_{1},u_{2}\\}$ for each $i\in[\ell]$. We assume the
former. Let $n_{1}$ and $n_{2}$ be the numbers of $i$ with
$v_{i+1}-v_{i}=u_{1}$ and $v_{i+1}-v_{i}=-u_{2}$, respectively. Then
$n_{1}u_{1}+n_{2}(-u_{2})=0$, so $n_{1}u_{1}=n_{2}u_{2}$. Since
$\gcd(u_{1},u_{2})=1$, $n_{1}\geq u_{2}$ and $n_{2}\geq u_{1}$ and so
$n_{1}+n_{2}\geq u_{1}+u_{2}>n$ and we reach a contradiction. By a similar
argument, we should reach a contradiction even in the latter case. ∎

Now we are ready to characterize the matrices of the form $T_{n}\langle
i_{1},i_{2};j_{1}\rangle$ whose row graph contains a cycle.

######  Theorem 3.9.

Let $T=T_{n}\langle i_{1},i_{2};j_{1}\rangle$ be a Toeplitz matrix in
${\mathcal{T}}_{\leq 2}$, $d=\gcd(i_{1}+j_{1},i_{2}-i_{1})$, and $r$ be an
integer such that $1\leq r\leq d$ and $n\equiv r\pmod{d}$. Then the row graph
of $T$ contains a cycle if and only if $i_{2}\neq 2i_{1}+j_{1}$,
$i_{2}+j_{1}\leq d\lceil n/d\rceil$ and $1+i_{1}\leq r$. Especially, if the
row graph contains a cycle, then its length is $\lceil n/d\rceil$.

###### Proof.

Let $G={\rm RG}(T)$. Since $T$ belongs to ${\mathcal{T}}_{\leq 2}$ by the
hypothesis, $i_{2}+j_{1}\geq n$ by Theorem 2.7. Therefore $G$ is a spanning
subgraph of the graph $L$ of $ST_{n}\langle i_{1}+j_{1},i_{2}-i_{1}\rangle$ by
Proposition 3.11. Let $G_{i}$ denote the subgraph of $L$ induced by the vertex
set $\\{v\in V(G)\mid v\equiv i\pmod{d}\\}$ for each $i=1,\ldots,d$.

To show the ‘only if’ part, suppose that $G$ contains a cycle $C$. Then $L$
contains $C$. By Lemma 3.6, $C$ is contained in $G_{t}$ for some $t\in[d]$. By
the same lemma, $G_{t}$ is isomorphic to the graph of $ST_{\lceil
n/d\rceil}\langle(i_{1}+j_{1})/d,(i_{2}-i_{1})/d\rangle$ or $ST_{\lfloor
n/d\rfloor}\langle(i_{1}+j_{1})/d,(i_{2}-i_{1})/d\rangle$. Note that

$\left\lceil\frac{n}{d}\right\rceil-1<\frac{n}{d}\leq\frac{i_{2}+j_{1}}{d}=\frac{i_{1}+j_{1}}{d}+\frac{i_{2}-i_{1}}{d}.$

Therefore, if $G_{t}$ is isomorphic to the graph of $ST_{\left\lceil
n/d\right\rceil-1}\langle(i_{1}+j_{1})/d,(i_{2}-i_{1})/d\rangle$, then $G_{t}$
is acyclic by Lemma 3.8 and we reach a contradiction. Thus $G_{t}$ is
isomorphic to the graph of $ST_{\left\lceil
n/d\right\rceil}\langle(i_{1}+j_{1})/d,(i_{2}-i_{1})/d\rangle$. Hence
$t\in[r]$ by Lemma 3.6.

Suppose, to the contrary, that $i_{2}+j_{1}>d\lceil n/d\rceil$. Then

$\left\lceil\frac{n}{d}\right\rceil<\frac{i_{2}+j_{1}}{d}=\frac{i_{1}+j_{1}}{d}+\frac{i_{2}-i_{1}}{d}.$

Therefore, by Lemma 3.8, the graph of $ST_{\lceil
n/d\rceil}\langle(i_{1}+j_{1})/d,(i_{2}-i_{1})/d\rangle$ is acyclic and we
reach a contradiction. Thus $i_{2}+j_{1}\leq d\lceil n/d\rceil$. Then

$\frac{n}{d}\leq\frac{i_{2}+j_{1}}{d}\leq\left\lceil\frac{n}{d}\right\rceil,$

so $(i_{2}+j_{1})/d=\lceil n/d\rceil$. Thus, by Lemma 3.7, $G_{t}$ is a cycle.
Hence, $G_{t}=C$ and the length of $C$ is $(i_{2}+j_{1})/d$.

Since $G_{t}$ is a cycle, $t$ is adjacent to two vertices in $G_{t}$. Since
$G$ is the row graph of $T_{n}\langle i_{1},i_{2};j_{1}\rangle$,
$t+i_{2}-i_{1}$, $t+i_{1}+j_{1}$ and $t+i_{2}+j_{1}$ are only possible
neighbors of $t$. Since $i_{2}+j_{1}\geq n$, $t+i_{2}-i_{1}$ and
$t+i_{1}+j_{1}$ are the two neighbors of $t$. Now, if $1+i_{1}>r$, then $1\leq
i\leq r<1+i_{1}$ and so, by Lemma 3.1, $i$ and $i+i_{2}-i_{1}$ cannot be
adjacent in $G$. Thus $1+i_{1}\leq r$ and we have shown the ‘only if’ part.

To show the ‘if’ part, suppose $i_{2}+j_{1}\leq d\lceil n/d\rceil$ and
$1+i_{1}\leq r$. Let $H$ be the subgraph of $G$ induced by the vertex set
$\\{v\in V(G)\mid v\equiv i_{1}+1\pmod{d}\\}$. Since $1+i_{1}\leq r$, $H$ has
$\lceil n/d\rceil$ vertices and $1+i_{1}$ is the vertex with smallest
labeling. We show that $H=G_{i_{1}+1}$. By the definition,
$V(H)=V(G_{i_{1}+1})$. Since $G$ is a subgraph of $L$, $H$ is a subgraph of
$G_{i_{1}+1}$. Take two adjacent vertices $x$ and $y$ in $G_{i_{1}+1}$. Then
$|x-y|=i_{2}-i_{1}$ or $i_{1}+j_{1}$. If $|x-y|=i_{1}+j_{1}$, $x$ adn $y$ are
adjacent in $G$ and so in $H$. Suppose $|x-y|=i_{2}-i_{1}$. Without loss of
generality, we may assume $x-y=i_{2}-i_{1}$. Since $y\in V(H)$, $y\geq
1+i_{1}$. Thus $x$ and $y$ are adjacent in $G$ by Lemma 3.1 and so in $H$.
Therefore we have shown $H=G_{i_{1}+1}$. By Lemma 3.7, $G_{i_{1}+1}$ is a
cycle. Thus $H$ is also a cycle, which implies that $G$ has a cycle. ∎

Since the row graphs of $T_{n}\langle\alpha;\beta\rangle$ and
$T_{n}\langle\beta;\alpha\rangle$ are isomorphic, we may obtain the following
result as well.

######  Corollary 3.10.

Let $T=T_{n}\langle i_{1};j_{1},j_{2}\rangle$ be a Toeplitz matrix in
${\mathcal{T}}_{\leq 2}$, $d=\gcd(i_{1}+j_{1},j_{2}-j_{1})$, and $r$ be an
integer such that $1\leq r\leq d$ and $n\equiv r\pmod{d}$. Then the row graph
of $T$ contains a cycle if and only if $j_{2}\neq i_{1}+2j_{1}$,
$i_{1}+j_{2}\leq d\lceil n/d\rceil$ and $1+j_{1}\leq r$. Especially, if the
row graph contains a cycle, then its length is $\lceil n/d\rceil$.

In the next subsection, we focus on the Toeplitz matrices in
${\mathcal{T}}_{\leq 2}^{\star}$ whose row graphs consist of only cycle
components. We denote the set of such matrices by ${\mathcal{T}}_{\leq
2}^{\circ}$.

###  3.2 Toeplitz matrices in ${\mathcal{T}}_{\leq 2}^{\circ}$

We first give a sufficient condition for a Toeplitz matrix belonging to
${\mathcal{T}}_{\leq 2}^{\circ}$. Before doing so, we need to deduce several
results.

Recall that ${\mathcal{C}}(T)$ denotes the adjacency matrix of ${\rm RG}(T)$
for a Toeplitz matrix $T$ and $ST_{n}\langle\gamma\rangle$ means a symmetric
Toeplitz matrix $T_{n}\langle\gamma,\gamma\rangle$. If ${\mathcal{C}}(T)$ is a
Toeplitz matrix for a Toeplitz matrix $T$ of order $n$, then
${\mathcal{C}}(T)=ST_{n}\langle\gamma\rangle$ for some $\gamma\subset[n-1]$
since ${\mathcal{C}}(T)$ is symmetric.

For $\alpha=\\{i_{1},\ldots,i_{k_{1}}\\}$ and
$\beta=\\{j_{1},\ldots,j_{k_{2}}\\}$ where $k_{1},k_{2}\geq 2$, define the
following sets based upon Lemma 3.1:

$\displaystyle\gamma_{1}$ $\displaystyle=\\{i_{t}-i_{s}\in[n-1]\mid 1\leq
s<t\leq k_{1}\\};$ $\displaystyle\gamma_{2}$
$\displaystyle=\\{j_{t}-j_{s}\in[n-1]\mid 1\leq s<t\leq k_{2}\\};$ (17)
$\displaystyle\gamma_{3}$ $\displaystyle=\\{i_{s}+j_{t}\in[n-1]\mid 1\leq
s\leq k_{1},1\leq t\leq k_{2}\\}.$

where $\gamma_{1}=\emptyset$ (resp. $\gamma_{2}=\emptyset$) if $k_{1}\leq 1$
(resp. $k_{2}\leq 1$) and $\gamma_{3}=\emptyset$ if $\alpha=\emptyset$ or
$\beta=\emptyset$.

For convenience, we let

$\gamma(\alpha,\beta)=\gamma_{1}\cup\gamma_{2}\cup\gamma_{3}.$

We denote by $A\leq B$ for matrices $A=[a_{ij}]$ and $B=[b_{ij}]$ of order $n$
such that $a_{ij}\leq b_{ij}$ for all $i,j\in[n]$. The following result
immediately follows from Lemma 3.1.

######  Proposition 3.11.

For $T=T_{n}\langle\alpha;\beta\rangle$, the row graph of $T$ is a spanning
subgraph of the graph of $ST_{n}\langle\gamma(\alpha,\beta)\rangle$, i.e.
${\mathcal{C}}(T)\leq ST_{n}\langle\gamma(\alpha,\beta)\rangle$.

######  Proposition 3.12.

Let $T=T_{n}\langle i_{1},i_{2};j_{1},j_{2}\rangle$ be a Toeplitz matrix with
$i_{1}+j_{2}=i_{2}+j_{1}=n$ and $2(i_{1}+j_{1})\neq n$. Then the row graph of
$T$ is the graph of $ST_{n}\langle i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$ and
consists of only cycle components.

###### Proof.

Since $i_{1}+j_{2}=i_{2}+j_{1}=n$, ${\mathcal{C}}(T)\leq ST_{n}\langle
i_{2}-i_{1},j_{2}-j_{1},i_{1}+j_{1}\rangle$ by (3.2) and Proposition 3.11. By
the hypothesis, $j_{2}-j_{1}=i_{2}-i_{1}=n-(i_{1}+j_{1})$, so $ST_{n}\langle
i_{2}-i_{1},j_{2}-j_{1},i_{1}+j_{1}\rangle=ST_{n}\langle
i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$. To show ${\mathcal{C}}(T)=ST_{n}\langle
i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$, take an entry $1$ of $ST_{n}\langle
i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$. Let $(v,w)$ be the address of the entry.
By symmetry, we may assume $v<w$. Then $w-v=i_{1}+j_{1}$ or
$w-v=n-(i_{1}+j_{1})$ by the definition of Toeplitz matrix.

If $w-v=i_{1}+j_{1}$, then the $(v,w)$-entry of ${\mathcal{C}}(T)$ is $1$ by
Lemma 3.1(iii). Now suppose $w-v=n-(i_{1}+j_{1})$.

Case 1. $w\leq n-j_{1}$. Then $j_{1}\leq n-w$. In addition,
$v=w-(n-j_{1})+i_{1}\leq i_{1}=n-j_{2}$, so $j_{2}\leq n-v$. Since
$w-v=n-(i_{1}+j_{1})=j_{2}-j_{1}$, the $(v,w)$-entry of ${\mathcal{C}}(T)$ is
$1$ by Lemma 3.1(i).

Case 2. $w>n-j_{1}$. Then $w>i_{2}$ and $v=w-(n-j_{1})+i_{1}>i_{1}$. Since
$w-v=n-(i_{1}+j_{1})=i_{2}-i_{1}$, the $(v,w)$-entry is $1$ by Lemma 3.1(ii).

In both cases, we have shown that ${\mathcal{C}}(T)=ST_{n}\langle
i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$. It is known that the number of $1$’s in a
symmetric Toeplitz matrix $ST_{n}\langle u_{1},\ldots,u_{k}\rangle$ is
$2(kn-\sum_{i=1}^{k}u_{i})$. Thus $ST_{n}\langle
i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$ has exactly $2n$ entries of $1$ and so
${\mathcal{C}}(T)$ has $2n$ entries of $1$, which implies that each row sum is
exactly $2$. Hence ${\mathcal{C}}(T)$ consists of only cycle components. ∎

######  Lemma 3.13 ([1]).

Let $G$ be the graph of a symmetric Toeplitz matrix $ST_{n}\langle
u_{1},u_{2}\rangle$ with $n\geq u_{1}+u_{2}$. Then $G$ contains a cycle of
length $(u_{1}+u_{2})/\gcd(u_{1},u_{2})$.

In the previous section, we showed that a cycle of length at least $5$ is a
Toeplitz-row graph. Now we identify the Toeplitz matrices each of whose row
graph is a cycle.

######  Theorem 3.14.

The row graph of a Toeplitz matrix $T$ is a cycle if and only if
$T=T_{n}\langle i_{1},i_{2};j_{1},j_{2}\rangle$ with
$i_{1}+j_{2}=i_{2}+j_{1}=n$ and $\gcd(n,i_{1}+j_{1})=1$.

###### Proof.

To show the ‘if’ part, let $T=T_{n}\langle i_{1},i_{2};j_{1},j_{2}\rangle$
with $i_{1}+j_{2}=i_{2}+j_{1}=n$ and $\gcd(n,i_{1}+j_{1})=1$. We denote the
row graph of $T$ by $G$. By Proposition 3.12, $G$ consists of cycle
components. Since $\gcd(n,i_{1}+j_{1})=1$, $n-(i_{1}+j_{1})\neq i_{1}+j_{1}$.
Therefore, by Lemma 3.13, $G$ contains a cycle of length $n$. Thus $G$ itself
is a cycle of length $n$.

To show the ‘only if’ part, suppose that the row graph $G$ of a Toeplitz
matrix $T\langle\alpha,\beta\rangle$ is a cycle of length $n$. By Proposition
2.13, $n\geq 5$. By Corollary 2.4, the maximum row sum of $T$ is at most $2$.
Suppose that $|\alpha|=1$. Then the vertex $n$ is adjacent to only
$n-i_{1}-j_{1}$ by the hypothesis that $i_{1}+j_{2}=n$ and Lemma 3.1(i) and
(iii). Thus $n$ has degree on in $G$. By a similar argument, one can show that
$1$ is adjacent to only $1+i_{1}+j_{1}$ if $|\beta|=1$. In both cases, we have
reached a contradiction. Thus $|\alpha|=|\beta|=2$. By Lemma 3.1, $G$ has at
most

$(n-j_{2})+(n-i_{2})+(n-j_{1}-i_{1})=3n-(i_{1}+j_{2})-(i_{2}+j_{1})$

edges. Since $G$ is a cycle of length $n$,

$3n-(i_{1}+j_{2})-(i_{2}+j_{1})\geq n.$

On the other hand, since the row sum of $T$ is at most $2$, $i_{1}+j_{2}\geq
n$ and $i_{2}+j_{1}\geq n$ by Theorem 2.7. Therefore
$i_{1}+j_{2}=i_{2}+j_{1}=n$. Thus, if $w$ and $x$ are adjacent in $G$, then
$|w-x|\in\\{i_{2}-i_{1},j_{2}-j_{1},i_{1}+j_{1}\\}$ by Lemma 3.1. Now let
$d=\gcd(n,i_{1}+j_{1})$. Since $i_{2}-i_{1}=j_{2}-j_{1}=n-(i_{1}+j_{1})$, $d$
is a common divisor of $i_{2}-i_{1}$, $j_{2}-j_{1}$, and $i_{1}+j_{1}$.
Therefore, if $w$ and $x$ are adjacent in $G$, then $w\equiv x\pmod{d}$. If
$d>1$, then $1\not\equiv 2\pmod{d}$ and $G$ has at least two components, which
is impossible. Thus $d=\gcd(n,i_{1}+j_{1})=1$. ∎

By Theorem 2.10, any triangle-free Toeplitz-row graph cannot have cycles of
three different lengths. Yet, we have not found a triangle-free Toeplitz-row
graph with cycles of two distinct lengths. The following theorem finds ones
whose row graphs consist of cycles of the same length among such Toeplitz
matrices, which extends Theorem 3.14.

######  Theorem 3.15.

Let $T=T_{n}\langle i_{1},i_{2};j_{1},j_{2}\rangle$ be a Toeplitz matrix with
$i_{1}+j_{2}=i_{2}+j_{1}=n$ and $2(i_{1}+j_{1})\neq n$. Then the row graph of
$T$ is a disjoint union of exactly $d$ cycles of length $n/d$ where
$d=\gcd(n,i_{1}+j_{1})$.

###### Proof.

Let $G$ be the row graph of $T$. By Proposition 3.12, $G$ is the graph of
$ST_{n}\langle i_{1}+j_{1},n-(i_{1}+j_{1})\rangle$ and consists of only cycle
components. Let $V_{i}=\\{i,i+d,\ldots,i+(n/d-1)d\\}$ for each $i\in[d]$.
Then, by Lemma 3.6, the subgraph $G_{i}$ of $G$ induced by $V_{i}$ is
isomorphic to the graph of
$ST_{n/d}\langle(i_{1}+j_{1})/d,(n-i_{1}-j_{1})/d\rangle$ and there is no edge
joining a vertex in $G_{i}$ and a vertex in $G_{j}$ if $i\neq j$. By Theorem
3.14, $ST_{n/d}\langle(i_{1}+j_{1})/d,(n-i_{1}-j_{1})/d\rangle$ is a cycle of
length $n/d$ and this completes the proof. ∎

## References

  * [1] G.-S. Cheon, J.-H. Jung, B. Kang, S.-R. Kim, and S. A. Mojallal,  Subgraph characterizations of Toeplitz graphs,  Under review.
  * [2] J. Choi, K. S. Kim, S.-R. Kim, J. Y. Lee, and Y. Sano,  On the competition graphs of $d$-partial orders,  Discrete Appl. Math., 204:29–37, 2016.
  * [3] J. E. Cohen,  Interval graphs and food webs: a finding and a problem, RAND Corporation Document, 17696-PR. Rand. Corp, Santa Monica, CA, 1968.
  * [4] K. A. S. Factor and S. K. Merz,  The $(1,2)$-step competition graph of a tournament,  Discrete Appl. Math., 159(2):100–103, 2011.
  * [5] K.F. Fraughnaugh, J.R. Lundgren, J.S. Maybee, S.K. Merz, and N.J. Pullman,  Competition graphs of strongly connected and hamiltonian digraphs,  SIAM J. Discrete Math., 8:179–185, 1995.
  * [6] I. Gohberg (ed.),  Toeplitz centennial, Birkhäuser, Boston, 1982.
  * [7] Harvey J Greenberg, J Richard Lundgren, and John S Maybee,  Inverting graphs of rectangular matrices,  Discrete Appl. Math., 8(3):255–265, 1984.
  * [8] D. Guichard,  Competition graphs of hamiltonian digraphs,  SIAM J. Discrete Math, 11:128–134, 1998.
  * [9] K. A. S. Hefner, K. F. Jones, S.-R. Kim, J. R. Lundgren, and F. S. Roberts,  $(i,j)$ competition graphs,  Discrete Appl. Math., 32:241–262, 1991.
  * [10] G. Heinig and K. Rost,  Algebraic methods for Toeplitz-like matrices and operators, Birkhäuser, Boston, 1984.
  * [11] I. S. Iohvidov,  Hankel and Toeplitz matrices and forms algebraic theory, Birkhäuser, Boston, 1982.
  * [12] J.-H. Jung, S.-R. Kim, B. Kang, and G.-S. Cheon,  Exponents of primitive directed Toeplitz graphs,  Lin. Multilin. alg. (in press).
  * [13] S.-R. Kim, J.Y. Lee, B. Park, W.J. Park, and Y. Sano,  The niche graphs of doubly partial orders,  Congr. Numer., 195:19–32, 2009.
  * [14] S.-R. Kim, J.Y. Lee, B. Park, and Y. Sano,  The competition hypergraphs of doubly partial orders,  Discrete Appl. Math., 165:185–191, 2014.
  * [15] S.-R. Kim, J.Y. Lee, B. Park, and Y. Sano,  The competition graphs of oriented complete bipartite graphs,  Discrete Appl. Math., 201:182–190, 2016.
  * [16] S.-R. Kim and F.S. Roberts,  Competition graphs of semiorders and the conditions ${\mathcal{C}}(p)$ and $c^{*}(p)$,  Ars Combinatoria., 63:161–173, 2002.
  * [17] J. Kuhl,  Transversals and competition numbers of complete multipartite graphs,  Discrete Appl. Math., 161(3):435–440, 2013.
  * [18] L. Langley, J.R. Lundgren, and S.K. Merz,  The competition graphs of interval digraphs,  Congr. Numer., 107:37–40, 1995.
  * [19] B.-J. Li and G. J. Chang,  Competition numbers of complete $r$-partite graphs,  Discrete Appl. Math., 160(15):2271–2276, 2012.
  * [20] J.R. Lundgren,  Food webs, competition graphs, competition-common enemy graphs, and niche graphs, in f.s. roberts (ed.),  Appl. Comb. Graph Theory in Bio. Soc. Sci., 17:221–243, 1989.
  * [21] J.R. Lundgren, J.S. Maybee, and C.W. Rasmussen,  Interval competition graphs of symmetric digraphs,  Discrete Math., 119:113–122, 1993.
  * [22] J.R. Lundgren and C.W. Rasmussen,  Two-step graphs of trees,  Discrete Math., 119:123–140, 1993.
  * [23] S. Malik and T. Zamfirescu,  Hamiltonian connectedness in directed Toeplitz graphs,  Bull. Math. Soc. Sci. Math. Roum., 53(2):145–156, 2010.
  * [24] B. Park, J.Y. Lee, and S.-R. Kim,  The $m$-step competition graphs of doubly partial orders,  Appl. Math. Lett., 24:811–816, 2011.
  * [25] B. Park and Y. Sano,  The phylogeny graphs of doubly partial orders,  Discuss. Math. Graph Theory, 33:657–664, 2013.
  * [26] A. Raychaudhuri and F.S. Roberts,  Generalized competition graphs and their applications, in p. brücker and r. pauly (eds.),  Methods of Operations Research, 49:295–311, 1985.
  * [27] R. C. Brigham and R. D. Dutton,  A characterization of competition graphs,  Discrete Appl. Math., 6:315–317, 1983.
  * [28] F. S. Roberts and J. E. Steif,  A characterization of competition graphs of arbitrary digraphs,  Discrete Appl. Math., 6:323–326, 1983.
  * [29] X. Zhang and R. Li,  The $(1,2)$-step competition graph of a pure local tournament that is not round decomposable,  Discrete Appl. Math., 205:180–190, 2016.


* visiting researcher at Rhode Island Hospital, Department of Diagnostic Imaging.
Code Available at Github: https://github.com/shruti-jadon/Brain-Lesions-
Segmentation

# A Comparative Study of 2D Image Segmentation Algorithms for Traumatic Brain
Lesions Using CT Data from the ProTECTIII Multicenter Clinical Trial

Shruti Jadon M.S  Owen P. Leary Sc.B  Warren Alpert Medical School of Brown
University, Diagnostic Imaging,Providence RI 02903  Warren Alpert Medical
School of Brown University, Neurosurgery,Providence RI 02903  Ian Pan M.S
Warren Alpert Medical School of Brown University, Diagnostic
Imaging,Providence RI 02903  Tyler J. Harder M.S  Warren Alpert Medical School
of Brown University, Diagnostic Imaging,Providence RI 02903  David W. Wright
MD  Emory University School of Medicine, Department of Emergency Medicine,
Atlanta GA 30322.  Lisa H. Merck M.D. M.P.H  Warren Alpert Medical School of
Brown University, Diagnostic Imaging,Providence RI 02903  Warren Alpert
Medical School of Brown University, Neurosurgery,Providence RI 02903  Warren
Alpert Medical School of Brown University, Emergency Medicine, Providence RI
02903  University of Florida School of Medicine, Department of Emergency
Medicine, Gainesville FL 32611.  Derek L. Merck Ph.D  Warren Alpert Medical
School of Brown University, Diagnostic Imaging,Providence RI 02903  University
of Florida School of Medicine, Department of Emergency Medicine, Gainesville
FL 32611.  Brown University Department of Engineering, Providence RI 02906.

###### Abstract

Automated segmentation of medical imaging is of broad interest to clinicians
and machine learning researchers alike. The goal of segmentation is to
increase efficiency and simplicity of visualization and quantification of
regions of interest within a medical image. Image segmentation is a difficult
task because of multiparametric heterogeneity within the images, an obstacle
that has proven especially challenging in efforts to automate the segmentation
of brain lesions from non-contrast head computed tomography (CT). In this
research, we have experimented with multiple available deep learning
architectures to segment different phenotypes of hemorrhagic lesions found
after moderate to severe traumatic brain injury (TBI). These include:
intraparenchymal hemorrhage (IPH), subdural hematoma (SDH), epidural hematoma
(EDH), and traumatic contusions. We were able to achieve an optimal Dice
Coefficient[1] score of 0.94 using UNet++ 2D Architecture with Focal Tversky
Loss Function, an increase from 0.85 using UNet 2D with Binary Cross-Entropy
Loss Function in intraparenchymal hemorrhage (IPH) cases. Furthermore, using
the same setting, we were able to achieve the Dice Coefficient score of 0.90
and 0.86 in cases of Extra-Axial bleeds and Traumatic contusions,
respectively.

###### keywords:

Automated segmentation; traumatic brain injury; non-contrast head computed
tomography; ProTECTIII; methods comparison

##  1 Background

Traumatic brain injury (TBI)[1] [2] is a leading cause of morbidity and
mortality [3] in children and young adults in the United States [4]. TBI is
also a major concern for elderly individuals, with high rates of mortality and
hospitalization due to falls among people aged 75 and older. Depending on the
severity of injury[5], TBI can have a lasting impact on quality of life for
survivors of all ages. Long-term deficits may include impairments of
cognition, decision making, concentration, memory, movement, or sensation
(vision or hearing), as well as emotional problems (personality changes,
impulsivity, anxiety, and depression)[6] and epilepsy [4].Annually, TBI
injuries cost an estimated $76 billion in direct and indirect medical expenses
in the US[4]. The long-term effects of TBI vary depending on patient
demographics and availability of prompt medical care at a trauma center, among
other factors.
While rapid diagnosis and treatment of TBI is directly related to patient
outcomes, attempts to automate identification[7], classification, and
segmentation[8] [9] of traumatic brain lesions on non-contrast head computed
tomography (CT), the gold standard for emergent imaging diagnosis of TBI, have
been met with limited success. Open research on machine learning resources for
TBI has been constrained by few large public patient imaging datasets, as well
as the emphasis of corporate developers on proprietary algorithms to be
incorporated into for-profit software packages. Despite such limitations, a
few studies have attempted classification and/or detection of TBI on CT and
magnetic resonance (MR) imaging, including concussion classification[10] using
implicit features of the entire voxel-wise white matter fiber strains and
detection of brain lesions[10].One group using Convolutional Neural Networks
(CNNs) and Scale-Invariant Feature Transform (SIFT , edge detection
algorithm)[11] on 409 CT scans was able to achieve 92.55% detection accuracy
[8]. Other groups have attempted prediction of mortality rate after traumatic
brain injury using logistic regression-based models[11], probability-based
models (Naïve Bayes)[12], Support Vector Machine, and Artificial Neural
Network (ANN). Maximum accuracies achieved included 81-84% accuracy using
regression, and 84% using ANN[12]. So far, less work has been done in
automated volumetric segmentation[13], mainly due to lack of large annotated
datasets. A group[14] using inception-based convolutional neural network on
dataset of 18 patients and were able to achieve dice score of 0.75, and others
working on MR FLAIR[8],[9] stroke lesion segmentation using a customized MRF
(markov random fields) method and U-Net model respectively, and were able to
achieve median Dice Coefficient of 0.79.
Application and comparison of available algorithms for rapid segmentation of
traumatic lesions is important for translating more accessible, fully
automated[15] diagnostic tools[16], [17],[18] to the clinic. Automated
segmentation (AS) can be used to increase efficiency and precision of
pathology visualization and quantification on non-contrast head CT. However,
intra-image and intra-lesion heterogeneity across multiple feature parameters,
such as variable Hounsfield unit ranges and irregular lesion boundaries, can
pose technical challenges to the automatic segmentation of traumatic brain
lesions[10][13]. In this work, we applied and compared previously published
deep learning architectures (e.g. SegNet, DenseNet, U-Net, etc) for semantic
segmentation of different classes of traumatic brain lesions, including
solitary intraparenchymal hemorrhage (IPH), subdural hematoma (SDH), epidural
hematoma (EDH), and multifocal hemorrhagic contusions. Semantic segmentation
is a method for assigning a class label to each pixel in a two-dimensional
(2D) image, and thereby producing 2D lesion segmentations on each slice
positive for pathology of interest. Models were tested using a large CT
imaging dataset collected during the ProTECTIII multicenter clinical trial[19]
of intravenous progesterone vs. placebo for moderate to severe TBI, as well as
associated ground truth slice-by-slice volumetric annotations of lesions of
interest. Models were compared in terms of Dice Coefficient[1] (DC),
Sensitivity[20], and specificity[20].

##  2 Method

In this work, we selected open source algorithms previously applied for three-
dimensional (3D)[21] and 2D segmentation of traumatic brain lesions[10] on
NCCT on the basis of their documented performance on existing databases (such
as the COCO dataset[22]) for semantic segmentation. Our dataset (refer to
section 2.1) was grouped according to index lesion phenotype, including
solitary intraparenchymal hemorrhage (IPH), multifocal hemorrhagic contusion,
and subdural / epidural hematoma (SDH & EDH, grouped together as “extra-axial
bleeds”). Algorithms were applied separately to data in each lesion phenotype
category. Algorithms were compared across bleed phenotypes in terms of dice
coefficient[1], sensitivity[20], and specificity[20] in two phases. First, 2D
and 3D segmentation algorithms were compared in terms of accuracy, with 2D
algorithms tested across single slice data points and 3D algorithms tested
across single case data points. Based on preliminary data from both groups of
algorithms suggesting poorer performance of 3D methods, only 2D methods were
then compared against each other in terms of the same parameters. Apart from
segmentation modeling variation, we also experimented with various objective
functions for sparse segmentation. The project code has been made available
for validation and replication of these experiments and can be found at
https://github.com/shruti-jadon/Brain-Lesions-Segmentation.

###  2.1 Imaging Dataset & Pre-Processing

881 patients with clinical impression of moderate-severe TBI were enrolled in
the ProTECTIII clinical trial (NCT00822900) between 2010 and 2014 and
underwent baseline head CT imaging to identify intracranial[23] pathology.
Imaging was carried out across 22 trauma centers in the United States
according to site-specific CT imaging protocols [24]. After collection of all
imaging, a central neuroradiologist screened and identified all baseline CTs
with the largest lesion classified as one of four pre-specified bleed
phenotypes of interest (SDH, EDH, multifocal hemorrhagic contusion, or
solitary IPH). Overall, 516 baseline CT scans of unique study participants,
each with approximately 100 slices, were selected for analysis. All imaging
data were anonymized and stored in a central imaging repository. Local IRB
approval was obtained for the project at the institution were imaging analyses
were performed.
Trained research associates annotated all 516 head CTs in standardized fashion
using 3D Slicer (Version 4, Brigham & Women’s Hospital, 2012) to trace the
boundary of the largest identified qualifying lesion (i.e. one of the pre-
specified bleed phenotypes) to produce one volumetric annotation per case. In
17 of the 516 cases, two lesions were segmented, yielding a total of 533
unique lesions. The resultant ground-truth dataset included 43 IPH
annotations, 48 EDH annotations, 212 SDH annotations, and 230 hemorrhagic
contusion annotations. From these data, individual 2D slices of each patient’s
baseline non-contrast head CT scan were considered as individual instances for
algorithmic experiments. After data segregation, we also applied image
preprocessing and normalization technique using nilearn library[25].

---
Figure 1:  Sample TBI case from the ProTECTIII dataset[19] demonstrating NCCT
with bone windowing and level (a) and outline of ground truth temporal lobe
intraparenchymal hemorrhage annotation (b).

###  2.2 Segmentation Algorithms

Medical image segmentation is one of the most challenging tasks in computer
vision. For an approach to be successful, it should employ methods capable of
covering all the outlying cases (e.g. those with sparse segmentation).
Traumatic brain lesion segmentation is particularly challenging due to the
small number of image features which are ubiquitously present across
individual cases and diverse bleed phenotypes. Unsurprisingly, experiments
with existing UNet-3D[26] models met limited success in our preliminary
analysis, likely due to the relatively small data set (i.e. 533 data points)
for discerning over 1.3 million parameters amidst significant inter-case
feature heterogeneity. Higher capacity models capable of segregating skull
from brain, and data sets including more case examples of each lesion
phenotype across various brain locations, are probably necessary to improve 3D
segmentation performance[27]. On the other hand, the 2D segmentation model
leverages a greater number of data points from the same dataset[28]; we have
approximately 100 slices per CT scan, comprising a total of approximately
58000 input data points. Based on preliminary results, our analytic comparison
focused on 2D segmentation models. In particular, we explored multiple
algorithms across two categories of machine learning 2D modeling techniques:

  * •

Image Segmentation models (U-Net 2d; Inception based UNet++ 2D model)

  * •

Objective Functions (Binary Cross-Entropy[29]; Dice Loss[30]; Focal Loss;
Focal Tversky Loss).

---
Figure 2:  Sample UNet2D[31] and UNet++ 2D [32] layer architecture

UNet[31] is a convolutional neural network model designed for biomedical image
segmentation. The architecture contains two parts: an encoder
(compression)[33] consisting of a stack of convolutional and max pooling
layers used to capture the context of the image, and a decoder (expansion)
which enables precise localization using transposed convolutions. UNet is
therefore is a fully convolutional network (FCN), i.e. it only contains
convolutional layers. UNet++ 2D model differs from standard UNet2D[31] in that
it’s type of layers’ and architecture. UNet++ 2D combines initial layer
features with all preceding layers, making it inception based across whole
network, this leads to a densely connected encoder-decoder architecture. This
helps the model to keep the context of input data across all layers, and
thereby helps converging model faster.

###  2.3 Objective Functions

Objective functions are also known as a “loss functions,” and also play a
crucial role in determining the success of a model. Objective functions map
required information from data into space where we can measure cost and
attempt to reduce it using some optimization algorithm such as stochastic
gradient descent[34]. There are various forms of objective functions that can
be used for semantic segmentation. The four used in this paper are summarized
subsequently.

####  2.3.1 Binary Cross-Entropy (BCE)

Cross-Entropy is a method to map information of data into categorical
distribution. As name suggests, Binary Cross-Entropy[29] means 2 class
categorical distribution.

$\displaystyle CrossEntropy(p,\hat{p})$
$\displaystyle=-(p*log(\hat{p})+(1-p)log(1-\hat{p}))$

####  2.3.2 Dice Loss

The Dice Coefficient[1] is similar to the Jaccard Index (Intersection over
Union, IoU), where TP are the true positives, FP false positives and FN false
negatives. The Dice Coefficient[1] can also be defined as a loss function:

$\displaystyle DiceLoss(p,\hat{p})$
$\displaystyle=1-\frac{2p\hat{p}}{p+\hat{p}+1}$

####  2.3.3 Focal Loss

Focal Loss[35] (FL) attempts to down-weight the contribution of easy examples
so that the CNN focuses more on hard examples. Focal Loss[35] can be defined
as follows:

$FocalLoss(p,\hat{p})=-(\alpha(1-\hat{p})^{\gamma}plog(\hat{p})+(1-\alpha)\hat{p}^{\gamma}(1-p)log(1-\hat{p}))$

####  2.3.4 Focal Tversky Loss

Tversky index (TI) is a generalization of Dice’s coefficient. TI adds a weight
to FP (false positives) and FN (false negatives), which is just the regular
Dice Coefficient[1]. Similarly, to Dice Loss[30], the Tversky Loss function
can be defined as follows:

$TI(p,\hat{p})=\frac{p\hat{p}}{p\hat{p}+(1-\beta)p(1-\hat{p})+\beta\hat{p}(1-p)}$
and Focal tversky $FTL=\sum(1-TI_{c})^{\frac{1}{\gamma}}$ where $\gamma$
varies in the range [1, 3]

###  2.4 Evaluation Metrics

One of the most challenging aspects of machine learning for healthcare
applications is measurement of accuracy, especially when it comes to clinical
acceptability of false positive and negative rates. There are various metrics
to measure the performance of a model ranging from accuracy to Jaccard
distance. For this work, we have chosen the following metrics as measure to
compare segmentation[36] approaches:

####  2.4.1 Dice Coefficient

The Dice Coefficient[1] also called the overlap index, is the most used metric
in validating medical volume segmentations. In addition to the direct
comparison between automatic and ground truth segmentations, it is common to
use the DICE to measure reproducibility (repeatability). [2] used the DICE as
a measure of the reproducibility as a statistical validation of manual
annotation where segmenters repeatedly annotated the same MRI image, then the
pairwise overlap of the repeated segmentations is calculated using the DICE,
which is defined by

$\displaystyle DiceCoefficient(DC)$
$\displaystyle=\frac{2TP}{2TP+FP+FN}=\frac{2|X,Y|}{|X|+|Y|}$

####  2.4.2 Sensitivity

True Positive Rate (TPR), also called Sensitivity[20] and Recall, measures the
portion of positive voxels in the ground truth that are also identified as
positive by the segmentation being evaluated.

$\displaystyle Sensitivity(TPR)$ $\displaystyle=\frac{TP}{TP+FN}$

####  2.4.3 Specificity

True Negative Rate (TNR), also called specificity[20], measures the portion of
negative voxels (background) in the ground truth segmentation that are also
identified as negative by the segmentation being evaluated.

$\displaystyle Specificity(TNR)$ $\displaystyle=\frac{TN}{TN+FP}$

---
Figure 3:  Selected slices from a ProtectIII MRI dataset with lesions (Left)
and corresponding mask (Center) and lesion segmentation (Right) using UNet++
2D segmentation model with Focal Tversky Loss objective function.)

##  3 Results

3D segmentation algorithms selected for testing included only 3D-Unet. 2D
segmentation algorithms tested included two image segmentation models (U-Net
2d; UNet++ 2D model) and three objective functions (Binary Cross-Entropy; Dice
Loss; Focal Loss; Focal Tversky Loss). Preliminary data comparing 3D-Unet to
2D-UNet found that due to lack of data and need to train high capacity model
of 1.3 million parameters, 3D models were underfitting. Attempts to increase
the number of iterations led to overfitting, with an average validation Dice
Coefficient of 0.37. These preliminary results suggested inferior performance
of 3D relative to 2D algorithms on this dataset. 2D segmentation algorithms
were then compared in detail. In IPH cases, using a total sample of 2700 CT
scan 2D slices over 200 epochs, we were able to achieve an optimized Dice
Coefficient score of 0.94(refer table 1) using UNet++ 2D Architecture with
Focal Tversky Loss Function, an increase from 0.85 using UNet2D with Binary
Cross-Entropy Loss Function. Similarly, we have observed an increase in Dice
Coefficient score in hemorrhagic contusion from 0.79 to 0.90(refer table 2) by
using 13000 2D images, and in case of extra-axial bleeds (SDH & EDH) from 0.71
to 0.85(refer table 3) using 15000 images.

Table 1: The Dice scores, Sensitivity and Specificity for the 2 lesion segmentation methods (UNet 2D, UNet++ 2D) using 4 objective functions (Binary Cross Entropy, Dice Loss, Focal Loss, Focal Tversky Loss) on Intraparenchymal Hemorrhage (IPH) Data Architecture | Objective Function | Dice Coefficient | Sensitivity | Specificity
---|---|---|---|---
UNet 2D | Binary Cross Entropy | 0.8485 | 0.8315 | 0.9996
UNet 2D | Focal Loss | 0.8022 | 0.8385 | 0.9996
UNet 2D | Dice Loss | 0.7945 | 0.7240 | 0.9994
UNet 2D | Focal Tversky Loss | 0.8667 | 0.8661 | 0.9994
UNet++ 2D | Binary Cross Entropy | 0.8784 | 0.8571 | 0.9996
UNet++ 2D | Focal Loss | 0.8776 | 0.9257 | 0.9999
UNet++ 2D | Dice Loss | 0.8377 | 0.8051 | 0.9995
UNet++ 2D | Focal Tversky Loss | 0.9424 | 0.9449 | 0.9998
Table 2: The Dice scores, Sensitivity and Specificity for the 2 lesion segmentation methods (UNet 2D, UNet++ 2D) using 4 objective functions (Binary Cross Entropy, Dice Loss, Focal Loss, Focal Tversky Loss) on Hemorrhagic Contusions Data Architecture | Objective Function | Dice Coefficient | Sensitivity | Specificity
---|---|---|---|---
UNet 2D | Binary Cross Entropy | 0.7894 | 0.7860 | 0.9996
UNet 2D | Focal Loss | 0.5833 | 0.6458 | 0.9998
UNet 2D | Dice Loss | 0.8480 | 0.8486 | 0.9996
UNet 2D | Focal Tversky Loss | 0.8413 | 0.8880 | 0.9994
UNet++ 2D | Binary Cross Entropy | 0.7979 | 0.8109 | 0.9996
UNet++ 2D | Focal Loss | 0.8458 | 0.8438 | 0.9996
UNet++ 2D | Dice Loss | 0.8402 | 0.8331 | 0.9996
UNet++ 2D | Focal Tversky Loss | 0.9015 | 0.9430 | 0.9996
Table 3: The Dice scores, Sensitivity and Specificity for the 2 lesion segmentation methods (UNet 2D, UNet++ 2D) using 4 objective functions (Binary Cross Entropy, Dice Loss, Focal Loss, Focal Tversky Loss) on Extra-Axial bleeds (SDH and EDH) Data Architecture | Objective Function | Dice Coefficient | Sensitivity | Specificity
---|---|---|---|---
UNet 2D | Binary Cross Entropy | 0.7128 | 0.7351 | 0.9994
UNet 2D | Focal Loss | 0.4818 | 0.6847 | 0.9998
UNet 2D | Dice Loss | 0.6879 | 0.6553 | 0.9991
UNet 2D | Focal Tversky Loss | 0.7438 | 0.7983 | 0.9986
UNet++ 2D | Binary Cross Entropy | 0.7276 | 0.7125 | 0.9989
UNet++ 2D | Focal Loss | 0.6966 | 0.7736 | 0.9998
UNet++ 2D | Dice Loss | 0.7252 | 0.7269 | 0.9989
UNet++ 2D | Focal Tversky Loss | 0.8578 | 0.8524 | 0.9998

###  3.1 Implications, Limitations, and Future Directions

Automated traumatic brain injury detection and segmentation has the potential
to assist physicians in faster and more accurate decision-making. As
demonstrated in this work, with only 516 CT scans, we were able to extract
40,000 2D slices and train a 2D segmentation model with very high dice
coefficient relative to those previously reported. 2D segmentation accuracy
could likely be further improved with even larger datasets that similarly
leverage multi-institutional patient cohorts and higher capacity models. In
this work, we trained our models with 800,000 parameters, as our dataset
consisted of 40,000 examples. In the past, the deep learning community has met
success in developing segmentation models with the help of large amounts of
data (for example, the Coco Dataset consists of 330,000 data points).
Establishing similarly large datasets in medical image analysis will be
necessary to continue to drive success in automated CT segmentation. Multi-
model approaches to training a single model capable of detecting and
segmenting all forms of brain lesions should also be assessed using large,
heterogeneous datasets.

##  4 Conclusion and Future Directions

In this paper, we have explored well known 2D segmentation architectures of
UNet 2D and UNet++ 2D, along with experiments with different objective
functions. Our results suggest that UNet++ 2D works better than normal UNet
2D, suggesting the importance of combination of initial layer’s extracted
features with final layer’s features. Among tested loss functions, Focal
Tversky loss[37] worked best for single-lesion segmentation, likely reflecting
the relatively small proportion of each slice by area occupied by lesion
annotation. Since annotation masks are relatively small, the algorithms which
assign more weight to the annotations relative to other features perform
better by 0.10 dice coefficient. Compared to previous reports which have
applied algorithmic approaches to automated 2D segmentation of traumatic brain
lesion, we report an improvement in Dice Coefficient[1] by approximately 0.08
for IPH and extra-axial hematomas.

## References

  * [1] Zou, K., Warfield, S., Bharatha, A., Tempany, C., Kaus, M., Haker, S., Wells, W., Jolesz, F., and Kikinis, R., “Statistical validation of image segmentation quality based on a spatial overlap index,” Academic radiology 11, 178–89 (02 2004).
  * [2] Taha, A. A. and Hanbury, A., “Metrics for evaluating 3d medical image segmentation: Analysis, selection, and tool,” BMC Medical Imaging 15 (08 2015).
  * [3] Taylor, C., Bell, J., Breiding, M., and Xu, L., “Traumatic brain injury–related emergency department visits, hospitalizations, and deaths — united states, 2007 and 2013,” MMWR. Surveillance Summaries 66, 1–16 (03 2017).
  * [4] “Traumatic brain injury at american association of neurological surgeons.”
  * [5] Chong, S.-L., Liu, N., Barbier, S., and Ong, M. E. H., “Predictive modeling in pediatric traumatic brain injury using machine learning,” in [BMC Medical Research Methodology ], (2015).
  * [6] Tepas, J. J., Leaphart, C. L., Pieper, P., Beaulieu, C. L., Spierre, L. R., Tuten, J. D., and Celso, B. G., “The effect of delay in rehabilitation on outcome of severe traumatic brain injury,” Journal of Pediatric Surgery 44, 368–372 (Feb. 2009).
  * [7] Vedaldi, A. and Lenc, K., “Matconvnet - convolutional neural networks for matlab,” (2014).
  * [8] Subbanna, N. K., Rajashekar, D., Cheng, B., Thomalla, G., Fiehler, J., Arbel, T., and Forkert, N. D., “Stroke lesion segmentation in flair mri datasets using customized markov random fields,” Frontiers in Neurology 10, 541 (2019).
  * [9] Duong, M., Rudie, J., Wang, J., Xie, L., Mohan, S., Gee, J., and Rauschecker, A., “Convolutional neural network for automated flair lesion segmentation on clinical brain mr imaging,” American Journal of Neuroradiology 40 (07 2019).
  * [10] Mitra, J., Shen, K., Ghose, S., Bourgeat, P., Fripp, J., Salvado, O., Pannek, K., Taylor, D. J., Mathias, J. L., and Rose, S. E., “Statistical machine learning to identify traumatic brain injury (tbi) from structural disconnections of white matter networks,” NeuroImage 129, 247–259 (2016).
  * [11] Keshavamurthy, K. N., Leary, O. P., Merck, L. H., Kimia, B., Collins, S., Wright, D. W., Allen, J. W., Brock, J. F., and Merck, D., “Machine learning algorithm for automatic detection of CT-identifiable hyperdense lesions associated with traumatic brain injury,” in [procspie ], Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 10134, 101342G (Mar 2017).
  * [12] Rau, C.-S., Kuo, P.-J., Chien, P.-C., Huang, C.-Y., Hsieh, H.-Y., and Hsieh, C.-H., “Mortality prediction in patients with isolated moderate and severe traumatic brain injury using machine learning models,” PLoS ONE 13, e0207192 (Nov 2018).
  * [13] Juang, L.-H. and Wu, M.-N., “Mri brain lesion image detection based on color-converted k-means clustering segmentation,” (2010).
  * [14] Roy, S., Butman, J. A., Chan, L., and Pham, D. L., “TBI Contusion Segmentation from MRI using Convolutional Neural Networks,” arXiv e-prints , arXiv:1807.10839 (Jul 2018).
  * [15] Phan, A.-C., Vo, V.-Q., and Phan, T.-C., “Automatic detection and classification of brain hemorrhages,” in [ACIIDS ], (2018).
  * [16] Roy, S., Nag, S., Bandyopadhyay, S. K., Bhattacharyya, D., and Kim, T., “Automated brain hemorrhage lesion segmentation and classification from mr image using an innovative composite method,” (2015).
  * [17] Fedorov, A., Beichel, R. R., Kalpathy-Cramer, J., Finet, J., Fillion-Robin, J.-C., Pujol, S., Bauer, C., Jennings, D., Fennessy, F., Sonka, M., Buatti, J. M., Aylward, S. R., Miller, J. V., Pieper, S., and Kikinis, R., “3d slicer as an image computing platform for the quantitative imaging network.,” Magnetic resonance imaging 30 9, 1323–41 (2012).
  * [18] Gillebert, C. R., Humphreys, G. W., and Mantini, D., “Automated delineation of stroke lesions using brain CT images,” NeuroImage: Clinical 4, 540–548 (2014).
  * [19] Denninghoff, K. R., Nuño, T., Pauls, Q., Yeatts, S. D., Silbergleit, R., Palesch, Y. Y., Merck, L. H., Manley, G. T., and Wright, D. W., “Prehospital intubation is associated with favorable outcomes and lower mortality in protect iii,” Prehospital Emergency Care 21(5), 539–544 (2017).  PMID: 28489506.
  * [20] Parikh, R., Mathai, A., Parikh, S., Sekhar, G. C., and Thomas, R., “Understanding and using sensitivity, specificity and predictive values,” Indian Journal of Ophthalmology 56(1), 45 (2008).
  * [21] Kamnitsas, K., Ledig, C., Newcombe, V. F. J., Simpson, J. P., Kane, A. D., Menon, D. K., Rueckert, D., and Glocker, B., “Efficient multi-scale 3d cnn with fully connected crf for accurate brain lesion segmentation,” Medical image analysis 36, 61–78 (2017).
  * [22] Lin, T.-Y., Maire, M., Belongie, S. J., Hays, J., Perona, P., Ramanan, D., Dollár, P., and Zitnick, C. L., “Microsoft coco: Common objects in context,” in [ECCV ], (2014).
  * [23] Chen, W., Cockrell, C., Ward, K., and Najarian, K., “Intracranial pressure level prediction in traumatic brain injury by extracting features from multiple sources and using machine learning methods,” 2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM) , 510–515 (2010).
  * [24] Wright, D. W., Yeatts, S. D., Silbergleit, R., Palesch, Y., Hertzberg, V. S., Frankel, M., Goldstein, F. C., Caveney, A. F., Howlett-Smith, H., Bengelink, E. M., Manley, G. T., Merck, L. H., Janis, L. S., and Barsan, W. G., “Very early administration of progesterone for acute traumatic brain injury.,” The New England journal of medicine 371 26, 2457–66 (2014).
  * [25] Abraham, A., Pedregosa, F., Eickenberg, M., Gervais, P., Mueller, A., Kossaifi, J., Gramfort, A., Thirion, B., and Varoquaux, G., “Machine learning for neuroimaging with scikit-learn,” CoRR abs/1412.3919 (2014).
  * [26] Çiçek, Ö., Abdulkadir, A., Lienkamp, S. S., Brox, T., and Ronneberger, O., “3d u-net: Learning dense volumetric segmentation from sparse annotation,” in [MICCAI ], (2016).
  * [27] Jadon, S. and Srinivasan, A., “Improving siamese networks for one shot learning using kernel based activation functions,” ArXiv abs/1910.09798 (2019).
  * [28] JADON, S., “Hands-on one-shot learning with python: A practical guide to implementing fast and… accurate deep learning models with fewer training,” (2019).
  * [29] Zhang, Z. and Sabuncu, M. R., “Generalized cross entropy loss for training deep neural networks with noisy labels,” in [NeurIPS ], (2018).
  * [30] Sudre, C. H., Li, W., Vercauteren, T., Ourselin, S., and Cardoso, M. J., “Generalised dice overlap as a deep learning loss function for highly unbalanced segmentations,” in [DLMIA/ML-CDS@MICCAI ], (2017).
  * [31] Ronneberger, O., Fischer, P., and Brox, T., “U-net: Convolutional networks for biomedical image segmentation,” ArXiv abs/1505.04597 (2015).
  * [32] Zhou, Z., Siddiquee, M. M. R., Tajbakhsh, N., and Liang, J., “Unet++: A nested u-net architecture for medical image segmentation,” ArXiv abs/1807.10165 (2018).
  * [33] Jadon, S., “Introduction to different activation functions for deep learning,” Medium, Augmenting Humanity 16 (2018).
  * [34] Ruder, S., “An overview of gradient descent optimization algorithms,” ArXiv abs/1609.04747 (2016).
  * [35] Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, P., “Focal loss for dense object detection,” (2017).
  * [36] Havaei, M., Davy, A., Warde-Farley, D., Biard, A., Courville, A. C., Bengio, Y., Pal, C. J., Jodoin, P.-M., and Larochelle, H., “Brain tumor segmentation with deep neural networks,” Medical image analysis 35, 18–31 (2017).
  * [37] Abraham, N. and Khan, N. M., “A novel focal tversky loss function with improved attention u-net for lesion segmentation,” 2019 IEEE 16th International Symposium on Biomedical Imaging (ISBI 2019) , 683–687 (2018).
  * [38] Gabr, R., Coronado, I., Robinson, M., Sujit, S., Datta, S., Sun, X., Allen, W., Lublin, F., Wolinsky, J., and Narayana, P., “Brain and lesion segmentation in multiple sclerosis using fully convolutional neural networks: A large-scale study,” Multiple Sclerosis Journal , 135245851985684 (06 2019).
  * [39] Chan, T., “Computer aided detection of small acute intracranial hemorrhage on computer tomography of brain,” Computerized medical imaging and graphics : the official journal of the Computerized Medical Imaging Society 31 4-5, 285–98 (2007).
  * [40] Kharrat, A., Ben messaoud, M., Benamrane, N., and Abid, M., “Detection of brain tumor in medical images,” (01 2009).
  * [41] Denninghoff, K. R., Nuño, T., Pauls, Q., Yeatts, S. D., Silbergleit, R., Palesch, Y. Y., Merck, L. H., Manley, G. T., and Wright, D. W., “Prehospital intubation is associated with favorable outcomes and lower mortality in ProTECT III,” Prehospital Emergency Care 21, 539–544 (May 2017).