# Agents Network on a Grid: An Approach with the Set of Circulant Operators

B. Birregah, Prosper K. Doh, Kondo Hloindo Adjallah

► To cite this version:

B. Birregah, Prosper K. Doh, Kondo Hloindo Adjallah. Agents Network on a Grid: An Approach with the Set of Circulant Operators. International journal of mathematical and computational methods (IJMCM), 2008, 2 (11), pp.879-884. 10.5281/zenodo.1075378. hal-03044965

HAL Id: hal-03044965

https://hal.univ-lorraine.fr/hal-03044965

Submitted on 7 Dec 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Agents Network on a Grid: An Approach with the Set of Circulant Operators

Babiga Birregah, Prosper K. Doh, and Kondo H. Adjallah

**Abstract**— In this work we present some matrix operators named circulant operators and their action on square matrices. This study on square matrices provides new insights into the structure of the space of square matrices. Moreover it can be useful in various fields as in agents networking on Grid or large-scale distributed self-organizing grid systems.

**Keywords**— Pascal matrices, Binomial Recursion, Circulant Operators, Square Matrix Bipartition, Local Network, Parallel networks of agents.

## I. INTRODUCTION

This section is dedicated to the presentation of the set of circulant operators. These operators are presented as transformations of the generic matrix subscript vector $(i, j)$ for $0 \le i, j \le n$.

**Definition 1: The circulant operators**

The $\alpha$-circulant operator

$$ (i, j) \xrightarrow{\alpha} (i, i+j) \quad \mod n+1 $$

The $\beta$-circulant operator

$$ (i, j) \xrightarrow{\beta} (-1+i-j, j) \quad \mod n+1 $$

The $\gamma$-circulant operator

$$ (i, j) \xrightarrow{\gamma} (i-j, j) \quad \mod n+1 $$

$\delta$-circulant operator

$$ (i, j) \xrightarrow{\delta} (i, 1+i+j) \quad \mod n+1 $$

One can easily notice that $\alpha$ and $\delta$ globally preserve rows, while $\beta$ and $\gamma$ globally preserve the columns.

For $\omega \in \{\alpha, \beta, \delta, \gamma\}$, we denote, in the sequel, by $\omega A$ the image of the matrix $A$ by the transformation $\omega$ and thus:

$$ [\omega A]_{\omega(i,j)} = [A]_{i,j} \quad (1) $$

The following algorithm gives the way one can compute the image of a given square $(n+1) \times (n+1)$ matrix $A$ by the

Manuscript received September 01, 2006. This work was supported by the project STICO of I.C.D. at University of Technology of Troyes (UTT) in the case of the first author.

Babiga Birregah is PhD student at University of Lomé, College of Science, Applied Math. Dpt., BP. 1515, TOGO (e-mail: bbirregah@tg.refer.org).

Prosper K. Doh is with University of Nancy2, 23, boulevard Albert 1er, BP 3397, F54015 Nancy Cedex, FRANCE (e-mail: Prosper.Doh@univ-nancy2.fr).

Kondo H. Adjallah is with University of Technology of Troyes, Institute Charles Delaunay, 12 rue Marie Curie, F10010 Troyes Cedex France, (Tel. +33 325715631, Fax. +33 325715649, e-mail: kondo.adjallah@utt.fr).

operator $\omega$.

**Algorithm 1 Computing of the matrix $\omega A$**

1. **for all** $i$ such that $0 \le i \le n$ **do**

2. **for all** $j$ such that $0 \le j \le n$ **do**

3. $[Temp]_{i,j} := [A]_{i,j}$
   $(i, j) := \omega(i, j)$
   $[\omega A]_{i,j} := [Temp]_{i,j}$

4. **end for**

5. **end for**

As illustration, we show below how $\alpha$ transforms a square matrix $A$.

$$ A = \begin{pmatrix} a & b & c & d \\ e & f & g & h \\ i & j & k & l \\ m & n & o & p \end{pmatrix}, \quad \alpha A = \begin{pmatrix} a & b & c & d \\ h & e & f & g \\ k & l & i & j \\ n & o & p & m \end{pmatrix} $$

These circulant transformations provide a useful framework for investigating the set of square matrices as it will be presented in section II. This study on square matrices provides new insights into the structure of the space of square matrices. In [8] we investigate the set of twelve triangular matrix forms of the Pascal Triangle with the circulant operators. This investigation confirms the importance of these operators in matrices study. Moreover it can intervene in various fields in agents networking on Grid or large-scale distributed self-organizing grid systems.

