# Applications of Matrices to a Matroidal Structure of Rough Sets

Authors: Jingqian Wang; William Zhu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Rough sets provide an efficient tool for dealing with the vagueness and granularity in information systems. They are widely used in attribute reduction in data mining. There are many optimization issues in attribute reduction. Matroids generalize the linear independence in vector spaces and are widely used in optimization. Therefore, it is necessary to integrate rough sets and matroids. In this paper, we apply matrices to a matroidal structure of rough sets through three sides, which are characteristics, operations, and axioms. Firstly, a matroid is induced by an equivalence relation, and the matroid is a representable matroid whose representable matrix is a matrix representation of the equivalence relation. Then some characteristics of the matroid are presented through the representable matrix mainly. Secondly, contraction and restriction operations are applied to the matroid through the representable matrix and approximation operators of rough sets. Finally, two axioms of circuit incidence matrices of 2-circuit matroids are obtained, where 2-circuit matroids are proposed based on the characteristics of the matroid. In a word, these results show an interesting view to investigate the combination between rough sets and matroids through matrices.


---

## Body

## 1. Introduction

Rough set theory was proposed by Pawlak [1, 2] in 1982 as a tool to conceptualize, organize, and analyze various types of data in data mining. It has been widely used to deal with many practical problems, such as attribute reduction [3, 4], feature selection [5–7], rule extraction [8–11], and knowledge discovery [12–14]. Moreover, through extending equivalence relations or partitions, rough set theory has been extended to generalized rough sets based on relations [15, 16] and covering-based rough sets [17, 18].However, many important problems including attribute reduction in rough sets are NP-hard. Therefore, the algorithms to solve them are often greedy ones [19, 20]. Matroid theory [21–23] is a generalization of linear algebra and graph theory and provides well-established platforms for greedy algorithms [24]. It has been used in diverse fields, such as combinatorial optimization [25], algorithm design [24], information coding [26], and cryptology [27]. Hence, matroid theory may bring new chances for rough set theory. Recently, matroid theory has been connected with other theories, such as rough set theory [28–31] and lattice theory [32, 33].In this paper, we apply matrices to a matroidal structure of rough sets through three sides, which are characteristics, operations, and axioms. Firstly, a matroid is induced by an equivalence relation on a universe through the circuit axiom, and a matrix representation of the equivalence relation is a representable matrix of the matroid. Then some characteristics of the matroid, which are bases, the rank function, and circuits, are presented through the representable matrix of the matroid mainly. Secondly, contraction and restriction operations are applied to the matroid through the representable matrix and approximation operators of rough sets. We present some relationships between some new matroids, which are obtained by using contraction and restriction operations. For example, we present a relationship between these two matroids: one is the contraction of the matroid to the complement of a single point set; the other one is a vector matroid of a matrix obtained from the representable matrix by deleting all the columns whose labels are in the equivalence class of this point. Finally, the matroid belongs to a type of matroids, which is called 2-circuit matroid. Two axioms of circuit incidence matrices of 2-circuit matroids are obtained.The rest of this paper is organized as follows. Section2 reviews some fundamental definitions about rough sets and matroids. In Section 3, we prove that the matroid induced by an equivalence relation is a representable matroid, and some characteristics of the matroid are presented through the representable matrix of the matroid mainly. Then contraction and restriction operations are applied to the matroid through the representable matrix and approximation operators of rough sets. In Section 4, the matroid belongs to a type of matroids called 2-circuit matroid. Two axioms of circuit incidence matrices of 2-circuit matroids are obtained. Finally, Section 5 concludes this paper and indicates further works.


## 2. Basic Definitions

This section recalls some fundamental definitions related to Pawlak’s rough sets and matroids.


### 2.1. Pawlak’s Rough Sets

Rough set theory provides a systematic approach to data preprocessing in data mining. In information or decision systems, any attribute subset is characterized by an equivalence relation. The following definition shows that a universe together with an equivalence relation on it forms an approximation space.Definition 1 (approximation space [34, 35]).
LetU be a nonempty and finite set called universe and R an equivalence relation on U. The ordered pair (U,R) is called a Pawlak’s approximation space.In rough sets, a pair of approximation operators is used to describe an object. In the following definition, we introduce the pair of approximation operators.Definition 2 (approximation operator [34, 35]).
LetR be an equivalence relation on U. A pair of approximation operators R*, R*:2U→2U, is defined as follows: for all X⊆U,
(1)R*(X)={x∈U:RN(x)⊆X},R*(X)={x∈U:RN(x)⋂X≠∅},
where RN(x)={y∈U:xRy}. They are called the lower and upper approximation operators with respect to R, respectively.In an approximation space, if a subset can be precisely described by an equivalence relation, then it is called a precise set; otherwise, it is called a rough set.Definition 3 (R-rough set [34, 35]).
LetR be an equivalence relation on U. For all X⊆U, if R*(X)=R*(X), then X is called a R-precise set; otherwise, X is called a R-rough set.


### 2.2. Matroids

Matroids draw heavily on both linear algebra and graphs for their motivation and notation. They have a variety of applications in combinatorial optimization, algorithm design, information coding, and cryptology. In the following definition, one of the most valuable definitions of matroids is presented from the viewpoint of independent sets.Definition 4 (matroid [21, 23]).
A matroidM is an ordered pair (U,I) where U (the ground set) is a finite set and I (the family of independent sets) is a family of subsets of U with the following properties:(I1)∅∈I
;(I2)
ifI∈I and I′⊆I, then I′∈I;(I3)
ifI1,I2∈I and |I1|<|I2|, then there exists e∈I2-I1 such that I1⋃‍{e}∈I, where |I| denotes the cardinality of I.We shall often writeU(M) for U and I(M) for I, particularly when several matroids are being considered. A type of matroids is provided to show that matroids generalize the linear independence in vector spaces.Proposition 5 (vector matroid [21, 23]).
LetU be the set of column labels of a matrix A=(aij)m×n over a field F and I the family of subsets X of U for which the columns labelled by X are linearly independent in the vector space V(m,F). Then (U,I) is a matroid, and it is called the vector matroid of A, denoted by M[A].Note that, the field used in this paper is real number fieldR. The transpose of a matrix A is denoted by A⊤. In order to show that linear algebra is an original source of matroid theory, we present an example from the viewpoint of the linear independence in vector spaces.Example 6.
LetA=(100-1010-10010)a1ia2ia3ia4 and U={a1,a2,a3,a4} be the set of all column labels of A. We suppose that I={X⊆U: the columns labelled by X are linearly independent in V(3,R)}; that is, I={∅, {a1}, {a2}, {a3}, {a4}, {a1,a2}, {a1,a3}, {a1,a4}, {a2,a3}, {a2,a4}, {a3,a4}, {a1,a2,a3}, {a1,a3,a4}, {a2,a3,a4}}. Then M=(U,I) is a vector matroid, denoted by M[A].A type of matroids named representable matroids is defined through vector matroids.Definition 7 (representable matroid [21, 23]).
LetM be a matroid. M is called representable matroid if there exist a field F and a matrix A over F such that M=M[A]. A is called a representable matrix of M.If a subset of the ground set is not an independent set of a matroid, then it is called a dependent set of the matroid. Based on the dependent set, we introduce the circuit of a matroid. For this purpose, some denotations are presented.Definition 8 (see [21, 23]).
LetA be a family of subsets of U. One can denote the following:Low(A)={X⊆U:∃A∈A(X⊆A)};Min(A)={X∈A:∀Y∈A,Y⊆X⇒X=Y};Opp(A)={X⊆U:X∉A}.The dependent set of a matroid generalizes the linear dependence in vector spaces and the cycle in graphs. Any circuit of a matroid is a minimal dependent set.Definition 9 (circuit [21, 23]).
LetM=(U,I) be a matroid. A minimal dependent set in M is called a circuit of M, and we denote the family of all circuits of M by C(M); that is, C(M)=Min(Opp(I)).Example 10 (continued from Example6).
C
(
M
)
=
Min
(
{
X
⊆
U: the columns labelled by X are linearly dependent in V(3,R)}); that is, C(M)={{a1,a2,a4}}.The following proposition shows that a matroid can be defined from the viewpoint of circuits.Proposition 11 (circuit axiom [21, 23]).
LetC be a family of subsets of U. Then there exists a matroid M such that C=C(M) if and only if C satisfies the following three conditions:(C1)∅∉C
;(C2)
ifC1,C2∈CandC1⊆C2, thenC1=C2;(C3)
ifC1,C2∈C, C1≠C2, andx∈C1⋂‍C2, then there existsC3∈Csuch thatC3⊆(C1⋃‍C2)-{x}.The following definition shows that a base of a matroid is a maximal independent set.Definition 12 (base [21, 23]).
LetM=(U,I) be a matroid. A maximal independent set in M is called a base of M, and we denote the family of all bases of M by B(M); that is, B(M)=Max(I).The following proposition shows that a matroid can be determined by its bases.Proposition 13 (base axiom [21, 23]).
LetB be a family of subsets of U. Then there exists a matroid M such that B=B(M) if and only if B satisfies the following two conditions:(B1)B≠∅
;(B2)
ifB1,B2∈Bandx∈B1-B2, then there exists an elementy∈B2-B1such that(B1-{x})∪{y}∈B.The rank of a matrix and the dimension of a vector space are important concepts in linear algebra. The following definition is a generalization of these two concepts.Definition 14 (rank function [21, 23]).
LetM=(U,I) be a matroid. The rank function rM of M is defined as rM(X)=max{|I|:I⊆X,I∈I} for all X⊆U. rM(X) is called the rank of X in M.


