# Explicit Information-Debt-Optimal Streaming Codes With Small Memory

Anonymous Authors  Please do NOT provide authors’ names and affiliations
in the paper submitted for review, but keep this placeholder.
ISIT23 follows a double-blind reviewing policy.  M. Nikhil Krishnan1, Myna
Vajha2, Vinayak Ramkumar3, P. Vijay Kumar4
The work of M. Nikhil Krishnan is supported by a faculty seed grant from the
Indian Institute of Technology Palakkad and the DST-INSPIRE faculty
fellowship. The work of P. Vijay Kumar is supported by the “Next Generation
Wireless Research and Standardization on 5G and Beyond” project funded by
MeITY and the SERB Grant No. CRG/2021/008479. 1Department of Electrical
Engineering, IIT Palakkad
2Qualcomm, Bengaluru
3 Department of Electrical Engineering–Systems, Tel Aviv University
4Department of Electrical Communication Engineering, IISc Bangalore
{nikhilkrishnan.m, mynaramana, vinram93<EMAIL_ADDRESS>
###### Abstract

For a convolutional code in the presence of a symbol erasure channel, the
information debt $I(t)$ at time $t$ provides a measure of the number of
additional code symbols required to recover all message symbols up to time
$t$. Information-debt-optimal streaming ($i$DOS) codes are convolutional codes
which allow for the recovery of all message symbols up to $t$ whenever $I(t)$
turns zero under the following conditions; (i) information debt can be non-
zero for at most $\tau$ consecutive time slots and (ii) information debt never
increases beyond a particular threshold. The existence of periodically-time-
varying $i$DOS codes are known for all parameters. In this paper, we address
the problem of constructing explicit, time-invariant $i$DOS codes. We present
an explicit time-invariant construction of $i$DOS codes for the unit memory
($m=1$) case. It is also shown that a construction method for convolutional
codes due to Almeida et al. leads to explicit time-invariant $i$DOS codes for
all parameters. However, this general construction requires a larger field
size than the first construction for the $m=1$ case.

##  I Introduction

Streaming codes are convolutional codes that ensure decoding within a worst-
case delay. In the streaming code literature [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14], packet-erasure channel models are often considered. In
contrast, we focus on codes over a more general symbol-erasure channel model
in this work. Let $(n,k,m)$ be the parameters of a convolutional code, where
$k$ is the number of message symbols per time slot, $n>k$ is the number of
code symbols per time slot, and $m$ is the memory. The information debt is a
measure of the number of additional coded symbols needed to decode the message
symbols encoded thus far. This notion was first introduced by Martinian in
[15]. The error probability of random linear streaming codes in the large
field size regime over i.i.d. symbol erasure channels is characterized in [16]
using an information-debt-based argument.

Consider symbol erasure patterns such that information debt stays positive for
no more than $\tau$ consecutive time slots. If the code is capable of
recovering message symbols whenever information debt drops to zero, then
$\tau$ can be thought of as a worst-case decoding delay. It is argued in [17]
that if information debt goes above $mk$ in any time slot, then it is not
possible to recover all message symbols. With these in mind, the authors of
[17] defined $(n,k,m,\tau)$ $i$DOS codes as an $(n,k,m)$ convolutional code
that is capable of decoding all previously unknown messages in any time slot
where information debt becomes zero provided the symbol erasure pattern is
such that i) information debt does not stay positive for more than $\tau$
successive time slots and ii) information debt never crosses $mk$.

For $\tau\leq m$, the existence of periodically-time-varying $(n,k,m,\tau)$
$i$DOS codes over a sufficiently large field follows from the results in [15].
In [17], this result is extended to all valid parameters over
$\mathbb{F}_{q}$, with $q>(\tau+1){n(\tau+1)\choose k(\tau+1)}.$ These
existence results are based on Combinatorial Nullstellensatz [18] and hence
provide no insights that will lead to an explicit construction. The connection
of $i$DOS codes with two well-known classes of (time-invariant) convolutional
codes, namely $m$-MDS codes [19] and maximum distance profile (MDP) codes
[20], is established in [17]. For $\tau\leq m$, $m$-MDS codes are shown to be
$i$DOS codes, and for $\tau\leq m+\lceil\frac{mk}{n-k}\rceil$, MDP codes are
shown to be $i$DOS codes. For parameters $\\{n,k=1,m=1,\tau\\}$, a special
case of the MDP code in [21] is shown to yield an explicit construction of
$i$DOS codes over a field of size $O(n)$. Apart from the results mentioned
above, the paper [17] does not provide explicit $i$DOS codes for $m<\tau$.
Small memory is advantageous in scenarios where low complexity encoders are
required, such as in sensor networks. Furthermore, having a larger $\tau$ for
a given $m$ implies recoverability from a larger set of erasure patterns. The
question of whether time-invariant $i$DOS codes always exist for $m\ll\tau$ is
also unanswered in [17].

### Our Contributions

  * •

As the primary result, we provide an explicit, time-invariant construction of
$i$DOS codes over $\mathbb{F}_{2^{d}}$ with unit memory $(m=1)$, for all valid
$\\{n,k,\tau\\}$, where $d>(n-1)k^{2}(\tau+1)$.

  * •

We also show that an explicit, time-invariant construction of $i$DOS codes for
all possible $\\{n,k,m,\tau\\}$ follows from a convolutional code construction
method due to Almeida et al. [22]. This construction is over a finite field of
size $2^{d}$, where $d=O(2^{{\tiny}mn+k}(\tau+1)k)$. Notably, for the unit
memory case, the former construction requires a smaller field size.

##### Organization of the Paper

In Section II, we first define $i$DOS codes. Then, we present some definitions
and known results that are needed for the later sections. Our unit memory
construction is presented in Section III. In Section IV, we present the
general construction.

##### Notation

We use $\mathbb{N}$ to denote $\\{1,2,3,\dots\\}$. If $r<s$, we will interpret
the sum $\sum_{i=s}^{r}x_{i}$ as being equal to $0$. For integers $x,y$, we
define the set of integers $[x:y]=\\{i\mid x\leq i\leq y\\}$. Furthermore, we
use the notation $[x]$ to denote $[1:x]$. We use $\mathbb{F}_{q}$ to denote
the finite field consisting of $q$ elements, where $q$ is a prime power. For
an $x\times y$ matrix $A$ and $\mathcal{S}\subseteq[x]$, let
$A(\mathcal{S},:)$ denote the submatrix obtained by restricting $A$ to the
rows in $\mathcal{S}$. Similarly, for $\mathcal{T}\subseteq[y]$, we use
$A(:,\mathcal{T})$ to denote the submatrix obtained by restricting $A$ to the
columns in $\mathcal{T}$. Moreover, $A(\mathcal{S},\mathcal{T})$ denotes the
$|\mathcal{S}|\times|\mathcal{T}|$ submatrix obtained by restricting
$A(\mathcal{S},:)$ to the columns in $\mathcal{T}$. We use $A(i,j)$ to denote
the element in row-$i$ and column-$j$ of $A$. Let $M$ denote an $x\times y$
matrix whose entries are drawn from $\\{-\infty,0\\}\cup\mathbb{N}$. If
$\alpha\in\mathbb{F}_{q}$, then $\alpha^{M}$ denotes an $x\times y$ matrix
over $\mathbb{F}_{q}$ whose entries are given by $\\{\alpha^{M(i,j)}\mid 1\leq
i\leq x,1\leq j\leq y\\}$. Here, we set $\alpha^{-\infty}\triangleq 0$. We use
$\deg(f(x))$ to denote the degree of a polynomial $f(x)$. For integer $x\geq
1$, let $S_{x}$ denote the symmetric group consisting of all permutations of
the set $[x]$. Let $\mathcal{S}\subseteq[x]$ and $\sigma\in S_{x}$. We define
$\sigma(\mathcal{S})\triangleq\\{\sigma(i)\mid i\in\mathcal{S}\\}$.

##  II Preliminaries

The first three subsections of this section focus on providing background on
the $i$DOS code setting, for which we follow the notation from [17]. The
latter part of the section introduces some definitions and results that are
needed for the proofs of explicit constructions.

###  II-A Convolutional Codes

An $(n,k,m)$ convolutional code over $\mathbb{F}_{q}$ can be described as
follows. The encoder gets $k$ message symbols and outputs $n>k$ coded symbols
in each time slot $t\in\mathbb{N}$. These message symbols are denoted by
$\underline{s}(t)=[s_{1}(t)\dots s_{k}(t)]^{T}\in\mathbb{F}_{q}^{k}$ and the
code symbols are given by $\underline{c}(t)=[c_{1}(t)\dots
c_{n}(t)]^{T}\in\mathbb{F}_{q}^{n}.$ The memory of the encoder is $m$. There
is an $n\times(m+1)k$ matrix over $\mathbb{F}_{q}$, denoted by $G_{t}$, such
that

$\displaystyle\underline{c}(t)=G_{t}\begin{bmatrix}\underline{s}(t-m)\\\
\underline{s}(t-m+1)\\\ \dots\\\ \underline{s}(t)\end{bmatrix}.$

For all $t\leq 0$, we set $\underline{s}(t)=\underline{0}$. The convolutional
code is said to be time-invariant if $G_{t}$ is the same for all
$t\in\mathbb{N}$. Let $G=[G^{(m)}~{}G^{(m-1)}~{}\dots~{}G^{(0)}],$ where each
$G^{(i)}$ is an $n\times k$ matrix over $\mathbb{F}_{q}$. The current paper
focuses only on time-invariant constructions, and hence we set $G_{t}=G$ for
all $t\in\mathbb{N}$. By abuse of notation, we will refer to $G$ as the
generator matrix. The $n$ symbols belonging to $\underline{c}(t)$ are sent to
the receiver in time slot $t$. We describe symbol erasure patterns using sets
$\mathcal{R}_{t}\subseteq[n]$ such that the receiver receives $\\{c_{j}(t)\mid
j\in\mathcal{R}_{t}\\}$ in time slot $t$ and $\\{c_{j}(t)\mid
j\in[n]\setminus\mathcal{R}_{t}\\}$ are erased by the channel. The number of
non-erased code symbols in time slot $t$ is denoted by
$n_{t}=|\mathcal{R}_{t}|$.

###  II-B Information Debt

Information debt, introduced by Martinian [15], is a measure of the extra code
symbols needed at the decoder to decode all unknown message symbols. The
information debt at time slot $0$ is set as zero. The information debt at any
time slot $t\in\mathbb{N}$ is given by
$I(t)=\max\\{k-n_{t}+I(t-1),0\\}~{}\text{for all}~{}t\in\mathbb{N}.$ Let
$\theta_{0}=0$. For any symbol erasure pattern, one can identify time slots
$\\{\theta_{i}\\}_{i=1}^{\infty}$ such that

$\theta_{i+1}=\inf\\{t>\theta_{i}\mid I(t)=0\\}.$

###  II-C $i$DOS Codes

The goal of $i$DOS codes is to recover messages whenever information debt
drops to zero. It is shown in [17] that if $I(t)>mk$ for any time slot $t$,
then there exists no $(n,k,m)$ convolutional code capable of decoding all the
message symbols. To ensure a worst-case decoding delay of $\tau$ whenever
recovery is possible, it is required that $\theta_{i+1}-\theta_{i}\leq\tau+1$,
for all $i$. With this background, $i$DOS codes can be formally defined as
follows.

######  Definition 1 ([17]).

