# Exploring the Set of Square Matrices with Circulant Operators

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

► To cite this version:

B. Birregah, Prosper K. Doh, Kondo Hloindo Adjallah. Exploring the Set of Square Matrices with Circulant Operators. WSEAS Transactions on Mathematics, 2007, 6 (2), pp.281-288. hal-03045126

HAL Id: hal-03045126

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

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
# Exploring the Set of Square Matrices with Circulant Operators

BABIGA BIRREGAH

University of Lomé
College of Science,
Applied Math. Dpt. BP. 1515
TOGO
bbirregah@tg.refer.org

PROSPER K. DOH

University of Nancy 2
23, boulevard Albert 1er - BP 3397
F54015 Nancy Cedex
FRANCE
Prosper.Doh@univ-nancy2.fr

KONDO H. ADJALLAH

University of Technology of Troyes
Institute Charles Delaunay
12 rue Marie Curie,
F.10010 Troyes Cedex
FRANCE
kondo adjallah@utt.fr

*Abstract:* Circulant operators are useful tools to highlight the way in which the twelve triangular matrix forms of Pascal triangle (collectively referred to as G-matrices) relate to each other. In this paper, we recall the notions of G-matrices and circulant operators, and then we present some main algebraic properties of these operators. We generalize these operators to the case of any square matrix.

*Key-Words:* Pascal Triangle, Pascal Matrices, k-Circulant Operators, Square Matrix bipartition, cobweb Partition, G-matrices.

## 1 Introduction

This section recalls the definition of the twelve G-matrices, $G_{k,n}$ $1 \le k \le 12$ as in [2, 22]. In the sequel, we write $[G_{k,n}]_{ij}$ to denote the coefficient at the intersection of row $i$ and column $j$ and denote by $G_n$ the set of the twelve G-matrices. Generic binomial coefficients $\frac{a!}{(a-b)!b!}$ will be denoted $\binom{a}{b}$. The Pascal triangle is assumed to comprise levels $0...n$.

### 1.1 The set $G_n$ of G-matrices

The following definitions present the twelve triangular matrix forms of the Pascal triangle. They are organized into four subsets.

**Definition 1** - The NE/sw G-matrices

$G_{1,n}$, $G_{5,n}$ and $G_{9,n}$

$$ [G_{1,n}]_{ij} = \begin{cases} \begin{pmatrix} i \\ j \end{pmatrix} & \text{if } i \le j \\ 0 & \text{otherwise} \end{cases} \quad (1) $$

$$ [G_{5,n}]_{ij} = \begin{pmatrix} n-i \\ n-j \end{pmatrix} \quad i, j = 0, \dots, n \quad (2) $$

$$ [G_{9,n}]_{ij} = \begin{cases} \begin{pmatrix} n+i-j \\ i \end{pmatrix} & \text{if } i \le j \\ 0 & \text{otherwise} \end{cases} \quad (3) $$

$$ G_n^{NE/sw} = \{G_{1,n}, G_{5,n}, G_{9,n}\} $$

**Definition 2** - The SE/nw G-matrices

$G_{2,n}$, $G_{6,n}$ and $G_{10,n}$

$$ [G_{2,n}]_{ij} = \begin{pmatrix} j \\ n-i \end{pmatrix} \quad i, j = 0, \dots, n \quad (4) $$

$$ [G_{6,n}]_{ij} = \begin{cases} \begin{pmatrix} 2n-i-j \\ n-j \end{pmatrix} & \text{if } i+j \ge n \\ 0 & \text{otherwise} \end{cases} \quad (5) $$

$$ [G_{10,n}]_{ij} = \begin{pmatrix} i \\ n-j \end{pmatrix} \quad i, j = 0, \dots, n \quad (6) $$

$$ G_n^{SE/nw} = \{G_{2,n}, G_{6,n}, G_{10,n}\} $$

**Definition 3** - The SW/ne G-matrices

$G_{3,n}$, $G_{7,n}$ and $G_{11,n}$

$$ [G_{3,n}]_{ij} = \begin{cases} \begin{pmatrix} n+j-i \\ j \end{pmatrix} & \text{if } i \ge j \\ 0 & \text{otherwise} \end{cases} \quad (7) $$