## II. ACTION OF CIRCULANT OPERATORS ON SQUARE MATRICES

### A. Triangular Bipartition of a Square Matrix

Now we give four definitions of the four bipartitions of any square matrix $A$ (See figure 1).

In each definitions below, $A$ is a $(n+1) \times (n+1)$ matrix with subscripts $i$ and $j$ range from 0 to $n$.

**Definition 2: The North-East/south-west bipartition**

The matrices $A^{NE}$ and $A^{sw}$, given by:

$$ [A^{NE}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i \le j \\ 0 & \text{if } i > j \end{cases} $$

and

$$ [A^{sw}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i > j \\ 0 & \text{if } i \le j \end{cases} $$

define the North-East/south-west bipartition of $A$ and

$$ A = A^{NE} + A^{sw} \equiv A^{NE/sw} $$
<figure><img src="image_2.png" /><figcaption>Fig. 1. Four bipartitions of a square matrix. The triangular sub-blocks in full line are those which include the main diagonal (NE/sw and SW/ne) or the anti-diagonal (NW/se, SE/nw). These sub-blocks are labelled with capital letters.</figcaption></figure>

**Definition 3: The South-West/north-east bipartition**

The matrices $A^{SW}$ and $A^{ne}$, given by:

$$[A^{SW}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i \ge j \\ 0 & \text{if } i < j \end{cases}$$

and

$$[A^{ne}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i < j \\ 0 & \text{if } i \ge j \end{cases}$$

define the **South-West/north-east** bipartition of A and

$$A = A^{SW} + A^{ne} \equiv A^{SW/ne}$$

**Definition 4: The North-West/south-east bipartition**

The matrices $A^{NW}$ and $A^{se}$, given by:

$$[A_{NW}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i + j \le n \\ 0 & \text{if } i + j > n \end{cases}$$

and

$$[A^{se}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i + j > n \\ 0 & \text{if } i + j \le n \end{cases}$$

define the **North-West/south-east** bipartition of A and

$$A = A^{NW} + A^{se} \equiv A^{NW/se}$$

**Definition 5: The South-East/north-west bipartition**

The matrices $A^{SE}$ and $A^{nw}$, such that:

$$[A^{SE}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i + j \ge n \\ 0 & \text{if } i + j < n \end{cases}$$

and

$$[A^{nw}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i + j < n \\ 0 & \text{if } i + j \ge n \end{cases}$$

define the **South-East/north-west** bipartition of A and

$$A = A^{SE} + A^{nw} \equiv A^{SE/nw}$$

If A is triangular, with $[A^B]_{i,j} = 0 \forall i, j$ then:

$$A^{B/B'} = A^B \quad \text{or} \quad A^{B'/B} = A^B$$

## B. Action of Circulant Operators on a Square Matrix

Now it is possible to derive twelve new matrices starting with a square matrix [2], [8]. Denoting the initial matrix A by $A_{1,n}$, the set $A_n$ of its transformation with circulant operators

can be derived in a particular order as shown in the following sequence:

$$\begin{align*} \mathbf{A}_{1,n} & \xrightarrow{\beta} A_{2,n} \xrightarrow{\delta} A_{3,n} \xrightarrow{\gamma} A_{4,n} \xrightarrow{\alpha} A_{5,n} \\ A_{5,n} & \xrightarrow{\beta} A_{6,n} \xrightarrow{\delta} A_{7,n} \xrightarrow{\gamma} A_{8,n} \xrightarrow{\alpha} A_{9,n} \\ A_{9,n} & \xrightarrow{\beta} A_{10,n} \xrightarrow{\delta} A_{11,n} \xrightarrow{\gamma} A_{12,n} \xrightarrow{\alpha} \mathbf{A}_{1,n} \end{align*}$$

The four bipartitions of the square matrix lead to a partition of $A_n$ into four subsets as it is described in Table I. One can observe that the subsets in the first column of this Table (up to down) are globally invariant by the action of (respectively) $\alpha\gamma\delta\beta$, $\beta\alpha\gamma\delta$, $\delta\beta\alpha\gamma$ and $\gamma\delta\beta\alpha$.

It is important to notice that for a given subset $A_n^{B/B'}$, each matrix $A_{k,n}$ is assumed to be put into the particular bipartition $A_{k,n}^{B/B'}$. More precisely, beginning with $A_{k,n}^{B/B'}$ and the appropriate operator (as it is shown in Fig. 2), one can derives the four subsets $A_n^{NE/sw}$, $A_n^{SE/nw}$, $A_n^{SW/ne}$ and $A_n^{NW/se}$. That will not be the case if one choose a bipartition with the *wrong* operator.

It follows that:

$$\begin{align*} A_n^{NE/sw} & \xrightarrow{\beta} A_n^{SE/nw} \xrightarrow{\delta} A_n^{SW/ne} \xrightarrow{\gamma} \\ A_n^{NW/se} & \xrightarrow{\alpha} A_n^{NE/sw} \end{align*}$$

<figure><img src="image_3.png" /><figcaption>Fig. 2 The bipartitions linked by circulant operators</figcaption></figure>

One can represent as in Fig. 3 a graph with $A_n$ as set of vertices, and the circulant operators as transition labels. As one can expect this graph turns out into a cycle or a ring.

<table><caption>TABLE I
PARTITION OF THE SET $A_n$</caption><thead><tr><th>Subsets</th><th colspan="3">Matrices</th></tr></thead><tbody><tr><td>$A_n^{NE/sw}$</td><td>A<sub>1,n</sub></td><td>A<sub>5,n</sub></td><td>A<sub>9,n</sub></td></tr><tr><td>$A_n^{SE/nw}$</td><td>A<sub>2,n</sub></td><td>A<sub>6,n</sub></td><td>A<sub>10,n</sub></td></tr><tr><td>$A_n^{SW/ne}$</td><td>A<sub>3,n</sub></td><td>A<sub>7,n</sub></td><td>A<sub>11,n</sub></td></tr><tr><td>$A_n^{NW/se}$</td><td>A<sub>4,n</sub></td><td>A<sub>8,n</sub></td><td>A<sub>12,n</sub></td></tr></tbody></table>

**Example:**

For illustration, here is the case of a 5 × 5 matrix A below.
<figure><img src="image_4.png" /><figcaption>Fig. 3. Ring behavior of A. This graph can be read in two different ways: - counterclockwise if the input alphabet is S , - clockwise if the input alphabet is S − 1 the set of the inverses of our four operators.</figcaption></figure>

Beginning with $\beta$, $A$ must be put into $A^{NE/sw}$ bipartition.
To properly observe the properties of the operators, the
south-west block in $A$ is boldfaced to distinguish it from
the North-East one. This distinction is carried through the
transformations.

$$
A = A_{1,5} = \begin{pmatrix}
a_1 & a_2 & a_3 & a_4 & a_5 \\
\mathbf{b}_1 & b_2 & b_3 & b_4 & b_5 \\
\mathbf{c}_1 & \mathbf{c}_2 & c_3 & c_4 & c_5 \\
\mathbf{d}_1 & \mathbf{d}_2 & \mathbf{d}_3 & d_4 & d_5 \\
\mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_3 & \mathbf{e}_4 & \mathbf{e}_5
\end{pmatrix}
$$

$$
A_{2,5} = \beta A_{1,5} = \begin{pmatrix}
\mathbf{b}_1 & \mathbf{c}_2 & \mathbf{d}_3 & \mathbf{e}_4 & a_5 \\
\mathbf{c}_1 & \mathbf{d}_2 & \mathbf{e}_3 & a_4 & b_5 \\
\mathbf{d}_1 & \mathbf{e}_2 & a_3 & b_4 & c_5 \\
\mathbf{e}_1 & a_2 & b_3 & c_4 & d_5 \\
a_1 & b_2 & c_3 & d_4 & e_5
\end{pmatrix}
$$

$$
A_{3,5} = \delta A_{3,5} = \begin{pmatrix}
a_5 & \mathbf{b}_1 & \mathbf{c}_2 & \mathbf{d}_3 & \mathbf{e}_4 \\
a_4 & b_5 & \mathbf{c}_1 & \mathbf{d}_2 & \mathbf{e}_3 \\
a_3 & b_4 & c_5 & \mathbf{d}_1 & \mathbf{e}_2 \\
a_2 & b_3 & c_4 & d_5 & \mathbf{e}_1 \\
a_1 & b_2 & c_3 & d_4 & e_5
\end{pmatrix}
$$

$$
A_{4,5} = \gamma A_{3,5} = \begin{pmatrix}
a_5 & b_5 & c_5 & d_5 & e_5 \\
a_4 & b_4 & c_4 & d_4 & \mathbf{e}_4 \\
a_3 & b_3 & c_3 & \mathbf{d}_3 & \mathbf{e}_3 \\
a_2 & b_2 & \mathbf{c}_2 & \mathbf{d}_2 & \mathbf{e}_2 \\
a_1 & \mathbf{b}_1 & \mathbf{c}_1 & \mathbf{d}_1 & \mathbf{e}_1
\end{pmatrix}
$$

$$
A_{5,5} = \alpha A_{4,5} = \begin{pmatrix}
a_5 & b_5 & c_5 & d_5 & e_5 \\
\mathbf{e}_4 & a_4 & b_4 & c_4 & d_4 \\
\mathbf{d}_3 & \mathbf{e}_3 & a_3 & b_3 & c_3 \\
\mathbf{c}_2 & \mathbf{d}_2 & \mathbf{e}_2 & a_2 & b_2 \\
\mathbf{b}_1 & \mathbf{c}_1 & \mathbf{d}_1 & \mathbf{e}_1 & a_1
\end{pmatrix}
$$

$$
A_{6,5} = \beta A_{5,5} = \begin{pmatrix}
\mathbf{e}_4 & \mathbf{e}_3 & \mathbf{e}_2 & \mathbf{e}_1 & e_5 \\
\mathbf{d}_3 & \mathbf{d}_2 & \mathbf{d}_1 & d_5 & d_4 \\
\mathbf{c}_2 & \mathbf{c}_1 & c_5 & c_4 & c_3 \\
\mathbf{b}_1 & b_5 & b_4 & b_3 & b_2 \\
a_5 & a_4 & a_3 & a_2 & a_1
\end{pmatrix}
$$

$$
A_{7,5} = \delta A_{6,5} = \begin{pmatrix}
e_5 & \mathbf{e}_4 & \mathbf{e}_3 & \mathbf{e}_2 & \mathbf{e}_1 \\
d_5 & d_4 & \mathbf{d}_3 & \mathbf{d}_2 & \mathbf{d}_1 \\
c_5 & c_4 & c_3 & \mathbf{c}_2 & \mathbf{c}_1 \\
b_5 & b_4 & b_3 & b_2 & \mathbf{b}_1 \\
a_5 & a_4 & a_3 & a_2 & a_1
\end{pmatrix}
$$

$$
A_{8,5} = \gamma A_{7,5} = \begin{pmatrix}
e_5 & d_4 & c_3 & b_2 & a_1 \\
d_5 & c_4 & b_3 & a_2 & \mathbf{e}_1 \\
c_5 & b_4 & a_3 & \mathbf{e}_2 & \mathbf{d}_1 \\
b_5 & a_4 & \mathbf{e}_3 & \mathbf{d}_2 & \mathbf{c}_1 \\
a_5 & \mathbf{e}_4 & \mathbf{d}_3 & \mathbf{c}_2 & \mathbf{b}_1
\end{pmatrix}
$$

$$
A_{9,5} = \alpha A_{8,5} = \begin{pmatrix}
e_5 & d_4 & c_3 & b_2 & a_1 \\
\mathbf{e}_1 & d_5 & c_4 & b_3 & a_2 \\
\mathbf{e}_2 & \mathbf{d}_1 & c_5 & b_4 & a_3 \\
\mathbf{e}_3 & \mathbf{d}_2 & \mathbf{c}_1 & b_5 & a_4 \\
\mathbf{e}_4 & \mathbf{d}_3 & \mathbf{c}_2 & \mathbf{b}_1 & a_5
\end{pmatrix}
$$

$$
A_{10,5} = \beta A_{9,5} = \begin{pmatrix}
\mathbf{e}_1 & \mathbf{d}_1 & \mathbf{c}_1 & \mathbf{b}_1 & a_1 \\
\mathbf{e}_2 & \mathbf{d}_2 & \mathbf{c}_2 & b_2 & a_2 \\
\mathbf{e}_3 & \mathbf{d}_3 & c_3 & b_3 & a_3 \\
\mathbf{e}_4 & d_4 & c_4 & b_4 & a_4 \\
e_5 & d_5 & c_5 & b_5 & a_5
\end{pmatrix}
$$

$$
A_{11,5} = \delta A_{10,5} = \begin{pmatrix}
\mathbf{a}_1 & \mathbf{e}_1 & \mathbf{d}_1 & \mathbf{c}_1 & \mathbf{b}_1 \\
\mathbf{b}_2 & \mathbf{a}_2 & \mathbf{e}_2 & \mathbf{d}_2 & \mathbf{c}_2 \\
\mathbf{c}_3 & \mathbf{b}_3 & \mathbf{a}_3 & \mathbf{e}_3 & \mathbf{d}_3 \\
\mathbf{d}_4 & \mathbf{c}_4 & \mathbf{b}_4 & \mathbf{a}_4 & \mathbf{e}_4 \\
\mathbf{e}_5 & \mathbf{d}_5 & \mathbf{c}_5 & \mathbf{b}_5 & \mathbf{a}_5
\end{pmatrix}
$$

$$
A_{12,5} = \gamma A_{11,5} = \begin{pmatrix}
a_1 & a_2 & a_3 & a_4 & a_5 \\
b_2 & b_3 & b_4 & b_5 & \mathbf{b}_1 \\
c_3 & c_4 & c_5 & \mathbf{c}_1 & \mathbf{c}_2 \\
d_4 & d_5 & \mathbf{d}_1 & \mathbf{d}_2 & \mathbf{d}_3 \\
e_5 & \mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_3 & \mathbf{e}_4
\end{pmatrix}
$$

Pascal matrices are one of the best examples which show circulant operators importance in matrix theory. For more details about Pascal matrices one can see [1], [3], [4], [5] which present various formes of matrices related to Pascal triangle and [8] which presents the circulant operators as one basic tool for generating the Pascal matrices. Considering the calculation above it follows that one can derive twelve matrices from any of them. We intentionally boldface one triangular sub-block to show the state of the bipartitions as we progress in the transformations.

III. MANAGING COMMUNICATION PROTOCOLS IN A NETWORK

In this section the matrix $A$ will represent a network of agents $[A]_{i,j}$ performing a set $T = \{t_k, 1 \le k \le (n+1)^2\}$ of tests on a grid of $(n+1)^2$ components. Figure 4 shows a representation of a grid for $n=3$.

<figure><img src="image_5.png" /><figcaption>Fig. 4 Grid of 16 components (n=3)</figcaption></figure>

A. Assumptions and Definitions

Definition 6: Neighborhood

The neighborhood of an agent $[A]_{r,s}$ is the set
$N_{r,s} = N_{r,s}^{+} \cup N_{r,s}^{-}$

where:

$N_{r,s}^{+}$ is the set of all agents sending information to $[A]_{r,s}$

$\mathcal{N}_{r,s}^{-}$ is the set of all agents receiving information from $[A]_{r,s}$.

Definition 7: *Task*

A task is an arrangement of the tests $t_i$ on the grid.
## Definition 8: Job

A Job is an arrangement of a subset of $T$ (the set of all tests $t_i$) on a sub-block of the grid.

We make the following assumptions:

* Each agent can receive information from only two agents and send messages to two others of its neighborhood. So $|N_{r,s}^+| = |N_{r,s}^-| = 2$.

* For $Ag \in N_{r,s}^+$ there exists $Ag' \in N_{r,s}^-$ such that $Ag, [A]_{r,s}$ and $Ag'$ are either in the same row, or in the same diagonal, or in the same column. Figure 5 shows an example of protocol. Thus the set $N_{r,s}$ is well determined by $N_{r,s}^+$ or $N_{r,s}^-$.

* Each agent can perform any of the $(n+1)^2$ tests.

* The agents network $A$ can dynamically reconfigure itself on the grid. As a result of this reconfiguration the topology of the network can change [6], [7].

For a permutation $\sigma$ on the set $\chi = \{(i, j), 0 \le i, j \le n\}$, let us denote by $\sigma A$ the matrix obtained by updating the cell $\sigma(i, j)$ by the agent $[A]_{i, j}$, then:

$$ \sigma A_n \equiv \{\sigma A, A \in A_n\} \quad (2) $$

<figure><img src="image_6.png" /><figcaption>Fig. 5. The protocol $P_{1,n}^{ij}$: the agent $[A]_{i,j}$ and its neighborhood</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6. Twelve Protocols generated by circulant operators displayed in the same order as they are generated (left to right and top to bottom). A fourth agent is accessory used to help the reader to localise the neighborhood $N_{r,s}^+$ of $[A]_{r,s}$ (in gray)</figcaption></figure>

## Definition 9: Communication protocol

For a given network $A$, where $[A]_{i,j}$ is performing the task $t_{j+1+(n+1)i}$, the set

$$ \mathcal{P} = \{(t_{k_1}, t_{k_2}, t_{j+1+(n+1)i}, t_{k_r} \in N_{i,j}^+, 0 \le i, j \le n) \text{ defines the communication protocol of } A. $$

Since $t_{k_r} \in N_{i,j}^+$, $k_r$ is a function of the entries $i, j$. As example, figure 5 shows the case

$$ \begin{cases} k_1 = j + (n+1)(i-1) \\ k_2 = j + 1 + (n+1)(i-1) \end{cases} $$

below denoted for more convenience by:

$$ P_{1,n}^{ij} : \begin{bmatrix} i-1 \\ j-1 \end{bmatrix} \star \begin{bmatrix} i \\ j-1 \end{bmatrix} \rightarrow \begin{bmatrix} i \\ j \end{bmatrix} \quad (3) $$

This notation remind the well-known binomial recursion in Pascal matrices. In the sequel, the reader must keep in mind the fact that in the notation $P_{k,n}^{r,s}$ the entries $(r, s)$ are computed modulus $(n+1)$.

## B. Transformation of a Protocol with Circulant Operators

Let's consider a network $A$ dealing with the protocol $P_{1,n}^{ij}$, and its bipartition $A^{NE/sw}$.

Figure 6 shows eleven protocols derived from $P_{1,n}^{ij}$ denoted $P_{k,n}^{ij}$, where:

Although the topology of the network changes through this generation, the neighborhood of a target component remains the same. This result is given by the following theorem.

**Theorem 10:** Let $\omega$ be a circulant operator and
$$ P_{k,n}^{ij} \xrightarrow{\omega} P_{k+1,n}^{rs} $$
Then $N_{i,j} = N_{r,s}$

**Proof:**

One can easily establish that $N_{i,j}^- = N_{r,s}^-$ for the cases $\omega \in \{\alpha, \beta, \gamma, \delta\}$. Thus $N_{i,j}^+ = N_{r,s}^+$ □

## Definition 11: Local network

A local network of an agent $[A]_{ij}$ is the set denoted by $L_{ij}$ such that:

(i) $N_{ij}$ is a subset of $L_{ij}$

(ii) For $Ag^+ \in L_{ij}$ there exists $Ag^- \in L_{ij}$ such that if $Ag^+ \notin N_{ij}^+$ then:

* either $Ag^+$ is in the intersection of the neighborhoods of the two elements in $N_{ij}^+$ and then the neighborhood of $Ag^-$ is $N_{ij}^-$.

* or $Ag^+$ and $[A]_{ij}$ (respectively $Ag^-$ and $[A]_{ij}$) are the neighborhood of one of the elements of $N_{ij}^-$.

The following theorem generalizes the result in theorem 10.

**Theorem 12:** Let $\omega$ be a circulant operator and and
$$ P_{k,n}^{ij} \xrightarrow{\omega} P_{k+1,n}^{rs} $$
<figure><img src="image_8.png" /><figcaption>Fig. 7. Local network for the protocol $P_{1,n}^{ij}$</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 8. Local network for the protocol $P_{2,n}^{ij}$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9. Local network for the protocol $P_{3,n}^{ij}$</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 10. Local network for the protocol $P_{4,n}^{ij}$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 11. Local network for the protocol $P_{5,n}^{ij}$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 12. Local network for the protocol $P_{6,n}^{ij}$</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 13. Local network for the protocol $P_{7,n}^{ij}$</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 14. Local network for the protocol $P_{8,n}^{ij}$</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Fig. 15. Local network for the protocol $P_{9,n}^{ij}$</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Fig. 16. Local network for the protocol $P_{10,n}^{ij}$</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Fig. 17. Local network for the protocol $P_{11,n}^{ij}$</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 18. Local network for the protocol $P_{12,n}^{ij}$</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Fig. 19. Cobweb partitioning of $\bigcup_{\sigma} \sigma A_n$</figcaption></figure>

Then:

$$ \mathcal{L}_{i,j} = \mathcal{L}_{r,s} $$

To illustrate this result, one can verify that the local network of the agent $b_4$ in the example above is constant.

### C. Changing Task without Changing Bipartition

**Definition 13: Bipartition preservation** A permutation $\sigma$ preserves a partition $A^{B/b}$ if there exists $\sigma_B$ and $\sigma_b$ such that $\sigma = \sigma_B \sigma_b$, where: $[A^b]_{\sigma_B(i,j)} = [A^b]_{i,j} \quad \forall i, j$ $[A^B]_{\sigma_b(i,j)} = [A^B]_{i,j} \quad \forall i, j$

Such permutation can be useful to change a task without mixing the two blocks of a particular bipartition, especially when the two subsets of agents in these blocks are working in parallel.

In the sequel this property will be denoted by the following equality: $\sigma(A^{B/b}) = A^{B/b}$, and the set $\{\sigma A_{k,n}\}_\sigma$ will be denoted by $A_{k,n}$.

### Theorem 14: Partition of $\sigma A_n$

Let $\sigma$ be a permutation on $\chi$ such that $\sigma(A^{NE/sw}) = A^{NE/sw}$. Then

$$ \bigcup_{\sigma} \sigma A_n = \bigcup_{k=1}^{12} A_{k,n} \quad \text{and} \quad A_{r,n} \cap A_{s,n} = \emptyset \quad \forall r \neq s $$

### Proof:

It follows directly from the definition of the set $A_{r,n}$. □

The theorem above leads to a partitioning of the set $\sigma A_n$ into orbits $A_{r,n}$ as it is represented in Fig. 19.

## IV. CONCLUSION AND DISCUSSIONS

In this work we present the circulant operators and their actions on square matrices. This study on square matrices provides new insights into the structure of the space of square matrices. Moreover it can be useful in various fields such as in agents networking on Grid or large-scale distributed self-organizing grid systems. We establish that, with a single initial matrix (and thus a single protocol), one can derive in this space concentric orbits describing a cobweb partition graph. Exploring the cobweb cyclically, one can reach the twelve matrices (which can be seen as states of a particular system) through the four bipartitions. This cyclic tour represent a dynamic reconfiguration of the network leading to twelve changes of the topology of the grid as shown by local networks. On the other hand, a radial trajectory enable to access "states" in which the two sets of tests in the bipartition are globally invariants. This can be seen as introduction of a new policy in the network conserving the agents localisations.

Another aspect of this study is that the circulant operator allows us to manage two blocks of components requested for parallel jobs in the network.

## REFERENCES

[1] Gregory S. Call; Daniel J. Velleman, Pascal's Matrices, *The American Mathematical Monthly*, 100, 4, 1993, pp. 372-376

[2] Prosper Kwaku Doh, Twelve Matrix Form of the Arithmetic Triangle: Mathematical Tools, Relation Diagrams, *Personal Communications*, 2004,

[3] Prosper Kwaku Doh, *Courbes paramétriques polynomiales et formes matricielles du théorème binomial: Nouveaux outils fondamentaux pour la conception et fabrication assiste par ordinateur*, Thse, Université de Nancy, 1988

[4] Alan Edelman and Gilbert Strang, Pascal's Matrices, *The American Mathematical Monthly*, 111, 3, pp. 189-197, March 2004

[5] Teijo Arponen, Matrix approach to polynomials 2, *Linear Algebra and its Applications*, 394, pp. 257-276, 2005

[6] Y. Ben-Asher, D. Peleg, R. Ramaswami and A. Schuster, The power of reconfiguration *Journal of Parallel and Distributed Computing*,13, 2, pp. 139-153, October 1991

[7] Kiyoaki Yoshida, Tohru Kohda, Yasumasa Sujaku, Self-Organizing Systems with Self-Diagnosability, dsn, p. 755, International Conference on Dependable Systems and Networks (DSN'02), 2002

[8] B. Birregah, P. K. Doh, K. H. Adjallah, The Twelve Triangular Matrix Forms of the Pascal Triangle: a Systematic Approach with the Set of Circulant Operators, *To appear in The 10th WSEAS International Conference on Applied Mathematics (MATH '06) Proceedings*, Dallas, Texas, USA, November 1-3, 2006