A symbol erasure pattern is said to be $(n,k,m,\tau)$-acceptable if $I(t)\leq
mk$ for all $t\in\mathbb{N}$, and $\theta_{i+1}-\theta_{i}\leq\tau+1$ for all
$i\in\mathbb{N}\cup\\{0\\}$. An $(n,k,m,\tau)$ $i$DOS code is an $(n,k,m)$
convolutional code which is such that for all $i\in\mathbb{N}\cup\\{0\\}$,
$\\{\underline{s}(t)\mid t\in[\theta_{i}+1:\theta_{i+1}]\\}$ are recoverable
at time $\theta_{i+1}$ over every $(n,k,m,\tau)$-acceptable symbol erasure
pattern.

The requirement that the messages need to be recovered whenever information
debt drops to zero, is intuitively related to the non-singularity of certain
matrices obtained from the generator matrix. In the rest of this section, we
will identify a sufficient property to be possessed by an $x\times x$ matrix
$M$ so that $\alpha^{M}$ is non-singular. This idea forms the core of our
unit-memory construction.

###  II-D Dominant Permutation

######  Definition 2 (Dominant Permutation of a Matrix).

Consider an $x\times x$ matrix $M$ composed of elements drawn from
$\\{-\infty,0\\}\cup\mathbb{N}$. The permutation $\sigma^{*}\in S_{x}$ (if
exists) is referred to as the dominant permutation if the following is true:

$\sum_{i=1}^{x}{M({\sigma^{*}(i),i})}>\sum_{i=1}^{x}{M({\sigma(i),i})},\forall\sigma\in
S_{x}\setminus\\{\sigma^{*}\\}.$

Furthermore, if such a $\sigma^{*}$ exists, we refer to the sum
$\sum_{i=1}^{x}{M({\sigma^{*}(i),i})}$ as the dominant sum of $M$. We make the
following simple observation.

######  Remark 1.

Assume that for the matrix $M$, we have $M({i,j})=-\infty$. If $\sigma\in
S_{x}$ is such that $\sigma(j)=i$, clearly, $\sigma$ cannot be a dominant
permutation of $M$.

######  Definition 3 (Dominant Submatrix).

Consider an $x\times y$ matrix $M$ composed of elements from
$\\{-\infty,0\\}\cup\mathbb{N}$, where $y\leq x$. A $y\times y$ submatrix
$\tilde{M}$ of $M$ (if exists) is referred to as the dominant submatrix of
$M$, if the following two conditions hold; (i) $\tilde{M}$ possesses a
dominant permutation, (ii) among all the $y\times y$ submatrices which possess
a dominant permutation, $\tilde{M}$ yields the single largest dominant sum –
i.e., dominant sums (if exist) of all other submatrices are strictly smaller.

We make the following straightforward observation which relates dominant
submatrices and the existence of dominant permutation.

######  Remark 2 (Submatrix Decomposition Strategy).

Consider an $x\times x$ matrix $M$ composed of elements from
$\\{-\infty,0\\}\cup\mathbb{N}$. Let $\mathcal{A}_{1},\ldots,\mathcal{A}_{l}$
denote a partition of the columns $[x]$ of $M$. Assume that for each
$\mathcal{A}_{i}$, the submatrix $M(:,\mathcal{A}_{i})$ possesses a dominant
submatrix ${M}_{\mathcal{A}_{i}}$. Let ${M}_{\mathcal{A}_{i}}$ be occupying
the rows $\mathcal{B}_{i}\subseteq[x]$ and let $s_{i}$ denote the dominant sum
of ${M}_{\mathcal{A}_{i}}$. If the rows
$\mathcal{B}_{1},\ldots,\mathcal{B}_{l}$ do not intersect (i.e., they form a
partition of $[x]$), it follows that $M$ possesses a dominant permutation.
Moreover, the dominant sum of $M$ is given by $\sum_{i=1}^{l}s_{i}$. We will
refer to this simple strategy of showing the existence of the dominant
permutation for a larger matrix by leveraging the existence of smaller
dominant submatrices whose rows do not intersect, as the submatrix
decomposition strategy.

Figure 1: In this figure, we illustrate how the submatrix decomposition
strategy can be utilized to show that the given matrix $M$ possesses a
dominant permutation. We choose:
$\mathcal{A}_{1}=\\{1,2\\},\mathcal{A}_{2}=\\{3,4\\}$. The dominant
submatrices associated with $M(:,\mathcal{A}_{1})$ and $M(:,\mathcal{A}_{2})$
are demarcated using red and blue rectangles, respectively. As the rows of
these submatrices do not intersect, it follows that $M$ possesses a dominant
permutation.

For the matrix illustrated in Fig. 1, the dominant permutation is given by
$\sigma^{*}=(1,2,4,3)$ and the corresponding dominant sum is $16$. In the
following example, we discuss a slight variation of the submatrix
decomposition strategy by making use of the observation made in Remark 1.

######  Example 1.

Consider the matrix $M$ illustrated in Fig. 2. Let $\mathcal{A}_{1}=\\{1,2\\}$
and $\mathcal{A}_{2}=\\{3,4\\}$. We highlight the corresponding dominant
submatrices using green and blue rectangles, respectively. As the rows of
these submatrices intersect, we cannot employ the naive submatrix
decomposition strategy. However, from Remark 1, it can be inferred that as
$M({1,3})=M({1,4})=-\infty$, if there is a dominant permutation $\sigma^{*}$,
it should be that $1\notin\sigma^{*}(\mathcal{A}_{2})$. In other words,
$1\in\sigma^{*}(\mathcal{A}_{1})$. Essentially, the implication here is that
$\sigma^{*}$ should “pass through” row $1$, when restricted to the columns in
$\mathcal{A}_{1}$. As a result, while searching for the dominant submatrix of
$M(:,\mathcal{A}_{1})$, we will consider only those submatrices which involve
row $1$. Given this constraint, it can be identified that the submatrix
demarcated using the red dashed rectangle is the (constrained) dominant
submatrix. Since the rows of the constrained dominant submatrix and the
dominant submatrix (indicated in blue) are not intersecting, it follows that
the matrix $M$ possesses a dominant permutation. We will utilize this idea of
constrained dominant submatrices later in our proofs.

Figure 2: For the given matrix $M$, the dominant permutation is
$\sigma^{*}=(2,1,3,4)$. We argue the existence of the dominant permutation in
Example 1 using a variant of the submatrix decomposition strategy.

The following lemma motivates our ongoing discussion on matrices that possess
dominant permutations. We attribute this lemma to an earlier work by Almeida
et al. [22], which explores similar ideas. The proof of this lemma is deferred
to Appendix -C.

######  Lemma 1.

Consider an $x\times x$ matrix $M$ with elements drawn from
$\\{-\infty,0\\}\cup\mathbb{N}$. Assume $M$ possesses the dominant permutation
$\sigma^{*}$ and the dominant sum $s_{\sigma^{*}}$. Let $\alpha$ be a
primitive element of $\mathbb{F}_{p^{d}}$, where $d>s_{\sigma^{*}}$. Then,
$\alpha^{M}$ is non-singular.

##  III Construction A: Explicit, Unit Memory Construction

In this section, we present an explicit construction of $i$DOS codes with unit
memory (i.e., $m=1$), for all parameters $\\{n,k,\tau\\}$. Without loss of
generality, we will henceforth take the characteristic of the underlying
finite field for our constructions to be two, i.e., $p=2$. To highlight the
key ideas, we first discuss an example for parameters $\\{n=4,k=2,\tau=2\\}$
in Sec. III-A. The general construction for any $\\{n,k,\tau\\}$ is described
in Sec. III-B.

###  III-A Example: $\\{n=4,k=2,m=1,\tau=2\\}$

Let $\alpha$ be a primitive element of $\mathbb{F}_{2^{d}}$. For now, we will
assume $d$ to be sufficiently large and later in the section we will
explicitly specify a value for $d$. We set $G^{(0)}\triangleq\alpha^{M^{(0)}}$
and $G^{(1)}\triangleq\alpha^{M^{(1)}}$, where:

$M^{(0)}\triangleq\begin{bmatrix}\color[rgb]{1,0,0}\color[rgb]{1,0,0}{0}&\color[rgb]{1,0,0}{0}\\\
\color[rgb]{1,0,0}{1}&\color[rgb]{1,0,0}{2}\\\
\color[rgb]{1,0,0}{2}&\color[rgb]{1,0,0}{4}\\\
\color[rgb]{1,0,0}{3}&\color[rgb]{1,0,0}{6}\end{bmatrix},~{}~{}M^{(1)}\triangleq\begin{bmatrix}\color[rgb]{0,0,1}{6}&\color[rgb]{0,0,1}{3}\\\
\color[rgb]{0,0,1}{4}&\color[rgb]{0,0,1}{2}\\\
\color[rgb]{0,0,1}{2}&\color[rgb]{0,0,1}{1}\\\
\color[rgb]{0,0,1}{0}&\color[rgb]{0,0,1}{0}\end{bmatrix}.$

Recall the definitions of $\mathcal{R}_{t}$, $\\{\theta_{i}\\}$ presented in
Sections II-A and II-B, respectively. Let
$\theta_{i+1}-\theta_{i}\triangleq\ell$. We will now show that all the message
symbols in $\\{\underline{s}(t)\mid t\in[\theta_{i}+1:\theta_{i}+\ell]\\}$ can
be recovered by the receiver using the available non-erased code symbols
$\\{c_{j}(t)\mid t\in[\theta_{i}+1:\theta_{i}+\ell],j\in\mathcal{R}_{t}\\}$.
This is under the assumption that the message symbols in
$\\{\underline{s}(t^{\prime})\mid t^{\prime}\in[\theta_{i}]\\}$ are already
known to the receiver (the assumption is trivially true when $i=0$). After
removing the contribution of these message symbols, it is as if the
transmitter has sent
$\underline{\hat{c}}(\theta_{i}+1)=G^{(0)}\underline{s}(\theta_{i}+1)$ and
$\underline{\hat{c}}(t^{\prime})=G^{(1)}\underline{s}(t^{\prime}-1)+G^{(0)}\underline{s}(t^{\prime})$,
where $t^{\prime}\in[\theta_{i}+2:\theta_{i}+\ell]$. Thus, effectively, the
received code symbols in time slots $[\theta_{i}+1:\theta_{i}+\ell]$ are given
by $\\{\hat{c}_{j}(t)\mid
t\in[\theta_{i}+1:\theta_{i}+\ell],j\in\mathcal{R}_{t}\\}$, where
$\underline{\hat{c}}(t)=[\hat{c}_{1}(t)~{}\cdots~{}\hat{c}_{n}(t)]^{T}$.

By definition of $\\{\theta_{i}\\}$, we have
$I(\theta_{i})=I(\theta_{i}+\ell)=0$. Hence,
$\sum_{t\in[\theta_{i}+1:\theta_{i}+\ell]}n_{t}\geq k\ell=2\ell$. Without loss
of generality, we will consider here only the worst-case scenario
$\sum_{t\in[\theta_{i}+1:\theta_{i}+\ell]}n_{t}=2\ell$. In addition, by
Definition 1, we have $I(t)\leq mk=2$ and $\ell\leq\tau+1=3$. As $I(t)\leq 2$
and $I(t)>0$ for $t\in[\theta_{i}+1:\theta_{i}+\ell-1]$, it follows that:
$2(\ell^{\prime}-1)\leq\sum_{t\in[\theta_{i}+1:\theta_{i}+\ell^{\prime}]}n_{t}<2\ell^{\prime}$,
for all $\ell^{\prime}\in[\ell-1]$. Thus, we restrict ourselves to
$\\{n_{\theta_{i}+1},\ldots,n_{\theta_{i}+\ell}\\}$ satisfying three
conditions:

  * (1)