$$ [G_{7,n}]_{ij} = \begin{pmatrix} n-j \\ n-i \end{pmatrix} \quad i, j = 0, \dots, n \quad (8) $$

$$ [G_{11,n}]_{ij} = \begin{pmatrix} i \\ j \end{pmatrix} \quad i, j = 0, \dots, n \quad (9) $$

$$ G_n^{SW/ne} = \{G_{3,n}, G_{7,n}, G_{11,n}\} $$
**Definition 4** - The NW/se G-matrices

$G_{4,n}, G_{8,n}$ and $G_{12,n}$

$$[G_{4,n}]_{ij} = \begin{pmatrix} n-i \\ j \end{pmatrix} \quad i, j = 0, \dots, n \quad (10)$$

$$[G_{8,n}]_{ij} = \begin{pmatrix} n-j \\ i \end{pmatrix} \quad i, j = 0, \dots, n \quad (11)$$

$$[G_{12,n}]_{ij} = \begin{cases} \begin{pmatrix} i+j \\ i \end{pmatrix} & \text{if } i+j \le n \\ 0 & \text{otherwise} \end{cases} \quad (12)$$

$$G_n^{\text{NW/se}} = \{G_{4,n}, G_{8,n}, G_{12,n}\}$$

Notation:

$$G_n = G_n^{\text{NW/sw}} \cup G_n^{\text{SE/nw}} \cup G_n^{\text{SW/ne}} \cup G_n^{\text{NW/se}} \quad (13)$$

It is easy to observe that:

**Theorem 5** If $B \neq B'$ and $b \neq b'$ then

$$G_n^{B/b} \cap G_n^{B'/b'} = \emptyset$$

**Proof:**

Considering definitions 1-4, one can easily establish this statement.

Matrices like the above and other matrix forms derived from the Pascal triangle are encountered in [1, 3, 4, 9, 10, 16, 8]. Every author simply refers to a particular form encountered as the Pascal matrix.

Some authors refer to $G_{1,n}$ and $G_{11,n}$ respectively as upper and lower triangular Pascal matrices [5, 19, 17, 18, 20, 21]. In [7, 8], the fourth G-matrix, $G_{4,n}$ is called binomial matrix. But, as it can be seen from the above definitions, this is just one of the three possible upper-left triangular forms. In some works, one recognizes $G_{12,n}$, the third northwest triangular matrix form. [12] refers to $G_{7,n}$ as the reflection of $G_{11,n}$ about the main anti-diagonal.

Considering the matrix formulation (14) of the well-known binomial theorem as proposed in [3],

$$(1 (1+t) (1+t)^2 \dots (1+t)^n) = (1 \ t \ t^2 \ \dots \ t^n) \underbrace{\begin{pmatrix} (0) & (1) & \dots & (0) \\ (0) & (1) & \dots & (1) \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \dots & \dots & 0 \end{pmatrix}}_{G_{1,n}} \quad (14)$$

these matrices can be seen as some reordering of the components of the polynomial power basis vector, and hence of the polynomial space [3].

To our knowledge, this is the first attempt to systematically investigate matrix forms of the Pascal triangle as mathematical objects in their own right.

Section 1.2 presents the four circulant operators and the way they intervene in generating the set of the twelve Pascal matrices, starting with one of them. Section 3 generalizes to the case of any square matrix.

## 1.2 The circulant operators

In this section, the circulant operators are presented as transformations of the generic matrix subscript vector $(i, j)$ ($0 \le i, j \le n$).

**Definition 6** - Circulant operator

The $\alpha$-circulant operator

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

The $\beta$-circulant operator

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

The $\gamma$-circulant operator

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

The $\delta$-circulant operator

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

Figure 1 illustrates how $\alpha$ transforms a square matrix.

<figure><img src="image_2.png" /><figcaption>Figure 1: The $\alpha$-circulant operator</figcaption></figure>

Circulant transformations carry circulant matrices to associated row- or column-constant matrices. To see this, consider the circulant matrix $C$ given below and its associated row-constant matrix denoted $\tilde{C}$:

$$C = \begin{pmatrix} c_1 & c_2 & c_3 & \cdots & c_n \\ c_n & c_1 & c_2 & \cdots & c_{n-1} \\ c_{n-1} & c_n & c_1 & \cdots & c_{n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_2 & c_3 & c_4 & \cdots & c_1 \end{pmatrix},$$
$$
\tilde{C} = \left( \begin{array}{ccccc} c_n & c_n & c_n & \cdots & c_n \\ c_{n-1} & c_{n-1} & c_{n-1} & \cdots & c_{n-1} \\ c_{n-2} & c_{n-2} & c_{n-2} & \cdots & c_{n-2} \\ \vdots & \vdots & \vdots & & \vdots \\ c_1 & c_1 & c_1 & \cdots & c_1 \end{array} \right)
$$

One readily sees for example that: $\tilde{C} = \beta C$.

**1.3 Circulant Operators action on G_n**

**Theorem 7 Action of circulant operators on G_n**

$$
\begin{array}{l@{\qquad}l@{\qquad}l}
\text{If } i \in \{1, 5, 9\} & \text{then } \beta G_{i,n} = G_{i+1} & [12], n \\
\text{If } i \in \{2, 6, 10\} & \text{then } \delta G_{i,n} = G_{i+1} & [12], n \\
\text{If } i \in \{3, 7, 11\} & \text{then } \gamma G_{i,n} = G_{i+1} & [12], n \\
\text{If } i \in \{4, 8, 12\} & \text{then } \alpha G_{i,n} = G_{i+1} & [12], n
\end{array}
$$

where $i + 1 [12] \equiv i + 1 \mod 12$.

From this stage one can now derived all the twelve G-
matrices starting with any particular one. Thus start-
ing with $G_{1,n}$, the twelve G-matrices can be derived
in their natural order by the following sequence:

$$
\begin{array}{rcl@{\quad}l}
\mathbf{G}_{1,n} & \xrightarrow{\beta} & G_{2,n} \xrightarrow{\delta} G_{3,n} \xrightarrow{\gamma} G_{4,n} \xrightarrow{\alpha} & G_{5,n} \\
G_{5,n} & \xrightarrow{\beta} & G_{6,n} \xrightarrow{\delta} G_{7,n} \xrightarrow{\gamma} G_{8,n} & \xrightarrow{\alpha} G_{9,n} \\
G_{9,n} & \xrightarrow{\beta} & G_{10,n} \xrightarrow{\delta} G_{11,n} \xrightarrow{\gamma} G_{12,n} & \xrightarrow{\alpha} \mathbf{G}_{1,n}
\end{array}
$$

This is a cycle since $(\alpha\gamma\delta\beta)^3 G_{1,n} = G_{1,n}$. Moreover,
it is readily verified that $\{G_{1,n}, G_{5,n}, G_{9,n}\}$ is glob-
ally $(\alpha\gamma\delta\beta)$-invariant.

Similar inspections show that: $(\gamma\delta\beta\alpha)^3 G_{4,n} = G_{4,n}$,
$(\delta\beta\alpha\gamma)^3 G_{3,n} = G_{3,n}$, $(\beta\alpha\gamma\delta)^3 G_{2,n} = G_{2,n}$,

The circulant transformations provide a useful frame-
work for investigating the G-matrices. Section 2 gives
some basic properties of these operators which arise
in the *p*-factor compositions. In section 3 we will
extend their application to square matrices to provide
new insights into the structure of the space of square
matrices.

The set of circulant operators will be denoted by $\mathcal{C}_n$ in dimension $n + 1$.

**2 Main algebraic properties of the**
**circulant operators**

In this section the set $\mathcal{C}_n$ is consider as an *alphabet*.
The aim here is to give a complete list of identities

which arise in the *p*-factor products (composition) of
circulant operators (*p* = 1, 2, 3).

**2.1 Notations and Definitions**

Let's put forward these notations first:

$$
\begin{align*}
\langle \alpha \rangle &:= \{ \epsilon, \alpha, \alpha^2, \alpha^3, \dots, \alpha^n \} \\
\langle \beta \rangle &:= \{ \epsilon, \beta, \beta^2, \beta^3, \dots, \beta^n \} \\
\langle \delta \rangle &:= \{ \epsilon, \delta, \delta^2, \delta^3, \dots, \delta^n \} \\
\langle \gamma \rangle &:= \{ \epsilon, \gamma, \gamma^2, \gamma^3, \dots, \gamma^n \} \\
\langle \xi \rangle^{\diamond} &:= \{ \xi, \xi^2, \xi^3, \dots, \xi^n \quad \forall \xi \in \mathcal{C}_n
\end{align*}
$$

with $\epsilon = \alpha^{n+1} = \beta^{n+1} = \delta^{n+1} = \gamma^{n+1}$ and
$\epsilon M = M$ for all $(n+1) \times (n+1)$ matrix.

**Definition 8 - Empty string**
*ε is called empty string and* $\forall \xi \in \mathcal{C}_n$, $\xi^0 = \varepsilon$

**Definition 9 - k-circulant operator**
An operator $\xi$ is k-circulant if:

$$
\exists \omega \in \mathcal{C}_n, \text{ such that } \xi = \omega^k
$$

**Theorem 10** For all $\xi$, $\psi \in \mathcal{C}_n$,

$$
\langle \xi \rangle^{\diamond} \cap \langle \psi \rangle^{\diamond} = \emptyset \quad (15)
$$

**2.2 Identities without k-circulants**

This section present all identities of exactly *p*-factors
strings for *p* = 2, 3, 4 without k-circulant as sub-
string.

**2.3 Two-factors identities**

**Theorem 11**

$$
\alpha\delta = \delta\alpha \qquad \beta\gamma = \gamma\beta \tag{16}
$$

**Proof:**

It is easy to see that:

$$
\begin{align*}
\alpha\delta(i, j) &= \alpha[\delta(i, j)] \\
&= \alpha[(i, 1+i+j) \bmod (n+1)] \\
&= \alpha[(i, 1+i+j)] \bmod (n+1) \\
&= (i, 1+2i+j) \bmod (n+1)
\end{align*}
$$
and

$$
\begin{align*}
\delta\alpha(i,j) &= \delta[\alpha(i,j)] \\
&= \delta[(i, i+j) \mod (n+1)] \\
&= \delta[(i, i+j)] \mod (n+1) \\
&= (i, 1+2i+j) \mod (n+1)
\end{align*}
$$

This leads to $\alpha\delta = \delta\alpha$.

The second identity is also established in the same
way.

**2.4 Three-factors identities**

We give above a collection of twelve identities.

$$
\alpha\beta\alpha = \beta\alpha\beta \qquad \alpha\gamma\alpha = \gamma\alpha\gamma \tag{17}
$$

$$
\alpha\delta\beta = \delta\alpha\beta \qquad \alpha\delta\gamma = \delta\alpha\gamma \tag{18}
$$

$$
\alpha\gamma\delta = \beta\alpha\gamma \qquad \alpha\gamma\delta = \delta\beta\alpha \tag{19}
$$

$$
\alpha\gamma\delta = \gamma\delta\beta \qquad \beta\alpha\gamma = \delta\beta\alpha \tag{20}
$$

$$
\beta\alpha\gamma = \gamma\delta\beta \qquad \beta\delta\beta = \delta\beta\delta \tag{21}
$$

$$
\delta\beta\alpha = \gamma\delta\beta \qquad \delta\gamma\delta = \gamma\delta\gamma \tag{22}
$$

One of the main results deriving from these identities
is:

**Theorem 12 -**
*row-column-row=column-row-column*

For all $r \in \{\alpha, \gamma\}$ and all $c \in \{\beta, \delta\}$,

$r c r = c r c$

Proof:

Using the same technic as for equations 16, it is easy
to verify that:

$\alpha\beta\alpha = \beta\alpha\beta$ and $\alpha\gamma\alpha = \gamma\alpha\gamma$ on the one hand

$\beta\delta\beta = \delta\beta\delta$ and $\delta\gamma\delta = \gamma\delta\gamma$ on the other hand.

Another result is provided by:

**Theorem 13**

$$
\alpha\gamma\delta = \beta\alpha\gamma = \delta\beta\alpha = \gamma\delta\beta
$$

Proof:

It directly follows using the definitions.

These identities give the base on which all other p-
factor identities (p > 3) will be derived. From this
stage we now give some relevant identities with k-
circulant operators for k = 1, 2, 3.

**2.5 k-circulants identities**

**2.5.1 Two-factors for $k=2$**

$$
\alpha^2 \delta^2 = \delta^2 \alpha^2 \qquad \beta^2 \gamma^2 = \gamma^2 \beta^2 \tag{23}
$$

**2.5.2 Three-factors for $k=2$**

$$
\alpha^2 \delta^2 \beta^2 = \delta^2 \alpha^2 \beta^2 \qquad \alpha^2 \delta^2 \gamma^2 = \delta^2 \alpha^2 \gamma^2 \tag{24}
$$

$$
\beta^2 \gamma^2 \alpha^2 = \gamma^2 \beta^2 \alpha^2 \qquad \beta^2 \gamma^2 \delta^2 = \gamma^2 \beta^2 \delta^2 \tag{25}
$$

**2.5.3 Two-factors for $k=3$**

$$
\alpha^3 \delta^3 = \delta^3 \alpha^3 \qquad \beta^3 \gamma^3 = \gamma^3 \beta^3 \tag{26}
$$

**2.5.4 Three-factors for $k=3$**

$$
\alpha^3 \delta^3 \beta^3 = \delta^3 \alpha^3 \beta^3 \qquad \alpha^3 \delta^3 \gamma^3 = \delta^3 \alpha^3 \gamma^3 \tag{27}
$$

$$
\beta^3 \gamma^3 \alpha^3 = \gamma^3 \beta^3 \alpha^3 \qquad \beta^3 \gamma^3 \delta^3 = \gamma^3 \beta^3 \delta^3 \tag{28}
$$

**2.6 Identities involving k-circulant and circulant operators ($k \ge 2$)**

We give here a theorem which can be considered
as a basic tool to derive identities involving both k-
circulant and circulant operators.

**Theorem 14**

$$
\alpha^k \delta^k = \delta^k \alpha^k \qquad \beta^k \gamma^k = \gamma^k \beta^k \tag{29}
$$

$$
\alpha \delta^k = \delta^k \alpha \qquad \beta \gamma^k = \gamma^k \beta \tag{30}
$$

$$
\alpha^k \delta = \delta \alpha^k \qquad \beta^k \gamma = \gamma \beta^k \tag{31}
$$

Proof:

One can prove the first one (for example) by recur-
rence.

Assuming that $\alpha^k \delta^k = \delta^k \alpha^k$ for a $k \in \mathbb{N}$,

$$
\begin{align*}
\alpha^{n+1} \delta^{k+1} &= \alpha^k \alpha \delta^k \\
&= \alpha^k \delta \alpha \delta^{k-1} \\
&= \alpha^k \delta^2 \alpha \delta^{k-1} \\
&= \dots \\
&= \alpha^k \delta^p \alpha \delta^{k-p+1} \\
&= \dots \\
&= \alpha^k \delta^k \alpha \delta \\
&= \delta^k \alpha^k \delta \alpha \\
&= \delta^k \alpha^{k-1} \alpha \delta \alpha \\
&= \delta^k \alpha^{k-1} \delta \alpha^2 \\
&= \dots \\
&= \delta^k \alpha^{k-p+1} \delta \alpha^p \\
&= \dots \\
&= \delta^k \alpha \delta \alpha^k \\
&= \delta^{k+1} \alpha^{k+1}
\end{align*}
$$
or:

$$
\begin{align*}
\alpha^{k+1} \delta^{k+1} &= \alpha \alpha^k \delta^k \delta \\
&= \alpha \delta^k \alpha^k \delta \\
&= \alpha \delta \delta^{k-1} \alpha^{k-1} \alpha \delta \\
&= \delta \alpha \delta^{k-1} \alpha^{k-1} \delta \alpha \\
&= \dots \\
&= \delta^p \alpha \delta^{k-p} \alpha^{k-p} \delta \alpha^p \\
&= \dots \\
&= \delta^k \alpha \delta \alpha^k \\
&= \delta^k \delta \alpha \alpha^k \\
&= \delta^{k+1} \alpha^{k+1}
\end{align*}
$$

On the other side:

$$
\begin{align*}
\alpha \delta^k &= (\alpha \delta) \delta^{k-1} \\
&= \delta \alpha \delta^{k-1} \\
&= \delta(\alpha \delta) \delta^{k-2} \\
&= \delta^2 \alpha \delta^{k-2} \\
\vdots & \\
&= \delta^p \alpha \delta^{k-p} \\
\vdots & \\
&= \delta^k \alpha
\end{align*}
$$

This ends the proof.

**3 Applications and generalizations**

**3.1 Triangular bipartition of a square matrix**

Now, the four triangular bipartitions of any square
matrix as illustrated in figure 2 are presented. The
triangular sub-block in full line indicate which block
includes the main or anti diagonal.

<figure><img src="image_3.png" /><figcaption>Figure 2: Four bipartitions of a square matrix</figcaption></figure>

**Definition 15** - Triangular bipartitions

Given A, a (n + 1) × (n + 1) matrix with subscripts
i and j ranging from 0 to n.

(i) The North-East/south-west bipartition

The matrices $A_{NE}$ and $A_{sw}$, such that:

$$
[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}
$$

(ii) The South-West/north-east bipartition

The matrices $A_{SW}$ and $A_{ne}$, such that:

$$
[A_{SW}]_{ij} = \begin{cases} [A]_{ij} & \text{if } i \geq 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}
$$

(iii) The North-West/south-east bipartition

The matrices $A_{NW}$ and $A_{se}$, such that:

$$
[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}
$$

(iv) 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}
$$

