![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In this article, we introduce another standard form of linear preservers. This new standard form provides characterizations of the linear transformations on the set of bisymmetric matrices with zero diagonal and zero antidiagonal over antinegative semirings without zero divisors which preserve some sort of term ranks and preserve the matrix that can be determined as the greatest one. The numbers of all possible linear transformations satisfying each condition are also obtained.
Public interest statement
A Boolean matrix is a matrix whose entries are 0 or 1 with addition and multiplication defined as if 0 and 1 are integers, except that 1 + 1 = 1. The term rank of a Boolean matrix A is the minimum number of lines containing all nonzero entries of A. Recently, the study of linear transformations preserving some certain functions over sets of many kinds of matrices has become established. In this article, we provide the patterns of linear transformations preserving term ranks of bisymmetric Boolean matrices via our new standard form. The number of such linear preservers is also counted. Moreover, the results on bisymmetric Boolean matrices are extended to bisymmetric matrices over semirings. We believe that the standard form that we have cooked up will be beneficial and will give a new point of view for research in related areas.
1. Introduction
Linear preserver problems (LPPs) are one of the most active research topics in matrix theory during the past half-century, which have been studied when linear transformations on spaces of matrices leave certain conditions invariant. An excellent reference for LPPs is Pierce et al. (Citation1992). There are many works on LPPs over various algebraic structures. The spaces of matrices over semirings also have been one of them.
Rank preserver problems play a pivotal role in investigating questions regarding other preservers. It can be found in Young & Choi (Citation2008) that there are many nonequivalent definitions of rank functions for matrices over semirings. Among many essential different definitions of rank functions of matrices over semirings, the combinatorial approach leads to the term ranks of such matrices.
Inspired by Beasley, Song and Kang’s recently work, in Beasley, Song, & Kang (Citation2012), on term rank preservers of symmetric matrices with zero diagonal over commutative antinegative semirings with no zero divisors, we investigate linear transformations on bisymmetric matrices whose all diagonal and antidiagonal entries are zeroes over such semirings that preserve some term ranks. We refer to Zhao, Hu, & Zhang (Citation2008) and the references therein for more results and applications of bisymmetric matrices.
The significant survey about LPPs in Chapter 22 of Hogben (Citation2007) indicates that linear preservers often have the standard forms. It turns out that our linear preservers do not possess any former standard forms; however, we invent a new standard form in order to obtain a natural and intrinsic characterization of term rank preserver on bisymmetric matrices whose all diagonal and antidiagonal entries are zeroes over commutative antinegative semirings with no zero divisors.
We organize this article as follows. In Section 2, some of the well-known terminologies and results on LPPs are reviewed and the notations in our work are introduced. In the third section, the results on term rank preservers of bisymmetric Boolean matrices with zero diagonal and zero antidiagonal are presented. Then, we extend the results to the case that all entries of such matrices are in commutative antinegative semirings with no zero divisors in the last section.
2. Definitions and preliminaries
We begin this section with the definition of a semiring. See Golan (Citation1999) for more information about semirings and their properties.
Definition 2.1. A semiring is a set
with two binary operations, addition (
) and multiplication (
), such that:
(i). is a commutative monoid (the identity is denoted by
);
(ii). is a semigroup (the identity, if exists, is denoted by
);
(iii). multiplication is distributive over addition on both sides;
(iv). for all
.
We say that is a commutative semiring if
is a commutative semigroup. A semiring is antinegative if the only element having an additive inverse is the additive identity. For a commutative semiring
, a nonzero element
is called a zero divisor if there exists a nonzero element
such that
.
Throughout this article, we let be a commutative antinegative semiring containing the multiplicative identity with no zero divisors and
is denoted by juxtaposition.
One of the simplest examples of an antinegative semiring without zero divisors is the binary Boolean algebra which is a set of only two elements
and
with addition and multiplication on
defined as though
and
were integers, except that
. Note that
is also called a Boolean semiring. Another example of these semirings is the fuzzy semiring which is the real interval
with the maximum and minimum as its addition and multiplication, respectively. Besides, any nonnegative subsemirings of
are other examples of such semirings.
Let denote the set of all
matrices over
. The usual definitions for addition and multiplication of matrices are applied to such matrices as well. The notation
is used when
. A matrix in
is called a Boolean matrix. A square matrix obtained by permuting rows of the identity matrix is called a permutation matrix.
In order to investigate LPPs on , we give the notions of a linear transformation on
and when it preserves some certain properties.
Definition 2.2. A mapping is said to be a linear transformation if
for all
and
.
Let be a subset of
containing all matrices with a property
and
a linear transformation on
. Then, we say that
preserves the property
if
whenever
for all
and
strongly preserves the property
if
if and only if
for all
.
We next state the most common concept of the standard form in the theory of linear preservers over semirings by the following definitions. Let .
Definition 2.3. A mapping is said to be a half-mapping (on
) if
satisfies the following properties:
(i) is a permutation on
, and
(ii) for all
.
If a half-mapping is also a permutation on , then we call it a half-permutation.
Note that a half-mapping on
is a permutation if
is even, but
is not necessarily a permutation when
is odd. If
is odd, and the half-mapping
on
satisfies
, then
is a permutation and hence a half-permutation.
Definition 2.4. Let be an
Boolean matrix whose only nonzero entry is in the
th row,
a half-mapping on
. We define the matrix induced by
to be the
Boolean matrix whose the
th column is
if
and the
th column is
when
is even, and
when
is odd. The matrix induced by
is denoted by
.
Definition 2.5. Let be a linear transformation. We say that
is induced by
if there exist mappings
and
on
and
, respectively, and a matrix
such that either
(i) for all
; or
(ii) and
for all
,
where denotes the Schur product, i.e.,
for all
.
We let denote the
matrix whose entries equal to
. From now on, the subscripts of matrices may be dropped when the sizes of matrices are clear from the context. We simply say that
is induced by
when
. We also say that
is induced by
if
is induced by
where
is a permutation on
. In general (see (Beasley & Pullman, Citation1987)), a linear transformation
on
induced by
where
and
are permutations on
and
, respectively, and all entries of
are nonzero, is usually called a
operator, where
and
are permutation matrices induced by
and
, respectively.
The characterizations of linear transformations preserving term ranks were first studied by Beasley and Pullman (Beasley & Pullman, Citation1987) in 1987. This work is continued later on (see (Kang & Song, Citation2012; Song & Beasley, Citation2013) and the references therein). We recall the definition of the term rank and its preserver theorem as follows.
Definition 2.6. The term rank of is the minimum number of rows or columns required to contain all the nonzero entries of
.
Theorem 2.7. (Beasley & Pullman, Citation1987) Let be a linear transformation. Then
preserves term ranks
and
if and only if
is induced by
where
and
are permutations on
and
, respectively, and all entries of
are nonzero.
Let denote the set of all
symmetric matrices with entries in
and all diagonal entries equal
. Let
. The matrix
is said to dominate the matrix
, written
or
, if
whenever
for all
. For
, the matrix
with
if
and
otherwise, is denoted
. Let
be the
identity matrix and
. The following theorem is a characterization of linear transformations on
preserving some term ranks provided by Beasley and his colleagues (Beasley et al., Citation2012). They also generalized this result to
.
Theorem 2.8. (Beasley et al., Citation2012) Let be a linear transformation. Then
preserves term rank
and
if and only if
is induced by
where
is a permutation on
.
Recently, the study of linear transformations preserving a certain matrix function on , called the star cover number, was provided in Beasley, Song, Kang, & Lee (Citation2013). The matrix in
whose entries in the
th row and the
th column, except at the
position, are
and
elsewhere is called the full star on row and column
. For
, a star cover of
is a sum of full stars dominating
and the star cover number of
is the minimum number of full stars whose sum dominates
.
Theorem 2.9. (Beasley et al., Citation2013) Let be a linear transformation. Then the following are equivalent:
(i) preserves the star cover number
and
;
(ii) preserves the star cover numbers
and
;
(iii) is induced by
where
is a permutation on
.
To investigate further on bisymmetric matrices over semirings , we let
denote the set of all
bisymmetric matrices with entries in
and all diagonal and antidiagonal entries are
. Note that if
, then
and
for all
. For
, let
be the matrix whose the four entries at the
,
,
and
positions are
and other entries are
. The matrix
is called a quadrilateral cell and the matrix
is called the corresponding quadrilateral cell of
. We let
(or
when the size of matrices is clear) denote the set of all quadrilateral cells in
. For each
, the sum of all
such that
is called the full double star on rows and columns
and
, denoted by
. A double-star matrix is a nonzero matrix in
dominated by a full double star. Let
. The following notion is given in order to investigate more on the preserver problems of the matrix function on
resembling the star cover number of matrices on
.
Definition 2.10. Let . A double-star cover of
is a sum of full double stars that dominates
. The double-star cover number of
is the minimum number of full double stars whose sum dominates
.
Next, a generalization of a linear transformation on induced by
, which turns out to be the standard form for our results, is given by the following definition. We begin with the notation of certain square Boolean matrices. For each
, we let
Definition 2.11. Let be a linear transformation. We say that
is induced by
if there exist a mapping
on
and matrices
such that
for all where
is the set of all quadrilateral cells summing to
.
We say that is induced by
if
is induced by
and
. Observe that (i)
and (ii)
.
To illustrate more clearly, we give the following example.
Example 2.12. Let be the half-mapping on
defined by
Then
.
Let ,
and be a linear transformation on
induced by
. Then the following table shows the images of each quadrilateral cell.
Table
We end this section by introducing some instrumental notions.
Definition 2.13. Let such that
,
and
be Boolean matrices. We define the set
and the set . We write
if
whenever
for all
. We say that matrix
is strongly dominated by
, denoted by
, if there exists
such that
and
for all
.
A matrix is called a tetrasymmetric matrix if
for all
.
3. Term rank preservers of bisymmetric matrices over Boolean semirings
In this section, we first consider linear preservers of bisymmetric matrices with zero diagonal and zero antidiagonal over Boolean semirings in order to generalize this notions to such matrices over other semirings. The following observations are obtained from the structure of the quadrilateral cells and the proofs are skipped.
Lemma 3.1. Let .
(i) is of term rank
or
if and only if
is a double-star matrix.
(ii) For each two distinct elements ,
and
if and only if
.
(iii) If the matrix can be written as
where each
is a full double-star matrix, then
.
The study of linear transformations that strongly preserve a certain property is a common research focus (see (Beasley & Song, Citation2016a, Citation2016b) and references therein). We provide a characterization of linear transformations on preserving the matrix
strongly; i.e.,
is the only matrix mapped to itself.
Lemma 3.2. Let be a linear transformation. Then
preserves the set of all nonzero matrices and
strongly preserves the matrix
if and only if
is bijective on
.
Proof. The sufficient part is obvious. To show the necessary part, we first show that is injective on
. Suppose on the contrary that there are two distinct quadrilateral cells
and
such that
. Let
denote the set
. Then
. This is a contradiction because
.
We suppose further that . Since the images of the quadrilateral cells are not zero, it follows that there exists a quadrilateral cell
such that
for some
distinct quadrilateral cells. Note that
because
strongly preserves the matrix
. Let
denote the set
. Since
, for each
, there exists
such that
. Let
be the collection of such fixed
‘s. Thus
. Then
. This contradicts the fact that
strongly preserves
. Hence
.
Therefore, it follows by the finiteness of that
is surjective on
.
Next, we prove one of the main results of this section.
Theorem 3.3. Let be a linear transformation. Then
(i) preserves double-star matrices, and
(ii) strongly preserves the matrix
if and only if is induced by
where
is a half-permutation and
is a tetrasymmetric matrix.
Proof. Note that is bijective on
because of the properties of
and
. Hence, the sufficient part follows.
To show the necessary part, we first show that for each nonzero matrix ,
is not the zero matrix. Suppose on the contrary that there is a nonzero matrix
such that
is zero. Since
is nonzero, there is a quadrilateral cell
such that
is zero. This is a contradiction because
is a double-star matrix. Hence
is bijective on
by Lemma3.2.
First, we consider the case that . There is nothing to do with the case
because
and
are the sets of the zero matrix.
For , we have
. Since
is bijective on
, it follows that
, i.e.,
is induced by
where
is the identity map on
and
is zero.
For , we have
. This implies that
is the identity map on
or
and
. Consequently,
is induced by
where
is the identity map on
and
is zero or
.
For , we have
. Since
preserves double-star matrices, and each of the three quadrilateral cells summing to
is mapped to three distinct quadrilateral cells, it follows that
or
. Similarly,
or
and we also obtain that
. This implies that
is induced by
where
is the identity map on
or
and
is zero or
.
Now, we consider the case that . We next define a permutation
on
. Since
preserves double-star matrices,
is a double-star matrix for all
. That means for each
,
is dominated by
for some
. Then we define
by
for all
.
To show that is well-defined, we suppose that there exist
such that
and
for some
with
. Then, it follows from Lemma 3.1(ii) that
. Next, we calculate the numbers of quadrilateral cells that are summed to
and
. Note that
We observe that if is odd and , then
, otherwise
. Since
, in both cases, the number of all quadrilateral cells that are summed to
is less than the number of quadrilateral cells excluding
and
. Since
, by the simple pigeonhole principle, the image of some quadrilateral cells dominates at least two quadrilateral cells. Then, there exists a quadrilateral cell
such that
where
,
,
and
. Since
is a double-star matrix, there exists
such that
. Hence,
. Then,
or either
if
, or
if
. For convenience, we may assume that
. We then separate our proof into two cases and two subcases therein.
Case 1. .
Subcase 1.1. .
This means that is the only double-star matrix that dominates
. Since
and
is a double-star matrix, it follows that
. Similarly,
. Note that we can consider
instead of
if
. Notice that the matrix
can be written as
for some
. Then
Thus, is dominated by the sum of at most
full-star matrices. This is a contradiction.
Subcase 1.2. .
Then, . Since
is the only sum of two distinct quadrilateral cells dominated by
, we obtain that
. Thus,
. It follows that
. Similarly,
If and
, then we get a contradiction as the subcase 1.1. Similarly,
and
cannot occur simultaneously. This leaves us either (i)
and
or (ii)
and
. In any cases,
because
is dominated by both
and
and
is linear. Hence,
. Thus,
. This is a contradiction since
is injective on
.
Case 2. .
Subcase 2.1. . This case is impossible.
Subcase 2.2. . In this case, we get a contradiction similarly to the subcase 1.1.
Now we can conclude that is well-defined.
By Lemma, we have that is bijective on
and since
is linear,
is bijective on
. This means that
maps
onto
injectively, and
. Indeed, if
is odd, then
. Hence,
is a permutation on
. Then, we extend
to be a half-permutation on
. That is,
for all
.
Let consider the image of the quadrilateral cells. Let . Without loss of generality, we assume that
. Then,
and
. By Lemma 3.1(ii), we obtain that
Since
sends injectively quadrilateral cells to quadrilateral cells, either
or
.
If , then we can conclude that
for all
and
for all
. Moreover, we obtain the similar result for the case that
. Hence, for each
with
, it follows that either
(i) if , then
for all
, or
(ii) if , then
for all
.
We now construct an Boolean matrix
by letting
(i) for all
;
(ii) if is odd,
whenever
or
;
(iii) for all
and
.
Then, is tetrasymmetric. Let
. Then
(i) implies
; and
(ii) implies
.
Thus, for each ,
. That is
is induced by
, where
is a half-permutation and
is a tetrasymmetric matrix.
From Lemma 3.1(i), we can conclude that preserves the set of all matrices of term ranks
and
if and only if
preserves double-star matrices. We observe that if
is induced by
, where
is a half-permutation and
is a tetrasymmetric matrix, then
preserves term ranks
and
. By these facts and the previous theorem, we obtain immediately the following results. We also provide the number of linear transformations satisfying such assumptions.
Corollary 3.4 Let be a linear transformation. Then
(i) preserves term ranks
and
, and
(ii) strongly preserves the matrix
if and only if is induced by
where
is a half-permutation and
is a tetrasymmetric matrix.
Moreover, the number of such linear transformations is .
Next, we provide the characterization of double-star cover number preservers. Note that when , we obtain the characterization of linear transformations on
preserving double-star cover number easily. From now on, we assume that
.
Theorem 3.5. Let be a linear transformation. Then,
preserves double-star cover numbers
and
if and only if
is induced by
where
is a half-mapping on
,
with
and
provided
is odd.
Moreover, the number of such linear transformations is
Proof . The sufficient part is obvious. To show the necessary part, we first define a permutation on . Since
preserves double-star cover number
, for each
, there exists
such that
. We then define
by
if
for all
.
To show that is well-defined, suppose that there exists
such that
and
where
with
. It follows from Lemma 3.1(ii) that
. Let
with
and
. Then
. Since
is of double-star cover number
, it follows that
or
. We consider only the case that
because the other case is obtained similarly. Then
. This is a contradiction because
is of double-star cover number
, but
is of double-star cover number
. Hence
is well-defined on
. Since
preserves double-star cover number
, it implies that
is a permutation on
. Next, we extend
to be a half-mapping on
.
Now we consider the images of the quadrilateral cells. Let . Without loss of generality, we may assume that
. Then,
and
. This implies that
Since
is nonzero, Boolean matrices
and
can be constructed as follows. Let
for all
and
for all with
. Also, let
for all
and
for all with
. Note that if
, then
because
. This implies that
. We can conclude that
(i) if , then
; and
(ii) if , then
; and
(iii) if , then
.
Thus, for each , it follows that
Consequently, is induced by
, where
is a half-mapping on
and
with
.
Furthermore, if is odd, then there exists
such that
. It follows that, for each
,
. That is
and
for all
. Hence
.
Next, we count the number of such linear transformations. We say that is free if
. The following table shows the possible elements of
and
when
is free.
Table
Case 1. is even. Since the number of half-mappings
is
and there are
sets of
, the number of such linear transformations is
.
Case 2. is odd. If
, then the number of half-mappings
is
and there are
sets of
which is free. Hence, there exist
such possible linear transformations in this case. On the other hand, if
, then the number of half-mappings
is
and the number of
being free is
whenever
and
, otherwise. This implies that the number of such possible linear transformations in this case is
. Therefore, if
is odd, there are
such linear transformations.
We investigate further that if the condition `the linear transformation preserves the matrix
’ is assumed, then, in the proof of Theorem 3.5, the entries of matrices
and
are obtained as follows. For each
, if
, then
and
, otherwise. This leads us to the following corollary.
Corollary 3.6. Let be a linear transformation. Then
(i) preserves double-star cover numbers
and
(ii)
if and only if is induced by
where
is a half-mapping on
,
and
provided
is odd.
Moreover, the number of such linear transformations is
The following lemma shows the relation between the term rank preservers and the double-star cover number preservers. The proof is done by using Lemma 3.1(iii) and considering the image of each quadrilateral cell.
Lemma 3.7. Let be a linear transformation. If
preserves double-star matrices and
, then
preserves double-star cover numbers
and
.
The converse of Lemma 3.7 does not hold as the following example shows.
Example 3.8. Let be defined by
Moreover, let
and
. Consider the linear transformation
on
induced by
.
Then ,
,
,
,
,
,
,
,
and
.
The next corollary is obtained from Lemma 3.1(i), Corollary 3.6 and Lemma 3.7.
Corollary 3.9. Let be a linear transformation. Then, the following are equivalent:
(i) preserves double-star matrices and
;
(ii) preserves the set of all matrices of term ranks
and
, and
;
(iii) preserves double-star cover numbers
and
, and
;
(iv) is induced by
where
is a half-mapping on
,
and
provided
is odd.
4. Term rank preservers of bisymmetric matrices over antinegative semirings
Let . Beasley and Pullman (Beasley & Pullman, Citation1987) defined the pattern
of
to be the Boolean matrix whose
th entry is
if and only if
. We say that
has an
-pattern whenever
. Note that the term ranks of
and
are equal and also the star cover numbers of
and
. For a linear transformation
on
, define
by
A BS_n^(0)
The following lemma is used to extend the results in to
. Note that the proof of this lemma is straightforward so that it is left to the reader.
Definition 4.1. Let be a linear transformation. We say that
is induced by
if there exist a mapping
on
, a matrix
and matrices
such that
for all where
is the set of all quadrilateral cells summing to
.
We say that is induced by
if
is induced by
and
.
Lemma 4.2. Let be a linear transformation. Then,
and
preserve the same term rank and the same double-star cover number.
The following characterizations are obtained by applying the results of the previous section and Lemma 4.2. Simply use the same methods of the proof of Corollary 3.3 in (Beasley et al., Citation2012) but with quadrilateral cells in place of digon cells.
Proposition 4.3. Let be a linear transformation. Then the following are equivalent:
(i) preserves double-star matrices and
strongly preserves
-pattern;
(ii) preserves term ranks
and
, and
strongly preserves
-pattern;
(iii) is induced by
where
is a half-permutation,
is a tetrasymmetric matrix and
is the matrix of
-pattern.
Proposition 4.4. Let be a linear transformation. Then the following are equivalent:
(i) preserves double-star matrices and
preserves
-pattern;
(ii) preserves the set of all matrices of term ranks
and
, and
preserves
-pattern;
(iii) preserves double-star cover numbers
and
, and
preserves
-pattern;
(iv) is induced by
where
is a half-mapping on
,
and
provided
is odd and
is the matrix of
-pattern.
5. Conclusion
A new standard form is carefully given in order to characterize linear transformations preserving term ranks of bisymmetric matrices over semirings with some certain conditions. In this research, we investigate term rank preservers on bisymmetric Boolean matrices. The number of such linear transformations is also determined. Besides, the results on Boolean matrices are extended to matrices over semirings. Moreover, the characterizations of linear transformations preserving the special kind of the term rank, which is called the double-star cover number, on bisymmetric matrices over semirings are provided.
In our opinion, many questions can be further studied as shown in the following examples.
(1) Is it possible to drop the condition that all entries of diagonal and antidiagonal lines of bisymmetric matrices must be zero?
(2) Are there other characterizations of term rank preservers on bisymmetric matrices?
(3) What are characterizations of other rank preservers on bisymmetric matrices?
Acknowledgements
We would like to thank anonymous referees for constructive comments. Furthermore, we are very grateful to every author of all references for inspirational work.
Additional information
Funding
Notes on contributors
L. Sassanapitax
L. Sassanapitax is a PhD student in the Department of Mathematics and Computer Science, Chulalongkorn University. Sajee Pianskool and Apirat Siraworakun are lecturers at Chulalongkorn University and Thepsatri Rajabhat University, respectively. Our research interests are algebra and matrix theory.
References
- Beasley, L. B., & Pullman, N. J. (1987). Term-rank, permanent, and rook-polynomial preservers. Linear Algebra and Its Applications, 90, 33–46. doi:10.1016/0024-3795(87)90302-8
- Beasley, L. B., & Song, S.-Z. (2016a). Zero-term rank and zero-star cover number of symmetric matrices and their linear preservers. Linear Multilinear Algebra. doi:10.1080/03081087.2016.1155534
- Beasley, L. B., & Song, S.-Z. (2016b). Primitive symmetric matrices and their preservers. Linear Multilinear Algebra. doi:10.1080/03081087.2016.1175414
- Beasley, L. B., Song, S.-Z., & Kang, K.-T. (2012). Preservers of term ranks of symmetric matrices. Linear Algebra and Its Applications, 436, 1727–1738. doi:10.1016/j.laa.2011.06.018
- Beasley, L. B., Song, S.-Z., Kang, K.-T., & Lee, S.-G. (2013). A comparison of term ranks of symmetric matrices and their preservers. Linear Algebra and Its Applications, 438, 3745–3754. doi:10.1016/j.laa.2011.03.038
- Golan, J. S. (1999). Semirings and their applications. Dordrecht: Kluwer Academic Publishers.
- Hogben, L. (2007). Handbook of linear algebra. Boca Raton: Chapman & Hall/CRC Press.
- Kang, K.-T., & Song, S.-Z. (2012). Term rank preserves of Boolean matrices. Linear Multilinear Algebra, 60, 241–247. doi:10.1080/03081087.2011.589048
- Pierce, S., et al. (1992). A survey of linear preserver problems. Linear Multilinear Algebra, 33, 1–119. doi:10.1080/03081089208818176
- Song, S.-Z., & Beasley, L. B. (2013). Linear transformations that preserve term rank between different matrix spaces. Journal Korean Mathematical Social, 50, 127–136. doi:10.4134/JKMS.2013.50.1.127
- Young, N., & Choi, Y. (2008). Surveys in contemporary mathematics. Cambridge: Cambridge University Press.
- Zhao, L., Hu, X., & Zhang, L. (2008). Least squares solutions to for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation. Linear Algebra and Its Applications, 428, 871–880. doi:10.1016/j.laa.2007.08.019