$\ell\leq\tau+1=3$,

  * (2)

$\sum_{t\in[\theta_{i}+1:\theta_{i}+\ell]}n_{t}=2\ell$,

  * (3)

$2(\ell^{\prime}-1)\leq\sum_{t\in[\theta_{i}+1:\theta_{i}+\ell^{\prime}]}n_{t}<2\ell^{\prime}$,
$\ell^{\prime}\in[\ell-1]$.

Let $\mathcal{R}_{t}=\\{i_{1},i_{2},\ldots,i_{n_{t}}\\}\subseteq[n]$ and
$\underline{\tilde{c}}(t)\triangleq[\hat{c}_{i_{1}}(t)~{}\cdots~{}\hat{c}_{i_{n_{t}}}(t)]^{T}$.
At time $(\theta_{i}+\ell)$, thus the decoder essentially has the following
matrix equation to solve:

$\begin{bmatrix}\underline{\tilde{c}}(\theta_{i}+1)\\\ \vdots\\\
\underline{\tilde{c}}(\theta_{i}+\ell)\end{bmatrix}=G_{\text{dec}}\begin{bmatrix}\underline{s}(\theta_{i}+1)\\\
\vdots\\\ \underline{s}(\theta_{i}+\ell)\end{bmatrix},$

where $G_{\text{dec}}$ is a decoding matrix of size $k\ell\times k\ell$ (i.e.,
$2\ell\times 2\ell$). Note that $G_{\text{dec}}$ is not a constant and is a
function of the symbol erasure pattern. The code is an $i$DOS code if and only
if $G_{\text{dec}}$ is non-singular for any symbol erasure pattern such that
$\\{n_{\theta_{i}+1},\ldots,n_{\theta_{i}+\ell}\\}$ satisfy the conditions
(1)–(3). The structure of decoding matrices for all the possible symbol
erasure scenarios is illustrated in Fig. 3. We illustrate the corresponding
exponents (with respect to $\alpha$) in Fig. 4. The high-level idea of the
construction is the following. For each $2\ell\times 2\ell$ decoding matrix
$G_{\text{dec}}$, we have a corresponding $2\ell\times 2\ell$ exponent matrix
$M_{\text{dec}}$ in Fig. 4. We will show that all the exponent matrices have
dominant permutations. This will prove that for a large enough degree of the
field extension $d$, the corresponding decoding matrices are non-singular
matrices (by applying Lemma 1). We will specify an explicit value for $d$
later in the section.

Figure 3: Let $\\{n_{\theta_{i}+1},\ldots,n_{\theta_{i}+\ell}\\}$ be such that
they satisfy conditions (1)–(3) listed in Sec. III-A. The code in the example
is an $(n=4,k=2,m=1,\tau=2)$ $i$DOS code if and only if the $2\ell\times
2\ell$ decoding matrix $G_{\text{dec}}$ obtained by selecting rows as
indicated above is non-singular.  Figure 4: Let
$\\{n_{\theta_{i}+1},\ldots,n_{\theta_{i}+\ell}\\}$ be such that they satisfy
conditions (1)–(3) listed in Sec. III-A. We will show that any $2\ell\times
2\ell$ exponent matrix $M_{\text{dec}}$ obtained by selecting rows as
indicated above possesses a dominant permutation.

Towards arguing that all the exponent matrices possess dominant permutations,
we first make the following remarks on $M^{(0)}$ and $M^{(1)}$.

  * P1

For each column, the elements of $M^{(0)}$ are strictly increasing from top to
bottom.

  * P2

For each column, the elements of $M^{(1)}$ are strictly increasing from bottom
to top.

  * P3

For $r\in[0:2]$, any $2\times 2$ matrix formed by stacking $r$ distinct rows
of $M^{(0)}$ followed by $2-r$ distinct rows of $M^{(1)}$ has a dominant
permutation.

Case $\ell=1$: Here, there is just one choice for $(n_{\theta_{i}+1})$
(satisfying conditions (1)–(3)), which is $n_{\theta_{i}+1}=2$. As can be
noted from Fig. 4(a), the exponent matrix $M_{\text{dec}}$ in this case is
obtained by selecting $2$ rows of $M^{(0)}$. From P3 (with the choice $r=2$),
it follows that any $2\times 2$ submatrix of $M^{(0)}$ possesses a dominant
permutation.

Case $\ell=2$: There are two possibilities for
$(n_{\theta_{i}+1},n_{\theta_{i}+2})$ here; $(0,4)$ and $(1,3)$. In Fig. 5, we
illustrate these two scenarios. In the figure, we use red-colored and blue-
colored asterisks as placeholders for the elements $M^{(0)}{(i,j)}$’s and
$M^{(1)}{(i,j)}$’s, respectively. We partition the columns of these $4\times
4$ matrices into two thick columns. For $i\in[\ell]$, thick column $i$
consists of columns $[(i-1)k+1:ik]$.

Figure 5: Here, we consider $\ell=2$. (a)
$(n_{\theta_{i}+1},n_{\theta_{i}+2})=(0,4)$; (b)
$(n_{\theta_{i}+1},n_{\theta_{i}+2})=(1,3)$. Vertical dashed lines demarcate
thick columns. Submatrices demarcated using solid red and blue rectangles are
dominant submatrices. The constrained dominant submatrix is indicated using a
blue dashed rectangle.

For the $(0,4)$ scenario, by P1 and P3 (with $r=2$), the lowermost $2\times 2$
submatrix (demarcated by a red rectangle in Fig. 5(a)) is the dominant
submatrix of the $2^{\text{nd}}$ thick column. Similarly, the topmost $2\times
2$ submatrix (shown by a blue rectangle) is the dominant submatrix of the
$1^{\text{st}}$ thick column by P2 and P3 (with $r=0$). Because the rows of
these submatrices do not overlap, any $4\times 4$ exponent matrix
$M_{\text{dec}}$ of the form illustrated in Fig. 5(a) has a dominant
permutation using the submatrix decomposition approach.

For the $(1,3)$ scenario, using similar arguments, the lowermost $2\times 2$
submatrix (demarcated by a red rectangle in Fig. 5(b)) may be shown to be the
dominant submatrix of the $2^{\text{nd}}$ thick column. As
$M_{\text{dec}}(1,3)=M_{\text{dec}}(1,4)=-\infty$, if there is a dominant
permutation $\sigma^{*}$, it should be that $1\in\sigma^{*}(\\{1,2\\})$
(similar to the scenario in Example 1). As a result, for the $1^{\text{st}}$
thick column, we limit our focus to those $2\times 2$ submatrices that involve
row $1$. It is worth noting that row $1$ of the $1^{\text{st}}$ thick column
is a row of $M^{(0)}$, whereas any other row of the thick column is a row of
$M^{(1)}$. If we augment one row each from $M^{(0)}$ and $M^{(1)}$, the
property P3 (with $r=1$) ensures the presence of a dominant permutation.
Furthermore, based on P2, the topmost $2\times 2$ submatrix (shown using a
blue dashed rectangle) is the (constrained) dominant submatrix of the
$1^{\text{st}}$ thick column. Because the rows of the red and blue dominant
submatrices do not intersect, using submatrix decomposition, it follows that
any $4\times 4$ exponent matrix $M_{\text{dec}}$ of the form illustrated in
Fig. 5(b) has a dominant permutation.

Case $\ell=3$: There are four possibilities for
$(n_{\theta_{i}+1},n_{\theta_{i}+2},n_{\theta_{i}+3})$ here; $(0,2,4)$,
$(0,3,3)$, $(1,1,4)$ and $(1,2,3)$. We illustrate these four cases in Fig. 6.
The basic idea remains the same as in the $\ell=2$ case, i.e., identification
of dominant submatrices whose rows do not intersect. By P1 and P3 (with
$r=2$), it follows that the submatrices demarcated by red rectangles within
the $3^{\text{rd}}$ thick column are dominant submatrices (for all the four
scenarios). For the $(0,2,4)$ scenario illustrated in Fig. 6(a), due to the
presence of $-\infty$ elements within the $1^{\text{st}}$ thick column of
$M_{\text{dec}}$, it may be noted that any dominant permutation $\sigma^{*}$
(if exists) should satisfy $\sigma^{*}([3:6])=[3:6]$. As a result, we will
search for the (constrained) dominant submatrix within the $2^{\text{nd}}$
thick column such that only rows $\\{3,4,5,6\\}$ are permitted. It now follows
from properties P2 and P3 (with $r=0$) that the blue dashed rectangle depicts
the constrained dominant submatrix of the $2^{\text{nd}}$ thick column. The
submatrix highlighted in green is a dominant submatrix by P3 (with $r=0$).
Because there is no intersection of rows among these dominant submatrices, the
$6\times 6$ matrix has a dominant permutation.

Figure 6: Here, we consider $\ell=3$. There are four possibilities for
$(n_{\theta_{i}+1},n_{\theta_{i}+2},n_{\theta_{i}+3})$; (a) $(0,2,4)$, (b)
$(0,3,3)$, (c) $(1,1,4)$ and (d) $(1,2,3)$. Vertical dashed lines demarcate
thick columns. Submatrices demarcated using solid red and green rectangles are
dominant submatrices. Constrained dominant submatrices are delineated using
blue and green dashed rectangles.

For the $(1,2,3)$ scenario (illustrated in Fig. 6(d)), due to the $-\infty$’s
in the $1^{\text{st}}$ thick column, it should be that
$\sigma^{*}([3:6])\supseteq[4:6]$. Because of the $-\infty$’s in the
$3^{\text{rd}}$ thick column, it should be that
$\sigma^{*}([5:6])\subseteq[4:6]$. It follows that $\sigma^{*}([3:4])$ should
contain precisely one element from $[4:6]$. Moreover, due to the $-\infty$’s
in the $2^{\text{nd}}$ thick column, we have:
$\sigma^{*}([3:4])\subseteq[2:6]$. Thus, $\sigma^{*}([3:4])$ should contain
precisely one element from $[2:3]$. Pictorially, these constraints correspond
to selecting one blue row and one red row within the $2^{\text{nd}}$ thick
column. Due to P1, P2 and P3 (with $r=1$), it follows that the submatrix
demarcated using a blue dashed rectangle is the constrained dominant
submatrix. With regard to the $1^{\text{st}}$ thick column, owing to the
constraint that $1\notin\sigma^{*}([3:6])$, we have that
$1\in\sigma^{*}([1:2])$ and $|\sigma^{*}([1:2])\cap[2:3]|=1$. This corresponds
to selecting the red row and one of the two blue rows in the $1^{\text{st}}$
thick column. From P2 and P3 (with $r=1$), it follows that the submatrix
indicated in the green dashed rectangle is the constrained dominant submatrix.
As rows of these three submatrices do not intersect, it follows that the
$6\times 6$ matrix possesses a dominant permutation. Proofs for the scenarios
$(0,3,3)$ and $(1,1,4)$ follow along similar lines. Since the largest term of
matrices $M^{(0)}$, $M^{(1)}$ is $6$, it can be noted that the dominant sum of
any exponent matrix will be at most $6*k*(\tau+1)=36$. Hence, choosing $d>36$
guarantees that all the decoding matrices are non-singular (by Lemma 1).