**Theorem 16**

$$
\alpha (A_{NW/se}) = \alpha (A_{NW}) + \alpha (A_{se}) \quad (32)
$$

$$
\beta (A_{NE/sw}) = \beta (A_{NE}) + \beta (A_{sw}) \quad (33)
$$

$$
\delta (A_{SE/nw}) = \delta (A_{SE}) + \delta (A_{nw}) \quad (34)
$$

$$
\gamma (A_{SW/ne}) = \gamma (A_{SW}) + \gamma (A_{ne}) \quad (35)
$$
<table><caption>Table 1: Partition of the set $\mathcal{G}_n$</caption><thead><tr><th>Subsets</th><th>Matrices</th></tr></thead><tbody><tr><td>G<sub>n</sub><sup>NE/sw</sup></td><td>G<sub>1,n</sub> G<sub>5,n</sub> G<sub>9,n</sub></td></tr><tr><td>G<sub>n</sub><sup>SE/nw</sup></td><td>G<sub>2,n</sub> G<sub>6,n</sub> G<sub>10,n</sub></td></tr><tr><td>G<sub>n</sub><sup>SW/ne</sup></td><td>G<sub>3,n</sub> G<sub>7,n</sub> G<sub>11,n</sub></td></tr><tr><td>G<sub>n</sub><sup>NW/se</sup></td><td>G<sub>4,n</sub> G<sub>8,n</sub> G<sub>12,n</sub></td></tr></tbody></table>