## 2.1. Pawlak’s Rough Sets

Rough set theory provides a systematic approach to data preprocessing in data mining. In information or decision systems, any attribute subset is characterized by an equivalence relation. The following definition shows that a universe together with an equivalence relation on it forms an approximation space.Definition 1 (approximation space [34, 35]).
LetU be a nonempty and finite set called universe and R an equivalence relation on U. The ordered pair (U,R) is called a Pawlak’s approximation space.In rough sets, a pair of approximation operators is used to describe an object. In the following definition, we introduce the pair of approximation operators.Definition 2 (approximation operator [34, 35]).
LetR be an equivalence relation on U. A pair of approximation operators R*, R*:2U→2U, is defined as follows: for all X⊆U,
(1)R*(X)={x∈U:RN(x)⊆X},R*(X)={x∈U:RN(x)⋂X≠∅},
where RN(x)={y∈U:xRy}. They are called the lower and upper approximation operators with respect to R, respectively.In an approximation space, if a subset can be precisely described by an equivalence relation, then it is called a precise set; otherwise, it is called a rough set.Definition 3 (R-rough set [34, 35]).
LetR be an equivalence relation on U. For all X⊆U, if R*(X)=R*(X), then X is called a R-precise set; otherwise, X is called a R-rough set.


## 2.2. Matroids

Matroids draw heavily on both linear algebra and graphs for their motivation and notation. They have a variety of applications in combinatorial optimization, algorithm design, information coding, and cryptology. In the following definition, one of the most valuable definitions of matroids is presented from the viewpoint of independent sets.Definition 4 (matroid [21, 23]).
A matroidM is an ordered pair (U,I) where U (the ground set) is a finite set and I (the family of independent sets) is a family of subsets of U with the following properties:(I1)∅∈I
;(I2)
ifI∈I and I′⊆I, then I′∈I;(I3)
ifI1,I2∈I and |I1|<|I2|, then there exists e∈I2-I1 such that I1⋃‍{e}∈I, where |I| denotes the cardinality of I.We shall often writeU(M) for U and I(M) for I, particularly when several matroids are being considered. A type of matroids is provided to show that matroids generalize the linear independence in vector spaces.Proposition 5 (vector matroid [21, 23]).
LetU be the set of column labels of a matrix A=(aij)m×n over a field F and I the family of subsets X of U for which the columns labelled by X are linearly independent in the vector space V(m,F). Then (U,I) is a matroid, and it is called the vector matroid of A, denoted by M[A].Note that, the field used in this paper is real number fieldR. The transpose of a matrix A is denoted by A⊤. In order to show that linear algebra is an original source of matroid theory, we present an example from the viewpoint of the linear independence in vector spaces.Example 6.
LetA=(100-1010-10010)a1ia2ia3ia4 and U={a1,a2,a3,a4} be the set of all column labels of A. We suppose that I={X⊆U: the columns labelled by X are linearly independent in V(3,R)}; that is, I={∅, {a1}, {a2}, {a3}, {a4}, {a1,a2}, {a1,a3}, {a1,a4}, {a2,a3}, {a2,a4}, {a3,a4}, {a1,a2,a3}, {a1,a3,a4}, {a2,a3,a4}}. Then M=(U,I) is a vector matroid, denoted by M[A].A type of matroids named representable matroids is defined through vector matroids.Definition 7 (representable matroid [21, 23]).
LetM be a matroid. M is called representable matroid if there exist a field F and a matrix A over F such that M=M[A]. A is called a representable matrix of M.If a subset of the ground set is not an independent set of a matroid, then it is called a dependent set of the matroid. Based on the dependent set, we introduce the circuit of a matroid. For this purpose, some denotations are presented.Definition 8 (see [21, 23]).
LetA be a family of subsets of U. One can denote the following:Low(A)={X⊆U:∃A∈A(X⊆A)};Min(A)={X∈A:∀Y∈A,Y⊆X⇒X=Y};Opp(A)={X⊆U:X∉A}.The dependent set of a matroid generalizes the linear dependence in vector spaces and the cycle in graphs. Any circuit of a matroid is a minimal dependent set.Definition 9 (circuit [21, 23]).
LetM=(U,I) be a matroid. A minimal dependent set in M is called a circuit of M, and we denote the family of all circuits of M by C(M); that is, C(M)=Min(Opp(I)).Example 10 (continued from Example6).
C
(
M
)
=
Min
(
{
X
⊆
U: the columns labelled by X are linearly dependent in V(3,R)}); that is, C(M)={{a1,a2,a4}}.The following proposition shows that a matroid can be defined from the viewpoint of circuits.Proposition 11 (circuit axiom [21, 23]).
LetC be a family of subsets of U. Then there exists a matroid M such that C=C(M) if and only if C satisfies the following three conditions:(C1)∅∉C
;(C2)
ifC1,C2∈CandC1⊆C2, thenC1=C2;(C3)
ifC1,C2∈C, C1≠C2, andx∈C1⋂‍C2, then there existsC3∈Csuch thatC3⊆(C1⋃‍C2)-{x}.The following definition shows that a base of a matroid is a maximal independent set.Definition 12 (base [21, 23]).
LetM=(U,I) be a matroid. A maximal independent set in M is called a base of M, and we denote the family of all bases of M by B(M); that is, B(M)=Max(I).The following proposition shows that a matroid can be determined by its bases.Proposition 13 (base axiom [21, 23]).
LetB be a family of subsets of U. Then there exists a matroid M such that B=B(M) if and only if B satisfies the following two conditions:(B1)B≠∅
;(B2)
ifB1,B2∈Bandx∈B1-B2, then there exists an elementy∈B2-B1such that(B1-{x})∪{y}∈B.The rank of a matrix and the dimension of a vector space are important concepts in linear algebra. The following definition is a generalization of these two concepts.Definition 14 (rank function [21, 23]).
LetM=(U,I) be a matroid. The rank function rM of M is defined as rM(X)=max{|I|:I⊆X,I∈I} for all X⊆U. rM(X) is called the rank of X in M.


## 3. Matrix and the Matroid Induced by an Equivalence Relation

In this section, we prove that the matroid induced by an equivalence relation is a representable matroid, and some characteristics of the matroid are presented through a representable matrix of the matroid mainly. Then contraction and restriction operations are applied to the matroid through the representable matrix and approximation operators of rough sets.


### 3.1. Characteristics of the Matroid through Matrices