###  III-B Construction A for any $\\{n,k,m=1,\tau\\}$

In this subsection, we describe our unit memory, explicit construction for any
$\\{n,k,\tau\\}$.

######  Construction A.

Let $\alpha$ be a primitive element of $\mathbb{F}_{2^{d}}$. We describe an
$(n,k,m=1)$ convolutional code over $\mathbb{F}_{2^{d}}$ by defining the
$(n\times 2k)$ generator matrix $G=[G^{(1)}\ G^{(0)}]$, where
$G^{(0)}=\alpha^{M^{(0)}},G^{(1)}=\alpha^{M^{(1)}}$. We choose the $n\times k$
matrices $M^{(0)},M^{(1)}$ as follows:

$\displaystyle M^{(0)}(i,j)=(i-1)*j,\ \ M^{(1)}(i,j)=(n-i)*(k+1-j).$

######  Theorem 1.

The $(n,k,m=1)$ convolutional code defined by Construction A is an
$(n,k,m=1,\tau)$ $i$DOS code over $\mathbb{F}_{2^{d}}$ if
$d>(n-1)k^{2}(\tau+1)$.

The proof of the theorem is in Appendix -D.

##  IV Construction B: Explicit Construction For All Parameters

The following convolutional code construction is a special case of the
construction in [22]. We will show that this code is an $(n,k,m,\tau)$ $i$DOS
code if the finite field size is sufficiently large.

######  Construction B.

Let $\alpha$ be a primitive element of $\mathbb{F}_{2^{d}}$. We describe an
$(n,k,m)$ convolutional code over $\mathbb{F}_{2^{d}}$ by defining the
$(n\times(m+1)k)$ generator matrix $G=[G^{(m)}\ \cdots\ G^{(0)}]$. For
$t\in[0:m]$, $G^{(t)}\in\mathbb{F}_{2^{d}}^{n\times k}$ takes the form
$G^{(t)}=\alpha^{M^{(t)}}$. We choose the $n\times k$ matrices $\\{M^{(t)}\\}$
as follows:

$\displaystyle M^{(t)}(i,j)=2^{t*n+i+k-1-j}.$

######  Example 2.

The generator matrix as per Construction B for parameters $(n=4,k=2,m=2)$ is
given by:

$G=[\alpha^{M^{(2)}}\ \alpha^{M^{(1)}}\ \alpha^{M^{(0)}}],$

where:

$\displaystyle M^{(0)}=\left[\begin{array}[]{cc}2^{1}&2^{0}\\\ 2^{2}&2^{1}\\\
2^{3}&2^{2}\\\
2^{4}&2^{3}\end{array}\right],M^{(1)}=\left[\begin{array}[]{cc}2^{5}&2^{4}\\\
2^{6}&2^{5}\\\ 2^{7}&2^{6}\\\ 2^{8}&2^{7}\end{array}\right]$
$\displaystyle\text{ and }M^{(2)}=\left[\begin{array}[]{cc}2^{9}&2^{8}\\\
2^{10}&2^{9}\\\ 2^{11}&2^{10}\\\ 2^{12}&2^{11}\end{array}\right].$

######  Theorem 2.

The $(n,k,m)$ convolutional code defined by Construction B is an
$(n,k,\tau,m)$ $i$DOS code over $\mathbb{F}_{2^{d}}$ if
$d>2^{((m+1)n+k-2)}(\tau+1)k$.

The proof can be found in Appendix -F.

######  Remark 3.

When $m=1$, Construction B has a much larger field extension degree
requirement of $d>2^{(2n+k-2)}(\tau+1)k$ compared to the
$d>(n-1)k^{2}(\tau+1)$ requirement of Construction A.

## References

  * [1] E. Martinian and C. W. Sundberg, “Burst erasure correction codes with low decoding delay,” _IEEE Trans. Inf. Theory_ , vol. 50, no. 10, pp. 2494–2502, 2004.
  * [2] E. Martinian and M. Trott, “Delay-optimal burst erasure code construction,” in _Proc. IEEE Int. Symp. Inf. Theory, Nice, France, June 24-29, 2007_ , pp. 1006–1010.
  * [3] A. Badr, A. Khisti, W. Tan, and J. G. Apostolopoulos, “Streaming codes for channels with burst and isolated erasures,” in _Proc. INFOCOM, Turin, Italy, April 14-19_ , 2013, pp. 2850–2858.
  * [4] A. Badr, P. Patil, A. Khisti, W. Tan, and J. G. Apostolopoulos, “Layered constructions for low-delay streaming codes,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 1, pp. 111–141, 2017.
  * [5] M. N. Krishnan and P. V. Kumar, “Rate-optimal streaming codes for channels with burst and isolated erasures,” in _Proc. IEEE Int. Symp. Inf. Theory, Vail, CO, USA, June 17-22, 2018_ , pp. 1809–1813.
  * [6] M. N. Krishnan, V. Ramkumar, M. Vajha, and P. V. Kumar, “Simple streaming codes for reliable, low-latency communication,” _IEEE Communications Letters_ , 2019.
  * [7] S. L. Fong, A. Khisti, B. Li, W. Tan, X. Zhu, and J. G. Apostolopoulos, “Optimal streaming codes for channels with burst and arbitrary erasures,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 7, pp. 4274–4292, 2019.
  * [8] M. N. Krishnan, D. Shukla, and P. V. Kumar, “Rate-optimal streaming codes for channels with burst and random erasures,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 8, pp. 4869–4891, 2020.
  * [9] V. Ramkumar, M. Vajha, M. N. Krishnan, and P. Vijay Kumar, “Staggered diagonal embedding based linear field size streaming codes,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 503–508.
  * [10] E. Domanovitz, S. L. Fong, and A. Khisti, “An explicit rate-optimal streaming code for channels with burst and arbitrary erasures,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 1, pp. 47–65, 2022.
  * [11] M. Vajha, V. Ramkumar, M. N. Krishnan, and P. V. Kumar, “Explicit rate-optimal streaming codes with smaller field size,” in _IEEE International Symposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021_ , pp. 736–741.
  * [12] V. Ramkumar, M. Vajha, and P. V. Kumar, “Generalized simple streaming codes from mds codes,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 878–883.
  * [13] ——, “Locally recoverable streaming codes for packet-erasure recovery,” in _Proc. IEEE Information Theory Workshop, ITW 2021, Kanazawa, Japan, October 17-21, 2021_. IEEE, 2021, pp. 1–6.
  * [14] M. Rudow and K. V. Rashmi, “Streaming codes for variable-size messages,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 9, pp. 5823–5849, 2022.
  * [15] E. Martinian, “Dynamic information and constraints in source and channel coding,” Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 2004.
  * [16] P. Su, Y. Huang, S. Lin, I. Wang, and C. Wang, “Random linear streaming codes in the finite memory length and decoding deadline regime - part I: exact analysis,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 10, pp. 6356–6387, 2022.
  * [17] V. Ramkumar, M. N. Krishnan, M. Vajha, and P. V. Kumar, “On information-debt-optimal streaming codes with small memory,” in _IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26 - July 1, 2022_. IEEE, 2022, pp. 1578–1583.
  * [18] N. Alon, “Combinatorial Nullstellensatz,” _Combinatorics, Probability and Computing_ , vol. 8, no. 1-2, pp. 7–29, 1999.
  * [19] E. M. Gabidulin, “Convolutional codes over large alphabets,” in _Proc. Int. Workshop on Algebraic Combinatorial and Coding Theory, Varna, Bulgaria_ , 1988, p. 80–84.
  * [20] H. Gluesing-Luerssen, J. Rosenthal, and R. Smarandache, “Strongly-MDS convolutional codes,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 2, pp. 584–598, 2006.
  * [21] G. N. Alfarano, D. Napp, A. Neri, and V. Requena, “Weighted Reed-Solomon convolutional codes,” _CoRR_ , vol. abs/2012.11417, 2020.
  * [22] P. Almeida, D. Napp, and R. Pinto, “Superregular matrices and applications to convolutional codes,” _Linear Algebra and its Applications_ , vol. 499, pp. 1–25, 2016.
  * [23] F. J. MacWilliams and N. J. A. Sloane, _The theory of error-correcting codes_. Elsevier, 1977, vol. 16.

###  -A Leibniz Formula

Given an $x\times x$ matrix $A$, the determinant $\det(A)$ can be computed as:

$\det(A)=\sum_{\sigma\in S_{x}}sgn(\sigma)\prod_{i=1}^{x}A({\sigma(i),i}).$
(3)

Here, $sgn(\sigma)=\pm 1$ ($+1$ if $\sigma$ is an even permutation, $-1$ if it
is an odd permutation).

###  -B Primitive Elements and Polynomials

We quote the following well-known result as a lemma.

######  Lemma 2 ([23, Ch. 4]).

Let $f(x)$ denote a non-zero polynomial of degree at most $d-1$ with
coefficients over the subfield $\mathbb{F}_{p}$ (of $\mathbb{F}_{p^{d}}$). If
$\alpha$ is a primitive element of $\mathbb{F}_{p^{d}}$, then $f(\alpha)\neq
0$.

###  -C Proof of Lemma 1

###### Proof.

Let $A\triangleq\alpha^{M}$. For $\sigma\in S_{x}$, let
$s_{\sigma}\triangleq\sum_{i=1}^{x}{M{(\sigma(i),i)}}$. From (3), we have:

$\displaystyle det(A)$ $\displaystyle=$ $\displaystyle\sum_{\sigma\in
S_{x}}sgn(\sigma)\prod_{i=1}^{x}\alpha^{M{(\sigma(i),i)}}$ $\displaystyle=$
$\displaystyle\sum_{\sigma\in
S_{x}}sgn(\sigma)\alpha^{\sum_{i=1}^{x}M{(\sigma(i),i)}}$ $\displaystyle=$
$\displaystyle sgn(\sigma^{*})\alpha^{s_{\sigma^{*}}}+\sum_{\sigma\in
S_{x}\setminus\\{\sigma^{*}\\}}sgn(\sigma)\alpha^{s_{\sigma}}$
$\displaystyle=$ $\displaystyle f(\alpha),$

where $f(x)\triangleq sgn(\sigma^{*})x^{s_{\sigma^{*}}}+\sum_{\sigma\in
S_{x}\setminus\\{\sigma^{*}\\}}sgn(\sigma)x^{s_{\sigma}}$. Clearly, $f(x)$ has
$\\{+1,-1\\}$ as its coefficients, which are drawn from the subfield
$\mathbb{F}_{p}$. Moreover, as $s_{\sigma^{*}}>s_{\sigma}$, $f(x)$ is a non-
zero polynomial. The lemma now follows from the application of Lemma 2. ∎

###  -D Proof of Theorem 1

To prove that a convolutional code is an $i$DOS code, we have to show that all
the message symbols in $\\{\underline{s}(t)\mid
t\in[\theta_{i}+1:\theta_{i+1}]\\}$ can be recovered by the receiver using the
available non-erased code symbols $\\{c_{j}(t)\mid
t\in[\theta_{i}+1:\theta_{i+1}],j\in\mathcal{R}_{t}\\}$, under the assumption
that the message symbols in $\\{\underline{s}(t^{\prime})\mid
t^{\prime}\in[\theta_{i}]\\}$ are already known to the receiver. Since the
code is time-invariant, we can assume without loss of generality that
$\theta_{i}=0$ and $\theta_{i+1}=\ell$.