<table><caption>Table 2: Partition of the set $\mathcal{A}_n$</caption><thead><tr><th>Subsets</th><th>Matrices</th></tr></thead><tbody><tr><td>$\mathcal{A}_n^{NE/sw}$</td><td>A<sub>1,n</sub> A<sub>5,n</sub> A<sub>9,n</sub></td></tr><tr><td>$\mathcal{A}_n^{SE/nw}$</td><td>A<sub>2,n</sub> A<sub>6,n</sub> A<sub>10,n</sub></td></tr><tr><td>$\mathcal{A}_n^{SW/ne}$</td><td>A<sub>3,n</sub> A<sub>7,n</sub> A<sub>11,n</sub></td></tr><tr><td>$\mathcal{A}_n^{NW/se}$</td><td>A<sub>4,n</sub> A<sub>8,n</sub> A<sub>12,n</sub></td></tr></tbody></table>

**Proof:**

It is derived from the fact that:

- $A_B$ and $A_b$ are triangular matrices (juste as G-matrices),

- circulant operators, if judiciously applied, doesn't mixe two triangular blocks in a square matrix as we have seen it in the case of G-matrices.

## 3.2 Partition of the set $\mathcal{G}_n$ with the circulant operators and generalization

The four bipartitions of the square matrix leads to a partition of $\mathcal{G}_n$ into four subsets as it is described in table 1. One can observe that the subsets in the first column of this table (up to down) are globally invariant by the action of $\alpha\gamma\delta\beta$, $\beta\alpha\gamma\delta$, $\delta\beta\alpha\gamma$ and $\gamma\delta\beta\alpha$ respectively.