In this subsection, a matroid is induced by an equivalence relation on a universe, and a matrix representation of the equivalence relation is a representable matrix of the matroid. Some characteristics of the matroid are presented through the representable matrix mainly. The following proposition shows that the matroid can be induced through the circuit axiom.Proposition 15 (see [29]).
LetR be an equivalence relation on U. One has that
(2){{x,y}⊆U:x≠y,(x,y)∈R}
satisfies (C1), (C2), and (C3) of Proposition 11. Then there exists a matroid M such that C(M)={{x,y}⊆U:x≠y,(x,y)∈R}, and we denote this matroid by M(R).In order to find a matrix to prove that the matroid induced by an equivalence relation is a representable matroid, a matrix representation of an equivalence relation is presented in the following definition.Definition 16.
LetR be an equivalence relation on U={x1,x2,…,xn} and a partition U/R={P1,P2,…,Pm}. We define a Boolean matrix AR=(aij)m×n as follows:
(3)aij={1,xj∈Pi,0,xj∉Pi.xj labels the jth column and Pi labels the ith row. AR is called a matrix representation of R.Note thataij is 1 or 0 depending on whether xj is or is not in Pi. An equivalence relation on a universe may have different matrix representations because of the randomness of the order of a set.Example 17.
LetU={a,b,c} and U/R={{a},{b,c}}. Then AR={a}{b,c}(100011)a0b0c, AR′={b,c}{a}(011100)a0b0c, and AR′′={a}{b,c}(010101)b0a0c are some matrix representations of R.On one hand, according to Definition16, two matrix representations of R with different orders of column labels have the same vector matroid because the columns labelled by X⊆U in these two matrices have the same linear dependence. On the other hand, there is an important result in matroid theory that a matrix and its row elementary transformed matrix have the same vector matroid. Therefore, all matrix representations of R induce the same vector matroid.Example 18 (continued from Example17).
M
[
A
R
]
=
(
U
,
I
(
M
[
A
R
]
), where I(M[AR])=Low({{a,b},{a,c}}); M[AR′]=(U,I(M[AR′])), where I(M[AR′])=I(M[AR]); M[AR′′]=(U,I(M[AR′′])), where I(M[AR′′])=I(M[AR]). Therefore, M[AR]=M[AR′]=M[AR′′].The following proposition shows that the matroid induced by an equivalence relation is a representable matroid, and a matrix representation of the equivalence relation is a representable matrix of the matroid.Proposition 19.
LetR be an equivalence relation on U={x1,x2,…,xn} and U/R={P1,P2,…,Pm}. Then M(R)=M[AR].Proof.
LetAR=x1x2⋯xn(α1α2⋯αn). Since M(R) and M[AR] have the same ground set, so we need to prove only that C(M(R))=C(M[AR]). According to Proposition 5 and Definition 9, C(M[AR])=Min({C⊆U: the columns labelled by C are linearly dependent in V(m,R)}). According to Definition 16, αi≠(0⋯0)⊤. Hence, {xi}∉C(M[AR]) for all i∈{1,2,…,n}. For any {xi,xj}∈C(M(R)), (xi,xj)∈R. According to Definition 16, the columns labelled by xi and xj are the same. Therefore, the columns labelled by {xi,xj} are linearly dependent in V(m,R). Hence, {xi,xj}∈C(M[AR]); that is, C(M(R))⊆C(M[AR]). Conversely, if C∈C(M[AR])-C(M(R)), according to (C2) of Proposition 11, {x,y}⫅C for any {x,y}∈C(M(R)). Therefore, for any xi,xj∈C and xi≠xj, (xi,xj)∉R. According to Definition 16, there is only a 1 in every column of AR and the columns labelled by C are different. Hence, the columns labelled by C are linearly independent in V(m,R), which is contradictory with C∈C(M[AR]). Thus C(M[AR])⊆C(M(R)). This completes the proof.Using the representable matrix of the matroid induced by an equivalence relation, some characteristics of the matroid will be obtained. For this purpose, the following definition proposes a function from a power set of a set to a set ofn-dimensional 0-1 vectors.Definition 20 (see [36]).
IfU={x1,x2,…,xn} and X⊆U, then the characteristic function of X is defined as φ(X)=(a1,…,ai,…,an), where
(4)ai={1,xi∈X,0,xi∉X.As we know,φ is a bijection from 2U to the set of all n-dimensional 0-1 vectors. Let A=(aij)m×n and B=(bij)n×l be Boolean matrices. Then A⊙B=(cij)m×l, where cij=∨s=1n(ais∧bsj) and ∨, ∧ denote maximum and minimum, respectively. In this paper, ⊙ denotes Boolean product of matrices and “·” denotes multiplication of matrices.The following proposition presents the family of bases of the matroid induced by an equivalence relation from the viewpoint of a representable matrix of the matroid.Proposition 21.
LetR be an equivalence relation on U. Then B(M(R))=Min({X⊆U:AR⊙(φ(X))⊤=1v}), where 1v is a column vector whose entries are all 1.Proof.
For anyX⊆U and AR⊙(φ(X))⊤=1v, we have RN(x)⋂‍X≠∅ for any x∈U. Therefore, Min({X⊆U:AR⊙(φ(X))⊤=1v})=Min({X⊆U:∀x∈U,RN(x)⋂‍X≠∅}). According to Definition 8, Min({X⊆U:∀x∈U,RN(x)⋂‍X≠∅})={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. First of all, we should prove that {X⊆U:∀x∈U,|RN(x)⋂‍X|=1} satisfies (B1) and (B2) of Proposition 13.(B1)
: It is straightforward that{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}≠∅.(B2)
: IfB1,B2∈{X⊆U:∀x∈U,|RN(x)⋂‍X|=1} and s∈B1-B2,then there exists y∈B2-B1 and y∈RN(s). Since B1⋂‍RN(s)={s}, so ((B1-{s})⋃‍{y})⋂‍RN(s)={y}. For any z∈U-RN(s), |((B1-{s})⋃‍{y})⋂‍RN(z)|=1. Therefore, ((B1-{s})⋃‍{y})∈{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}.
Hence,{X⊆U:∀x∈U,|RN(x)⋂‍X|=1} satisfies (B1) and (B2) of Proposition 13. Then we should prove that the matroid whose family of bases is {X⊆U:∀x∈U,|RN(x)⋂‍X|=1} is M(R); that is, they have the same family of circuits. Since Low({X⊆U:∀x∈U,|RN(x)⋂‍X|=1})={X⊆U:∀x∈U,|RN(x)⋂‍X|≤1}, so Min(Opp({X⊆U:∀x∈U,|RN(x)⋂‍X|≤1}))=Min({X⊆U:∃x∈U,|RN(x)⋂‍X|≥2})= {{x,y}⊆RN(x):x≠y}=C(M(R)). Hence, B(M(R))=Min({X⊆U:AR⊙(φ(X))⊤=1v}). This completes the proof.According to Proposition21, a representable matrix of the matroid induced by an equivalence relation and the corresponding characteristic function can get the family of bases of the matroid. In order to get the family of bases of the matroid, we need to get only one representable matrix.Example 22 (continued from Example17).
A
R
⊙
(
φ
(
{
a
}
)
)
⊤ = (100011)⊙(100)⊤ = (100011)⊙(100)=(10); AR⊙(φ({b}))⊤=AR⊙(010)⊤=(01); AR⊙(φ({c}))⊤=(01); AR⊙(φ({a,b}))⊤=(11); AR⊙(φ({a,c}))⊤=(11); AR⊙(φ({b,c}))⊤=(01); AR⊙(φ({a,b,c}))⊤=(11). Hence, B(M(R))=Min({{a,b},{a,c},{a,b,c}})={{a,b},{a,c}}.The following proposition presents another method to obtain the family of bases of the matroid induced by an equivalence relation from the viewpoint of a representable matrix.Proposition 23.
LetR be an equivalence relation on U={x1,x2,…xn}, U/R={P1,P2,…,Pm}, and AR=(aij)m×n. Then B(M(R))={{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}.Proof.
According to the proof of Proposition21, B(M(R))={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. We need to prove only {{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. For all X∈{{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}, suppose that X={xj1,xj2,…,xjm}. Since a1j1a2j2⋯amjm=1, so aiji=1 for any 1≤i≤m. Therefore, xji∈Pi; that is, |X⋂‍RN(x)|=1 for any x∈U. Hence, {{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}⊆{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. Conversely, for all X∈{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}, it is straightforward that X∈{{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}. Therefore, {X⊆U:∀x∈U,|RN(x)⋂‍X|=1}⊆{{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}. This completes the proof.The following definition presents a matrix related to circuits of a matroid.Definition 24 (circuit incidence matrix [21, 23]).
LetM be a matroid on U={x1,x2,…,xn} and C(M)={C1,C2,…,Cm}. A circuit incidence matrix of M is A(C(M))=(aij)m×n, where
(5)aij={1,xj∈Ci,0,xj∉Ci.According to Definition24, circuits can be replaced by bases of a matroid. Therefore, we can also get a base incidence matrix. Let M be a matroid on U={x1,x2,…,xn} and B(M)={B1,B2,…,Bm}. A base incidence matrix of M is A(B(M))=(aij)m×n, where
(6)aij={1,xj∈Bi,0,xj∉Bi.Note that the matroid induced by an equivalence relation may have different base incidence matrices because of the randomness of the order of a set. But these base incidence matrices can induce a unique rank function of the matroid.Proposition 25.
LetR be an equivalence relation on U and X⊆U. Then rM(R)(X)=max1≤i≤lbi, where
(7)(b1⋮bi⋮bl)=A(B(M(R)))·φ(X)⊤.Proof.
It is straightforward thatbi=|Bi⋂‍X|, where Bi∈B(M(R)). Suppose that bj=max1≤i≤lbi. Since Bj∈B(M(R)), so Bj⋂‍X∈I(M(R)). In fact, if there exists I1∈I(M(R)) such that |I1⋂‍X|>|Bj⋂‍X|, then there must be a Bk∈B(M(R)) such that I1⊆Bk. Therefore, bk=|Bk⋂‍X|≥|I1⋂‍X|>|Bj⋂‍X|=bj, which is contradictory with bj=max1≤i≤lbi. Hence, rM(R)(X)=max1≤i≤lbi. This completes the proof.Example 26 (continued from Example22).
LetX1={a,b}, and X2={b,c}, A(B(M(R)))=(110101)a0b0c. Since A(B(M(R)))·φ(X1)⊤=(110101)·(110)=(21), so rM(R)(X1)=2; since A(B(M(R)))·φ(X2)⊤=(11), so rM(R)(X2)=1.The rank function of the matroid induced by an equivalence relation can also be obtained through the representable matrix of the matroid.Proposition 27.
LetR be an equivalence relation on U and X⊆U. Then rM(R)(X)=1v·(AR⊙φ(X)⊤), where 1v is a row vector whose entries are all 1.Proof.
Suppose thatU/R={P1,P2,…,Pm}. The ith entry of AR⊙φ(X) is 1 or 0 depending on whether or not Pi⋂‍X≠∅. It is straightforward that 1v·(AR⊙φ(X)⊤)=|{RN(x):x∈U,RN(x)⋂‍X≠∅}|. We need to prove only that rM(R)(X)=|{RN(x):x∈U,RN(x)⋂‍X≠∅}|. According to Proposition 25, rM(R)(X)=max{|B⋂‍X|:B∈B(M(R))}. According to the proof of Proposition 21, B(M(R))={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. Therefore, rM(R)(X)=|{RN(x):x∈U,RN(x)⋂‍X≠∅}|. This completes the proof.Example 28 (continued from Example26).
r
M
(
R
)
(
X
1
)
=
1
v
·
(
A
R
⊙
φ
(
X
1
)
⊤
)
=
(
1
1
)
·
(
(
1
1
0
1
0
1
)
⊙
(
1
1
0
)
)
=
(
1
1
)
·
(
1
1
)
=
2.
Propositions25 and 27 present two direct and simple methods to calculate the rank function of the matroid induced by an equivalence relation compared with the traditional method in Definition 14. In fact, the rank function of the matroid can be used in attribute reduction of information systems. Integrating these two methods with the following theorem which presents an equivalent formulation of attribute reduction of information systems, one can obtain a reduct of an information system.Theorem 29 (see [29]).
LetIS=(U,A) be an information system. For all B⊆A, B is a reduct of IS if and only if it satisfies the following two conditions:(1)
∀b∈B,{X⊆U:∀c∈B-{b},rM(c)(X)=1}≠{X⊆U:∀c∈B,rM(c)(X)=1};(2)
{X⊆U:∀b∈B,rM(b)(X)=1}={X⊆U:∀a∈A,rM(a)(X)=1},where M(a) denotes the matroid induced by the equivalence relation induced by attribute subset {a}.In order to present circuits of the matroid induced by an equivalence relation from the viewpoint of matrices, a new matrix is established through a matrix representation of an equivalence relation and its transpose.Lemma 30.
LetR be an equivalence relation on U={x1,x2,…,xn}. Then AR⊤·AR=(bij)n×n is a relational matrix of R, where
(8)bij={1,(xi,xj)∈R,0,otherwise.Note that the matrix representation of an equivalence relation is the representable matrix of the matroid induced by the equivalence relation. Therefore, the family of circuits of the matroid can be obtained through the representable matrix. Letei be a n-dimensional 0-1 vector in which only the ith entry is 1; that is, ei=(0,…,0,1,0,…,0).Proposition 31.
LetR be an equivalence relation on U and U={x1,x2,…,xn}. Then C(M(R))={{xi,xj}:ei·(AR⊤·AR)·ej⊤=1(1≤i<j≤n)}.Proof.
We need to prove only that{{xi,xj}:ei·(AR⊤·AR)·ej⊤=1(1≤i<j≤n)}={{xi,xj}⊆U:xi≠xj,(xi,xj)∈R}. Let AR⊤·AR=(bij)n×n. For any 1≤i<j≤n,ei·(AR⊤·AR)·ej⊤=bij. According to Lemma 30, bij=1 if and only if (xi,xj)∈R. Since R is an equivalence relation, so AR⊤·AR is a symmetric matrix. Therefore, {{xi,xj}:ei·(ARΤ·AR)·ej⊤=1(1≤i<j≤n)}={{xi,xj}:(xi,xj)∈R(1≤i<j≤n)}={{xi,xj}⊆U:xi≠xj,(xi,xj)∈R}. This completes the proof.Example 32 (continued from Example22).
There isAR⊤·AR = (100101)·(100011)=abck(100011011)a0b0c. Hence, C(M(R))={{b,c}}.


### 3.2. Contraction and Restriction Operations through Matrices

This subsection applies contraction and restriction operations to the matroid induced by an equivalence relation through the representable matrix and approximation operators of rough sets. First of all, the concepts of these two operations are presented in the following two propositions. In fact, two new matroids are obtained by applying restriction and contraction operations to a matroid, respectively.Proposition 33 (restriction and deletion [21, 23]).
LetM=(U,I) be a matroid and X⊆U. Then (X,IX) is a matroid, where IX={I⊆X:I∈I}. We call this matroid the restriction of M to X and denote it by M∣X. M∖X=(U-X,IU-X) is called the deletion of U-X from M.Proposition 34 (contraction [21, 23]).
LetM=(U,I) be a matroid and X⊆U and BX is a base of M∣X (i.e., BX∈B(M|mX)). Then (U-X,I′) is matroid, where I′={I⊆U-X:I⋃‍BX∈I}. We call this matroid the contraction of M to U-X and denote it by M/X.Note that the definition ofM/X has no relationship with the selection of BX∈B(M∣X). The following lemma shows an interesting relationship between a single point set and the equivalence class of this point through applying contraction and restriction operations to the matroid induced by an equivalence relation.Lemma 35 (see [37]).
LetR be an equivalence relation on U. For all x∈U, I(M(R)/{x})=I(M(R)/RN(x))=I(M(R)∖RN(x)).LetA be a matrix over F and X a subset of the set U of column labels of A. We shall denote by A⊖X the matrix obtained from A by deleting all the columns whose labels are in X.Inspired by Lemma35, we obtain a relationship between two matroids, which are the contraction of the matroid induced by an equivalence relation to the complement of a single point set and a vector matroid of a matrix obtained from the representable matrix by deleting all the columns whose labels are in the equivalence class of this point.Proposition 36.
LetR be an equivalence relation on U. Then I(M(R)/{x})=I(M[AR⊖RN(x)]).Proof.
According to Proposition19 and Lemma 35, we need to prove only that I(M[AR]∖RN(x))=I(M[AR⊖RN(x)]). According to Proposition 33, I(M[AR]∖RN(x))={I⊆U(M[AR])-RN(x):I∈I(M[AR])}. According to Proposition 5, I∈I(M[AR]∖RN(x)) if and only if I⊆U(M[AR])-RN(x) and the columns labelled by I are linearly independent. I∈I(M[AR⊖RN(x)]) if and only if I⊆U(M[AR⊖RN(x)]) and the columns labelled by I are linearly independent. Since U(M[AR]) is the set of all columns of AR and U(M[AR⊖RN(x)]) is the set of all columns of AR⊖RN(x), so U(M[AR])-RN(x)=U(M[AR⊖RN(x)]). Hence, I(M[AR]∖RN(x))=I(M[AR⊖RN(x)]). This completes the proof.Note that the above proposition also shows a relationship between a single point set and the equivalence class of this point.Example 37 (continued from Example22).
SinceRN(b)={b,c} and
(9)AR⊖RN(b)=(100011)a00b00c⊖{b,c}=(10)a,
so I(M[AR⊖RN(b)])={∅,{a}}. Since B(M(R))={{a,b},{a,c}}, so I(M(R))=Low(B(M(R)))={∅,{a},{b},{c},{a,b},{a,c}}, M(R)∣{b}=({b},I{b}), {b}∈B(M(R)∣{b}), where I{b}={∅,{b}} and B(M(R)∣{b})={{b}}. Hence, I(M(R)/{b})={∅,{a}}. Therefore, I(M(R)/{b})=I(M[AR⊖RN(b)]).The following corollary presents an equivalent description of the above proposition from the viewpoint of upper approximations.Corollary 38.
LetR be an equivalence relation on U. Then I(M(R)/{x})=I(M[AR⊖R*({x})]).When we apply a sequence of operations to the matroid induced by an equivalence relation like Lemma35, the following lemma is obtained.Lemma 39 (see [37]).
LetR be an equivalence relation on U. For all X⊆U, I(M(R)/X)=I(M(R)/R*(X))=I(M(R)∖R*(X)).Inspired by Proposition36, we obtain the similar relationship between a subset and the upper approximation of this subset through these two operations and the representable matrix of the matroid induced by an equivalence relation.Proposition 40.
LetR be an equivalence relation on U. Then I(M(R)/X)=I(M[AR⊖R*(X)]).Proof.
According to Proposition19 and Lemma 39, we need to prove only that I(M[AR]∖R*(X))=I(M[AR⊖R*(X)]). According to Proposition 33, I(M[AR]∖R*(X))={I⊆U(M[AR])-R*(X):I∈I(M[AR])}. According to Proposition 5, I∈I(M[AR]∖R*(X)) if and only if I⊆U(M[AR])-R*(X) and the columns labelled by I are linearly independent. I∈I(M[AR⊖R*(X)]) if and only if I⊆U(M[AR⊖R*(X)]) and the columns labelled by I are linearly independent. Since U(M[AR]) is the set of all columns of AR and U(M[AR⊖R*(X)]) is the set of all columns of AR⊖R*(X), so U(M[AR])-R*(X)=U(M[AR⊖R*(X)]). Hence, I(M[AR⊖R*(X)])=I(M[AR]∖R*(X)). This completes the proof.Example 41 (continued from Example22).
LetX={b,c}. Since R*(X)={b,c} and
(10)AR⊖R*(X)=(100011)a00b00c⊖{b,c}=(10)a,
so I(M[AR⊖R*(X)])={∅,{a}}. Since B(M(R))={{a,b},{a,c}}, so I(M(R))={∅,{a},{b},{c},{a,b},{a,c}}, M(R)∣X=(X,IX), {c}∈B(M(R)∣X), where IX={∅,{b},{c}} and B(M(R)∣X)={{b},{c}}. Hence, I(M(R)/X)={∅,{a}}. Therefore, I(M(R)/X)=I(M[AR⊖R*(X)]).


## 3.1. Characteristics of the Matroid through Matrices

In this subsection, a matroid is induced by an equivalence relation on a universe, and a matrix representation of the equivalence relation is a representable matrix of the matroid. Some characteristics of the matroid are presented through the representable matrix mainly. The following proposition shows that the matroid can be induced through the circuit axiom.Proposition 15 (see [29]).
LetR be an equivalence relation on U. One has that
(2){{x,y}⊆U:x≠y,(x,y)∈R}
satisfies (C1), (C2), and (C3) of Proposition 11. Then there exists a matroid M such that C(M)={{x,y}⊆U:x≠y,(x,y)∈R}, and we denote this matroid by M(R).In order to find a matrix to prove that the matroid induced by an equivalence relation is a representable matroid, a matrix representation of an equivalence relation is presented in the following definition.Definition 16.
LetR be an equivalence relation on U={x1,x2,…,xn} and a partition U/R={P1,P2,…,Pm}. We define a Boolean matrix AR=(aij)m×n as follows:
(3)aij={1,xj∈Pi,0,xj∉Pi.xj labels the jth column and Pi labels the ith row. AR is called a matrix representation of R.Note thataij is 1 or 0 depending on whether xj is or is not in Pi. An equivalence relation on a universe may have different matrix representations because of the randomness of the order of a set.Example 17.
LetU={a,b,c} and U/R={{a},{b,c}}. Then AR={a}{b,c}(100011)a0b0c, AR′={b,c}{a}(011100)a0b0c, and AR′′={a}{b,c}(010101)b0a0c are some matrix representations of R.On one hand, according to Definition16, two matrix representations of R with different orders of column labels have the same vector matroid because the columns labelled by X⊆U in these two matrices have the same linear dependence. On the other hand, there is an important result in matroid theory that a matrix and its row elementary transformed matrix have the same vector matroid. Therefore, all matrix representations of R induce the same vector matroid.Example 18 (continued from Example17).
M
[
A
R
]
=
(
U
,
I
(
M
[
A
R
]
), where I(M[AR])=Low({{a,b},{a,c}}); M[AR′]=(U,I(M[AR′])), where I(M[AR′])=I(M[AR]); M[AR′′]=(U,I(M[AR′′])), where I(M[AR′′])=I(M[AR]). Therefore, M[AR]=M[AR′]=M[AR′′].The following proposition shows that the matroid induced by an equivalence relation is a representable matroid, and a matrix representation of the equivalence relation is a representable matrix of the matroid.Proposition 19.
LetR be an equivalence relation on U={x1,x2,…,xn} and U/R={P1,P2,…,Pm}. Then M(R)=M[AR].Proof.
LetAR=x1x2⋯xn(α1α2⋯αn). Since M(R) and M[AR] have the same ground set, so we need to prove only that C(M(R))=C(M[AR]). According to Proposition 5 and Definition 9, C(M[AR])=Min({C⊆U: the columns labelled by C are linearly dependent in V(m,R)}). According to Definition 16, αi≠(0⋯0)⊤. Hence, {xi}∉C(M[AR]) for all i∈{1,2,…,n}. For any {xi,xj}∈C(M(R)), (xi,xj)∈R. According to Definition 16, the columns labelled by xi and xj are the same. Therefore, the columns labelled by {xi,xj} are linearly dependent in V(m,R). Hence, {xi,xj}∈C(M[AR]); that is, C(M(R))⊆C(M[AR]). Conversely, if C∈C(M[AR])-C(M(R)), according to (C2) of Proposition 11, {x,y}⫅C for any {x,y}∈C(M(R)). Therefore, for any xi,xj∈C and xi≠xj, (xi,xj)∉R. According to Definition 16, there is only a 1 in every column of AR and the columns labelled by C are different. Hence, the columns labelled by C are linearly independent in V(m,R), which is contradictory with C∈C(M[AR]). Thus C(M[AR])⊆C(M(R)). This completes the proof.Using the representable matrix of the matroid induced by an equivalence relation, some characteristics of the matroid will be obtained. For this purpose, the following definition proposes a function from a power set of a set to a set ofn-dimensional 0-1 vectors.Definition 20 (see [36]).
IfU={x1,x2,…,xn} and X⊆U, then the characteristic function of X is defined as φ(X)=(a1,…,ai,…,an), where
(4)ai={1,xi∈X,0,xi∉X.As we know,φ is a bijection from 2U to the set of all n-dimensional 0-1 vectors. Let A=(aij)m×n and B=(bij)n×l be Boolean matrices. Then A⊙B=(cij)m×l, where cij=∨s=1n(ais∧bsj) and ∨, ∧ denote maximum and minimum, respectively. In this paper, ⊙ denotes Boolean product of matrices and “·” denotes multiplication of matrices.The following proposition presents the family of bases of the matroid induced by an equivalence relation from the viewpoint of a representable matrix of the matroid.Proposition 21.
LetR be an equivalence relation on U. Then B(M(R))=Min({X⊆U:AR⊙(φ(X))⊤=1v}), where 1v is a column vector whose entries are all 1.Proof.
For anyX⊆U and AR⊙(φ(X))⊤=1v, we have RN(x)⋂‍X≠∅ for any x∈U. Therefore, Min({X⊆U:AR⊙(φ(X))⊤=1v})=Min({X⊆U:∀x∈U,RN(x)⋂‍X≠∅}). According to Definition 8, Min({X⊆U:∀x∈U,RN(x)⋂‍X≠∅})={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. First of all, we should prove that {X⊆U:∀x∈U,|RN(x)⋂‍X|=1} satisfies (B1) and (B2) of Proposition 13.(B1)
: It is straightforward that{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}≠∅.(B2)
: IfB1,B2∈{X⊆U:∀x∈U,|RN(x)⋂‍X|=1} and s∈B1-B2,then there exists y∈B2-B1 and y∈RN(s). Since B1⋂‍RN(s)={s}, so ((B1-{s})⋃‍{y})⋂‍RN(s)={y}. For any z∈U-RN(s), |((B1-{s})⋃‍{y})⋂‍RN(z)|=1. Therefore, ((B1-{s})⋃‍{y})∈{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}.
Hence,{X⊆U:∀x∈U,|RN(x)⋂‍X|=1} satisfies (B1) and (B2) of Proposition 13. Then we should prove that the matroid whose family of bases is {X⊆U:∀x∈U,|RN(x)⋂‍X|=1} is M(R); that is, they have the same family of circuits. Since Low({X⊆U:∀x∈U,|RN(x)⋂‍X|=1})={X⊆U:∀x∈U,|RN(x)⋂‍X|≤1}, so Min(Opp({X⊆U:∀x∈U,|RN(x)⋂‍X|≤1}))=Min({X⊆U:∃x∈U,|RN(x)⋂‍X|≥2})= {{x,y}⊆RN(x):x≠y}=C(M(R)). Hence, B(M(R))=Min({X⊆U:AR⊙(φ(X))⊤=1v}). This completes the proof.According to Proposition21, a representable matrix of the matroid induced by an equivalence relation and the corresponding characteristic function can get the family of bases of the matroid. In order to get the family of bases of the matroid, we need to get only one representable matrix.Example 22 (continued from Example17).
A
R
⊙
(
φ
(
{
a
}
)
)
⊤ = (100011)⊙(100)⊤ = (100011)⊙(100)=(10); AR⊙(φ({b}))⊤=AR⊙(010)⊤=(01); AR⊙(φ({c}))⊤=(01); AR⊙(φ({a,b}))⊤=(11); AR⊙(φ({a,c}))⊤=(11); AR⊙(φ({b,c}))⊤=(01); AR⊙(φ({a,b,c}))⊤=(11). Hence, B(M(R))=Min({{a,b},{a,c},{a,b,c}})={{a,b},{a,c}}.The following proposition presents another method to obtain the family of bases of the matroid induced by an equivalence relation from the viewpoint of a representable matrix.Proposition 23.
LetR be an equivalence relation on U={x1,x2,…xn}, U/R={P1,P2,…,Pm}, and AR=(aij)m×n. Then B(M(R))={{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}.Proof.
According to the proof of Proposition21, B(M(R))={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. We need to prove only {{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. For all X∈{{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}, suppose that X={xj1,xj2,…,xjm}. Since a1j1a2j2⋯amjm=1, so aiji=1 for any 1≤i≤m. Therefore, xji∈Pi; that is, |X⋂‍RN(x)|=1 for any x∈U. Hence, {{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}⊆{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. Conversely, for all X∈{X⊆U:∀x∈U,|RN(x)⋂‍X|=1}, it is straightforward that X∈{{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}. Therefore, {X⊆U:∀x∈U,|RN(x)⋂‍X|=1}⊆{{xj1,xj2,…,xjm}:a1j1a2j2⋯amjm=1}. This completes the proof.The following definition presents a matrix related to circuits of a matroid.Definition 24 (circuit incidence matrix [21, 23]).
LetM be a matroid on U={x1,x2,…,xn} and C(M)={C1,C2,…,Cm}. A circuit incidence matrix of M is A(C(M))=(aij)m×n, where
(5)aij={1,xj∈Ci,0,xj∉Ci.According to Definition24, circuits can be replaced by bases of a matroid. Therefore, we can also get a base incidence matrix. Let M be a matroid on U={x1,x2,…,xn} and B(M)={B1,B2,…,Bm}. A base incidence matrix of M is A(B(M))=(aij)m×n, where
(6)aij={1,xj∈Bi,0,xj∉Bi.Note that the matroid induced by an equivalence relation may have different base incidence matrices because of the randomness of the order of a set. But these base incidence matrices can induce a unique rank function of the matroid.Proposition 25.
LetR be an equivalence relation on U and X⊆U. Then rM(R)(X)=max1≤i≤lbi, where
(7)(b1⋮bi⋮bl)=A(B(M(R)))·φ(X)⊤.Proof.
It is straightforward thatbi=|Bi⋂‍X|, where Bi∈B(M(R)). Suppose that bj=max1≤i≤lbi. Since Bj∈B(M(R)), so Bj⋂‍X∈I(M(R)). In fact, if there exists I1∈I(M(R)) such that |I1⋂‍X|>|Bj⋂‍X|, then there must be a Bk∈B(M(R)) such that I1⊆Bk. Therefore, bk=|Bk⋂‍X|≥|I1⋂‍X|>|Bj⋂‍X|=bj, which is contradictory with bj=max1≤i≤lbi. Hence, rM(R)(X)=max1≤i≤lbi. This completes the proof.Example 26 (continued from Example22).
LetX1={a,b}, and X2={b,c}, A(B(M(R)))=(110101)a0b0c. Since A(B(M(R)))·φ(X1)⊤=(110101)·(110)=(21), so rM(R)(X1)=2; since A(B(M(R)))·φ(X2)⊤=(11), so rM(R)(X2)=1.The rank function of the matroid induced by an equivalence relation can also be obtained through the representable matrix of the matroid.Proposition 27.
LetR be an equivalence relation on U and X⊆U. Then rM(R)(X)=1v·(AR⊙φ(X)⊤), where 1v is a row vector whose entries are all 1.Proof.
Suppose thatU/R={P1,P2,…,Pm}. The ith entry of AR⊙φ(X) is 1 or 0 depending on whether or not Pi⋂‍X≠∅. It is straightforward that 1v·(AR⊙φ(X)⊤)=|{RN(x):x∈U,RN(x)⋂‍X≠∅}|. We need to prove only that rM(R)(X)=|{RN(x):x∈U,RN(x)⋂‍X≠∅}|. According to Proposition 25, rM(R)(X)=max{|B⋂‍X|:B∈B(M(R))}. According to the proof of Proposition 21, B(M(R))={X⊆U:∀x∈U,|RN(x)⋂‍X|=1}. Therefore, rM(R)(X)=|{RN(x):x∈U,RN(x)⋂‍X≠∅}|. This completes the proof.Example 28 (continued from Example26).
r
M
(
R
)
(
X
1
)
=
1
v
·
(
A
R
⊙
φ
(
X
1
)
⊤
)
=
(
1
1
)
·
(
(
1
1
0
1
0
1
)
⊙
(
1
1
0
)
)
=
(
1
1
)
·
(
1
1
)
=
2.
Propositions25 and 27 present two direct and simple methods to calculate the rank function of the matroid induced by an equivalence relation compared with the traditional method in Definition 14. In fact, the rank function of the matroid can be used in attribute reduction of information systems. Integrating these two methods with the following theorem which presents an equivalent formulation of attribute reduction of information systems, one can obtain a reduct of an information system.Theorem 29 (see [29]).
LetIS=(U,A) be an information system. For all B⊆A, B is a reduct of IS if and only if it satisfies the following two conditions:(1)
∀b∈B,{X⊆U:∀c∈B-{b},rM(c)(X)=1}≠{X⊆U:∀c∈B,rM(c)(X)=1};(2)
{X⊆U:∀b∈B,rM(b)(X)=1}={X⊆U:∀a∈A,rM(a)(X)=1},where M(a) denotes the matroid induced by the equivalence relation induced by attribute subset {a}.In order to present circuits of the matroid induced by an equivalence relation from the viewpoint of matrices, a new matrix is established through a matrix representation of an equivalence relation and its transpose.Lemma 30.
LetR be an equivalence relation on U={x1,x2,…,xn}. Then AR⊤·AR=(bij)n×n is a relational matrix of R, where
(8)bij={1,(xi,xj)∈R,0,otherwise.Note that the matrix representation of an equivalence relation is the representable matrix of the matroid induced by the equivalence relation. Therefore, the family of circuits of the matroid can be obtained through the representable matrix. Letei be a n-dimensional 0-1 vector in which only the ith entry is 1; that is, ei=(0,…,0,1,0,…,0).Proposition 31.
LetR be an equivalence relation on U and U={x1,x2,…,xn}. Then C(M(R))={{xi,xj}:ei·(AR⊤·AR)·ej⊤=1(1≤i<j≤n)}.Proof.
We need to prove only that{{xi,xj}:ei·(AR⊤·AR)·ej⊤=1(1≤i<j≤n)}={{xi,xj}⊆U:xi≠xj,(xi,xj)∈R}. Let AR⊤·AR=(bij)n×n. For any 1≤i<j≤n,ei·(AR⊤·AR)·ej⊤=bij. According to Lemma 30, bij=1 if and only if (xi,xj)∈R. Since R is an equivalence relation, so AR⊤·AR is a symmetric matrix. Therefore, {{xi,xj}:ei·(ARΤ·AR)·ej⊤=1(1≤i<j≤n)}={{xi,xj}:(xi,xj)∈R(1≤i<j≤n)}={{xi,xj}⊆U:xi≠xj,(xi,xj)∈R}. This completes the proof.Example 32 (continued from Example22).
There isAR⊤·AR = (100101)·(100011)=abck(100011011)a0b0c. Hence, C(M(R))={{b,c}}.


## 3.2. Contraction and Restriction Operations through Matrices

This subsection applies contraction and restriction operations to the matroid induced by an equivalence relation through the representable matrix and approximation operators of rough sets. First of all, the concepts of these two operations are presented in the following two propositions. In fact, two new matroids are obtained by applying restriction and contraction operations to a matroid, respectively.Proposition 33 (restriction and deletion [21, 23]).
LetM=(U,I) be a matroid and X⊆U. Then (X,IX) is a matroid, where IX={I⊆X:I∈I}. We call this matroid the restriction of M to X and denote it by M∣X. M∖X=(U-X,IU-X) is called the deletion of U-X from M.Proposition 34 (contraction [21, 23]).
LetM=(U,I) be a matroid and X⊆U and BX is a base of M∣X (i.e., BX∈B(M|mX)). Then (U-X,I′) is matroid, where I′={I⊆U-X:I⋃‍BX∈I}. We call this matroid the contraction of M to U-X and denote it by M/X.Note that the definition ofM/X has no relationship with the selection of BX∈B(M∣X). The following lemma shows an interesting relationship between a single point set and the equivalence class of this point through applying contraction and restriction operations to the matroid induced by an equivalence relation.Lemma 35 (see [37]).
LetR be an equivalence relation on U. For all x∈U, I(M(R)/{x})=I(M(R)/RN(x))=I(M(R)∖RN(x)).LetA be a matrix over F and X a subset of the set U of column labels of A. We shall denote by A⊖X the matrix obtained from A by deleting all the columns whose labels are in X.Inspired by Lemma35, we obtain a relationship between two matroids, which are the contraction of the matroid induced by an equivalence relation to the complement of a single point set and a vector matroid of a matrix obtained from the representable matrix by deleting all the columns whose labels are in the equivalence class of this point.Proposition 36.
LetR be an equivalence relation on U. Then I(M(R)/{x})=I(M[AR⊖RN(x)]).Proof.
According to Proposition19 and Lemma 35, we need to prove only that I(M[AR]∖RN(x))=I(M[AR⊖RN(x)]). According to Proposition 33, I(M[AR]∖RN(x))={I⊆U(M[AR])-RN(x):I∈I(M[AR])}. According to Proposition 5, I∈I(M[AR]∖RN(x)) if and only if I⊆U(M[AR])-RN(x) and the columns labelled by I are linearly independent. I∈I(M[AR⊖RN(x)]) if and only if I⊆U(M[AR⊖RN(x)]) and the columns labelled by I are linearly independent. Since U(M[AR]) is the set of all columns of AR and U(M[AR⊖RN(x)]) is the set of all columns of AR⊖RN(x), so U(M[AR])-RN(x)=U(M[AR⊖RN(x)]). Hence, I(M[AR]∖RN(x))=I(M[AR⊖RN(x)]). This completes the proof.Note that the above proposition also shows a relationship between a single point set and the equivalence class of this point.Example 37 (continued from Example22).
SinceRN(b)={b,c} and
(9)AR⊖RN(b)=(100011)a00b00c⊖{b,c}=(10)a,
so I(M[AR⊖RN(b)])={∅,{a}}. Since B(M(R))={{a,b},{a,c}}, so I(M(R))=Low(B(M(R)))={∅,{a},{b},{c},{a,b},{a,c}}, M(R)∣{b}=({b},I{b}), {b}∈B(M(R)∣{b}), where I{b}={∅,{b}} and B(M(R)∣{b})={{b}}. Hence, I(M(R)/{b})={∅,{a}}. Therefore, I(M(R)/{b})=I(M[AR⊖RN(b)]).The following corollary presents an equivalent description of the above proposition from the viewpoint of upper approximations.Corollary 38.
LetR be an equivalence relation on U. Then I(M(R)/{x})=I(M[AR⊖R*({x})]).When we apply a sequence of operations to the matroid induced by an equivalence relation like Lemma35, the following lemma is obtained.Lemma 39 (see [37]).
LetR be an equivalence relation on U. For all X⊆U, I(M(R)/X)=I(M(R)/R*(X))=I(M(R)∖R*(X)).Inspired by Proposition36, we obtain the similar relationship between a subset and the upper approximation of this subset through these two operations and the representable matrix of the matroid induced by an equivalence relation.Proposition 40.
LetR be an equivalence relation on U. Then I(M(R)/X)=I(M[AR⊖R*(X)]).Proof.
According to Proposition19 and Lemma 39, we need to prove only that I(M[AR]∖R*(X))=I(M[AR⊖R*(X)]). According to Proposition 33, I(M[AR]∖R*(X))={I⊆U(M[AR])-R*(X):I∈I(M[AR])}. According to Proposition 5, I∈I(M[AR]∖R*(X)) if and only if I⊆U(M[AR])-R*(X) and the columns labelled by I are linearly independent. I∈I(M[AR⊖R*(X)]) if and only if I⊆U(M[AR⊖R*(X)]) and the columns labelled by I are linearly independent. Since U(M[AR]) is the set of all columns of AR and U(M[AR⊖R*(X)]) is the set of all columns of AR⊖R*(X), so U(M[AR])-R*(X)=U(M[AR⊖R*(X)]). Hence, I(M[AR⊖R*(X)])=I(M[AR]∖R*(X)). This completes the proof.Example 41 (continued from Example22).
LetX={b,c}. Since R*(X)={b,c} and
(10)AR⊖R*(X)=(100011)a00b00c⊖{b,c}=(10)a,
so I(M[AR⊖R*(X)])={∅,{a}}. Since B(M(R))={{a,b},{a,c}}, so I(M(R))={∅,{a},{b},{c},{a,b},{a,c}}, M(R)∣X=(X,IX), {c}∈B(M(R)∣X), where IX={∅,{b},{c}} and B(M(R)∣X)={{b},{c}}. Hence, I(M(R)/X)={∅,{a}}. Therefore, I(M(R)/X)=I(M[AR⊖R*(X)]).


## 4. Axioms of Circuit Incidence Matrices of 2-Circuit Matroids

This section presents two axioms of circuit incidence matrices of 2-circuit matroids. Based on the characteristics of the matroid induced by an equivalence relation, a type of matroids is abstracted, which is called 2-circuit matroid. Therefore, the study of 2-circuit matroid is a further study for the matroid induced by an equivalence relation.Definition 42 (2-circuit matroid [29]).
LetM=(U,I) be a matroid. M is called a 2-circuit matroid if |C|=2 for all C∈C(M).Note that ifC(M)=∅, then M is also a 2-circuit matroid. In this section, we do not consider this case. The following proposition shows that the matroid induced by an equivalence relation is a 2-circuit matroid.Proposition 43 (see [29]).
LetR be an equivalence relation on U. Then M(R) is a 2-circuit matroid.In order to obtain the axioms of circuit incidence matrices of 2-circuit matroids, some fundamental signs are presented. Letα=(a1,…,an) be a n-dimensional 0-1 vector. Then the complement of α is denoted by α¯=(b1,…,bn), where
(11)bi={1,ai=0;0,ai=1.According to Definition20, φ-1 is also a bijection, where φ-1 is called φ inverse. The following lemma shows some properties of φ-1.Lemma 44 (see [36]).
Letα and β be n-dimensional 0-1 vectors and φ the characteristic function from 2U to the set of all n-dimensional 0-1 vectors. Then the following conditions hold:(1)
φ-1(α∧β)=φ-1(α)⋂‍φ-1(β);(2)
φ-1(α∨β)=φ-1(α)⋃‍φ-1(β);(3)
φ-1(α¯)=U-φ-1(α).We shall denoteα⊗β=α∧β¯. Hence, φ-1(α⊗β)=φ-1(α∧β¯)=φ-1(α)⋂‍(U-φ-1(β))=φ-1(α)-φ-1(β). The vector whose entries are all 0 is denoted by 0. The following theorem presents an axiom of circuit incidence matrices of 2-circuit matroids through row vectors.Theorem 45.
The matrix(12)Cm×n=(α1⋮αi⋮αm)
is a circuit incidence matrix of a 2-circuit matroid if and only if the following conditions hold:(1)
Cm×nis a 0-1 matrix where there are two
1
in any row and any row is different;(2)
ifαi∧αj≠0andi≠j, then there existsαksuch thatαk=(αi∨αj)⊗(αi∧αj).Proof.
(
⇒
): (1) Since Cm×n is a circuit incidence matrix of a 2-circuit matroid, so there are two 1 in any row of Cm×n and Cm×n is a 0-1 matrix. According to (C2) of Proposition 11, any row of Cm×n is different.
(
2
) If αi∧αj≠0 and i≠j, then there exist Ci, Cj∈C, Ci≠Cj, and x∈Ci⋂‍Cj, where Ci=φ-1(αi) and Cj=φ-1(αj). According to (C3) of Proposition 11, there exists Ck∈C such that Ck⊆(Ci⋃‍Cj)-{x}. Since |Ci|=|Cj|=|Ck|=2, so {x}=Ci⋂‍Cj and Ck=(Ci⋃‍Cj)-{x}. Hence, there exists αk=φ(Ck) such that φ-1(αk)=(φ-1(αi)⋃‍φ-1(αj))-(φ-1(αi)⋂‍φ-1(αj))=φ-1(αi∨αj)-φ-1(αi∧αj)=φ-1[(αi∨αj)⊗(αi∧αj)]. Since φ-1 is a bijection, so αk=(αi∨αj)⊗(αi∧αj).
(
⇐
): We need to prove that {φ-1(αi):1≤i≤m} satisfies (C1), (C2), and (C3) of Proposition 11 and |φ-1(αi)|=2 for any 1≤i≤m. Since Cm×n is a 0-1 matrix where there are two 1 in any row and any row is different, so it is straightforward that {φ-1(αi):1≤i≤m} satisfies (C1) and (C2), and |φ-1(αi)|=2 for any 1≤i≤m. Since αi∧αj≠0 and i≠j, so φ-1(αi)≠φ-1(αj) and x∈φ-1(αi)⋂‍φ-1(αj). Since |φ-1(αi)|=2 for any 1≤i≤m, so φ-1(αi)⋂‍φ-1(αj)={x}. Then there exists φ-1(αk) such that φ-1(αk)=φ-1[(αi∨αj)⊗(αi∧αj)]=φ-1(αi∨αj)-φ-1(αi∧αj)=(φ-1(αi)⋃‍φ-1(αj))-(φ-1(αi)⋂‍φ-1(αj))=(φ-1(αi)⋃‍φ-1(αj))-{x}. Hence, {φ-1(αi):1≤i≤m} satisfies (C3) of Proposition 11. This completes the proof.The following lemma shows how a matroid induces an equivalence relation through circuits of the matroid.Lemma 46 (see [21]).
LetM=(U,I) be a matroid. For any x,y∈U, one can denote a relation R such that xRy if and only if x=y or {x,y}∈C(M). Then R is an equivalence relation.The following theorem presents another axiom of circuit incidence matrices of 2-circuit matroids through row vectors and a special relation.Theorem 47.
The matrix(13)Cm×n=(α1⋮αi⋮αm)
is a circuit incidence matrix of a 2-circuit matroid if and only if the following conditions hold:(1)
Cm×n is a 0-1 matrix where there are two 1 in any row and any row is different;(2)
letx,y∈U, xRy if and only if x=y or {x,y}∈{φ-1(αi):1≤i≤m}. Then R is an equivalence relation.Proof.
(
⇒
): According to the proof of Theorem 45, we need to prove only the second condition. According to Lemma 46, R is an equivalence relation.
(
⇐
): We need to prove that {φ-1(αi):1≤i≤m} satisfies (C1), (C2), and (C3) of Proposition 11 and |φ-1(αi)|=2 for any 1≤i≤m. Since Cm×n is a 0-1 matrix where there are two 1 in any row and any row is different, so it is straightforward that {φ-1(αi):1≤i≤m} satisfies (C1) and (C2), and |φ-1(αi)|=2 for any 1≤i≤m. Let φ-1(αh),φ-1(αj)∈{φ-1(αi):1≤i≤m}, φ-1(αh)≠φ-1(αj), and x∈φ-1(αh)⋂‍φ-1(αj). Since |φ-1(αh)|=|φ-1(αj)|=2, so φ-1(αh)⋂‍φ-1(αj)={x}. Suppose φ-1(αh)={x,y} and φ-1(αj)={x,z}, where x,y,z∈U and x≠y≠z. Therefore, xRy and xRz. Since R is an equivalence relation, so yRz. Therefore, there exists φ-1(αk)∈{φ-1(αi):1≤i≤m} such that φ-1(αk)={y,z}; that is, φ-1(αk)=(φ-1(αh)⋃‍φ-1(αj))-{x}. Hence, {φ-1(αi):1≤i≤m} satisfies (C3) of Proposition 11. This completes the proof.Note that Theorems45 and 47 show us a new view to define matroids through circuit incidence matrices. There is not an axiom about circuit incidence matrices in matroid theory and there are three conditions in the circuit axiom, but there are only two conditions in the axiom of circuit incidence matrices of 2-circuit matroids.


## 5. Conclusions

In this paper, we apply matrices to a matroidal structure of rough sets. We prove that the matroid induced by an equivalence relation on a universe is a representable matroid. Some characteristics of the matroid are presented through the representable matrix of the matroid mainly. We apply contraction and restriction operations to the matroid through the representable matrix and approximation operators of rough sets. Moreover, two axioms of circuit incidence matrices of 2-circuit matroids are obtained. We will do more works in combining rough sets and matroids through matrices.



---

*Source: 493201-2013-11-26.xml*