Properties (1)–(3) noted earlier in Sec. III-A can be generalized to the
following:

  * (1)

$\ell\leq\tau+1$,

  * (2)

$\sum_{i=1}^{\ell}n_{i}=k\ell$,

  * (3)

$k(\ell^{\prime}-1)\leq\sum_{i=1}^{\ell^{\prime}}n_{i}<k\ell^{\prime}$,
$\ell^{\prime}\in[\ell-1]$.

In other words, $\\{n_{1},\dots,n_{\ell}\\}$ corresponding to any
$(n,k,m=1,\tau)$-acceptable symbol erasure pattern will satisfy these three
properties. Let
$\mathcal{R}_{t}=\\{i_{1},i_{2},\ldots,i_{n_{t}}\\}\subseteq[n]$ and
$\underline{\tilde{c}}(t)\triangleq[c_{i_{1}}(t)~{}\cdots~{}c_{i_{n_{t}}}(t)]^{T}$.
At time $\ell$, the decoder has to solve the following matrix equation:

$\begin{bmatrix}\underline{\tilde{c}}(1)\\\ \vdots\\\
\underline{\tilde{c}}(\ell)\end{bmatrix}=G_{\text{dec}}\begin{bmatrix}\underline{s}(1)\\\
\vdots\\\ \underline{s}(\ell)\end{bmatrix},$ (4)

where $G_{\text{dec}}$ is a decoding matrix of size $k\ell\times k\ell$. Note
that $G_{\text{dec}}$ is dependent on the symbol erasure pattern. It is easy
to see that the code is an $i$DOS code if $G_{\text{dec}}$ is non-singular for
any symbol erasure pattern such that $\\{n_{1},\ldots,n_{\ell}\\}$ satisfy the
properties (1)–(3). In our construction, for each decoding matrix
$G_{\text{dec}}$, we have a corresponding $k\ell\times k\ell$ exponent matrix
$M_{\text{dec}}$ such that $G_{\text{dec}}=\alpha^{M_{\text{dec}}}$.

We first start by presenting Lemma 3 that shows some properties that are
satisfied by $\\{n_{1},\cdots,n_{\ell}\\}$. These properties will be used in
Lemmas 4 and 5 to prove the constraints that need to be satisfied by the
dominant permutation (if it exists) of the exponent matrix $M_{\text{dec}}$.

######  Lemma 3.

The sequence $\\{n_{1},n_{2},\ldots,n_{\ell}\\}$ produced by any
$(n,k,m=1,\tau)$-acceptable erasure pattern should satisfy the following
conditions:

  * (a)

$n_{\ell}\geq k$,

  * (b)

$n_{\ell^{\prime}}\neq 0$ for $\ell^{\prime}\in[2:\ell]$,

  * (c)

$\sum_{i=\ell-\mu+2}^{\ell}n_{i}\leq\mu k<\sum_{i=\ell-\mu+1}^{\ell}n_{i}$,
$\mu\in[\ell-1]$,

  * (d)

$n_{\ell^{\prime}}+n_{\ell^{\prime}+1}\geq k$ for any
$\ell^{\prime}\in[\ell-1]$.

###### Proof.

Recall properties (1)–(3) defined in Appendix -D.

  * (a)

If $\ell=1$, from property (2), we have $n_{\ell}=k$. If $\ell\geq 2$, from
property (3) (with the choice $\ell^{\prime}=\ell-1$), we have
$\sum_{i=1}^{\ell-1}n_{i}<k(\ell-1)$. Using (2), it follows that $n_{\ell}>k$.

  * (b)

Since $n_{\ell}>k$, the statement is true for $\ell^{\prime}=\ell$. We will
now assume $\ell^{\prime}\in[2:\ell-1]$. From property (3), we have
$\sum_{i=1}^{\ell^{\prime}-1}n_{i}<k(\ell^{\prime}-1)$. If
$n_{\ell^{\prime}}=0$, we can then write
$\sum_{i=1}^{\ell^{\prime}}n_{i}<k(\ell^{\prime}-1)$ resulting in a
contradiction of the first part of property (3).

  * (c)

From property (2) and the first part of property (3) (with
$\mu=\ell-\ell^{\prime}$), we have:
$\sum_{i=1}^{\ell}n_{i}-\sum_{i=1}^{\ell^{\prime}}n_{i}>(\ell-\ell^{\prime})k$.
Thus, we have $\sum_{i=\ell-\mu+1}^{\ell}n_{i}>\mu k$, where
$\mu\in[1:\ell-1]$.

From property (2) and the second part of property (3) (with
$\mu=\ell-\ell^{\prime}+1$), we have:
$\sum_{i=1}^{\ell}n_{i}-\sum_{i=1}^{\ell-\mu+1}n_{i}\leq(\ell-\ell^{\prime}+1)k$.
Thus, we have $\sum_{i=\ell-\mu+2}^{\ell}n_{i}\leq\mu k$, where
$\mu\in[2:\ell]$. If $\mu=1$, we have
$0\triangleq\sum_{i=\ell+1}^{\ell}n_{i}\leq k$, which is trivially true.

  * (d)

From property (2) and first part of property (3), it follows that for all
$\ell^{\prime}\in[\ell-1]$:

$\displaystyle n_{\ell^{\prime}}+n_{\ell^{\prime}+1}$ $\displaystyle\geq$
$\displaystyle k\ell^{\prime}-\sum\limits_{i=1}^{\ell-1}n_{i}$
$\displaystyle\geq$ $\displaystyle k\ell^{\prime}-k(\ell^{\prime}-1)=k,$

where the last inequality follows from the second part of property (3).

∎

Figure 7: In this figure, we illustrate how the columns of the $k\ell\times
k\ell$ exponent matrix $M_{\text{dec}}$ are grouped into $\ell$ thick columns.
Regions marked red and blue indicate submatrices of $M^{(0)}$ and $M^{(1)}$,
respectively. Here, diagonal striped areas indicate $-\infty$ entries.

From Lemma 3(b), it follows that a given $k\ell\times k\ell$ exponent matrix
$M_{\text{dec}}$, we can partition its columns into $\ell$ thick columns (see
Fig. 7) where $\ell^{\prime}$-th thick column has columns with indices ${\cal
A}_{\ell^{\prime}}=[(\ell^{\prime}-1)k+1:\ell^{\prime}k]$. Notice that for a
permutation $\sigma^{*}$ to be dominant, for each thick column
$\ell^{\prime}$, the choice of the $k$ rows that get picked (given by
$\sigma^{*}({\cal A}_{\ell^{\prime}})$) has to come from the
$n_{\ell^{\prime}}+n_{\ell^{\prime}+1}$ rows indicated by red and blue
portions in Fig. 8.

In the upcoming Lemmas 4 and 5, we will further show the exact split of the
red and blue rows that need to be picked by the dominant permutation for any
thick column.

######  Lemma 4.

Suppose there exists a dominant permutation $\sigma^{*}$ for $M_{\text{dec}}$.
Then for any thick column $(\ell-\mu)$ such that $\mu\in[1:\ell-1]$,
$\sigma^{*}$ should satisfy that

$\displaystyle|\sigma^{*}({\cal A}_{\ell-\mu})\cap\hat{\cal B}_{\ell-\mu}|$
$\displaystyle=$ $\displaystyle r_{\mu}\text{ and ,}$
$\displaystyle|\sigma^{*}({\cal A}_{\ell-\mu})\cap\hat{\cal B}_{\ell-\mu+1}|$
$\displaystyle=$ $\displaystyle k-r_{\mu},$

where $\hat{\cal
B}_{\ell-\mu}=[\sum_{i=1}^{\ell-\mu-1}n_{i}:\sum_{i=1}^{\ell-\mu}n_{i}]$ and
$r_{\mu}\triangleq(\mu+1)k-\sum_{i=\ell-\mu+1}^{\ell}n_{i}$. (See Fig. 8 for
an illustration).

Figure 8: Let $\mu\in[\ell-1]$. Here, diagonal striped areas indicate
$-\infty$ entries and regions marked red and blue indicate submatrices of
$M^{(0)}$ and $M^{(1)}$, respectively and rows $\hat{\cal B}_{\ell-\mu}$,
$\hat{\cal B}_{\ell-\mu+1}$ respectively. Suppose a dominant permutation
$\sigma^{*}$ exists for $M_{\text{dec}}$. Consider the restriction of
$\sigma^{*}$ to the thick column $(\ell-\mu)$, denoted by
$\tilde{\sigma}^{*}_{\mu}$. Then, $\tilde{\sigma}^{*}_{\mu}$ involves
precisely $(k-r_{\mu})$ blue rows and $r_{\mu}$ red rows.

###### Proof.

Consider the Fig. 9. Note that $\sigma^{*}({\cal
A}_{\ell-\mu})\subseteq\hat{\cal B}_{\ell-\mu}\cup\hat{\cal B}_{\ell-\mu+1}$
as the remaining rows see $-\infty$’s in the thick column given by ${\cal
A}_{\ell-\mu}$.

_Condition 1:_ We first note that when restricted to thick columns
$[\ell-\mu-1]$, the rows $\cup_{i=\ell-\mu+1}^{\ell}\hat{\cal B}_{i}$ consist
of $-\infty$’s. As a result these rows need to be exhausted by the thick
columns $\ell-\mu$ and beyond, i.e.,

$\displaystyle\cup_{i=\ell-\mu+1}^{\ell}\hat{\cal
B}_{i}\subseteq\sigma^{*}(\cup_{i=\ell-\mu}^{\ell}{\cal A}_{i}).$

_Condition 2:_ Since the thick columns $[\ell-\mu+1:\ell]$, given by indices
$\cup_{i=\ell-\mu+1}^{\ell}{\cal A}_{i}$ when restricted to the rows
$\cup_{i=1}^{\ell-\mu}\hat{{\cal B}}_{i}$ consist of $-\infty$ it follows
that:

$\displaystyle\sigma^{*}(\cup_{i=\ell-\mu+1}^{\ell}{\cal
A}_{i})\subseteq\cup_{i=\ell-\mu+1}^{\ell}\hat{\cal B}_{i}.$

Therefore, $\mu k$ rows out of the rows $\cup_{i=\ell-\mu+1}^{\ell}\hat{{\cal
B}}_{i}$ are already used up by thick columns $\ell-\mu+1$ and beyond. The
remaining rows $\sum\limits_{i=\ell-\mu+1}^{\ell}n_{i}-\mu k=(k-r_{\mu})$ need
to be exhausted by the thick column $\ell-\mu$ due to Condition 1 i.e.,

$\displaystyle|\sigma^{*}({\cal
A}_{\ell-\mu})\cap\cup_{i=\ell-\mu+1}^{\ell}\hat{\cal B}_{i}|=(k-r_{\mu}).$

Note that $r_{\mu}$ is well defined within $[0:k]$ due to Lemma 3. Also from
the observation that $\sigma^{*}({\cal A}_{\ell-\mu})\subseteq\hat{\cal
B}_{\ell-\mu}\cup\hat{\cal B}_{\ell-\mu+1}$ it follows that