Globally, it follows that:

$$ \begin{array}{ccc} \mathcal{G}_n^{NE/sw} & \xrightarrow{\beta} & \mathcal{G}_n^{SE/nw} \\ \mathcal{G}_n^{NW/se} & \xrightarrow{\alpha} & \mathcal{G}_n^{NE/sw} \end{array} \xrightarrow{\delta} \mathcal{G}_n^{SW/ne} \xrightarrow{\gamma} $$

<figure><img src="image_4.png" /><figcaption>Figure 3: Four bipartitions linked by circulant operators</figcaption></figure>

where $\xrightarrow{\mathcal{O}}$ denotes the transformation by the operator $\mathcal{O}$ as shown in figure 3 which summarizes the generalization to the case of any square matrix $A$ shown in table 2, where $\mathcal{O}A_{i,n} = A_{i+1[12],n}$ and $A_{1,n} = A$, with:

$$ i + 1[12] = i + 1 \text{ modulus } 12, $$

$$ \text{and } \mathcal{O} = \begin{cases} \beta & \text{if } i \in \{1, 5, 9\} \\ \delta & \text{if } i \in \{2, 6, 10\} \\ \gamma & \text{if } i \in \{3, 7, 11\} \\ \alpha & \text{if } i \in \{4, 8, 12\} \end{cases} $$

