1. Introduction
In 1941, Hopf [1] first put forward the concept of both algebra structure and coalgebra structure in the study of cohomology algebra
of Lie group G. After that, more and more interesting questions about algebras and coalgebras have attracted many mathematicians to work and study on them continuously. Among those questions, it is a hot topic how to construct algebras and coalgebras on combinatorial objects.
In 2014, Vargas [2] defined a super-shuffle product
and a coproduct
, called cut-box coproduct by Liu and Li [3] on permutations. In 2005, Aguiar and Sottile introduced the global descents of permutations in symmetric groups [4] . On this basis, Zhao and Li derived another shuffle product and deconcatenation coproduct from the classical one on permutations. Then they proved the vector space spanned by permutations with the shuffle product that is a graded algebra and with the deconcatenation coproduct that is a graded coalgebra [5] in 2020. In the same year, Aval, Bergeron and Machacek introduced the super-shuffle product and the cut-box coproduct on labeled simple graphs without proof [6] . In 2023, Dong [7] proved the vector space spanned by labeled graphs with the super-shuffle product is a graded algebra and with the cut-box coproduct is a graded coalgebra.
In fact, matrices are related to permutations and graphs closely. A (0,1)-matrix is a matrix whose entries are all 0 or 1, also called a binary matrix. It is widely used in graph theory [8] [9] , combinatorics [10] , linear programming [11] [12] [13] and computer science [14] . In this paper, we first generalize the super-shuffle product and the cut-box coproduct from labeled simple graphs to (0,1)-matrices, then we prove that the vector space with the super-shuffle product that is a graded algebra and with the cut-box coproduct that is a graded coalgebra.
This paper is organized as follows. We start by recalling some notations on (0,1)-matrices and defining the vector space
spanned by (0,1)-matrices in Section 2. In Section 3, we define the cut-box coproduct
on
and prove
with coproduct
that is a graded coalgebra. In Section 4, we define the super-shuffle product
on
and prove
with product
that is a graded algebra. Lastly, we summarize our main conclusions in Section 5.
2. Basic Definitions
An
matrix
is called a (0,1)-matrix if
where
is either 0 or 1. In particular, the empty matrix is the matrix with no entries, denoted by
.
Define
and
Let
and
, where
and
. For an
(0,1)-matrix A, the restriction of A on
is the submatrix formed by the entries, in the same relative positions, in both rows indexed by I and columns indexed by J, denoted by
. In particular, if
and
,
and if I or J is empty,
. For convenience, let
denote
and call
the restriction of A on I.
Example 1. The matrix
is a 4 × 7 (0,1)-matrix. We have
and
Let
and
be the vector space spanned by
over field
, for any non-negative integer n. For example,
In particular,
and
. Denote
If A and B are both non-empty matrices, then we denote
, where O’s are zero matrices. In particular,
for any (0,1)-matrix A.
Example 2. For
and
, we have
For A in
, we call i a spilt of A, if
where
. By the definition, 0 and n are always splits of a (0,1)-matrix in
when
, called trivial splits. Obviously,
when i is a trivial spilt of A;
and
when i is a non-trivial spilt of A. We call A indecomposible if it is non-empty and only has trivial splits.
For A in
,
, suppose that
is the set of all splits of A, where
. We call
an atom of A,
. Obviously, there is no non-trivial split of
for
. Let
for
. We define the decomposition of A by
In particular, when A is indecomposable or empty, its decomposition is itself.
Example 3. 1) The set of splits of
is
and its decomposition is
Its atoms are
2) The set of splits of
is
, so it is indecomposable. Its decomposition is itself, and so is its atom.
3. Cut-Box Coproduct and Coalgebra
In this section, we define the cut-box coproduct on the vector space
. Then we prove the space with the cut-box coproduct is a graded coalgebra.
Define the cut-box coproduct
on
by
for non-empty matrix A in
with decomposition
, where
. In particular, define
.
Define the counit
from
to
by
for A in M.
Example 4. From Example 3 and the definition of the cut-box coproduct, we have
and
Theorem 1.
is a graded coalgebra.
Proof. It is easy to verify that
is a counit. Obviously,
Suppose A in
with
and its decomposition is
Then
where
for
. So
satisfies the coassociative law.
Obviously, by the definitions of
and
, we have
and
for
. Hence
is a graded coalgebra.
□
4. Super-Shuffle Product and Algebra
In this section, we define the super-shuffle product on the vector space
. Then we prove the space with the super-shuffle product is a graded algebra.
Define the super-shuffle product
on
by
(1)
for A in
and B in
, where C traverses all matrices in
with the restriction on I is A, on J is B, on
and
are arbitrary (0,1)-matrices. Obviously, the product
is commutative and
, for any A in M. Define the unit
from
to
by
.
Example 5. For
we have
Here, we color the entries of C in
restricted to A red and to B blue, respectively. Although
and
are same matrices, we consider they are different. Then each term in
is unique.
Let
be a set of positive integers where
. Define a mapping
from W to
by
for
, and call it the standardization of W [6] . For a subset T of W, denote
. Obviously,
is a 1-1 mapping from the set of subsets of W to the set of subsets of
. Therefore, for any subset H of
, there must exist a unique subset P of W such that
.
Remark 1. ( [15] ) Let W be a set of positive integers and P be a subset of W. Then there exists a unique subset H in
such that
for any i in P. Actually,
.
Example 6. For
and
,
,
,
,
,
and
. Take
. Furthermore,
,
,
.
Next, in order to prove
is a graded algebra, we give one lemma.
Lemma 2. Assume
is a (0,1)-matrix,
and
. Then there exists a subset P of W such that
.
Proof. By the definition of
, there must exist a subset P of W such that
. Next, we prove
.
Let
be
,
be
and
be
. Obviously, B and D are both (0,1)-matrices. We just need to show that
for each
in
. For
in, there must exist
and
in P such that
,
and. Since P is a subset of W, there must exist
and
in
such that
,
and
. On the other hand, we have
and
is a 1-1 mapping from the set of subsets of W to the set of subsets of
, therefore
and
are in H. Then there must exist
and in
such that
,
and
. Hence,
. By Remark 1, we have
and
Thus, for each
in
,
, i.e.,
. □
Theorem 3.
is a graded algebra.
Proof. It is easy to verify that
is a unit. For A in
, B in
and C in
, we have
Then for any term Y in
, there exist two disjoint subsets W and L of
with
and
such that
is a term in
and
. It means
(2)
For a fixed W in
with cardinality
, there exist two disjoint subsets H and K of
with
and
such that
Since H is a subset of
, due to the Lemma 2, there exists a subset P of W corresponding to H with
such that
and
Similarly, there exists a subset Q of W with
corresponding to K such that
and
In (2), for a fixed subset W in
with cardinality
, H traverses all subsets with cardinality h in
, since
traverses all terms in
. Meanwhile, P traverses all subsets with cardinality h in W. Therefore, P traverses all subsets with cardinality h in
when W traverses all subsets with cardinality
in
. Similarly, Q traverses all subsets with candinality k in
when W traverses all subsets with cardinality
in
from
. Thus (2) can be rewritten as
(3)
Similarly,
can be rewritten as (3). Hence,
satisfies the associative law and
is an algebra.
By the definitions of the product
and
, we have
and
. So
is a graded algebra. □
5. Conclusion and Suggestion
Let
be the vector space spanned by (0,1)-matrices. Firstly, we introduce splits and the decomposition of a (0,1)-matrix. Then we define the cut-box coproduct
and the super-shuffle product
on
. We prove the cut-box coproduct
satisfies coassociativity and the super-shuffle product
satisfies associativity, i.e.,
is a graded coalgebra and
is a graded algebra.
Acknowledgements
This work is supported by the National Natural Science Foundation of China (Nos. 11701339 and 12071265).