$\displaystyle|\sigma^{*}({\cal
A}_{\ell-\mu})\cap\cup_{i=\ell-\mu+1}^{\ell}\hat{\cal B}_{i}|$
$\displaystyle=$ $\displaystyle|\sigma^{*}({\cal A})_{\ell-\mu}\cap\hat{\cal
B}_{\ell-\mu+1}|$ $\displaystyle=$ $\displaystyle(k-r_{\mu})\text{ and }$
$\displaystyle|\sigma^{*}({\cal A})_{\ell-\mu}\cap\hat{\cal B}_{\ell-\mu}|$
$\displaystyle=$ $\displaystyle r_{\mu}.$

Figure 9: Figure highlighting structure of $M_{\text{dec}}$ matrix. Regions
marked red and blue indicate submatrices of $M^{(0)}$ and $M^{(1)}$,
respectively. Diagonal stripes indicate regions where we have $-\infty$’s. We
do not care about the values of the unshaded regions.

∎

######  Lemma 5.

Suppose there exists a dominant permutation $\sigma^{*}$ for $M_{\text{dec}}$
then

$\displaystyle|\sigma({\cal A}_{\ell})\cap\hat{\cal B}_{\ell}|=k\triangleq
r_{0},$

where $\hat{\cal B}_{\ell}=[\ell k-n_{\ell}+1:\ell k]$.

###### Proof.

Clearly, $|\sigma({\cal A}_{\ell})|$ is equal to $k$. In the thick column
$\ell$, all rows except the rows given by $\hat{\cal B}_{\ell}$ consist of
$-\infty$ elements. Thus, the lemma follows. ∎

We will now examine a few properties of the matrices $M(0)$, $M(1)$ defined by
Construction A. Subsequently, we use these properties to prove Corollary 1.

######  Lemma 6.

The matrices $M^{(0)},M^{(1)}$ defined in Construction A satisfy the following
three properties.

  * P1

For each column, the elements of $M^{(0)}$ are strictly increasing from top to
bottom.

  * P2

For each column, the elements of $M^{(1)}$ are strictly increasing from bottom
to top.

  * P3

For $r\in[0:k]$, any $k\times k$ matrix formed by stacking $r$ distinct rows
of $M^{(0)}$ followed by $2-r$ distinct rows of $M^{(1)}$ has a dominant
permutation.

Proof: The properties P1 and P2 follow directly from the definition of
matrices $M^{(0)},M^{(1)}$ defined in Construction A. Let $\hat{M}$ be the
matrix obtained by augmenting $(k-r)$ rows indexed by
$R_{1}=\\{i_{1},\cdots,i_{k-r}\\}$ of $M^{(1)}$ followed by $r$ rows
$R_{0}=\\{i_{k-r+1},\cdots,i_{k}\\}$ of $M^{(0)}$. Then,

$\displaystyle\hat{M}=\left[\begin{array}[]{c}M^{(1)}(R_{1},[k])\\\
M^{(0)}(R_{0},[k])\\\ \end{array}\right].$

If $\hat{M}$ has a dominant permutation, then the $k\times k$ matrix
considered in ${\bf{P3}}$ will also have a dominant permutation as these two
matrices differ only in the ordering of rows. To prove property P3 we will
show that the identity permutation $\sigma_{0}\in S_{k}$ defined by
$\sigma_{0}(i)=i$ for all $i\in[k]$ is the dominant permutation of the matrix
$\hat{M}$.

Let us consider any other permutation $\sigma\in
S_{k}\setminus\\{\sigma_{0}\\}$; we will show that the sum corresponding to
$\sigma$ is strictly less than the dominant sum. To do this, for any
$\sigma\in S_{k}\setminus\\{\sigma_{0}\\}$, let $j$ be the smallest integer
such that $\sigma(j)\neq\sigma_{0}(j)=j$, we will construct $\hat{\sigma}$
such that

  1. 1.

$\hat{\sigma}(i)=\sigma_{0}(i)=i$ for all $i\leq j$ and

  2. 2.

$\sum\limits_{i=1}^{k}\hat{M}{(\sigma(i),i)}<\sum\limits_{i=1}^{k}\hat{M}{(\hat{\sigma}(i),i)}$.

We can then use this method to recursively construct a permutation that has a
larger sum until we arrive at the permutation $\sigma_{0}$, indicating that
$\sigma_{0}$ is the dominant permutation.

Let $j^{\prime}=\sigma^{-1}(j)$. We define the permutation $\hat{\sigma}$ as

$\displaystyle\hat{\sigma}=\begin{cases}\sigma(i)&i\neq j,j^{\prime}\\\
\sigma(j^{\prime})=j&i=j\\\ \sigma(j)&i=j^{\prime}.\end{cases}$

Note that $j^{\prime}>j$ and $\sigma(j)>\sigma(j^{\prime})=j$ by the
definition of $j$ and $j^{\prime}$. From the definition, it is also clear to
see that $\hat{\sigma}(i)=i$ for all $i\leq j$. We look at the difference
between the sum corresponding to the permutation $\hat{\sigma}$ and the sum
for the permutation $\sigma$ and prove that it is strictly positive.

$\displaystyle\sum\limits_{i=1}^{k}\hat{M}{(\hat{\sigma}(i),i)}-\sum\limits_{i=1}^{k}\hat{M}{(\sigma(i),i)}=\hat{M}{(\hat{\sigma}(j),j)}+\hat{M}{(\hat{\sigma}(j^{\prime}),j^{\prime})}-\hat{M}{(\sigma(j),j)}-\hat{M}{(\sigma(j^{\prime}),j^{\prime})}.$

We divide the rest of the proof into three cases: (1) $j\leq k-r,\sigma(j)\leq
k-r$, (2) $j\leq k-r,\sigma(j)>k-r$ and (3) $j>k-r$ and argue for each case
that the difference between sums above is strictly positive.

  * (1)

$j\leq k-r,\sigma(j)\leq k-r$: The difference between sums reduces to the
following expression in this case:

$\displaystyle
M^{(1)}(i_{\hat{\sigma}(j)},j)+M^{(1)}(i_{\hat{\sigma}(j^{\prime})},j^{\prime})-M^{(1)}(i_{\sigma(j)},j)-M^{(1)}(i_{\sigma(j^{\prime})},j^{\prime})=(i_{\sigma(j)}-i_{\sigma(j^{\prime})})(j^{\prime}-j)>0.$

  * (2)

$j\leq k-r,\sigma(j)>k-r$: The difference between sum reduces to the following
expression:

$\displaystyle
M^{(1)}(i_{\hat{\sigma}(j)},j)+M^{(0)}(i_{\hat{\sigma}(j^{\prime})},j^{\prime})-M^{(0)}(i_{\sigma(j)},j)-M^{(1)}(i_{\sigma(j^{\prime})},j^{\prime})=(k-1+i_{\sigma(j)}-i_{\sigma(j^{\prime})})(j^{\prime}-j)>0.$

  * (3)

$j>k-r$: The difference between sums reduces to the following expression:

$\displaystyle
M^{(0)}(i_{\hat{\sigma}(j)},j)+M^{(0)}(i_{\hat{\sigma}(j^{\prime})},j^{\prime})-M^{(0)}(i_{\sigma(j)},j)-M^{(0)}(i_{\sigma(j^{\prime})},j^{\prime})=(i_{\sigma(j)}-i_{\sigma(j^{\prime})})(j^{\prime}-j)>0.$

$\Box$

By applying Lemma 6, we obtain the following result on the structure of
constrained dominant submatrices.

######  Corollary 1.

Let $r\in[0:k]$, $w_{0},w_{1}\in[0:n]$ such that $w_{0}\geq r,w_{1}\geq k-r$
and $\hat{M}$ be a $((w_{0}+w_{1})\times k)$ matrix formed by augmenting the
$w_{0}$ rows of $M^{(0)}$ followed by $w_{1}$ rows of $M^{(1)}$. Among the
$(k\times k)$ submatrices of $\hat{M}$ that pick first $r$ rows from $M^{(0)}$
and later $(k-r)$ rows from $M^{(1)}$, the submatrix
$\hat{M}([w_{0}-r+1:w_{0}-r+k],:)$ has the largest dominant sum.

###### Proof.

From property P3 shown in Lemma 6 it follows that any constrained submatrix
$\hat{M}({\cal A},:)$ has a dominant permutation if $|{\cal A}\cap[w_{0}]|=r$
and $|{\cal A}\cap[w_{0}+1:w_{0}+w_{1}]|=k-r$. The constraint comes from the
fact that the first $r$ rows of the submatrix come from $M^{(0)}$ and the rest
$(k-r)$ come from $M^{(1)}$. From P1, the elements in $M^{(0)}$ increase from
top to bottom. Therefore it follows that for any ${\cal A}$ such that ${\cal
A}\cap[w_{0}]\neq[w_{0}-r+1:w_{0}]$, the dominant sum of $\hat{M}({\cal A},:)$
is strictly smaller than $\hat{M}(\hat{\cal A},:)$ where $\hat{\cal
A}=[w_{0}-r+1:w_{0}]\cup({\cal A}\cap[w_{0}+1:w_{0}+w_{1}])$. Similarly from
P2, the elements in $M^{(1)}$ decrease from top to bottom. Therefore, it
follows that for any ${\cal A}$ such that ${\cal
A}\cap[w_{0}+1:w_{0}+w_{1}]\neq[w_{0}+1:w_{0}+k-r]$, the dominant sum of
$\hat{M}({\cal A},:)$ is strictly smaller than $\hat{M}(\tilde{\cal A},:)$
where $\tilde{\cal A}=({\cal A}\cap[w_{0}])\cup[w_{0}+1:w_{0}+k-r]$.
Therefore, the dominant sum of submatrix $\hat{M}([w_{0}-r+1:w_{0}+k-r],:)$ is
the largest indicating that it is the constrained dominant submatrix. ∎

We now have all the results needed to prove the Theorem 1.

_Proof of Theorem 1:_ We will show that there exists a dominant permutation
for $M_{\text{dec}}$, provided $\\{n_{1},\ldots,n_{\ell}\\}$ satisfy the
properties (1)–(3). This will, in turn, prove that the corresponding $G_{dec}$
is invertible due to Lemma 1, thereby proving the Theorem 1.

####  -D1 Constrained Dominant Submatrix of Thick Column $(\ell-\mu)$ for
$\mu\in[0:\ell-1]$

From the Lemmas 4 and 5, if there exists a dominant permutation $\sigma^{*}$
of $M_{\text{dec}}$, for the $(\ell-\mu)$-th thick column it needs to pick
$r_{\mu}$ rows from within indices $\hat{\cal B}_{\ell-\mu}$ and $(k-r_{\mu})$
rows from indices $\hat{\cal B}_{\ell-\mu+1}$. This is same as picking
$r_{\mu}$ rows from matrix $M^{(0)}({\cal R}_{\ell-\mu},:)$ and $(k-\mu)$ rows
from matrix $M^{(1)}({\cal R}_{\ell-\mu+1},:)$. See Fig. 8 for an
illustration.

From Corollary 1, it follows picking the last $r_{\mu}$ rows of $M^{(0)}({\cal
R}_{\ell-\mu},:)$ out of the $n_{\ell-\mu}$ rows and the first $(k-r_{\mu})$
rows of $M^{(1)}({\cal R}_{\ell-\mu+1},:)$ out of the $n_{\ell-\mu+1}$ rows
results in the largest dominant sum. Therefore the rows of the constrained
dominant submatrix that can be picked for the thick column ${\cal
A}_{\ell-\mu}$ are given by:

$\displaystyle{\cal B}_{\ell-\mu}$ $\displaystyle=$
$\displaystyle[\sum\limits_{i=1}^{\ell-\mu}n_{i}-r_{\mu}+1:\sum\limits_{i=1}^{\ell-\mu}n_{i}-r_{\mu}+k]$
$\displaystyle=$ $\displaystyle[(\ell-\mu-1)k+1:(\ell-\mu)k]={\cal
A}_{\ell-\mu}.$

This indicates that the constrained dominant sub matrix of $\hat{M}(:,{\cal
A}_{\ell-\mu})$ is $\hat{M}({\cal A}_{\ell-\mu},{\cal A}_{\ell-\mu})$.

####  -D2 Disjoint Row Property

It is clear to see that the rows selected by the constrained dominant
submatrices, ${\cal B}_{\ell-\mu}={\cal A}_{\ell-\mu}$ are disjoint.
Therefore, by the submatrix decomposition strategy given in Remark 2, there
exists a dominant permutation $\sigma^{*}$ and it is such that
$\sigma^{*}({\cal A}_{\ell-\mu})={\cal A}_{\ell-\mu}$ for all
$\mu\in[0:\ell-1]$.

####  -D3 Field Size Requirement

Since the largest term in the matrices $M^{(0)}$, $M^{(1)}$ is $(n-1)k$, it
can be noted that the dominant sum of any decoding matrix will be at most
$(n-1)k^{2}(\tau+1)$. Therefore, given $d>(n-1)k^{2}(\tau+1)$, by Lemma 1,
$G_{\text{dec}}$ is invertible for any $(n,k,m,\tau)$-acceptable erasure
pattern. $\Box$

###  -E Superregular Matrix

Each product of the form $\prod_{i=1}^{x}A({\sigma(i),i})$ in (3)
corresponding to the permutation $\sigma$, is referred to as a term. A term is
a trivial term if $A({\sigma(i),i})=0$ for some $i\in[x]$. Consider a $y\times
z$ matrix $B$. An $x\times x$ square submatrix $C$ of $B$ is said to be a non-
trivial submatrix if at least one of the terms in the Leibniz formula for
$\det(C)$ is non-trivial. The matrix $B$ is superregular if all its non-
trivial submatrices are non-singular.

###  -F Proof of Theorem 2

We first restate a theorem from [22] that presents an explicit construction of
superregular matrix. See Appendix -E for the definition of superregular
matrices.

######  Theorem 3.

Let $\alpha$ be a primitive element of a finite field $\mathbb{F}_{p^{d}}$ and
$B=[v_{i,j}]$ be a matrix over $\mathbb{F}_{p^{d}}$ with the following
properties

  * •

if $v_{i,j}\neq 0$ then $v_{i,j}=\alpha^{\beta_{i,j}}$ for a positive integer
$\beta_{i,j}$;

  * •

if $v_{i,j}=0$ then $v_{i^{\prime},j}=0$ , for any $i^{\prime}>i$ or
$v_{i,j^{\prime}}=0$, for any $j^{\prime}>j$;

  * •

if $j^{\prime}<j$ and $v_{i,j}\neq 0$ and $v_{i,j^{\prime}}\neq 0$ then
$2\beta_{i,j}\leq\beta_{i,j^{\prime}}$.

  * •

if $i<i^{\prime}$ and $v_{i,j}\neq 0$ and $v_{i^{\prime},j}\neq 0$ then
$2\beta_{i,j}\leq\beta_{i^{\prime},j}$.

Suppose $d$ is greater than any exponent of $\alpha$ appearing as a non-
trivial term in the Leibniz formula for the determinant of any square
submatrix of $B$. Then $B$ is superregular.

Figure 10: Let $\check{G}=\alpha^{\check{M}}$. For $(n=4,k=2,m=2)$ example
construction given in Example 2, the figure shows the matrix $\check{M}$ for
$\ell=4$ case.

_Proof of Theorem 2:_ As in the beginning of Appendix -D, we can assume
without loss of generality that $\theta_{i}=0$ and $\theta_{i+1}=\ell$. Let
$\check{G}$ be the $n\ell\times k\ell$ matrix such

$\begin{bmatrix}\underline{c}(1)\\\ \vdots\\\
\underline{c}(\ell)\end{bmatrix}=\check{G}\begin{bmatrix}\underline{s}(1)\\\
\vdots\\\ \underline{s}(\ell)\end{bmatrix}.$

See Fig. 10 for an example illustration of $\check{G}$ matrix. It can be
verified that $\check{G}$ satisfies all the four conditions stated in Theorem
3. Now recall the definition of the $\ell k\times\ell k$ matrix
$G_{\text{dec}}$ in (4). It can be seen that $G_{\text{dec}}$ is a square
submatrix of $\check{G}$. The code defined in Construction B is an
$(n,k,m,\tau)$ $i$DOS code if $G_{\text{dec}}$ is non-singular for any
$\\{n_{1},\ldots,n_{\ell}\\}$ corresponding to an $(n,k,m,\tau)$-acceptable
symbol erasure pattern. Since all $M^{(t)}(i,j)\leq 2^{mn+n+k-2},$ the
exponent of $\alpha$ appearing as a non-trivial term in the determinant of any
square submatrix of $\check{G}$ is upper bounded by $2^{((m+1)n+k-2)}\ell k$.
If $\ell\leq\tau+1$, $\check{G}$ is superregular due to Theorem 3 and every
non-trivial square submatrix of $\check{G}$ is non-singular. For all
$(n,k,m,\tau)$-acceptable symbol erasure patterns, we have $\ell\leq\tau+1$.
By superregular property of $\check{G}$, to show that $G_{\text{dec}}$ is non-
singular, it suffices to show that the determinant of $G_{\text{dec}}$ has a
non-trivial term. This follows from [17, Lemma 4], in which it is shown that
all the diagonal entries are non-zero for $G_{\text{dec}}$ of any
$(n,k,m,\tau)$-acceptable symbol erasure pattern. $\Box$


#  On Clique Version of the Randic Index

Hossein Teimoori Faal  Department of Mathematics and Computer Science,
Allameh Tabataba’i University, Tehran, Iran

###### Abstract.

In this paper, we first review the weighted-version of the handshaking lemma
based on the idea of a weighted vertex-edge incidence matrix of a given graph
$G$. Then, we obtain a generalized version of the handshaking lemma based on
the concept of the clique value. We also define a generalized version of
Randic index. More importantly, we prove an upper bound for the generalized
Randic index of a graph $G$. We finally concluse the paper with some
disscussions about possible future works.

##  1\. Introduction and Motivation

One of the important parameters of a simple, finite graph is the _degree_ of a
vertex. It simply reflects a topological property of a graph which is the size
of an _open neighborhood_ of a given vertex. Therefore, one interesting line
of research in graph theory is to generalize this local concept and also
seeking for its potential applications.
In [1], the author of this paper has suggested an extension this concept to
the value of an edge $e=\\{u,v\\}$ as the size of the intersection of the open
neighborhoods of its end-vertices; that is $val_{G}(e)=|N_{G}(u)\cap
N_{G}(v)|$ . He also has used this idea in [1] to find a new upper bound for
the number of edges with respect to the number of triangles in any
$K_{4}$-free graph.
The well-known $Randi\check{c}$ index $R(G)$ of a graph $G$ was introduced in
1975 by $Randi\check{c}$ [2]. More precisely, he has defined it by

(1.1) $R(G):=\sum_{\\{u,v\\}\in E(G)}\frac{1}{\sqrt{deg_{G}(u)deg_{G}(v)}}.$

Indeed, in this paper we will call it the _vertex-version_ of $Randi\check{c}$
index. It seems that this parameter is very useful in _mathemaical chemistry_
and has been extensively investigated in the literature (see [3] and the
references therein). It is worth to mention the following two classical
results in the context of $Randi\check{c}$ index.

######  Theorem 1.1 (Bollobas and Erdos [4]).

For any connected graph $G$ with $n$ vertices, $R(G)\geq\sqrt{n-1}$ with
equality if and only if $G\cong K_{1,n-1}$.

######  Theorem 1.2 (Fajtlowicz [5]).

For a graph $G$ with $n$ vertices, $R(G)\leq\frac{n}{2}$ with equality if and
only if each component of $G$ has alt least two vertices and is regular.

Our main goal in this paper is to obtain an extension of Theorem 1.2, based on
the idea of the value of a clique.

##  2\. Basic Definitions and Notations

We assume that our graphs are simple, finite and undirected. For a given graph
$G=(V,E)$ and a vertex $v\in V(G)$, the set of vertices adjacent to $v$ is
called the _open neighborhood_ of $v$ in $G$ and will be denoted by $N_{G}(v)$
.

The cardinality of $N_{G}(v)$ is called the _degree_ of $v$ and is denoted by
$\deg_{G}(v)$. A complete subgraph of $G$ is called a _clique_ of $G$. A
clique on $k$ vertices is called a $k$-clique. A clique on $3$ vertices is
called a triangle. We will denote the set of triangles of $G$ by $T(G)$. We
denote the set of all $k$-cliques of $G$ by $\Delta_{k}(G)$ . The number of
$k$-cliques of $G$ is denoted by $c_{k}(G)$. We also recall that the well-
known _Cauchy-Schwartz_ is the following inequality.

######  Lemma 2.1.

[Geometric-Harmonic Mean Inequality] For any real sequences
$\\{a_{k}\\}_{k\geq 1}$, we have

(2.1) $\sqrt[k]{a_{1}a_{2}\cdots
a_{k}}\geq\frac{k}{\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{k}}},$

with equality whenever $a_{1}=a_{2}=\cdots=a_{k}$.

In what follows, we quickly review the weighted-version of the well-known
handshaking lemma and one of its consequences which is known as Mantel’s
theorem for triangle-free graphs.
The _weighted-version_ of the well-known _handshaking lemma_ can be read, as
follows. From now on, we will denote the set of non-negative real numbers with
$\mathbb{R}^{+}$.

######  Lemma 2.2 (Weighted Handshaking Lemma [6]).

Let $G=(V,E)$ be a graph and $f:~{}V(G)\mapsto\mathbb{R}^{+}$ be a non-
negative _weight_ function. Then, we have

(2.2) $\sum_{v\in V(G)}f(v)\deg_{G}(v)=\sum_{e=uv\in
E(G)}\Big{(}f(u)+f(v)\Big{)}.$

In particular, we have

(2.3) $\sum_{v\in V(G)}\deg^{2}_{G}(v)=\sum_{e=uv\in
E(G)}\Big{(}\deg_{G}(u)+\deg_{G}(v)\Big{)}.$

##  3\. A vertex-version of Randic index

In chemical graph theory literature, the _branching index_ of a given graph
$G$ is known as the $Randi\check{c}$ index of the graph $G$ denoted by $R(G)$.
Here, we will denote it by $R_{v}(G)$ and call it _vertex-version_
$Randi\check{c}$ index of $G$. It is defined, as follows

(3.1) $R_{v}(G)=\sum_{e=uv\in E(G)}\frac{1}{\sqrt{\deg_{G}(u)\deg_{G}(v)}}.$

In [6], the following result is proved by a simple argument based on the
_weighted version of handshaking_ lemma and _geometric-harmonic mean_
inequality.

######  Theorem 3.1 ([5]).

For a graph $G$ of order $n$,

$R_{v}(G)\leq\frac{n}{2},$