Thus:

$$ \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} $$

This leads to the set $\mathcal{A}_n$ of twelve new matrices from the single matrix $A$. Figure 4 shows a graph with $\mathcal{A}_n$ as set of vertices, and the circulant operators as transitions labels.

<figure><img src="image_5.png" /><figcaption>Figure 4: Ring behavior of $\mathcal{A}_n$ with alphabet in $\{\alpha, \beta, \gamma, \delta\}$</figcaption></figure>

## 4 New structure of the space of square matrices

Let $A = ([A]_{i,j})_{0 \le i,j \le n}$ be a square matrix:

- the set of the coefficients of $A$ will be denoted by $\text{Coef}(A)$,

- the permutation group on $\{(i, j), 0 \le i, j \le n\}$ will be denoted by $\text{Perm}(n)$,

- For $\sigma \in \text{Perm}(n)$:
$$
\begin{align*}
\sigma((i, j)) &\equiv (i_{\sigma}, j_{\sigma}) \\
[A]_{i_{\sigma}, j_{\sigma}} &\equiv [\sigma A]_{i,j}, \quad 0 \le i, j \le n, \\
\sigma A_n &\equiv \{\sigma A, A \in A_n\} \\
A_{k,n} &\equiv \{\sigma A_{k,n}, \sigma \in \operatorname{Perm}(n)\} \text{ where } 1 \le k \le 12
\end{align*}
$$

**Definition 17** - A permutation $\sigma \in \operatorname{Perm}(n)$ preserves a partition $A_{B/b}$ if their exists $\sigma_B$ and $\sigma_b$ such that

$\sigma = \sigma_B \sigma_b$

where :

$$
[A_b]_{i_{\sigma_B}, j_{\sigma_B}} = [A_b]_{i,j} \quad \forall i, j
$$

$$
[A_B]_{i_{\sigma_b}, j_{\sigma_b}} = [A_B]_{i,j} \quad \forall i, j
$$

In the sequel this property will be denoted by the
following equality: $\sigma(A_{B/b}) = A_{B/b}$.

As example of such a permutation, one can easily
take the permutation derived from the composition
$\beta\delta\gamma\alpha$

**Theorem 18 -**
Partition and exploration in $\bigcup_{\sigma} \{\sigma A_n\}_{\sigma}$

If $\sigma_i \in \operatorname{Perm}(n)$ and $\sigma(A_{NE/sw}) = A_{NE/sw}$ then

$$
\sigma_p A_n \cap \sigma_q A_n = \emptyset \quad \forall p \neq q \quad (36)
$$

$$
A_{r,n} \cap A_{s,n} = \emptyset \quad \forall r \neq s \quad (37)
$$

Proof:

It follows directly from the definition of the set $\mathcal{A}_{r,n}$.

The above theorem leads to a partitioning of the set
$\mathcal{A}_n$ into orbits $\sigma \mathcal{A}_{r,n}$ as represented in figure 5.

<figure><img src="image_6.png" /><figcaption>Figure 5: Cobweb partitioning of $\bigcup_{\sigma} \{\sigma A_n\}_{\sigma}$</figcaption></figure>

5 Conclusion and discussions

In this work we have presented an investigation of
twelve triangular matrix forms of the Pascal Trian-
gle. We have then presented one way in which the
G-matrices relate to each other by introducing a set
of circulant operators. As algebraic tools, these oper-
ators have several properties among which we gave
some concerning their composition. Besides these
properties, these operators turn out to provide a new
insight into the structure of the space of square ma-
trices. We established that, beginning with a single
matrix, 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 state of a grid system) through
the four bipartitions. On the other hand, a radial tra-
jectory enable to access states in which the two sets
of coefficients in the bipartition are globally invari-
ants. As matter of applications, this study can provide
some basic tools to effective simulations in the area of
grid networks.

**Acknowledgements:** The research was supported by the project STICO of ICD-FRE CNRS 2848 (University of Technology of Troyes - UTT) in the case of the first author.

References:

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

[2] P. K. Doh, Twelve Matrix Form of the Arithmetic Triangle: Mathematical Tools, Relation Diagrams, *Personnal Communications*, 2004,

[3] P. K. Doh, *Courbes paramétriques polynomiales et formes matricielles du théorème binomial: Nouveaux outils fondamentaux pour la conception et fabrication assiste par ordinateur*, Thesis of University of Nancy 1, 1988

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

[5] G. Boyd, C. A. Micchelli, Gilbert Strang and Ding-Xuan Zhou, *Binomial Matrices, Advances in Computational Mathematics*, 14, 4, May 2001, pp. 379-391

[6] P. C. Abbott, Pascal Matrices in Tricks of the Trade, *The Mathematica Journal*, 9, 4, 2005, pp. 691-694

[7] E. Liverance, J. Pitsenberger, Diagonalization of the binomial matrix, *Fibonacci Quarterly*, 34, 1, 1996, pp. 55-67, ISSN 0015-0517
[8] Z. Zhang; T. Wang, Generalized Pascal matrix and recurrence sequences, *Linear Algebra and its Applications*, 283, 1998, pp. 289-299

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

[10] T. Arponen, A Matrix approach to polynomials, *Linear Algebra and its Applications*, 359, 2002, pp. 181-196

[11] R. Basher, Matrices related to the Pascal triangle, *Journal de Théorie des Nombres de Bordeaux*, 14, 2002, pp. 19-41

[12] L. Abrams, Donniell E., Fishkind and Silvia Valdes-Leon, Reflecting Pascal Matrix About its Main Antidiagonal, *Linear and Multilinear Algebra*, 47, 2000, pp. 129-136

[13] M. F. Aburdene; J. E. Dorband, Unification of Legendre, Laguerre, Hermite, and Binomial Secret Transforms using Pascal's Matrix, *Multidimensional Systems and Signal Processing*, 5, 1994, pp. 301-305

[14] Z. Tang, R. Duraiswami, & N. Gumerov, Algorithms to compute matrix-vector products for Pascal matrices, *Multidimensional Systems and Signal Processing*, 5, pp. 301-305, 1994

[15] A. Barbé, Symmetric patterns in the cellular automaton that generates Pascal's triangle modulo 2, *Discrete Applied Mathematics*, 105, 2000, pp. 1-38

[16] Seog-Hoon, R. Seok-Zun, S. Gi-Sang Cheon, Suk-Geun Hwang, Matrices determined by a linear recurrence relation among entries, *Linear Algebra and its Applications*, 373, 2003, pp. 89-99

[17] W. Xiang, Z. Jituan, A Fast Eigenvalue Algorithm for Pascal matrices, To appear in *Applied Mathematics and Computation*, 2006

[18] W. Xiang, L. Linzhang, A Fast Algorithm for Solving Linear Systems of the Pascal Type, *Applied Mathematics and Computation*, 175, 2006, pp. 441-451

[19] M. E. A. El-Mikkawy, On Solving Linear Systems of the Pascal Type, *Applied Mathematics and Computation*, 136, 2003, pp. 195-202

[20] L. Aceto, D. Trigiante, The Matrices of Pascal and Other Greats, *American Mathematical Monthly*, 108, 3, 2001, pp. 232-245, Mar.

[21] S.-Y. Yang, Z.-K. Liu, Explicit Inverse of The Pascal Matrix Plus One, *International Journal of Mathematics and Mathematical Sciences*, Vol.2006 Article ID 90901, 2006, 7 pages

[22] 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