with equality if and only if every component of $G$ is regular and $G$ has no
isolated vertices.

For the sake of completeness, here we also provide a short proof of Theorem
3.1 based on the reference [6].

###### Proof.

First, we note that by defining the function $f$ in the equation (2.2) by

$\big{(}f(v)=\begin{cases}\frac{1}{\deg_{G}(v)}&\textnormal{if}~{}\deg_{G}(v)>0,\\\
1&\textnormal{if}~{}\deg_{G}(v)=0,\end{cases}$

we obtain

(3.2) $\sum_{uv\in
E(G)}\Big{(}\frac{1}{\deg_{G}(u)}+\frac{1}{\deg_{G}(v)}\Big{)}=n-n_{0},$

where $n_{0}$ denotes the number of isolated vertices in $G$.
Now considering the _geometric-harmonic_ inequality for $k=2$, Lemma 2.1, we
have

$\displaystyle R_{v}(G)$ $\displaystyle=$ $\displaystyle\sum_{e=uv\in
E(G)}\frac{1}{\sqrt{\deg_{G}(u)\deg_{G}(v)}}$ $\displaystyle\leq$
$\displaystyle\sum_{uv\in
E(G)}\frac{1}{2}\big{(}\frac{1}{\deg_{G}(u)}+\frac{1}{\deg_{G}(v)}\big{)}$
$\displaystyle=$ $\displaystyle\frac{n-n_{0}}{2}\leq\frac{n}{2},$

as required.

∎

##  4\. An edge-version of Randic index

In this section, we aim to obtain an edge version of the upper bound for the
$Randi\check{c}$ index, based on the new concept of the value of an edge.

######  Definition 4.1.

Let $G=(V,E)$ be a graph and $e=uv$ be an edge of $G$. Then, we define the
_edge value_ of $e$, denoted by $val_{G}(e)$, as follows

(4.1) $val_{G}(e)=|N_{G}(e)|=|N_{G}(u)\cap N_{G}(v)|.$

Here, $N_{G}(e)$ denotes the set of common neighbors of end vertices of the
edge $e$.

Next, we generalize the weighted handshaking lemma for values of edges of a
given graph.

######  Lemma 4.1.

[Weighted Edge Handshaking Lemma] Let $G=(V,E)$ be a graph and
$g:~{}E(G)\mapsto\mathbb{R}^{+}$ be a non-negative _weight_ function. Then, we
have

(4.2) $\sum_{e\in E(G)}g(e)val_{G}(e)=\sum_{\delta=e_{1}e_{2}e_{3}\in
T(G)}\Big{(}g(e_{1})+g(e_{2})+g(e_{3})\Big{)}.$

In particular, we have

(4.3) $\sum_{e\in E(G)}val^{2}_{G}(e)=\sum_{\delta=e_{1}e_{2}e_{3}\in
T(G)}\Big{(}val_{G}(e_{1})+val_{G}(e_{2})+val_{G}(e_{3})\Big{)}.$

As an immediate consequence of the above lemma, we have the following
interesting result. Recall that an edge $e\in E(G)$ is called _isolated_ if we
have $val_{G}(e)=0$ .

######  Corollary 4.2.

For any graph $G$ with $m$ edges, we have

(4.4) $\sum_{\delta=e_{1}e_{2}e_{3}\in
T(G)}\bigg{(}\frac{1}{val_{G}(e_{1})}+\frac{1}{val_{G}(e_{2})}+\frac{1}{val_{G}(e_{3})}\bigg{)}=m-m_{0},$

in which $m_{0}$ is the number of _isolated edges_.

Nect, we give a generalization of the result in [5]. To do so, we first need
to give a generalization of the concept of $Randi\check{c}$ index.

######  Definition 4.2.

For a given graph $G=(V,E)$, the edge-version of the $Randi\check{c}$ index,
denoted by $R_{e}(G)$, is defined as

(4.5) $R_{e}(G):=\sum_{\delta=e_{1}e_{2}e_{3}\in
T(G)}\frac{1}{\sqrt{val_{G}(e_{1})val_{G}(e_{2})val_{G}(e_{3})}}$

From now on, we will call a graph _edge-regular_ if $val_{G}(e)$ is the same
for all edges of $G$.

######  Theorem 4.3.

For a graph $G$ of size $m$, we have

$R_{e}(G)\leq\frac{m}{3},$

with equality if and only if every component of $G$ is edge-regular and $G$
has no isolated edges.

###### Proof.

Considering Corollary 4.2 and arithmetic-geometric inequality, we have

$\displaystyle R_{e}(G)$ $\displaystyle:=$
$\displaystyle\sum_{\delta=e_{1}e_{2}e_{3}\in
T(G)}\frac{1}{\sqrt{val_{G}(e_{1})val_{G}(e_{2})val_{G}(e_{3})}}$
$\displaystyle\leq$ $\displaystyle\frac{1}{3}\sum_{\delta=e_{1}e_{2}e_{3}\in
T(G)}\bigg{(}\frac{1}{val_{G}(e_{1})}+\frac{1}{val_{G}(e_{2})}+\frac{1}{val_{G}(e_{3})}\bigg{)}$
$\displaystyle=$ $\displaystyle\frac{1}{3}(m-m_{0})\leq\frac{m}{3}.$

∎

##  5\. the clique handshaking lemma

In this section, we attempt to find a more generalized version of
$Randi\check{c}$ index which we call it _the generalized_ $Randi\check{c}$
index. To this end, we first need to present an extension of the definition of
the degree of vertex to the value of any clique of higher order.

######  Definition 5.1.

Let $G=(V,E)$ be a graph and $q_{k}\in\Delta_{k}(G)$ be a $k$-clique in $G$.
Then, we define the value of the clique $q_{k}$ with the vertex set
$V(q_{k})=v_{i_{1}}\cdots v_{i_{k}}$ denoted by $val_{G}(q_{k})$, as follows

(5.1) $val_{G}(q)=\bigg{|}\bigcap_{i=1}^{k}N_{G}(v_{j_{i}})\bigg{|}.$

We will also call an $k$-clique $q_{k}$ with $val_{G}(q_{k})=0$, an _isolated_
clique of $G$.

Note that any $k$-clique $q_{k}=v_{i_{1}}\cdots v_{i_{k}}\in\Delta_{k}(G)$ in
$G$ can also be represented (uniquely) by $q_{k}=q_{k-1,1}\cdots q_{k-1,k}$
where for each $i=1,\ldots,k$ the symbol $q_{k-1,i}$ denotes a $(k-1)$-clique
subgraph of $q_{k}$. We will use this fact in our next key lemma.

######  Lemma 5.1 (Weighted Clique Handshaking Lemma).

Let $G=(V,E)$ be a graph and and let $h:~{}\Delta_{k}(G)\mapsto\mathbb{R}^{+}$
$(k\geq 2)$ be a _weight_ function. Then, we have

(5.2)
$\sum_{q_{k}\in\Delta_{k}(G)}h(q_{k})val_{G}(q_{k})=\sum_{q_{k+1}=q_{k,1}\cdots
q_{k,k+1}\in\Delta_{k+1}(G)}\Big{(}h(q_{k,1})+\ldots+h(q_{k,k+1})\Big{)}.$

In particular, we have

(5.3)
$\sum_{q_{k}\in\Delta_{k}(G)}val^{2}_{G}(q_{k})=\sum_{q_{k+1}=q_{k,1}\cdots
q_{k,k+1}\in\Delta_{k+1}(G)}\Big{(}val_{G}(q_{k,1})+\cdots+val_{G}(q_{k,k+1})\Big{)}.$

###### Proof.

We proceed by defining the weighted _subclique-superclique_ matrix
$I_{f,k}(G)$ of order $k$, as follows

$\big{(}I_{f,k}(G)\big{)}_{q_{k},q_{k+1}}=\begin{cases}h(q_{k})&\textnormal{if}~{}q_{k}~{}\textnormal{is~{}a~{}subgraph~{}of}~{}q_{k+1},\\\
0&\textnormal{ otherwise }.\end{cases}$

Next, we note that in the matrix $I_{f,k}(G)$ each row corresponding to the
clique $q_{k}$ has $val_{G}(q_{k})$ non-zero entries. Hence, the resulting
row-sum equals to $h(q_{k})val_{G}(q_{k})$ . On the other hand, each column
corresponding to the clique $q_{k+1}=q_{k,1}\cdots q_{k,k+1}$ has the column-
sum $h(q_{k,1})+\cdots+h(q_{k,k+1})$ . Thus, by summing over all rows and
columns and equating them we get the desired result.

∎

##  6\. The Generalized Randic Index

In this last section, we obtain a more generalized version of $Randi\check{c}$
index which we call it the _generalized $Randi\check{c}$ index_.
Next, we define the _generalized $Randi\check{c}$ index_ of a graph $G$ or a
_cliuqe-version_ of the $Randi\check{c}$ index based on the new concept of the
_clique value_ in graph theory.

######  Definition 6.1.

Let $G=(V,E)$ be a graph. Then, the _generalized $Randi\check{c}$ index_ of
$G$, denoted by $R_{cliq}(G)$, is defined by

(6.1) $R_{clq}(G;k):=\sum_{q_{k+1}=q_{k,1}\cdots
q_{k,k+1}\in\Delta_{k+1}(G)}\frac{1}{\sqrt{\prod_{j=1}^{k+1}val_{G}(q_{k,j})}},~{}~{}~{}(k\geq
1)$

We first need the following key result.

######  Proposition 6.1.

Let $G=(V,E)$ be a graph. Then, we have

(6.2) $\sum_{q_{k+1}=q_{k,1}\cdots
q_{k,k+1}\in\Delta_{k+1}}\bigg{(}\frac{1}{val_{G}(q_{k,1})}+\cdots+\frac{1}{val_{G}(q_{k,k+1})}\bigg{)}=c_{k}(G)-c_{k,0}(G),$

in which $c_{k,0}(G)$ is the number of isolated $k$-cliques of $G$.

Now, we are at the position to state the main result of this paper which a
generalized version of the result in [5]. Form now one, a graph in which all
values of $val_{G}(q_{k})$ are the same for $k$-cliques of $G$ is called
$k$-_clique regular_ graph.

######  Theorem 6.2.

Let $G$ be a graph. Then, we have

(6.3) $R_{clq}(G;k)\leq\frac{c_{k}(G)}{k+1}.$

The equality holds if and only if each component of $G$ is a $k$-clique
regular graphs.

###### Proof.

The proof is straight forward based on Proposition 6.1 and the arithmetic-
geometric mean inequality 2.1.

∎

## References

  * [1] H. Teimoori, ON CLIQUE VALUES IDENTITIES AND MANTEL-TYPE THEOREMS, Transactions on Combinatorics, 9 (2020) pp. 139–146.
  * [2] M. Randic, On characterization of molecular branching, J. Am. Chem. Soc., 97 (1975), pp. 6609–6615.
  * [3] X. Li and I. Gutman, Mathematical Aspects of Randi´c-Type Molecular Structure Descriptors University of Kragujevac, Kragujevac, (2006).
  * [4] B. Bollobás and P. Erdos, Graphs of extremal weights, Ars Combin., 50 (1998), pp. 225–-233.
  * [5] S. Fajtlowicz, Written on the Wall, a list of conjectures of Graffiti, Available from the author.
  * [6] B. Wu, The weighted version of the handshaking lemma with an application, J. Inequalities and Applications, 1 (2014), pp. 225–-233.