O 251 Rxgs XEKDlg 92 P KQC 4 N Ojv Owcfq
O 251 Rxgs XEKDlg 92 P KQC 4 N Ojv Owcfq
Hypergraphs are systems of finite sets and form, probably, the most gen-
developed very rapidly during the latter part of the twentieth century,
which an edge can join any number of vertices. The basic idea consists in
first properties such as the Helly property, the König property, and so on.
1
PRELIMINARIES
Definitions
Graph
set, E(G) is a set disjoint from V (G) and IG is an "incidence" relation that
or points) of G; and elements of E(G) are called the edges (or lines) of
G.V (G) and E(G) are the vertex set and edge set of G, respectively. If, for
Example:
2
Here V (G) = {v1 , v2 , v3 , v4 , v5 } E(G) = {e1 , e2 , e3 , e4 , e5 , e6 } and IG is
given by
an edge of G with u and v as its ends. Two distinct edges e and f are said
of vertices and edges beginning and ending with vertices in which vi−1
and vi are the ends of ei. . A walk is called a trail if all the edges appearing
in the walk are distinct. It is called a path if all the vertices are distinct. A
cycle is a closed trail in which the vertices are all distinct. The length of a
3
A Graph G is said to be connected if every pair of vertices u, v are con-
Bipartite graph
A graph is bipartite if its vertex set can be partitioned into two nonempty
subsets X and Y such that each edge of G has one end in X and the other
Example:
4
Let G be a loopless graph. We construct a graph LG) in the following
way: The vertex set of L(G) is in 1-1 correspondence with the edge set
ofG and twO vertices of L(G) are joined by an edge if and only if the
always a simple graph) is called the line graph or the edge graph of G.
Example:
5
MATRIX REPRESENTATION OF THE GRAPH
Adjacency Matrix
Example:
Incidence Matrix
mi j is the number of times the vertex vi is incident with the edge e j . i.e,
6
0 if vi is not an end vertex of ej
Example:
7
CHAPTER 1
Hypergraph
A hypergraph H is a pair H = V ; E = (ei )i∈I where V is a set of elements
Example:
8
In this hypergraph H, V = {x1 , x2 . . . x11 } and E = {e1, e2 , e3 , e4 , e5 } =
{{x1 , x2 , x3 , x4 } , {x4 , x6 , x7 , x8 } , {x5 , x6 } , {x1 , x5 , x8 } , {x10 }}
Order of a hypergraph
Size of a hypergraph
Empty hypergraph
• V = 0/
• E = 0/
9
Trivial hypergraph
• V ̸= 0/
• E = 0/
Isolated vertex
S
If i∈I ei = V the hypergraph is without isolated vertex, where a vertex x
is isolated if x ∈ V\
S
i∈l ei. In fig 1.1x11 , x9 are isolated vertices.
Loop
Adjacent vertices
to itself.
10
Incident hyperedges
Star
x.
Degree of a hypergraph
d(x) = |H(x)|, excepted for a loop {x} where the degree d(x) = 2.
11
Regular hypergraph
If each vertex has the same degree, we say that the hypergraph is regular,
x ∈ V, d(x) = k
Rank r(H)
hypergrah:
Co-rank cr(H)
Uniform hypergraph
12
Simple hypergraph
Linear hypergraph
i ̸= j.
Example:
13
The hypergraph H above has 11 vertices; 5 hyperedges; 1 loop: e5 ; 2
isolated vertices: x11 , x9 . The rank r(H) = 4, the co-rank cr(H) = 1. The
Examples of hypergraph
Example 1:
Let V be the set of people at this meeting. Assume that each session is
way:
• The set of vertices is the set of people who attend the meeting;
Example 2:
Fano Plane
14
The Fano plane is the finite projective plane of order 2, which have
the smallest possible number of points and lines, 7 points with 3 points
on every line and 3 lines through every point. To a Fano plane we can
• The set of hyperedges is E = {013, 045, 026, 124, 346, 235, 156}
• The rank is equal to the co-rank which is equal to 3, hence, the Fano
hypergraph is 3-uniform.
15
Path in a hypergraph
xs+1 ;
Connected hypergraph
16
Distance
The distance d(x, y) between two vertices x and y is the minimum length of
Connected component
Diameter
Example:
17
Complete hypergraph
Incidence matrix
18
where
0 if v j ∈ e j
(ai, j ) =
1 otherwise
Example:
x1 x2 x3 x4 x5
e1 1 1 1 0 0
0 0
e2 1 1 0
e3 1 1 0 0 1
19
Adjacency matrix
It is a square matrix which rows and columns are indexed by the vertices
ax,x = 0.
Example:
x1 x2 x3 x4 x5
x1 0 2 1 0 1
x2 2 0 1 0 1
x3 1 1 0 1 0
x4 0 0 1 0 0
x5 1 1 0 0 0
20
Induced Subhypergraph
Let H = V ; E = (ei )i∈I be a hypergraph. The induced subhypergraph
(V ′ , E ′ ) defined as E ′ = {V (ei ) ∩V ′ ̸= 0;
/ ei ∈ E and either ei is a loop or
|V (ei ) ∩V ′ | ≥ 2}.
Example:
21
Consider the above hypergraph H.
hypergraph.
22
Subhypergraph
Let H = V ; E = (e j ) j∈J be a hypergraph. Given a subset V ′ ⊆ V , the
′ ′ ′ ′
subhypergraph H is the hypergraph H = V , E = (e j ) j∈J such that for
all e j ∈ E ′ : e j ⊆ V ′ .
Example:
Partial hypergraph
Let H = V ; E = (e j ) j∈J be a hypergraph. A partial hypergraph gen-
′ ′ ′
erated by J ⊆ I, H of H is a hypergraph H = V , (e j ) j∈J , where
by J = {1, 2}
24
CHAPTER 2
HYPERGRAPHS: FIRST
PROPERTIES
Line graph
Let H = V ; E = (ei )i∈I be a hypergraph such that E ̸= 0.
/ The line-
Example
black dots and its edges are the curves between these dots.
Lemma
25
Proposition
Proof
since Γ is simple;
26
• The collection of hyperedges X is the family of Xi where Xi is the set
Notice that if Γ has only one edge then V = {x1 , x2 } and X1 = X2 .It is the
linear graph of H.
27
Dual of a hypergraph
of hyperedges E;
{1, 2, . . . n}.
V ∗ of H ∗ .
28
Example
(Xi )i∈{1,2,3,4,5} .
We notice that H is without repeated hyperedge but its dual has one.
Proposition
2-Section of a hypergraph
by [H2 , which vertices are the vertices of H and where two distinct vertices
form an edge if and only if they are in the same hyperedge of H. Example
30
Degree of a hyperedge
Incidence graph
with a vertex set S = VUE, and where x ∈ V and e ∈ E are adjacent if and
only if x ∈ e.
31
Proposition
Proof :
Let IG(H) be the incidence graph of H. We sum the degrees in the part
E and in the part V in IG(H). Since the sum of the degrees in these two
32
Intersecting Families
Let H = V ; E = (ei )i∈I be a hypergraph. A subfamily of hyperedges
Example:
e1 ∩ e2 ∩ e3 = 0/ is called a triangle.
33
Helly Property and Strong Helly Property
A hypergraph has the Helly property if each intersecting family has a non-
has not the Helly property. A hypergraph having the Helly property will
Example :
The hypergraph above has the Helly property but not the strong Helly
triangle:
34
35
This hypergraph has no helly property since, intersecting family e1 , e3 , e4
36
CHAPTER 3
HYPERGRAPH COLORING
Coloring
Let H = V ; E = (ei )i∈I be a hypergraph and k ≥ 2 be an integer. A
such that:
From this definition it is easy to see that any coloring induces a partition
of the set of vertices in k - classes: (Cl ,C2 ,C3 , . . . ,Ck ) such that for e ∈
E(H), |e| > 1 then e not a subset of Ci for all i ∈ {1, 2, . . . k}.
Example
The figure below shows a colored hypergraph H where (r) is red and (b) is
blue.
37
Chromatic number χ(H)
Example:
smallest number of waste disposal sites that the factory needs in order to
38
Proposition
α(H) ≥ n.
Proof
that for e ∈ E , |e| > 1 then e ← Ci , for all i ∈ {1, 2, 3, . . . k}, consequently
Ci is a stable for all i ∈ {1, 2, 3, . . . k}. Hence |Ci| ≤ α(H), for all i ∈
Proposition
α(H) ≤ n + 1
Proof
Assume that S is a stable with |S| = α(H). We can color any vertex of S
with the same color andusing n − α(H) other colors to color the set V − S
39
with different colors. Hence we have :
χ(H) ≤ n − α(H) + 1
that leads to
χ(H) + α(H) ≤ n + 1.
Particular Colorings
Strong Coloring
of V such that the same color does not appear twice in the same hyperedge.
In another word: |e ∩Cl | ≤ 1 for any hyperedge and any element of the
partition.
Equitable Coloring
{1, 2, . . . , k} appear the same number of times, to within one, if k does not
40
divide |ei |. That is for all e ∈ E,
|e| |e|
| ≤ |e ∩ Ci |≤ i ∈ {1, 2, 3 . . . k}
k k
Example:
Good Coloring
41
of different colors, i.e. for every e ∈ E, the number of colors in e is
min{|e|; k}.
Lemma
transversal sets;
Proof:
Ci ∩ e j ̸= 0,
/ ∀ j ∈ {1, 2, . . . , m}.
42
Uniform Coloring
k-partition: (C1 ,C2 , . . . ,CK ) of V such that the number of vertices of the
same color is always the same, to within one, if k does not divide n, i.e
|n| |n|
≤ |Ci | ≤ , i ∈ {1, 2, 3 . . . k}
k k
Hyperedge Coloring
Chromatic index
43
Lemma
Proof
44
CHAPTER 4
APPLICATION OF HYPERGRAPH
THEORY
Like in most fruitful mathematical theories, the theory of hypergraphs has
location problems and so on. This chapter shows some possible uses
the main drawback of the graph theory is the lack of convenient tools to
45
A hypergraph H = (V, E) is a molecular hypergraph if it represents
systems. A cellular system is a set of cells where two cells can use the
(b) An edge exists between two vertices if and only if the distance be-
tween the corresponding cells is less than the distance called reuse
46
minimal with respect to this property, i.e. no proper subset of a minimal
(Sk )) where:
• A set of attributes.
48
CONCLUSION
A hypergraph is defined to be a family of hyperedges which are sets of
sciences in a much more general setting than graphs do. Hypergraph theory
schemes, etc.
49
BIBLIOGRAPHY
1. Hypergraph Theory - An Introduction by Alain Bretto
4. A First Look at Graph Theory by John Clark and Derek Allen Holton
50
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1907)
ACKNOWLEDGEMENT
RAHINA
CONTENTS
1. INTRODUCTION ........................................................... 01
4. NETS IN TOPOLOGY....................................................12
NETS AND ITS CONVERGENCE ......................................12
TOPOLOGICAL PROPERTIES AND NETS........................17
6. CONCLUSION....................................................................41
7. BIBLIOGRAPHY ...............................................................42
INTRODUCTION
When we are working on metric spaces ( or first countable topologi-
cal spaces) sequences are sufficient to describe almost all topological
properties. This dissertation mainly deals with the generalisation
of sequences called nets and the concept of filters. The goal of the
first chapter is to justify via examples the fact that sequences are
not enough to describe general topological spaces. Here some basic
definitions and results are included which we use further.
The second chapter deals with the definition of nets and basic proper-
ties of nets which ensure that nets are the generalisation of sequences.
Later we characterise some of the topological properties; such as
Hausdorff property, continuity of a function, closure of set, etc. Last
part of this chapter gives you an interesting proof of Tychonoff the-
orem via nets that proves the importance of nets in analysis.
The last chapter describes the use of filters and its interesting applica-
tions. Here first section talks about the definition and convergence of
filters with some examples while the next section characterise topo-
logical properties which is more easier compared to that of nets.
Coming to the end, we are introducing the concept of ultrafilters
and gives another proof of Tychonoff theorem using ultrafilters.
1
PRELIMINARY
Definition
A Topological space is a pair (X,τ ) where X is a non-empty set and
τ is a family of subsets of X satisfying:
(i) ϕ ∈ τ and X ∈ τ .
(ii) τ is closed under arbitrary union
(iii)τ is closed under finite intersection.
The members of τ are called open sets and the compliment of open
sets are called closed sets.
Example
2
2) Discrete topology : If P(X) is the power set of X, then τ = P(X)
is a topology on X and is called as Discrete topology on X.
In this topology only eventually constant sequence is convergent and
it converges to the repeating point of the sequence.
3) Co-finite topology : Let
3
Definition: Hausdorff space
Definition: Function
4
Y such that (x, y) ∈ X × Y .The set X, Y and f are called domain,
codomain and graph of (X, Y, f) respectively. We also denote (X, Y,
f) by f : X → Y .
proof
5
Definition: Cover of a set
6
proof
c
S
C∈C C =X
7
CHAPTER 1
Example 1
8
Example 2
Example 3
9
Claim: xn → x if xn = x eventually.
Case 1: x ̸= x0 ,
then {x} ∈ ω, then by definition of convergence,xn → x if and only
if v = x eventually.
Case 2: x = x0 .
Assume xn ̸= x0 for infinitely many n.
Define F = {xn : xn ̸= x0 }.
Then x0 ∈ F c and (F c )c = F, countable ⇒ F c ∈ ω.
ie, F c is an open neighbourhood of x0 which fails to hold xn ∈ F c ∀
n ≥ n0 for any n0 ∈ N.
Hence xn ̸= x0 is wrong.
⇒ xn = x0 = x eventually.
Conversely, if xn ↛ x0 , then ∃ O ∈ ω , x0 ∈ O ∋ xn ∈
/ O infinitely
often.
ie, xn ̸= x0 infinitely often.
Hence xn → x0 if and only if xn = x0 eventually.
Let A = ({x0 })c
Then x0 ∈ A, but there does not exist a sequence {xn } in A such
that xn → x0 in ω because any sequence in A satisfy xn ̸= x0 n ≥ 1.
Hence by above result, xn does not converge to x0 .
But for any open set O such that x0 ∈ O, we have O ∩ A ̸= ϕ,
∴ Oc is countable.
10
∴Every neighbourhood of x0 intersect A implies x0 ∈ A.
ie, Sequences do not characterise points of closure.
Note : A metric space is compact if and only if it is sequentially
compact.
But we cannot generalise compactness using sequential compactness.
Moreover there exist compact space which is not sequentially com-
pact and vice versa.
11
CHAPTER 2
Nets in topology
2.1 Nets and its convergence
Example
12
Definition 2.1.2 Nets
Example
Riemann net: Let f be a bounded real valued function from [0, 1] and
D be the set of all pairs (P, ξ) where P is a partition of [0, 1]. Say P
= {a0 ,a1 ,.......an } and ξ = (ξ1 , ξ2 , ..., ξn ) is finite sequence such that
ξi ∈ [ai1, ai] for i = 1, 2, ..., n. And define (P, ξ) (Q, η) of D if P is
a refinement of Q. Now the Riemann net S : D → R is defined by,
S(P, ξ) = ni=1 f (ξi )(ai -ai+1 )
P
13
set S 1 (A) is an eventual subset of D.
ie, a subset E is eventually if and only if it contains all elements in
D ’after a certain stage’ and a net S : D → X eventually in A if and
only if A contains all its terms after a certain stage
14
Definition 2.1.6 Cluster point
proof
Let U be a neighbourhood of x in X.
Let m ∈ D be given.
S|F → x ⇒ ∃ m1 ∈ F ∋ ∀ n ∈ F, n ≥ m, ⇒ Sn ∈ U
Choose n1 ∈ D such that n1 ≥ m and n1 ≥ m1 .
Since F is cofinal subset we can find n ∈ F ∋ n ≥ m1 .
Then n ≥ n1 ≥ m and S(n) ∈ U. So S is frequently in U.
Since U was arbitrary, x is a cluster point of S.
15
(i) T = S ◦ N.
(ii) for any n ∈ D, there exists p ∈ E such that for all m ∈ E, m ≥
p implies N(m) ≥ n in D.
proof
16
For (n, U) , (m, V ) ∈ E we let (n, U) ≥ (m, V ) means n ≥ m and
U⊆V.
It is easy to show that E is a directed set with the defined binary
relation.
Define T : E → X by T(n,U) = S(n) for any (n, U) ∈ E.
For N : E → D suchthat N(n, U) = n we get that T = SN(n, U) =
S(n) and for any m ∈ D, for any U’ ∈ ηx m1 ∈ D ∋ m1 ≥ m and
S(m1 ) ∈ U’.
Then (m1 , U’) ∈ E. Now for (n, U) ≥ (m1 , U’) n ≥ m2 ≥ m.
Hence T is a subnet of S.
Now we will prove that T → x ∈ X.
Let G be any open set of x in X. Since x is a cluster point of S, we
get S is frequently in G.
Fix n0 ∈ D ∋ S(n0 ) ∈ G. Then (n0 , G) ∈ E.
Now (m, G) ∈ E , (m, U) ≥ (n0 , G) ⇒ T(m, U) = Sm ∈ U ⊆ G.
Thus T converges to x in X.
Hence the proof.
17
in topology depends ultimately on open [Link] suffices to characterise
closure property in terms of convergence of nets since closed sets and
open sets are characterised in terms of closures. Here we begin with
the characterisation of Hausdorff property.
S → x and S → y in X.
claim : x = y.
If x ̸= y, then there exists open sets U, V ∋ x ∈ U , y ∈ V and U ∩
V = ϕ. But by the definition of convergence,
S → x implies ∃ m1 ∈ D ∋ sn ∈ U ∀ n ≥ m1 and n ∈ D.
S → y implies ∃ m2 ∈ D ∋ sn ∈ U ∀ n ≥ m2 and n ∈ D.
⇒ Sn ∈ U ∩ V ∀ n ≥ p and n ∈ D.
18
Suppose X is not Hausdorff.
Then there exists two points x and y with the property that the open
sets of x and y are not disjoint.
Let ηx and ηy be the neighbourhood system of x and y respectively.
Let D = ηx × ηy and (U1 , V1 ) , (U2 , V2 ) ∈ D.
Define (U1 , V1 ) ≥ (U2 , V2 ) if U1 ⊆ U2 and V1 ⊆ V2 .
Clearly D is a directed set.
Define S : D → X ∋ S(U, V ) be any point in U ∩ V .
We will prove that S is converging to both x and y.
Let G be any open set of x. Then (G, X) ∈ D.
Now if (U, V ) ≥ (G, X) in D then U ⊆ G and so S(U, V ) ∈ U ∩
V ⊆ U ⊆ G.
Thus S converges to x. Similarly S converges to y.
Hence S converges to both x and y which is a contradiction to our
hypothesis.
So X is Hausdorff
19
proof
20
net in the complement X/B converges to a point in X
Proof
21
proof
22
contains no point of net f◦S.
Thus f◦S ↛ f(x0 ),a contradiction.
Hence f is continuous
Characterisation of compactness
proof
23
Since D is a directed set ∃ m ∈ D m ≥ mi i = 1, 2, ..., k.
Now by assumption S(m) ∈ ∩ki=1 (X/N xi) = X / ∪ki=1 N xi which is
not possible.
So S has atleast one cluster point in X.
Conversely assume (2) holds.
We will use Theorem 1.1.2. to prove X is compact.
Let C be a family of closed sets of X having finite intersection prop-
erty.
D be the family of all finite intersections of members of C.
Note that D itself closed under finite intersection property, and C ⊆
D.
Define D ≥ E for D, E ∈ D if D ⊆ E.
Thus D is a directed set.
If D, E ∈ D then D ∩ E ∈ D and D ∩ E ≥ D , D ∪ E ≥ E.
Clearly ϕ ̸= D , since C has finite intersection property
Define S : D → X , S(D) =any point in D.
By the hypothesis, S has a cluster point, say x in X.
T
Claim: x ∈ C∈C C
If not there exists C ∈ C such that x ∈ C. Then X / C is a neigh-
bourhood of x, since C is closed set belongs to C.
By the definition of cluster point, for C ∈ D there exists D ∈ D such
that D ≥ C and S(D) ∈ X / C.
24
D ≥ C ⇒ D ⊆ C so X / C ⊆ X / D.
But S(D) ∈ X / C ⊆ X / D = Dc , which is a contradiction since
S(D) is a point in D.
T
So x ∈ C∈C C.
25
CHAPTER 3
Filters in topology
3.1 Filters and its convergence
Definition [Link]
A filter on (or in) a set X is a non-empty family F of non-empty
subsets of X suchthat:
(i) F is closed under finite intersections ,
(ii) if B ∈ F and B ⊆ A then A ∈ F for all A, B ⊆ X.
Clearly, X is an element of filter F always.
Example
26
Definition [Link] of a filter
Let F be a filter on a set X. Then a sub-family B of F is said to
be a base of F (or a filter base) if for any A ∈ F there exists B ∈
B such that B ⊆ A.
proof
27
/ F as ϕ ∈
Hence ϕ ∈ /B.
It only remains to show that F is closed under finite intersections.
So suppose A1 , A2 ∈ F .
Then there exists B1 , B2 ∈ B such that B1 ⊂ A1 and B2 ⊂ A2 .
By assumption there exists B3 ∈ B such that B3 ⊆ B1 ∩ B2 .
But A1 ∩ A2 is superset of B1 ∩ B2 hence it is a superset of B3 ∈
B.
So A1 ∩ A2 ∈ F .
Thus F is a filter on X and B is a base for it by the construction.
Corollary 3.1.1. Any family which does not contain the empty set
and which is closed under finite intersection is a base for a unique
filter.
proof
28
section property and so does every subfamily of F .
Conversely suppose S has the finite intersection property.
Let B be the family of finite intersections of members of S .
/ B and B is closed under finite intersections.
Then ϕ ∈
So by the Corollary 3.1.1., B is a base for a filter F on X and thus
S is a sub base for F .
29
form Bm for m ∈ D.
Using the fact that D is a directed set, we can show that F is a filter
on X.
This filter is called the filter associated with the net S.
Conversely let F be a filter on X. Let
D = {(x, F) ∈ X × F : x ∈ F}
For (x, F), (y, G) ∈ D define (x, F) ≥ (y, G) if F ⊆ G.
It is clear that D is a directed set because F is closed under finite
intersections.
Define S : D → X by S(x, F) = x.
Now this net is called the net associated with F .
proof
Assume S converges to x.
Let U be any neighbourhood of x in X.
Then there exists m ∈ D such that Bm ∈ U, where Bm = {S(n) : n
∈ D, n ≥ m}.
But this means U ∈ F by the definition of F .
30
So ηx ⊂ F ,
i.e, F converges to x.
Conversely suppose F converges to x.
Let U be any neighbourhood of x.
Then U ∈ F . By the construction of F , there exists m ∈ D such
that Bm ⊂ U, where Bm is defined above.
⇒ S(n) ∈ U n ∈ D , n ≥ m.
Thus S → x in X.
Now for the second part , suppose x is a cluster point of the net S,U
be any neighbourhood of x.
Let F ∈ F .
Then we have to show U ∩ F ̸= ϕ.
F ∈ F ⇒ ∃ m ∈ D ∋ Bm ⊂ F.
U is a neighbourhood of x and m ∈ D
⇒ n ∈ D ∋ n ≥ m and S(n) ∈ U (by the definition of cluster point
of a net)
⇒ S(n) ∈ U ∩ F.
Since U and F are arbitrary, we get x is a cluster point of F .
Conversely, suppose x is a cluster point of F .
Let U be any neighbourhood of x and m0 ∈ D.
We have Bm m∈D where Bm = S(n) : n ≥ m is a base for F .
⇒ Bm ∈ F .
31
There fore Bm0 ∈ F .
Hence Bm0 U ̸= = ϕ,
x is a cluster point of F .
There fore ∃ n ≥ m0 ∋ S(n) ∈ U.
Since neighbourhood N of x and m0 ∈ D are arbitrary, we get x is a
cluster point of S.
Hausdorff property
proof
32
that F has finite intersection property.
So x = y.
Conversely assume that no filter in X converges to more than one
limit in X.
If X is not Hausdorff , there exists x, y ∈ X, x ̸= y such that every
neighbourhood of x intersects every neighbourhood of y.
∴ ηx ∪ ηy has finite intersection property,so there exists a filter F
on X containing ηx ∪ ηx .
Then clearly F converges to both x and y which contradict our hy-
pothesis.
So X is a hausdorff space.
33
base {f(A) : A ∈ F } . The image filter is denoted by f( F ).
Continuity of a function
proof
34
By convergence of F to x f 1 (N) ∈ F .
So N ⊇ f 1 (N) ∈ f(F ) .
N is an arbitrary neighbourhood of f(x), implies f(F ) converges to
f(x).
Conversely suppose the condition about filter is satisfied.
We have to show that f is continuous at x. If not there exists a
neighbourhood N of f(x) such that f 1 (N)is not a neighbourhood of
x.
So every neighbourhood of x intersects X / f 1 (N) and hence the fam-
ily, S = ηx ∪ X / f 1 (N)has finite intersection property.
Therefore S generates a filter F and converges to x.
However f(F ) is not converging to f(x).
Since X / f 1 (N) ∈ F we get f(X /f 1 (N) ) ∈ f(F ) .
But Y / N contains f(X / f 1 (N)) Y / N ∈ f(F ).
Therefore N ∈
/ f(F ) [ no filter can contain both a set and its com-
pliment].
Thus f(F ) does not converge to f(x). This contradiction proves that
f is continuous at x.
35
proof
N ∈ F ⇒ ηx ⊃ F .
∴ F converges to x.
3.3 Ultrafilters
36
Theorem 3.3.1. Let F be a filter on a set X,then there is an ul-
trafilter F on X with F ⊃ F .
proof
(a) Let {Fi }i∈I be a chain (i.e, totally ordered set of filters on X) of
collection of filters containing F with the inclusion ordering.
For the chain, take ∪i∈I Fi = G and F ⊂ Fi ∀i ⇒ F ⊆ G is a filter
which is an upper bound for the chain.
So there exist a maximal filterF which contains F by Zorn’s lemma,
as we required.
proof
(i) ⇒ (ii)
For all Y ⊂ X either Y ∈ F or X / Y ∈ F .
If there exist a larger filter then it contains both Y and X/Y which
is not possible as Y ∩ (X / Y ) = ϕ.
(ii) ⇒ (i)
Let Y ⊂ X. If there exist A1 , A2 ∈ F such that Y ∩ A1 = (X / Y )
∩ A2 = ϕ ⇒ A1 ∩ A2 = ϕ which is a contradiction.
37
So we must have
Y ∩ A = ϕ A ∈ F or (X / Y ) ∩ A ̸= ϕ ∀ A ∈ F .
If Y ∩ A ̸= ϕ ∀ A ∈ F , then by (part b) there exist a filter G con-
taining F ∪ {Y ,since F is an ultrafilter.
So we must have G = F .
If (X / Y ) ∩ A ̸= ϕ A ∈ F , similarly we will get G ⊇ F ∪ {X / Y
} ⇒ G = F.
G = F implies either Y ∈ G or X / Y ∈ G .
proof
W ⊃ f( f −1 (W)) ∈ f(F ).
where as,
Y / W ⊃ f( f −1 (Y W)) ∈ f(F ).
So f(F ) is an ultrafilter on Y .
38
proof Suppose x is a limit point.
39
Clearly A = A1 ∩ A2 ∩ ... ∩ An ∈ F .
(Ux1 )c ∈ F such that (Ux1 )c = ni=2 Uxi ∈ F F .
S
Then,
which is a contradiction.
Hence there exist a limit point for F ⇒ every ultrafilter is conver-
gent.
Conversely suppose every ultrafilter in it is convergent by proposi-
tion 3.3.3.
Suppose X is not compact.
Then there exist collection C of closed sets of X having finite inter-
section property and C∈C C = ϕ (⇒ {C c : C ∈ C } is an open cover
T
40
CONCLUSION
The importance of nets and filters in general topology, especially
where compactness is involved, is established here. The nets were
introduced by E H Moore in the early 20th century while the idea
of filters and its applications are primarily developed by European
mathematicians, beginning with the work of H Cartan which is fol-
lowed by Bourbaki. Some topological properties which are not easy
to characterise using sequences are also characterised with the help
of nets and filters. However, the importance of convergence theory
of nets and filters extends beyond this project.
41
BIBLIOGRAPHY
1. Paul R. Chernoff, A simple proof of Tychonoff’s theorem via nets,
The American Mathematical Monthly, Vol.99, 932-934 (Dec 1992)
2. Abdellatif Dasser, The use of filters in topology, University of
central Florida(2004)
3. K. D. Joshi, Introduction to General Topology, New age interna-
tional(P) limited, publishers,India(2006).
4. J. L. Kelley, General topology, Springer-Verlag, New York,1975.
5. Tommaso Russo, Introduction to Nets, [Link].
6. Rui Xiong, Nets and Filters in Topology, [Link], Feb(2017).
42
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1903)
ACKNOWLEDGEMENT
ANAGHA.C
CONTENTS
1. INTRODUCTION ........................................................... 01
6. FIBONACCI .................................................................... 35
7. CONCLUSION ................................................................ 42
8. BIBLIOGRAPH ............................................................... 43
INTRODUCTION
Number theory an old branch of mathematics is the science of
studying the properties of numbers. In accordance with research
methods and objective, we briefly divided Number theory into four
classes:Elementary Number theory, Analytic Number theory,Geometric
Number theory.
There are plenty of numbers with some interesting and magical prop-
erties in the history of the numbers. The numbers with some unique
and fascinating properties have always received a great attention in
the world of mathematics. There are so many kinds of numbers like
P erf ect number, M ersenne numbers , F ermat numbers ,f ibanocci
etc which shows some special characteristics. it was well said by
great mathematician Kronecker that ”God created the natural num-
bers,and all rest is the work of man”.
The second chapter deals with perfect numbers and related theo-
rems of perfect numbers. The third chapter consists of study on
M ersenne numbers with some theorem relating perf ect and mersenne
numbers. In fourth chapter we discus about F ermat numbers with
some [Link] in the last chapter we discus about a sequence
1
called f ibanocci and its terms are called f ibanocci numbers
2
CHAPTER - 1
PRELIMINARY RESULTS
Definition 1.1
a ≡ b(modn)
Example
(i) 15 ≡ 3(mod4)
(ii) 32 ≡ −1(mod5)
Theorem 1.2
Definition 1.3
Theorem 1.4
3
k +1 k +1
P1 1 −1 P2 2 −1 Prkr +1 −1
σ(n)= p1 −1 p2 −1 · · · pr −1
Definition 1.5
P
σα (n) = d/n
Definition 1.6
Theorem 1.7
F ERM AT ′ S theorem
Theorem 1.8
Theorem 1.9
If p is a prime ,then
1 if p ≡ 1(mod8)orp ≡ 7(mod8)
(2 p) =
−1
if p ≡ 3(mod8)orp ≡ 5(mod8).
Theorem 1.10
4
only if k h; in particular, k ϕ(n).
Theorem 1.11
Definition 1.12
For n ≥ 1, let ϕ(n) denote the number of positive integers not ex-
ceeding n that are relatively prime to n.
Theorem 1.13
Definition 1.14
Definition 1.15
Legendresymbol is a function of
1 if a is a quadratic residue modulo p and a ̸≡ 0 (mod p),
a
= −1 if a is a quadratic non-residue modulo p,
p
0 if a ≡ 0 (mod p).
5
a p−1 a
≡ a 2 (mod p) and ∈ {−1, 0, 1}.
p p
Definition 1.17
The Euclidean Algorithm for finding gcd(A, B) is as follows:
Lemma :18
a) (a,b)=(b,a)
Example :
A = 78, B = 36
(a) A ̸= 0
(b) B ̸= 0
6
(c) Use long division to find that 78/36 = 2 with a remainder of 6.
We can write this as:
(d) 78 = 36 · 2 + 6
Theorem 1.19
ar = (a − 1)(ar−1 − ar−2 · · · a + 1)
Theorem 1.20
Theorem 1.21
ax −1
a+1 = a2x−1 − a2x−2 + · · · + a − 1
NOTATION
Pn : Perfect Numbers
Mn : Mersenne Numbers
un : Fibonacci Numbers
Fn : Fermat Numbers
7
CHAPTER - 2
PERFECT NUMBERS
The history of the theory of numbers abounds with famous conjec-
tures and open question. The present chapter focuses on some of
the intriguing conjectures associated with perfect numbers. A few of
these have been satisfactorily answered, but most remain unresolved;
all have stimulated the development of the subject as a whole.
6=1+2+3
The next number after 6 having this feature is 28; for the positive
divisors of 28 are found to be1,2,4,7,14,and 28, and
28 =1+2+4+7+14
Definition 2.1
8
than n, is given by σ(n) - [Link], the condition ”n is perfect”
amounts to asking that σ(n) - n = n or equivalently, that
σ((n) = 2n
σ(6) = 1 + 2 + 3 + 6 = 2 · 6
and
σ(28) = 1 + 2 + 4 + 7 + 14 + 28 = 2 · 28
P1 = 6 P2 = 28 P3 = 496 P4 = 8128
9
2. The even perfect numbers end , alternately, in 6 and 8.
P5 = 33550336
P6 = 8589869056
1
1+2+22 +23 +....+ 2k− =p
10
1 + 2 + 22 + 23 + .... + 2k−1 = 2k − 1
Theorem - 2.2
Proof :
Let 2k -1 =P , a prime, and consider the integer n=(2k−1 )P . Inas-
much as gcd(2k − 1, P ) = 1, the multiplicativity of σ ( as well as
Theorem 1.6) entails that
σ (n) = σ(2k−1 )P )
=(2k -1)(P+1)
=(2k -1)2k
=2n
11
σ (n) = σ ((2k−1 )m)
= σ (2k−1 ) σ (m)
= (2k − 1) σ (m)
σ (n) = 2n = 2k m
2k m=2k − 1)σ(m)
2k m = σ(m) ≥ m + M = 2k M
12
2k − 1 is a prime number, then the exponent k must itself be prime.
More generally, we have the following lemma.
Lemma - 2.3
If ak − 1 is prime (a > 0, k ≥ 2), then a = 2 and k is also prime
Proof :
It can be verified without difficulty that
ak − 1 = (a − 1)(ak−1 + ak−2 + + a + 1)
ak − 1 = (ar )s − 1
(s−2)
=(ar − l)(ar(s−1) + ar + ... + ar + 1)
and each factor on the right is plainly greater than 1. But this
violates the primality of ak − 1 , so that by contradiction k must be
prime
13
2(22 − 1) = 6
22 (23 − 1) = 28
24 (25 − 1) = 496
26 (27 − 1) = 8128
14
of a number, Cataldi determined that 217 − 1 was prime and, in
consequence, that
Theorem - 2.4
An even perfect number n ends in the digit 6 or 8; equivalently,
either n ≡ 6(mod10) or n ≡ 8(mod10).
Proof :
Being an even perfect number, n may be represented as
n = 2k−l (2k − 1), where 2k − 1 is a prime. According to the last
lemma, the exponent k must also be prime. Ifk = 2, thenn = 6, and
the asserted result holds. We may therefore confine our attention to
the case k > 2. The proof falls into two parts, according as k takes
the form 4m + 1 or 4m + 3
If k is of the form 4m + 1, then
n = 24m (24m+1 − 1)
= 28m+1 − 24m
15
= 2.162m − 16m
n ≡ 26 − 6 ≡ 6(mod10)
n =24m+2 (24m+3 − 1)
= 28m+5 - 24m+2
=28m .25 - 4.16m
=2.162m .16 - 4.16m
= 2.162m+1 − 4.16m
n ≡ 26 − 46 ≡ −12 ≡ 8(mod10)
16
2k−1 = 24m+2 = 16m 4 ≡ 64 ≡ 4(mod10)
whence
n = 2k−1 (2k − 1)
17
CHAPTER - 3
MERSENNE PRIMES
It has become traditional to call numbers of the form
Mn = 2n − 1 n >1
M1 M2 M3 M4 M5 M6 M7 M8
1 3 7 15 31 63 127 255
M2 M3 M5 M7 M13
3 7 31 127 8191
18
nounced; but neither could they. Euler verified (1772) that M31
was prime by examining all primes up to 46339 as possible divisors,
but M67 , M127 , and M257 were beyond his technique; in any event,
this yielded the eighth perfect number
19
to be composite.
Theorem - 3.1
If p and q = 2p + 1 are primes, then either q Mp or q Mp + 2, but
not both.
Proof :
2q−1 − 1 ≡ 0(modq)
≡ 0(modq)
Mp (Mp + 2) ≡ 0(modq)
20
Let us consider p = 23 ,then q = 2p + 1 =47 is also a prime. so
that we may consider the case of M23 . The question reduces to one
of whether 47 M23 or, to put it differently, whether 223 ≡ 1(mod47).
Now, we have
223 = 23 220
= 23 (25 )4
≡ 23 (−15)4 (mod47)
Also we get
223 ≡ 23 · 6 ≡ 1(mod47)
that is M23 .
EXAMPLE 2
Let p = 29 then q = 2 · 29 + 1 = 59
Theorem 3.2
21
If q = 2n + 1 is prime, then we have the following:
(a) q Mn , provided that q ≡ 1(mod8) or q ≡ 7(mod8).
(b) q Mn + 2, provided that q ≡ 3(mod8) or q ≡ 5(mod8).
Proof :
2(q−l)/2 = 2n ≡ 1(modq)
2(p−1)/2 = 2n ≡ −1(modq)
Corollary :3.3
Proof :
22
q ≡ 7(mod8).
⇒ q/mp
If p = 4k + 1 then q = 2p + 1 = 2(4k + 1) + 1 = 8k + 3 then buy
above theorem q ≡ 3(mod8). ⇒ q/Mn + 2 then by using theorem
3.1 q ̸ |Mn
Theorem 3.4
Proof :
We have,
Mp = 2p − 1
2p ≡ 1(modq)
23
an odd integer, then q would be even and a contradiction occurs.
Hence, we must have q = 2kp + 1 for some choice of k, which gives
q the required form.
Theorem 3.5
Proof:
24
S1 S2 S3 S4 S5 S6
4 14 67 42 -16 0
Proof:
25
0(mod4)
if ki is odd
≡
1(mod4) if ki is even
≡ 1 + 11 + 12 + + 1ki ; (mod4)
≡ ki + 1(mod4)
26
= pk11 m2
Corollary
n = pk m2
Proof.
n = pk m2 = 11 ≡ 1(mod4)
27
CHAPTER - 4
FERMAT NUMBERS
Let us mention another class of numbers that provides a rich source
of conjectures, the Fermat numbers. These may be considered as a
special case of the integers of the form 2m + 1. We observe that if
2m + 1 is an odd prime, then m = 2n for some n ≥ 0. Assume to the
contrary that m had an odd divisor 2k + 1 > 1, say m = (2k + 1)r
; then 2m + 1 would admit the nontrivial factorization
Definition 4.1.
A Fermat number is an integer of the form
n
Fn = 22 + 1, n≥0
F0 = 3 F1 = 5 F2 = 17 F3 = 257 F4 = 65537
28
5
F5 = 22 + 1 = 424967297
Theorem 4.2
The Fermat number F5 is divisible by 641.
Proof
We begin by putting a = 27 and b = 5, so that
1 + ab = 1 + 27 · 5 = 641
1 + ab − b4 = 1 + (a − b3 )b
= 1 + 640 − 625
= 1 + 15
= 1 + 3b = 24
= 24 a4 + 1
= (1 + ab − b4 )a4 + 1
= (1 + ab)a4 + (1 − a4 b4 )
= (1 + ab)[a4 + (1 − ab)(1 + a2 b2 )]
29
To this day it is not known whether there are infinitely many Fermat
primes or, for that matter, whether there is at least one Fermat prime
beyond F4 . The best guess is that all Fermat numbers Fn > F4
are composite.
A useful property of Fermat numbers is that they are relatively prime
to each other. Or ”No two Fermat numbers have a common divisor
grater than 1”.
Theorem 4.3
No two Fermat numbers have a common divisor grater than 1
Proof
suppose that Fn and Fn+k ,where k>0, are two Fermat numbers , and
that m/Fn , m/Fn+k
n
If x = 22 , we have
n+k
Fn+k − 2 22 + 1 − 2
=
Fn 22n + 1
xk −1
= x+1
= x2k−1 − x2k−2 + · · · − 1
30
that there are infinitely many Fermat numbers, which leads to the
number of Fermat prime is also infinite.
Later Jesuit priest [Link] devised the practical test (Pepin’s test)
for determining the primality of Fn that is embodied in the following
theorem.
3Fn −1 ≡ 1(modFn )
3Fn −1 ≡ 1(modp)
31
or
32
= 3128
= 33 (35 )25
≡ 27(−14)25
≡ 27.1424 (−14)
≡ 27(17)(−14)
≡ 2719 ≡ 513 ≡ −1(mod257)
so that F3 is prime.
Theorem 4.5
n
Any prime divisor p of the Fermat number Fn = 22 +1, where n ≥ 2,
is of the form p = k · 2n+2 + 1.
Proof
h 2n+1
33
we may further conclude that 2n+1 p − 1. The point is that for
n ≥ 2, p ≡ 1(mod8), and therefore, by Theorem 1.9 , the Legendre
symbol (2/p) = 1. Using Euler’s criterion, we immediately pass to
n Character of Fn
0, 1, 2, 3, 4 prime
5, 6, 7, 8, 9, 10, 11 completely factored
12, 13, 15, 16, 18, 19,25,27,30 two or more prime factors known
17,21,23,26,28,29,31,32 only one prime factor known
14,20,22,24 composite, but no factor known
33,34 ,35 character unknown
The case for F16 was settled in 1953 and lays to rest the tantalizing
conjecture that all the terms of the sequence
2 22 222
2 + 1, 22 + 1, 22 + 1, 22 + 1 22 + 1, · · ·
34
CHAPTER - 5
FIBONACCI
The Fibonacci numbers may be defined by the recurrence relation
u0 = 0, u1 = 1,
and
un = un−1 + un−2 for n > 1.
1, 1,2,3,5,8, 13,21,34,55,89, 144,233,377, ...
is called the Fibonacci sequence and its terms the Fibonacci numbers.
Theorem:5.1
Proof
Let us suppose that the integer d > 1 divides both un and un+1 ·
Then their difference un+1 − un = un−1 is also divisible by d. From
this and from the relation un − un−1 = un − 2, it may be concluded
that d un−2 · Working backward continuously like this we can say
that d un−3 ,d un−4 , ... , and finally that d u1 . But u1 = 1, which
is certainly not divisible by any d > 1. This contradiction ends our
proof.
35
subscript n > 2 is a prime.
But the term u19 shows that the assumption is false. Since the term
un+2 = 1 · un+l + un
un+l = 1 · un + un−1
·
·
·
u4 = 1 · u3 + u2
u3 = 2 · u2 + 0
gcd(un+2 , un+1 ) = u2 = 1
36
we need 6 divisions to find the greatest common divisor of the inte-
gers u8 = 21 and u7 = 13:
21 = 1 · 13 + 8
13 = 1.8 + 5
8=1·5+3
5=1·3+2
3=1·2+1
2=2·1+0
Also we can see that one of the features of the Fibonacci sequence is
that the greatest common divisor of two Fibonacci numbers is itself
a Fibonacci [Link] equation
37
it is obviously true. Let us assume that it is true for n = 1, 2, ..., k.
Now we have to show that the equation holds, when n = k + 1.
The equation holds for n=k, implies
Theorem 5.2 :
Proof :
38
um+n = um−1 un + um un+1
Lemma:5.3
Proof:
we can wright
gcd(um , un ) = gcd(uqn+r , un )
= gcd(uqn−1 ur + uqn ur+1 , un )
Claim : gcd(uqn−1 , un ) = 1
Let d = gcd(uqn−1 , un ).The relations d/un and un /uqn imply that
39
d/uqn ,and therefore d is a positive common divisor of the succes-
sive Fibonacci numbers uqn−1 and uqn · Because successive Fibonacci
numbers are relatively prime, the effect of this is that d = 1.
Theorem:5.4
Proof:
m = q1 · n + r1 0 < r1 < n
n = q1 · r1 + r2 0 < r2 < r1
r1 = q3 · r2 + r3 0 < r3 < r2
·
·
·
rn−2 = qn · rn−1 + rn 0 < rn < rn−1
rn−1 = qn+1 · rn + 0
40
gcd(um , un ) = gcd(ur1 , un ) = gcd(ur1 , ur2 ) = · · · = gcd(urn−1 , urn )
Because rn /rn−1 , Theorem 14.2 tells us that urn /urn−1 whence gcd(urn−1 , urn ) =
urn . But rn , being the last nonzero remainder in the Euclidean Al-
gorithm for rn and n, is equal to gcd(m, n).We get,
gcd(um , un ) = ugcd(m,n)
= ud
Corollary:5.5
Proof:
41
CONCLUSION
42
BIBLIOGRAPHY
43
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1901)
ACKNOWLEDGEMENT
PRANAV K P
CONTENTS
1. INTRODUCTION ................................................................ 01
2. PRELIMINARIES .................................................................03
5. APPLICATIONS .................................................................. 38
6. BIBLIOGRAPHY................................................................ 40
INTRODUCTION
1
as Topological vector spaces.
2
PRELIMINARIES
Definition 0.1(Vector spaces): A vector space over K (where
K = R or C) is a set X, whose elements are called vectors, and in
which two operations, vector addition and scalar multiplication, are
defined with following algebraic properties:
2. X contains the unique vector zero such that x+0 = x for every
x ∈ X.
1 × x = x,
α(βx) = (αβ)x,
α(x + y) = αx + αy
(α + β)x = αx + βx
hold.
3
Definition 0.2.(Topological space): A Topological space is a pair
(X, τ ) where X is a set and τ is a family of subsets of X satisfying:
1.ϕ ∈ τ and X ∈ τ .
4
that both f and f −1 are continuous.
Definition 0.7. (Open set): A subset A ⊆ X is said to be open
if for every x ∈ A, there exists some open ball around x which is
contained in A.
2. For all n ∈ D, n ≥ n
5
Definition 0.13. (Filter): A filter on a set X is a non-empty
family F of subsets of X such that:
1. ϕ ∈
/F
6
Definition 0.20. (Tottaly bounded): Let A be a subset of a
metric space (X, d). Let ϵ > 0. A finite set {x1 , x2 , ..., xn } of points
of X is said to form a finite ϵ-net if A ⊆ Bϵ (x1 ) ∪ ... ∪ Bϵ (xn ). The
set A is totally bounded if A has a finite ϵ-net for every ϵ > 0.
7
CHAPTER 1
• (x, y) → x + y of X × X into X
• (α, x) → αx of K × X into X, K = C or R
8
Next, to verify that the algebraic operations addition and scalar
multiplications are continuous, we have to show that given ϵ > 0,
there is a δ > 0 such that
≤ ∥x − a∥ + ∥y − b∥
≤δ+δ
= 2δ
Take δ = ϵ/2, we get ∥x + y − (a + b)∥ < ϵ. Therefore, vector
addition is continuous.
Now, to prove scalar multiplication is continuous, we have the
identity
λx − αa = λx − αa + λa − λa
= λ(x − a) + a(λ − α).
≤ |λ|∥x − a∥ + |λ − α|∥a∥
ϵ ϵ
Hence, ∥λx − αa∥ < ϵ, whenever ∥x − a∥ < 2|λ| and |λ − α| < 2∥a∥ .
Hence, the result.
Here, a normed linear space satisfies the conditions of a topolog-
ical vector space.
9
Example 1.4 The real line with discrete topology is not a topolog-
ical vector space.
1 1
(λ − , λ + ){x} ⊂ Uλ Ux ⊂ Uz = {z} = {λx}
n n
1 1
⇒ (λ − , λ + ){x} ⊆ {λx}
n n
This is not possible. Since interval ̸⊂ singleton set
10
x ∈ X, fx : X → X is defined by fx (y) = x + y.
To prove that fx is a homeomorphism
suppose fx (y) = fx (z)
=⇒ x + y = x + z
=⇒ y = z
g(U ) = U × {y} ⊂ W
Hence, g is continuous.
By the definition of a topological vector space, the function h :
X × X → X defined by h[(x, y)] = x + y.
Then h is continuous.
Therefore, the composition h ◦ g is continuous.
11
Similarly, we can show that fx−1 : X → X defined by
λx + (1 − λ)y ∈ A
whenever x, y ∈ A and 0 ≤ λ ≤ 1, or equivalently A is convex if
x, y ∈ A, λ ≥ 0, µ ≥ 0, and λ + µ = 1. Then λx + µy ∈ A.
12
∥λx∥ = |λ|∥x∥ ≤ 1
=⇒ λx ∈ B(0, 1).
This show that B(0,1) is balanced.
λA + µA ⊂ A
13
Theorem 1.19. A set A is absolutely convex if and only if A is
both balanced and convex.
x ∈ A, |λ| ≤ 1 =⇒ λx ∈ A.
Hence A is balanced.
Conversely suppose that A is convex and balanced.
We want to show that A is absolutely convex.
Let x, y ∈ A and |λ| + |µ| ≤ 1.
• Case 1. If λ = 0 or µ = 0
then λx + µy ∈ A, because A is balanced.
14
λ µ |λ| |µ|
[Since |λ| x ∈ A, |µ| y ∈ A,and |λ|+|µ| + |λ|+|µ| = 1,A is con-
vex.]
λx µy
Therefore by equation (1.19.2) we get, |λ|+|µ| + |λ|+|µ| ∈A
Now A is balanced and |λ| + |µ| ≤ 1 we have
λx µy
(|λ| + |µ|) |λ|+|µ| + |λ|+|µ| ∈ A
=⇒ λx + µy ∈ A
15
So, λU is a neighbourhood of 0.
(1.22.1) f (V ) ⊂ U
16
Also, by (1.22.1), W ⊂ U .
Finally, we shall show that W is balanced.
Let x ∈ W and 0 < |λ| ≤ 1.
=⇒ λx ∈ W .
Hence W is balanced.
i.e., every neighbourhood of 0 in a topological vector space X in-
cludes a balanced neighbourhood of 0.
(x + U ) ∩ A ̸= ϕ
17
Hence, x ∈ A + U .
Thus
(1.23.1) Ā ⊂ ∩{A + U }.
18
For this, let x ∈ Ā. Then for any neighbourhood U of 0, we have U
is balanced and x + U is a neighbourhood of x. As x ∈ Ā
(x + U ) ∩ A ̸= ϕ
λ[(x + U ) ∩ A] ⊂ (λx + U ) ∩ A.
Hence,
λx0 ∈ (λx + U ) ∩ A,
V + V ⊂ U.
Now
x ∈ Ā =⇒ (x + V ) ∩ A ̸= ϕ
y ∈ Ā =⇒ (y + V ) ∩ A ̸= ϕ
19
λx0 + (1 − λ)y0 ∈ (λx + V ) ∩ λA + [(1 − λ)y + V ] ∩ (1 − λ)A
⊂ A ∩ [λx + (1 − λ)y + U ]
Therefore,
λx + (1 − λ)y + U ∩ A ̸= ϕ.
Hence,
λx + (1 − λ)y ∈ Ā
z = λx + (1 − λ)y
W = λU + (1 − λ)V
Then
W = ∪{λu + (1 − λ)V : u ∈ U }
20
In particular, f is continuous at 0 = (0, 0) [since f is continuous at
each point]
Hence, given a neighbourhood U of 0, there exists a neighbourhood
N of (0, 0) with f (N ) ⊂ U .
[ since we have by definition of continuity, “Let X and Y be two
topological spaces, a function f from X to Y is said to be contin-
uous at x ∈ X if for each neighbourhood U of f (x) there exist a
neighbourhood V of x such that f (V ) ⊂ U ”. ]
Take W = V1 × V2 Where V1 and V2 are neighbourhoods of 0.
Let
V = V1 ∩ V2 .
Then
V + V ⊂ V1 + V2 = f (v1 , V2 ) ⊂ f (N ) ⊂ U .
Thus,
(1.25.1) V + V ⊂ U.
(1.25.2) W ⊂V.
W ⊂V +W ⊂V +V
21
That is, Every neighbourhood of 0 in a topological vector space X
includes a closed and balanced neighbourhood of 0.
22
CHAPTER 2
NORMABLE SPACES
Defintion 2.1. Let X be a vector space. A Semi-norm on X is a
function p : X → R satisfying
1. p(x) ≥ 0
2. p(λx) = |λ|p(x)
4. p(x) = 0 ⇐⇒ x = 0
p(x) = |f (x)| ∀x ∈ X.
Then p is a semi-norm on X.
p(λx) = |f (λx)|
= |λ||f (x)|
23
= |λ|p(x).
and
p(x + y) = |f (x + y)|
= |f (x) + f (y)|
≤ |f (x)| + |f (y)|
= p(x) + p(y).
Hence p is a semi-norm on X.
1. ∥x∥ ≥ 0∀x ∈ X
24
p(x) = p[y + (x − y)]
≤ p(y) + p(x − y)
That is,
= p(x) + | − 1|p(x − y)
That is,
25
Definition 2.5. A set in a topological vector space X is said to
be bounded if it is absorbed by every neighbourhood of 0. In other
words, a set A is bounded if and only if for every neighbourhood U
of 0 there exist ρ > 0 such that λA ⊂ U whenever |λ| < ρ.
1. A is bounded.
ϵn xn ∈ ϵn A ⊂ U
ϵn xn → 0 as n → ∞
(Since U is a neighbourhood of 0)
Since (xn ) is arbitrary, for every sequence (xn ) in A and for every
26
sequence (ϵn ) of scalars with ϵn → 0 it is true that ϵn xn → 0 as
n → ∞.
Step 2 : Suppose that for every sequence (xn ) in A and for every
sequence (ϵn ) of scalars with ϵn → 0 it is true that ϵn xn → 0 as
n → ∞.
We want to prove that for every sequence (xn ) in A, it is true that
( n1 )xn → 0 as n → ∞.
Let (xn ) be a sequence in A, and take ϵn = n1 , where n = 1, 2, ...
So that ϵn → 0.
Then from (2), we have ϵn xn → 0.
i.e.,
( n1 )xn → 0 as n → ∞
Choose
xn ∈ A − nU for n = 1, 2, ...
Then
27
1
n xn ∈
/ U for n = 1, 2, ....
{a + U : a ∈ A}
A ⊂ ∪{ai + U }
(2.9.1) V +V ⊂U
28
(2.9.2) A⊂F +V
Hence A is bounded.
29
∩{T z : z ∈ D} =
̸ ϕ,
a ∈ ∩{Tz : z ∈ D}.
(2.10.1) xα − xα0 ∈ V
But a ∈ Tz ∀z ∈ D.
Thus, (a + V ) ∩ Tz ̸= ϕ and accordingly, there exist
(2.10.2) xα ∈ a + V ∀α ≥ z.
xα′ − a = xα′ − xα + xα − a ∈ V + V ⊂ U .
x+V ⊃B
30
for some B ∈ F because F is a filter base.
But, S ∈ F .
Hence B ∩ S ̸= ϕ and hence
(x + V ) ∩ S ̸= ϕ.
(α + β)A = αA + βA
• Case 1: If α = 0, β = 0.
If z ∈ A then
αz + βz ∈ αA + βA.
But
αz + βz = (α + β)z.
Therefore,
(α + β)z ∈ αA + βA, ∀z ∈ A,
31
that is,
(2.11.1) (α + β)A ⊂ αA + βA
If x, y ∈ A
α β
where α1 = α+β and β1 = α+β .
(2.11.3) α1 x + β1 y ∈ A
αx + βy ∈ (α + β)A
hence
(2.11.4) αA + βA ⊂ (α + β)A
αA + βA = (α + β)A.
32
Theorem 2.14. (Kolmogoroff ’s Criterion for Normability)
Let X be a topological vector space. Then X is normable if and only
if X is Hausdorff and X contains a bounded convex open neighbour-
hood of 0.
Also
1
W = {x ∈ X : ∥x∥ ≤ r} =⇒ r {x ∈ X : ∥x∥ ≤ r} = V
i.e., V = 1r W ,
and 1r W ⊂ 1r G
i.e., V ⊂ 1r G
Hence V is a bounded set in X.
Next we would show that V is convex.
Let x, y ∈ V and let 0 ≤ t ≤ 1 we have the following implications:
x ∈ V =⇒ ∥x∥ ≤ 1
y ∈ V =⇒ ∥y∥ ≤ 1.
and hence
=1
33
That is, ∥tx + (1 − t)y∥ ≤ 1.
Thus tx + (1 − t)y ∈ V .
Thus we established that there exists a non empty, open, bounded,
convex set namely V in X. And also we have the result that “ Every
Topological vector space is a Hausdorff space. ”
i.e., X is Hausdorff and X contains a bounded convex open neigh-
bourhood V of 0.
Conversely suppose that X is Hausdorff and X contains a bounded
convex open neighbourhood U of 0.
Then we can find an absolutely convex open neighborhood V of 0
such that V ⊂ U .
Boundedness of U =⇒ Boundedness of V . Let ∥ · ∥ be the
Minkowski’s functional of V , that is,
34
λ < ∥x∥ + ϵ.
µ < ∥y∥ + ϵ.
Hence
x + y ∈ λV + µV = (λ + µ)V
∥x + y∥ ≤ ∥x∥ + ∥y∥.
= inf{µ µλ : x ∈ µλ V }
= µ inf{ µλ : x ∈ µλ V }
= µ∥x∥
µx ∈ λV ⇐⇒ |µ|x ∈ λV
and consequently,
35
Thus
x ̸= 0 =⇒ ∥x∥ > 0
λ ∈ A(x) =⇒ x ∈ λV
x
=⇒ λV ⊂ tW
=⇒ x ∈ λtW
1
=⇒ t < λ < ∥x∥ + ϵ
1
=⇒ t < ∥x∥ + ϵ
1
=⇒ 0 < t < ∥x∥ since ϵ is arbitrary
36
W be any τ - neighbourhood of 0. Since V is bounded, we have
rV ⊂ W for some r > 0
37
APPLICATIONS OF
TOPOLOGICAL VECTOR SPACES
38
structures on manifolds. For example, the tangent space to a
manifold at a point is a topological vector space, and the space
of vector fields on a manifold is a topological vector space as
well.
39
Bibliography
40
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1906)
ACKNOWLEDGEMENT
GIFTY P GEORGE
CONTENTS
1. INTRODUCTION ................................................................ 01
2. PRELIMINARIES ................................................................ 03
0.1 Graph Theoretic Definitions ........................................ 03
0.2 Definitions Related to Algebra ..................................... 05
6. BIBLIOGRAPHY................................................................. 44
INTRODUCTION
Graph theory has become a very popular and rapidly growing area of
discrete mathematics for its numerous theoretical development and
countless applications to practical problems. As a research area,
graph theory is still relatively young, but it is maturing rapidly with
many deep results having been discovered over the last couple of
[Link] meaning of the term graph in graph theory is not same
as the term graph that used to represent a function or statistical
data. The study of graph theory was introduced by Euler in 1736.
For the contribution of Euler towards graph theory, he is known as
the father of graph theory. But the term graph was introduced by
Sylvester in a paper published in 1878. It took 200 years since Eu-
ler’s publication to revive graph theory and the first book on graph
theory was published in 1936 by Denes Konig.
1
structures and the results and methods of algebra are used to de-
duce theorems about the graphs. On the other hand, many algebraic
structures can also be studied by translating them into graph and
using the properties of graphs. Algebraic graph theory includes the
study of symmetry and regularity properties of graphs which can
be studied using group theory. Asymmetry property of a graph is
related to the existence of automorphism. The concept of automor-
phism of a graph, which is the permutation of vertices that preserves
adjacency, played an important role in the characterization of graphs.
The existence of automorphism led to the idea of permutation group
of graphs. In recent times many researches are showing their interest
towards the relation of graphs with rings. In this project we mention
some significant results in this field which have been proved in the
last century.
2
PRELIMINARIES
n(n−1)
1. A simple graph with n vertices can have at most 2 edges.
3
nality of E(G) is called the size of G.
Definition 0.1.5.
The set of all neighbors of vertex u is the open neighborhood of u or
the neighborhood set of u and is denoted by N(u).
N[u] = N(u) ∪ {u} is the closed neighborhood of u.
Definition 0.1.6.
Isomorphism of graphs:If G and H are simple graphs, an isomor-
phism from G to H is a bijection ϕ : V(G) −→ V(H) such that u
and v are adjacent if and only if ϕ(u) and ϕ(v) are adjacent in H.
Definition 0.1.7.
Bipartite graph:A graph is bipartite if its vertex set can be parti-
tioned into two non empty subsets X and Y such that each edge of
G has one end in X and the other end in Y .The pair (X,Y) is called
a bipartition of the bipartite graph.
Definition 0.1.8.
Complete bipartite graph:A simple bipartite graph is complete if
each vertex of X is adjacent to all the vertices of Y .
If |X| = p and |Y| = q then the complete bipartite graph is denoted
by Kp,q .
Definition 0.1.9.
A complete bipartite graph of the form K1,n is called a star graph.
Definition 0.1.10. Subgraph:A graph H is called a subgraph of G
if V(H)⊆ V(G) or E(H) ⊆ E(G).
Definition 0.1.11.
A digraph is a graph with directed edges. If G is a digraph then the
4
elements of the set E(G) are ordered pairs and are called arcs.
For a digraph, there are two types of degree defined. For a vertex
v of a digraph G, the number of edges incident from it is called
out-degree of v and is denoted by deg − (v) and the number of edges
incident to it is called in-degree of v and is denoted by deg + (v).
Here the word ring we shall mean a commutative ring with an iden-
tity element, that is, a ring satisfying above axioms.
Definition 2.2.2.
A ideal r of a ring R is a subset of R which is an additive subgroup
and is such that Rr ⊂ r(i.e.,x ∈ R, and y ∈ r imply xy ∈ r).
5
Definition 0.2.3.
If a and b are two non zero elements of a ring R such that ab = 0,
then a and b are divisors of zero or [Link] particular a is
left zero-divisor and b is a right zero-divisor.
Remark 0.2.4.
There is no distinction between left and right zero-divisors in a com-
mutative ring.
Definition 0.2.5.
An integral domain is a commutative ring with unity containing no
zero-divisors. For example, Z and K[x1 , x2 , ..., xn ] (K a field, xi in-
determinates) are integral domains.
Definition 0.2.6.
An element x ∈ R is nilpotent if xn = 0 for some n>0.
A nilpotent element is a zero-divisor but not conversely.
Definition 0.2.7. A unit in R is an element x which divides 1, that
is an element x such that xy = 1 for some y ∈ R.
Definition 0.2.8.
A field is a ring R in which 1 0 and every non zero element is a
[Link] field is an integral domain but not conversely.
Definition 0.2.9.
A ring R is said to be Noetherian if it satisfies the following three
conditions.
6
3. Every ideal in R finitely generated.
Definition 0.2.10.
An Artin ring is one which satisfies the descending chain condition
on ideals.
Definition 0.2.11.
A ring is quasi local if it contains a unique maximal ideal.
Definition 0.2.12.
In a commutative ring R an annihilator(ideal) of an element x, de-
noted ann(x), is the set of those elements y for which xy = [Link] terms
of the zero divisor graph this would be the set of vertices adjacent
to x. Note that x itself may be an element of ann(x).
7
Chapter 1
Definition 1.1.1.
Let R be a commutative ring (with unity 1) and let Z(R) be its set
of zero [Link] zero divisor graph of a ring R is a simple graph
(that is with no loops and multiple edges) whose set of vertices con-
sists of all non zero zero divisors of R , with an undirected edge
between two distinct vertices x and y if and only if xy = 0. The zero
divisor graph ofR is denoted byΓ(R).
Exercise 1.1.2.
Let us draw a graph for the ring R = Z12 , where
Z12 = {0, 1, 2, ..., 11}. The zero-divisors of Z12 are {2, 3, 4, 6, 8, 9,
10} which is the vertex set of the zero divisor graph Γ(Z12 ). Edge
set of this graph contains pair of vertices. For example, {3, 4} is
an edge because 3 × 4 = 0 in Z12 .Note that we do not consider the
loops, so even though 6 × 6 = 0 in Z12 . Therefore {6, 6} is not an
edge. Now we list all edges in the complete edge set E as follows.
E = {{2, 6}, {3, 4}, {3, 8}, {4, 6}, {4, 9}, {6, 8}, , 9}, {6, 10}}.
8
The graph Γ(Z12 ) is,
Figure 1.1
The main objective of this topic is to study the interplay of ring the-
oretic properties of R with graph theoretic properties of Γ(R). This
study helps to illuminate the structure of Z(R).
9
Remark 1.1.3.
The zero divisor graph Γ(R) is the empty graph if and only if R is
an integral domain.
In this section we show that Γ(R) is always connected and has small
girth and diameter and we determine which complete graphs and
star graphs may be realized as Γ(R).
Theorem 1.2.1.
Let R1 and R2 be two finite commutative rings. If R1 ∼
= R2 , then
ΓR1 ∼
= ΓR2 .
Proof.
Assume R1 ∼
= R2 . Then there exists an isomorphic map
ϕ : R1 → R2 , Since ϕ is a ring isomorphism that preserves zero-
divisor. That is ϕ maps zero-divisor of R1 to a zero-divisor of R2 .
Let ai and bi be the zero divisor of R1 and R2 respectively, where i
= 1, 2, ..., n. Then ϕ (ai ) = bi for some i. Also if ai is adjacent to
aj , then ϕ (ai ) is adjacent to ϕ(aj ), for all i j. Then ϕ is a graph
isomorphism. Hence Γ(R1 ) ∼
= Γ (R2 ).
10
Remark 1.2.2.
Converse of the above theorem is not [Link] this consider the ex-
ample given below.
Exercise 1.2.3.
Below are the zero-divisor graphs for several rings. These examples
show that non isomorphic rings may have the same zero divisor graph
and that the zero divisor graph does not detect nilpotent elements.
Figure1.2
Exercise 1.2.4.
Path graph (Linear graph) cannot always be realised as a zero divisor
graph. It is not possible to find a ring which gives Γ(R) with vertices
{a, b, c, d} and edges a - b, b - c, c - d. That is there is no ring R
such that Γ(R) is,
Figure 1.3
11
We can give a proof for it as follows:
Suppose R is a ring with Γ(R) as shown in the figure above.
Then Z(R)= {0, a, b, c, d}.
Since {a, b} and {b, c} are edges, so ab = bc = 0.
Therefore b(a + c) = 0 → a + c = 0 or a + c ∈ (R) . Since b makes
an edge with a and c only, a + c = 0, a, b, [Link] will show that
the possibilities gives a contradiction. Suppose a + c = 0. Then
ad = (-c)d = [Link] there is no edge between a and d. So a + c ̸=
0. Also a + c cannot be a or c either because then c = 0 or a = 0
by the cancellation property of rings. Now let us assume that a + c
= b. By the symmetry of graph we can assume that b + d = c. Then
(a + c)(b + d) = bc
⇒ (a + c)b + (a + c)d = bc
⇒ ad = bc = 0.
Exercise 1.2.5.
We have seen above that Γ(R) can be a triangle or square. But Γ(R)
cannot be an n-gon for n ≥ 5.
It can be proved as in the above case.
12
Figure 1.4
Remark 3.2.6.
For each n ≥ 3 there is a zero divisor graph with n-cycle.
Remark 3.2.7.
Let A and B be integral domain and let R = A × B. Then Γ(R) is
13
a complete bipartite graph with | ΓR| = |A| × |B| - 2.
Exercise 1.2.8.
If A = Z12 , then Γ(R) is a star graph with |ΓR|=|B|.
For example, Γ(Fp ×Fq )=K p−1,q−1 and Γ(Z2 ×Fq )=K 1,q−1 .We give two
specific examples.
Figure 1.5
Remark 1.2.9.
ΓR may be [Link] is a ring may have an infinite number of
zero divisors. But ΓR is probably of most interest when it is finite,for
then one can draw Γ(R) .
Theorem 1.2.10.
Let R be a commutative ring. Then Γ(R) is finite if and only if
either R is finite or an integral [Link] particular, if
1 ≤ |Γ R| < ∞, then R is finite and not a field.
14
Proof.
Suppose that Γ(R) is finite and non empty. Then there are non zero
x, y ∈ R with xy = 0. Let I = ann(x). Then y ∈ I and in fact,ry ∈ I
for all r ∈ R and I ⊆ Z(R). Thus R must be [Link] R is in-
finite with finitely many zero divisors. Since I is a subset of the zero
divisors of R, it is [Link] there exists an i ∈ I such that J = {r ∈
R : ry = i} is [Link] r, s ∈ J, (r s)y = 0. Thus, ann(y) is infinite,
contradicting the fact that there are only finitely many zero divisors.
Definition 1.2.11.
A graph Γ is connected if there is a path between any two distinct
vertices.
For distinct vertices x and y of Γ, let d(x, y) be the length of the
shortest path from x to y (d(x, y) = ∞ if there is no such path).
Definition 1.2.12.
The diameter of Γ is diam(Γ) = sup {d(x, y) : x, y ∈ Γ}.
The girth of Γ, denoted by g(Γ), is defined as the length of the
shortest cycle in Γ (g(Γ)=∞ if Γ contains no cycle). Note that if Γ
contains a cycle, then g(Γ) ≤ 2diam(Γ)+1.
We next show that the zero divisor graphs are all connected and
have exceedingly small(≤ 3) diameter and girth. Thus, for distinct
x, y ∈ Z(R)∗ , either xy = 0, xz = zy = 0 for some z ∈ Z(R)∗ - {x,
15
y}, or xz1 = z1 z2 = z2 y = 0 for some distinct z1 , z2 ∈ Z(R)∗ -{x, y}.
Theorem 1.2.13.
Let R be a commutative ring (not necessarily finite). Then Γ R is
connected. Moreover diam ( Γ R )≤ 3.
Proof.
Let x, y ∈ Γ(R) , with x ̸= y. If xy = 0, then d(x, y) = 1. Suppose
now that xy ̸= 0. If x2 = 0 =y 2 , then x - xy - y is a path of length
two and d(x, y) = 2. Suppose x2 = 0 and y 2 ̸= 0. There exists an
element b ∈ Γ(R) with b ∈ y such that by = 0. If bx = 0, then x -
b - y is a path of length two between x and y. In either case, d(x, y)
= 2. A symmetric argument holds if y 2 = 0 and x2 ̸= 0. Thus we
may suppose that neither x2 and y 2 is zero. Then there exists non
zero zero divisors a, b ∈ Γ(R) (not necessarily distinct) with ax = 0
= by. If a = b, then x - a - y is a path of length two, and hence d(x,
y) = 2. Thus we may assume that a ̸= b. Consider the element ab.
If ab = 0, then x - a - b - y is a path of length 3, and hence d(x, y)
≤ 3. If ab ̸= 0, then x - ab - y is a path of length 2, and hence d(x,
y) = 2. In all of the cases, there is a path between x and y of length
less than or equal to 3, and since x and y were arbitrary it follows
that the diameter of Γ(R) is less than or equal to 3.
16
Remark 1.2.14.
It is clear that the zero divisor graphs of Z4 , Z2 × Z2 and Z6 have
diameter 0,1 and 2 respectively. We can show that the diameter 3 is
also achieved. For this consider the ring Z2 × Z2 × Z2 . The distance
between the elements (1,1,0) and (0,1,1) is three. In fact, a shortest
path is (1,1,0) - (0,0,1) - (1,0,0) - (0,1,1).
The fact that the distance between points is small also constraints
the length of the shortest cycle, that is to say, the girth of the graph.
The following corollary make use of the previous theorem to estab-
lish a bound for the girth of a zero divisor graph.
Corollary 1.2.15.
If R is a ring, then the girth of Γ(R) is less than eight.
Proof.
It is enough to suppose to the contrary that we could find a ring
R such that Γ(R) has a smallest cycle C of length exactly 8, say,
v0 - v1 - v2 - v3 - v4 - v5 - v6 - v7 - v8 = v0 . Let P1 denote the
path v0 - v1 - v2 - v3 - v4 and P2 denote the path v0 - v7 - v6 - v5 -
v4 .To help in visualizing the proof the figure below provides a hypo-
thetical representation of each of the two main considerations which
[Link] observe that for 0 < i < 4 < j < 8, vi and vj are not
connected. Assume the case is otherwise. Then v0 - v1 ...- vi - vj ...-
v0 is a cycle of length less than eight contradicting the assumption
that the girth is eight. Now assume there is a path v0 - x - y - v4
17
by previous theorem(If not, then there is a path v0 - x -v4 . The
proof goes through if in this case we just identify x and y. The im-
possibility of v0 and v4 being adjacent is apparent). The fact just
proved implies that the path v0 - x - y - v4 intersects P1 , or perhaps
P2 , but not [Link], by symmetry we may as well assume that
the path v0 - x - v4 does not intersect P2 . This assumption yields a
cycle v0 − x − y − v4 − v5 − v6 − v7 − v8 = v0 of length seven, the
final contradiction.
Figure 1.6
Exercise 1.2.16.
Let T be a an integral domain, and n ≥ 3 an integer. Define
18
Chapter 2
CAYLEY GRAPHS
Definition 2.1.1.
Let G be a finite group with identity 1. Let S be a subset of G
/ S and S = S −1 . That is, s ∈ S if and only if s−1 ∈ S.
satisfying 1 ∈
The Cayley graph Cay (G, S) on G with connection set S is defined
as follows:
(a) the vertices are the elements of G;
(b) there is an edge joining g and h if and only if h = sg for some s
19
∈ S.
The set of all Cayley graphs on G is denoted by Cay (G).
Note 2.1.2.
When G is an abelian group, we use additive notation for the group
operation. Hence we write S = -S for the connection set and h = s
+ g(for some s ∈ S).
For example consider Cay (Z9 , {1, 3, 6, 8}).
Figure 2.1
1. Cayley Digraphs
20
2. Cayley Color Graphs
Figure 2.2
(2) Cayley Color Graphs: We can extend the idea of Cayley di-
graph to a Cayley color graph, where S is a generating set for G, each
si ∈ S is assigned a color, and if g = si h, then the arc connecting
them is colored si .
Example given below shows the Cayley color graph of s3 with con-
nection set S = {a, b}, where a = (1 2 3) and b = (1 2).
21
Figure 2.3
Definition 2.2.1.
An automorphism ϕ ∈ Aut (D(G, S)) is color preserving if given an
arbitrary arc {g, h}, {g, h} and {ϕ (g) , ϕ (h)} have the same color.
Proposition 2.2.3.
Let G be a group with generating set S and let ϕ be a color pre-
22
serving permutation on V (D(G, S)). Then ϕ is a color preserving
automorphism of D(G, S) if ϕ (gh) = ϕ (g)h.
Proof.
Suppose that ϕ (gh) = ϕ (g)h. To show that ϕ is color preserving,
we need to show that if gh−1 = s then ϕ(gh−1 )=s.
Suppose gh−1 = s. Then,
ϕ(gh−1 ) = ϕ(g)h−1
= ϕ(g)g −1 s
= ϕ(gg −1 s)
=s
Theorem 2.2.4.
Let G be a nontrivial group with generating set S. Then the group
of color preserving automorphisms of D(G, S) is isomorphic to G.
Proof.
Let G be a group of order n and gi ∈ G for 1 ≤ i ≤ n. Define the
map ϕi : V (D(G, S)) −→ V (D(G, S)) by ϕi (g) = gi g. This map
is surjective, since given any g ∈ V (D(G, S)), g = ϕi (gi−1 g). This
map is also injective since if
ϕi (g1 ) = ϕi (g2 )
⇒ gi g1 = gi g2
⇒ g1 = g2 .
23
ϕi (g1 g2 ) = gi (g1 g2 )
= (gi g1 )g2
= ϕi (g1 ) g2 .
ϕ(gj ) = ϕ(egj )
= ϕ(es1 r1 s2 r2 ... sm rm .)
= ϕ(e)s1 r1 s2 r2 ... sm rm .
= gi gj
= ϕi (gj ).
24
α(gi gj ) = ϕij
= ϕi ◦ ϕj
= α(gi ) ◦ α(gj ).
25
are G - equivalent if gx = y for some g ∈ G. This G - equivalence
is an equivalence relation on V . Each partition of V into such an
equivalence class is called an orbit of V under G. Also recall that the
stabilisersubgroup of G for an element x ∈ V , denoted Gx , is the
set of all group elements in G that fix x.
That is,
Gx = {g ∈ G : gx = x }
Definition 2.2.5.
A graph Γ is vertex transitive if there exists a single orbit of V (Γ)
under Aut(Γ). That is, given any v, u ∈ V (Γ) there exists a ϕ ∈
Aut(Γ) such that ϕ (v) = u.
Note that here Γ denote simply a graph not a zero divisor graph.
Theorem 2.2.6.
Every Simple Cayley Graph is Vertex-Transitive.
Proof.
Let ρg : v −→ vg for all v ∈ V (Cay (G, S)). Clearly, ρg permutes
the elements of V (Cay (G, S)). To show that ρg ∈ Aut(Cay (G, S))
we must show that {v, u} ∈
E (Cay (G, S)) if and only if {vg, ug} ∈ E (Cay (G, S)).
Suppose {v, u} ∈ E (Cay (G, S)). Then we know that v = su for
some s ∈ S or equivalently, vu−1 = s. But
26
= vu−1 .
Therefore, {v, u} ∈ E (Cay (G, S)) if and only if {vg, ug} ∈ E (Cay
(G, S)) and ρg is the group of Cay(G, S).
Now given any vertices v, u the mapping ρv−1 u maps v to u, since
vv −1 u = u. Thus any Cayley graph is vertex-transitive.
Just as a subgroup of an automorphism group for a Cayley color
graph of G contained a subgroup isomorphic to G, simple Cayley
graph possess a similar property.
Definition 2.2.7.
A group G acting on a set V is semi-regular if Gv = e for all v ∈ V.
If a group is semi-regular and transitive, then we say it is regular.
Theorem 2.2.8.
Let G be a group and S be an inverse closed subset of G. Then
Aut(Cay(G, S)) contains a regular subgroup isomorphic to G.
Proof.
Let G be a group with connection set S and Cay(G, S) be the Cayley
graph for G defined on S. Now consider the mapping ρg : v −→ vg.
We know that ρg ∈ Aut(Cay(G, S)),and it can be easily shown that
H = {ρg : g ∈ G} is a subgroup of G. This group acts regularly on
G, since it is clearly semi-regular and is also transitive by the proof
of the above theorem. The map ϕ : H −→ G defined by ϕ(ρg ) = g
is an isomorphism by Cayley’s theorem. Thus, H ≤ Aut(Cay(G, S))
is isomorphic to G.
27
It is natural to ask whether all vertex-transitive graphs are Cay-
ley graphs. This question was negatively answered by the counter
example of the Petersen graph.
Figure 2.4
Theorem 2.2.9.
If a group G acts regularly on the vertices of the graph Γ, then Γ is
a Cayley graph for G relative to some inverse closed connection set
S.
28
Proof.
Let Γ be a graph with degree n and let G be a group acts normally
on V (Γ) = {v1 , v2 , ..., vn }. Since G acts normally on Γ, there ex-
ists a unique element gi ∈ G such that gi v1 = vi Now define a set S by,
29
Definition 2.2.10.
A path of length r from vertex x to vertex y in a graph is a sequence
of r + 1 distinct vertices starting with x and ending with y such that
consecutive vertices are adjacent.
Definition 2.2.11.
A graph Γ is connected if there is a path between any two vertices
of Γ.
Theorem 2.2.12.
The Cayley graph Cay(G, S) is connected if and only if S is a gen-
erating set for G.
Exercise 2.2.13.
Consider the group G = Z5 , with connection set S = {2, 3}.Since
0 + 2−1 = 3, 0 + 3−1 = 2, 1 + 3−1 = 3, 1 + 4−1 = 2, 2 + 4−1 = 3.
Below is the graph ,Cay(Z5 ,{2, 3}).
Figure 2.5
30
Notice that the graph is connected, since S is a generating set for G.
Definition 2.3.1.
A group G admits graphical regular representation if the automor-
phism of Cayley graph is isomorphic to G.
Proposition 2.3.2.
Let Cay(G, S) be a Cayley graph for G defined on the connection
set S. Suppose that ϕ is an automorphism of the group G that fixes
S set-wise. Then, ϕ regarded as a permutation of the vertices of
Cay(G, S) fixes the vertex corresponding to the identity element of
G.
31
Proof.
Let ϕ be a group automorphism. Then ϕ must fix the identity ele-
ment. Let us show that ϕ is a graph automorphism. Suppose that
v, w are adjacent vertices. Then vw−1 ∈ S. Therefore, ϕ(vw−1 ) ∈ S.
But, ϕ(vw−1 ) = ϕ(v)ϕ(w−1 ). So ϕ(v) and ϕ(w) are adjacent. There-
fore, ϕ preserves adjacency and is a graph automorphism.
32
Let us think for a moment what this theorem officially states. By
theorem, If a group G acts regularly on the vertices of the graph Γ,
then Γ is a Cayley graph for G relative to some inverse closed con-
nection set S, we know that if G acts regularly on a graph Γ, then Γ
is a Cayley graph for G. Therefore, we know that if a graph has an
abelian automorphism group, then this abelian group has a graphi-
cal regular representation. Furthermore, we know that this can only
happen when G is an abelian 2-group. Thus, the only abelian groups
that have a graphical regular representation are abelian 2-groups.
33
= deg− (a) = n. Its proof is as follows: Let a ∈ G. Then
g1−1 a,g2−1 a,...gn−1 a n a are n distinct elements in G(by closure),
since suppose that
gi−1 a = gj−1 a
⇒ gi−1 = gj−1
⇒ gi = gj .
34
D(G2 , S2 ).
1. Any problem for which graphs are used as a model and the
use of edges is being optimized provides a natural setting for
Cayley [Link] example, suppose that we are to construct
a network for which the number of direct links we may use is
restricted, but we want to maximize the probability that the
network remains connected after some links or vertices of the
network are deleted. Then there is a strong tendency for the
graph to be either vertex-transitive or close to [Link]
Cayley graphs in particular the K-dimensional cube QK have
been extensively studied by researchers working with networks.
35
n bits could change, and slight misalignments between reading
elements could cause high levels of error since flipping a bit will
increase or decrease the value by a power of two. For example,
an error flipping the MSB of an 8-bit word will change the value
by 27 .
Gray codes can be represented by the direct product (C2 )n .The
difference between Gray code and normal binary code is the
ordering of the elements. In gray code the greater than or equal
to relation is defined as follows:
For a, b ∈ (C2 )n , a ≥ b if and only if a → b. The fact that
((C2 )n , ≥) is a totally ordered set follows from that we can
always find a Hamiltonian path in ((C2 )n , S)(since every two
elements in the path are comparable). Thus ((C2 )n , ≥) is a
well ordered set by choosing the starting vertex(element) of the
Hamiltonian path as the least element.
36
Chapter 3
AUTOMORPHISM GROUP OF
GRAPHS
Definition 3.0.1.
A graph automorphism is an isomorphism from a graph to itself. In
other words, an automorphism of a graph G is a bijection
ϕ : V (G) −→ V (G) such that uv ∈ E(G) if and only if ϕ(u)ϕ(v) ∈
E(G).
37
Since σ is a bijection, it has an inverse. By definition, this is an
automorphism.
Figure 3.1
38
exists ϕ ∈ Aut(G) such that ϕ (u) = v. We claim that this is an
equivalence relation.
1. Reflexive: Note that e(u) = ufor all u ∈ V (G), where eis the
identity automorphism.
Proposition 3.0.2.
Let G be a graph.
39
Proof.
40
that Aut(G) = Aut(G).
Theorem 3.1.1.
Proof.
41
mapping τ (vi ) = vn−1−i and τ (vn−1−i ) = vi for i = 0, 1, ..., n2 − 1.
If n is odd, then consider the mapping τ (v0 ) = v0 , τ (vi ) = vn −i,
and τ (vn − i) = vi for i = 0, 1, ..., n−1
2 . In both cases, vi vi+1
Theorem 3.1.2.
For the complete bipartite graph, Kn,m , if n > m, then
Aut(Kn,m ) ∼
= Sn × Sm .
Proof.
By above theorem, Aut(Kn ) ∼
= Sn . By proposition 3.0.2 Aut(K n ) ∼
=
Sn . Thus, any automorphism of the form (xi , xj 4 ) or of the form
(yk , yl ) is in Aut(Kn,m ). Thus, Sn × Sm is a subgroup of Aut(Kn,m ).
Now suppose that n > m. Since deg(xi ) = m and deg(yj ) = n,it
follows from the proof of proposition 3.0.2 that there is no automor-
42
phism ϕ such that ϕ(xi ) = yj . Thus, Aut(Kn,m ) ∼
= Sn × Sm .
Definition 3.1.3.
The double star is the tree with two adjacent non-leaf vertices x and
y such that x1 , x2 , ..., xn are the leafs adjacent to x and y1 , y2 , ..., ym
are the leafs adjacent to y. This graph is denoted Sn,m .
Example,
The double star S5,4 is,
Figure 3.2
43
Bibliography
44
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
BILINEAR FORMS
DON BOSCO ARTS & SCIENCE COLLEGE
ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
BILINEAR FORMS
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1909)
ACKNOWLEDGEMENT
SWATHI SUDHAKARAN
CONTENTS
1. INTRODUCTION .......................................................... 01
6. CONCLUSION ................................................................. 42
7. BIBLIOGRAPHY ........................................................... 43
INTRODUCTION
Inner products are maps which are not completely linear, in the
sense that they are linear in its first argument and conjugate linear in
the second argument. So naturally a question arises is there any sim-
ilar map which includes inner products as well in its collection and
can be considered as a generalization of inner [Link] bilin-
ear form include certain types of inner products in its collection and
these are linear in both of its [Link] form has established
an important role through out many of the topics of mathematics
such as Linear Algebra and Coding [Link] forms also showed
importance in different fields like Engineering,Biology,Economics This
made me to read and study extra in bilinear forms.
1
The main aim of this project is to provide an introduction to
bilinear forms and some of its basis properties and characterisation
.
2
CHAPTER 1
PRELIMINARY RESULTS
Let V be a non empty set with two operation addition and scalar
multiplication for each α, β ∈ V and F be a field of scalars such that
α + β ∈ V ∀ α, β ∈ V
α ∈ V, a ∈ F → aα ∈ V
Then V is called a vector space over the field F, if and only if the
following axioms are satisfied ∀ α, β ∈ V
1) Commutativity: α + β = β + α
2)Associativity: α + (β + γ) = (α + β) + γ
α+0=0+α = 0
α + (−α) = 0 = (−α) + α
3
The element (-α) in V is called the additive inverse of α in V
5) k(α + β) = kα + kβ, k ∈ F
6) (k1 + k2 )α = k1 α + k2 α , k1 and k2 ∈ F
Basis(1.3)
Dimension(1.4)
4
Linear transformation(1.6)
Let V and W be two vector space over the field F . A linear trans-
formation from V into W is a function T from V into W such that
, T(cx+y)= cT(x)+T(y) ∀ x, y ∈ V and c ∈ F
Let U(F) and V(F) be two vector spaces over the same field F. Then
a mapping T: U → V is called an isomorphism from U to V ,if
Transpose of a matrix(1.8)
h i
Let A = aij then the matrix obtained by interchanging rows
m×n
and columns of A is called the transpose of A and is denoted by At
5
of V ,
V ∗ = L(V,F)
The basis B ∗ = {f1 , f2 , ...fn } for V ∗ is called the dual basis of
B = {a1 , a2 , ..., an } the basis for V.
V + W = {α + β : α ∈ V, β ∈ W}
Direct sum(1.11)
Group(1.12)
6
XX −1 = X −1 X = e
Field(1.13)
a) k1 + k2 = k2 + k1 ∀k1 , k2 ∈ K
b) k1 + (k2 + k3 ) = (k1 + k2 ) + k3 , ∀k1 , k2 , k3 ∈ K
k+0 = 0+k ,∀ k ∈ K
k+(-k) = 0 = (-k)+k
7
k −1 · k = k ·k −1
k1 · (k2 + k3 ) = k1 · k2 + k1 .k3 ∀ k1 , k2 , k3 ∈ K
8
CHAPTER 2
BILINEAR FORMS
Definition(2.1)
Results
9
= [af1 (α1 , β)+bf1 (α2 , β)]+[af2 (α1 , β)+bf2 (α2 , β)]
(since f1 and f2 are bilinear )
= a[f1 (α1 , β)+f2 (α1 , β)]+b[f1 (α2 , β)+f2 (α2 , β)]
= a[(f1 + f2 )(α1 , β)] + b[(f1 + f2 )(α2 , β)]
Also
(f1 + f2 )(α, aβ1 + bβ2 ) = f1 (α, aβ1 + bβ2 ) + f2 (α, aβ1 + bβ2 )
= [af1 (α, β1 )+bf1 (α, β2 )]+[af2 (α, β1 )+bf2 (α, β2 )]
(since f1 and f2 are bilinear )
= a[f1 (α, β1 )+f2 (α, β1 )]+b[f1 (α, β2 )+f2 (α, β2 )]
= a[(f1 + f2 )(α, β1 )] + b[(f1 + f2 )(α, β2 )]
=⇒ f1 + f2 is a bilinear form on V
(cf)(α, β) = cf (α, β) ∀ α, β ∈ V
Thus,
10
Then cf is a bilinear [Link] have g is also a bilinear [Link]
fore cf+g is a bilinear form.
That is any linear combination of bilinear forms on V is again a
bilinear form.
NOTE
The set of all bilinear forms on V is closed under addition and scalar
multiplication.[follows from the above result]
The set of all bilinear forms on V(F) is generally denoted by L(V,V,F)
0̂(α, β) = 0 ∈ F ∀ α, β ∈ V
Now,
0̂(aα1 + bα2 , β)= 0 = 0+0
= a 0+b 0
= a 0̂(α1 , β) + b 0̂(α2 , β)
Also
0̂(α, aβ1 + bβ2 ) = 0 = 0+0
= a 0+b 0
= a 0̂(α, β1 )+ b 0̂(α, β2 )
∀a, b ∈ F and α, β, α1 , β1 , α2 , β2 ∈ V
11
=⇒ 0̂ is a bilinear form
Where ,
We have,
-f (aα1 + bα2 , β)= - [f(aα1 + bα2 , β)]
= - [af(α1 , β) + bf (α2 , β)]
= -af (α1 , β)- bf (α2 , β)
= a(-f) (α1 , β)+b(-f)(α2 , β)
Similarly,
=⇒ -f is a bilinear form on V
12
(cf)(α, β) = cf (α, β) ∀ (α, β) ∈ V× V and a ∈ F
Examples
13
Solution :
We have ,
g(aα1 + bα2 , β) = f [T (aα1 + bα2 ), Tβ ]
= f(aTα1 +b Tα2 , Tβ )
= af(Tα1 , T β)+bf(Tα2 , T β)
= ag(α1 , β)+bg(α2 , β)
Also ,
g(α, aβ1 + bβ2 )= f[Tα , T (aβ1 + bβ2 )]
= f(Tα, aT β1 + bT β2 )
= af(Tα , Tβ1 ) + bf (Tα , Tβ2 )
= ag(α, β1 )+bg(α, β2 )
=⇒ g is a biinear form on V
We have,
f(aα1 + bα2 , β) = L1 (aα1 + bα2 )L2 (β)
= [a L1 (α1 ) + bL1 (α2 )]L2 (β)
= a L1 (α1 )L2 (β) + bL1 (α2 )L2 (β)
= a f(α1 , β) + bf (α2 , β)
Also ,
f(α, aβ1 + bβ2 ) = L1 (α)L2 (aβ1 + bβ2 )
14
= L1 (α)[(aL2 (β1 ) + bL2 (β2 )]
= a L1 (α)L2 (β1 ) + bL1 (α)L2 (β2 )
= a f(α, β1 ) + bf (α, β2 )
=⇒ f is a bilinear form on V
15
4) Let V be a vector space of all ordered n tuples over the field F
, that is V = Vn (F) . If α = (a1 , a2 , ...an ) and β = (b1 , b2 ...bn ) be
any two elements of V and let f be a scalar valued function on V,
defined by ,
f(α, β) = a1 b1 + a2 b2 + ... + an bn
solution:
Let
α = (a1 , a2 , ..., an )
β = (b1 , b2 , ..., bn )
γ = (c1 , c2 , ..., cn )
Then,
k1 α + k2 γ = k1 (a1 , a2 , ...an ) + k2 (c1 , c2 ...cn )
= (k1 a1 , k1 a2 , ..., k1 an ) + (k2 c1 , k2 c2 , ..., k2 cn )
= (k1 a1 + k2 c1 , k1 a2 + k2 c2 , ..., k1 an + k2 cn )
k1 β + k2 γ = k1 (b1 , b2 , ...bn ) + k2 (c1 , c2 ...cn )
= (k1 b1 , k1 b2 , ..., k1 bn ) + (k2 c1 , k2 c2 , ..., k2 cn )
= (k1 b1 + k2 c1 , k1 b2 + k2 c2 , ...k1 bn + k2 cn )
Thus we have,
16
=⇒ f (k1 α + k2 γ, β) = k1 f (α, β) + k2 f (γ, β)
Also,
f(α,k1 β +k2 γ) = [(a1 , a2 , ..., an )(k1 b1 +k2 c1 , k1 b2 +k2 c2 , ..., k1 bn +k2 cn )]
= a1 (k1 b1 +k2 c1 )+a2 (k1 b2 +k2 c2 )+...+an (k1 bn +k2 cn )
= k1 (a1 b1 +a2 b2 +...+an bn )+k2 (a1 c1 +a2 c2 +...+an cn )
= k1 f (α, β) + k2 f (α, γ)
=⇒ f (α, k1 β + k2 γ) = k1 f (α, β) + k2 f (α, γ)
=⇒ f is a bilinear form on V
Exercise
Solution:
Let α = (x1 , x2 )
β = (y1 , y2 )
γ = (z1 , z2 )
Then,
aα + bβ = a(x1 , x2 ) + b(y1 , y2 )
= (ax1 , ax2 ) + (by1 , by2 )
= (ax1 + by1 , ax2 + by2 )
17
f(β, γ) = f [(y1 , y2 ), (z1 , z2 )]
= y1 z2 − y2 z1
f(γ, α) = f [(z1 , z2 ), (x1 , x2 )]
= z1 x2 − z2 x1
f(γ, β) = f [(z1 , z2 ), (y1 , y2 )]
= z1 y2 − z2 y1
18
af(α, γ) + bf (β, γ) = a(x1 − z1 )2 + ax2 z2 + b(y1 − z1 )2 + by2 z2
= a(x1 − z1 )2 + b (y1 − z1 )2 + (ax2 +by2 )z2
That is f(aα + bβ, γ) ̸= af (α, γ) + bf (β, γ)
=⇒ f is not a bilinear form on R2
Definition(2.2)
x
1
x2
Therefore coordinate matrix of α = X =
..
.
xn
h i
t
Therefore X = x1 , x2 , . . . , xn
Pn
β= j=1 yj αj
y
1
y2
There fore coordinate matrix of β = Y =
..
.
yn
19
Now,
Pn Pn
= i=1 j=1 xi yj f (αi , αj )
y
1
ih i y2
h
= x1 , x2 , . . . , xn ai,j
..
.
yn
= X t AY
h it h i
= α A β
B B
Theorem(2.3)
Let V be a finite dimensional vector space over the field F. for each
ordered basis B of V , the function which associates with each bilin-
ear form on V it’s matrix in the ordered basis B is an isomorphism
of the space L(V,V,F) onto the space of n × n matrices over the
field F .
Proof:
Let S be the vector space of all n × n matrices over the field F and
let ϕ be a function from L(V,V,F) into S
h i
ϕ(f ) = f ∀f ∈ L(V,V,F)
B
20
Let B = { α1 , α2 , ..., αn } be the basis of V .
Then for a,b ∈ F and f,g ∈ L(V,V,F) we have ,
h i
ϕ(af + bg) = af + bg
B
Also,
(af+bg) (αi , αj ) = (af)(αi , αj ) + (bg)(αi , αj )
= af(αi , αj ) + bg(αi , αj )
(i = 1,2, ...,n ; j = 1,2,...,n)
h i h i h i
=⇒ af + bg = a f + b g
B B B
=⇒ f = g
=⇒ ϕ is one-one
Next to prove that ϕ is onto
h i
Let A = ai,j be any n × n matrix over F , then there exist a linear
h i
form f on V such that f =A
B
That is ϕ(f) = A
=⇒ ϕ is onto
Hence ϕ is an isomorphism of L(V,V,F) onto the space of all n × n
21
matrices over F .
Corollory(2.4)
Proof:
The dual basis defined by the fact that Li (α) is the ith coordinates
of α in the ordered basis B . Also fij defined by
fij (α, β) = Li (α)Lj (β) .
We have to prove that this is a bilinear form .
fi,j (aα1 + bα2 , β) = Li (aα1 + bα2 )Lj (β)
= [aLi (α1 ) + bLi (α2 )]Lj (β)
= a Li (α1 )Lj (β) + bLi (α2 )Lj (β)
= a fi,j (α1 , β) + bfi,j (α2 , β)
Also
fi,j (α, aβ1 + bβ2 ) = Li (α)Lj (aβ1 + bβ2 )
= Li (α)[aLj (β1 ) + bLj (β2 )]
= a Li (α)Lj (β1 ) + bLi (α)Lj (β2 )
= a fi,j (α, β1 ) + bfi,j (α, β2 )
=⇒ f is a bilinear form .
If α = x1 α1 + x2 α2 + · · · + xn αn
22
β = y1 α 1 + y2 α 2 + · · · + yn α n
Then fi,j (α, β) = xi yj
Let f be any bilinear form V and let A be the matrix of f in the
ordered basis B
Then,
P
f(α, β) = i,j Ai,J xi yj
P
=⇒ f = i,j Ai,J fi,j
Therefore n2 forms fij comprise a basis for L(V,V,F)
That is dim( L(V,V,F) = n2
Theorem(2.5)
Example
23
Solution:
h i h i
let f = ai,j
B1 B1
Therefore
h i a1,1 a1,2 1 0
f = =
B1 a2,1 a2,2 0 1
h i h i
let f = bi,j
B2 B2
There fore
h i 2 0
f =
B2 0 2
24
Let T be a linear operator on V such that T(αi ) = βi
h i
i = 1, 2, . . . and Cij be the matrix of T relative to basis B .
Now,
T(αi ) = βi [by definition]
∴ T(1,0) = (1,-1) =(1,0) + (-1) (0,1)
Or
T(α1 ) = α1 − α2
T(0,1) = (1,1) =(1,0) + (0,1)
Or
T(α2 ) = α1 − α2
Then,
1 1
C=
−1 1
1 −1
=⇒ C t =
1 1
t
h i 1 −1 1 0 1 1
=⇒ C f C=
B1 1 1 0 1 −1 1
2 0
=
0 2
h i
= f
B2
25
h i h i
t
=⇒ f =C f C
B2 B1
Definition(2.6)
Definition(2.7)
26
CHAPTER 3
Definition(3.1.1)
Result
At = A
27
Proof : Let the matrices of α, β with respect to a certain basis B
h i
be X and Y and A = f
B
Now,
h i
t
f(α, β) = X f Y
B
= X t AY
h i
t
f(β, α) = Y f X
B
=Y t AX
Now, f will be a symmetric bilinear form if and only if f(α, β) =
f (β, α)
∀ α, β ∈ V Or X t AY = Y t AX ∀ matrices X and Y .
Now X t AY is a 1 × 1 matrix and as such it is equal to its transpose
.
t
X t AY = Y t AX
t
⇒ Y t At (X t ) = Y t AX
⇒ Y t At X = Y t AX
t
(since (X t ) = X)
⇒ At = A
That is A is symmetric
Hence bilinear form will be symmetric if and only if its matrix is
symmetric .
28
Theorem(3.1.2)
Further extension
1 1
f(α, β) = 4 q(α + β) - 4 q(α − β)
29
From above theorem we have ,
2f(α, β) = q(α + β) − q(α) − q(β).......(1)
Also
q(α − β) = f (α − β, α − β)
= f(α, α − β) − f (β, α − β)
= f(α.α) − f (α, β) − f (β, α) + f (β, β)
= q(α) + q(β) − 2f (α, β)
(since f is symmetric)
2 f (α, β) = q(α) + q(β) − q(α − β) .......(2)
Adding .......(1) and ......(2) we get,
4 f (α, β) = q(α + β) − q(α − β)
1 1
⇒ f (α, β) = 4 q(α + β) - 4 q(α − β)
Theorem (3.1.3)
30
for each α ∈ V
Then q(α) = 0
Thus by polarization identity ,
We get f(α, β) = 0 ∀ α, β ∈ V
Thus f = 0 which controdicts our assumption and hence there must
exist a vector α ∈ V such that f(α, α) = q(α) ̸= 0
Let U be the one dimensional subspace of V which is spanned by
vectors α and W be the set of all vectors β such that f(α, β) = 0
Then W is a subspace of V
claim: V = U ⊕ W
Let δ ∈ U ∩ W
⇒ δ ∈ U and δ ∈ W
δ ∈ U ⇒ δ = kα for some scalar k
Also,
δ ∈ W ⇒ 0 = f (α, δ) = f (α, kα) = kf (α, α)
But f(α, α) ̸= 0
Therefore,
k =0 and so δ = kα=0
⇒ U ∩ W = {0}
2) To show that V = U+W
Let γ ∈ V
31
f (γ,α)
Put β = γ − f (α,α) α
We have,
f (γ,α)
f(α, β) = f (α, γ − f (α,α) α)
f (γ,α)
= f(α, γ) − f (α,α) f (α, α)
= f(α, γ) − f (γ, α)
=0
Hence β ∈ W
f (γ,α)
Thus γ = f (α,α) α +β
That is γ ∈ U+W
Thus by (1) ans (2) we get V = U ⊕ W
⇒ dimW = dimV − dimU
= n -1
Let h be the restriction of f from V to W . It is bilinear form on W
and dim W = n-1 < n
Thus by mathematical induction we assume there exist a basis {α2 , α3 , ...αn }
of W such that f(αi , αj ) = 0 , i ̸= j (i≥ 2,j≥ 2)
Again {α1 } is the basis of U and we have V = U ⊕ W
Therefore it follows that {α1 , α2 , ...αn } is the basis of V such that
f(αi , αj ) = 0 , i ̸= j
That is the matrix of f with respect to the basis B is a diagnal ma-
trix.
Corollory(3.1.4)
32
metric matricx over F then there is an invertible n×n matrix C over
F such that C t AC is diagonal
Proof:
Let V be a finite dimensional vector space and let X = {α1 , α2 , ..., αn }
be an ordered basis of V
h i
Then f = A , where f is bilinear form on V
X
33
3.2 SKEW SYMMETRIC BILINEAR FORMS
Definition(3.2.1)
f(α, β) = −f (β, α) ∀ α, β ∈ V
Theorem(3.2.2)
34
= - 1/2 [ f(α, β) − f (β, α)]
= -f2 (α, β)
⇒ f2 is skew symmetric bilinear form
From (1) and (2) we have
f1 (α, β) + f2 (α, β) = f (α, β)
⇒ (f1 + f2 )(α, β) = f (α, β) ∀ α, β ∈V
⇒ f1 + f2 = f
Uniqueness:
Further suppose that f = f3 + f4 where f3 is symmetric and f4 is
skew symmetric
We have,
Also,
35
Substracting (4) from (3) we also get ,
Theorem (3.2.3)
36
= Y t At X
The bilinear form f will skew symmetric if and only if Y t At X = -
Y t At X forall column matrices X and Y
That is At = -A
That is A is skew symmetric
37
CHAPTER 4
GROUP PRESERVING
BILINEAR FORMS
Definition(4.1)
Remarks
38
Theorem(4.2)
f(Tα , Tβ ) = f (α, β)
f(Sα , Sβ ) = f (α, β)
Closure property:
Associative:
For each T,S,P ∈ G we have,
39
Hence it is associative.
Identity :
Inverse:
Let T ∈ G so that,
f(T α, T β) = f(α, β), ∀α, β ∈ V
We have to show that T is invertible and T −1 ∈ G
Since V is finite dimensional it will be sufficient to show that T is
nonsingular
That is
Tα = 0
⇒α=0
= f(0,T β )
=0
40
Now f(α, β) = 0, ∀β ∈ V and f is non degenerate .That is for all non
zero α there exist β ∈ V such that f(α, β) ̸= 0
Therefore
α=0
Thus
Tα = 0
⇒α=0
⇒ T is non singular
⇒ T is invertible and T −1 be inverse of T
= f(I α, Iβ)
= f(α, β)
Which shows that T −1 also preserves f.
That is T −1 ∈ G
Thus inverse of each element of G exists
Hence G is a group.
41
CONCLUSION
42
REFERENCE
43
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
FUZZY ALGEBRA
DON BOSCO ARTS & SCIENCE COLLEGE
ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
FUZZY ALGEBRA
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1904)
ACKNOWLEDGEMENT
ANJU JAYARAJ
CONTENTS
1. INTRODUCTION .......................................................... 01
2. PRELIMINARIES .......................................................... 03
4. FUZZY GROUPS............................................................. 13
4.1 Normal fuzzy subgroups and Cosets ............................ 23
6. CONCLUSION ................................................................. 43
7. BIBLIOGRAPHY ........................................................... 44
INTRODUCTION
The concept of sets and functions to represent problem were defined
in the 20th century. This way of representing problems is more
rigid. In many circumstances the solutions using this concepts are
meaningless. This difficulty was overcome by the introduction of
fuzzy concept.
In 1965, L.A Zadeh mathematically formulated the fuzzy subset
concept. He introduced the notion of a fuzzy subset of a set as a
method for representing uncertainity. He defined the fuzzy subset of
a non-empty set as a collection of objects with grade of membership
in a continuum, with each object being assigned a value between
0 and 1 by a membership function. Fuzzy set theory was guided
by the assumption that classical sets were not natural, appropriate
or useful notion in describing the real life problems, because every
object encountered in this real physical world carries some degree
of fuzziness. Further the concept of grade of membership is not a
probabilistic concept.
As know to us, a relation is a subset of the Cartesian product of
two sets. A relation is fuzzified while a subset is fuzzified. Infact
whether two objects have a relation is not always easy to determine.
For example, the relation ”greater than” on the set of real numbers
is a crisp one because we can determine the order relation of any
two real numbers without vagueness. However the relation ”much
greater than” is a fuzzy one because it is impossible for us to figure
1
out the exact minimum difference of two numbers satisfying this
relation. In real world problems, there exists a lot of such relations.
For example, ”being friend of” and ”being confident in” between
some people. These relations will be termed as fuzzy relations.
After the concept of fuzzy sets first introduced by Zadeh, the
theory of fuzzy mathematics has been widely used in Mathematics
and many more areas.
In 1971, Rosenfeld introduced the concept of fuzzy subgroup,
which spreads the area of fuzzy algebra. Fuzzy algebra plays an
important role in the field of computer, such as fuzzy codes, fuzzy fi-
nite state machines, regular fuzzy languages and codes and so on, so
it is necessary for us to do further research on fuzzy algebra theory.
In 1981, W.J Liu introduced the concept of fuzzy ideals of a ring.
It was followed by the studies of Mukherjee and Sen who defined
and examined fuzzy prime ideals of a ring. Fuzzy ideals were fur-
ther investigated by Malik and Mordeson and they gave complete
characterization of fuzzy prime ideals of an arbitrary ring.
2
PRELIMINARIES
Definition 1.0.1
Let X be a nonempty set. A fuzzy set A in X is characterised by
membership function µA : X → [0, 1] and µA (x) is interpreted as a
degree of membership of element x in fuzzy set A, for each x ∈ X.
It is clear that A is completely determined by the set of tuple
Proposition 1.0.2
Let X be a non empty set. Then there exists an isomorphism be-
tween (P (X), ∩, ∪c ) and (Ch(X), ∨, ∧,c ), where P (X) is the power-
set of X and Ch(X) is the set of two valued characteristic function
on X. - It follows from the above proposition that every subset of
X may be regarded as a mapping from X to {0, 1}
3
In this sense an ordinary set is also a fuzzy set whose member-
ship function is just its characteristic function. Accordingly we shall
identify the membership degree A(x) with the value χA (x) of the
characteristic function χA at x when A is an ordinary set.
For the two extreme cases ∅ and X, the membership functions
are defined by
Example 1.0.3
A realter wants to classify the house he offer to his client. One indi-
cator of comfort of these house is the number of bedrooms in it. Let
X = {1, 2, . . . , 10} be the set of available types of houses described
by x = the number of bedrooms in house. Then the fuzzy set com-
fortable type of house for a four person family may be described as
A = {(1, 0.2), (2, 0.5)(3, 0.8)(4, 1)(5, 0.7)(6, 0.3)}.
In the set of ordered pair, the first element denote element and
second element denote the degree of membership.
4
If A ̸= ∅, A ⊆ B and ∃x ∈ X such that A(x) < B(x), then we
say that A is properly contained in B, denoted by A ⊂ B, where
A, B ∈ F (X).
Proposition 1.0.4
∀A, B, C, D ∈ F (X)
2. A ⊆ B and C ⊆ D ⇒ A ∪ C ⊆ B ∪ D and A ∩ C ⊆ B ∩ D
3. A ⊆ B ⇒ B c ⊆ Ac
1. idempotency : A ∪ A = A, A ∩ A = A
2. commutativity : A ∪ B = B ∪ A, A ∩ B = B ∩ A
4. absorption law : A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A
5. distributivity : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
7. involution : (Ac )c = A
5
8. De- Morgan’s law : (A ∪ B)c = Ac ∩ B c , (A ∩ B)c = Ac ∪ B c
• The number
W
x∈X A(x) is called the height of A, hgt(A).
• The number
V
x∈X A(x) is referred to as the plinth of A, denoted
by plt(A).
Definition 1.0.5
Let A be a fuzzy set on X. For α ∈ [0, 1], the α cut Aα of A is
defined as Aα = {x | A(x) ≥ α}, and the strong α cut Âα of A is
defined as Âα = {x | A(x) > α}
1. A ∩ B ⊆ A and A ⊆ A ∪ B
6
Chapter 1
FUZZY RELATION
Definition 2.0.1
Let X and Y be two non-empty sets. A mapping R : X× Y →
[0, 1]] is called a fuzzy(binary) relation from X to Y . For (x, y) ∈
X × Y, R(x, y) ∈ [0, 1] is referred to as the degree of relationship
between x and y.
Particularly, a fuzzy relation from X to X is called a fuzzy(binary)
relation on X
By definition, a fuzzy relation R is a fuzzy set on X × Y , i.e.,
R ∈ F (X × Y )
Definition 2.0.2
Let R be a fuzzy relation from X to Y . The R-afterset xR of x(x ∈
X) is a fuzzy set on Y defined by, ∀y ∈ Y, (xR)(y) = R(x, y).
The R-foreset Ry of y(y ∈ Y ) is a fuzzy set on X defined by,
∀x ∈ X, (Ry)(x) = R(x, y)
Since fuzzy relations are fuzzy sets, they have the same set-theoretic
operations as fuzzy sets.
Let R and S be fuzzy relations from X to Y.R is contained in S,
denoted R ⊆ S if and only if ∀(x, y) ∈ X × Y, R(x, y) ≤ S(x, y); R is
equal to S, denoted R = S, if and only if ∀(x, y) ∈ X × Y, R(x, y) =
7
S(x, y). Clearly, R = S if and only if R ⊆ S and S ⊆ R The union
R ∪ S ∈ F (X × Y ) of R and S is defined by, ∀(x, y) ∈ X × Y ,
!
[ _
Ri (x, y) = Ri (x, y)
i∈I i∈I
T T
and i∈I Ri is defined by ∀(x, y) ∈ X × Y, i∈I (Ri ) (x, y) =
∧i∈i Ri (x, y)
8
Proposition 2.0.8 (R ∪ S)−1 = R−1 ∪ S −1
c
Proposition 2.0.10 (Rc )−1 = R−1
A fuzzy relation also has the concept of (strong) α cut. The crisp
relation, Rα = {(x, y) | R(x, y) ≥ α} for α ∈ [0, 1] will be called the
α-cut relation of R. Rα = {(x, y) | R(x, y) > α} for α ∈ [0, 1] will
be called the strong α-cut relation of R.
Fuzzy Equivalence
Definition 2.1.1
If R(x, x) = 1, ∀x ∈ X, then R is called a reflexive(fuzzy) relation.
Definition 2.1.2
R is reflexive if and only if ∀α ∈ [0, 1], Rα is reflexive.
Proof. If R is reflexive, then ∀α ∈ [0, 1], R(x, x) = 1 ≥ α. Hence
(x, x) ∈ Rα . Thus Rα is reflexive.
Conversely, assume that ∀α ∈ [0, 1], Rα is reflexive.
Particularly, R1 is reflexive.
Hence ∀x ∈ X, (x, x) ∈ R1 or R(x, x) = 1
It follows from that R is reflexive if and only if R1 (1-cut relation
of R )is reflexive.
9
Definition 2.1.3
If ∀x, y ∈ X, R(x, y) = R(y, x), then R is called a symmetric( fuzzy)
relation.
Obviously, R is symmetric if and only if R = R−1
Definition 2.1.3
R is symmetric if and only if ∀α ∈ [0, 1], Rα is a symmetric relation.
Definition 2.1.4
Proof. If R is symmetric and (x, y) ∈ Rα , then R(y, x) = R(x, y) ≥
α.
Hence (y, x) ∈ Rα , which proves the symmetry of Rα
Conversely, assume that ∀α ∈ [0, 1], Rα is symmetric.
For any x, y ∈ X, take α = R(x, y). Then (x, y) ∈ Rα and hence
(y, x) ∈ Rα due to the symmetry of Rα
Therefore, R(y, x) ≥ α = R(x, y)
Next, x, y ∈ Rα and hence (y, x) ∈ Rα implies R(x, y) ≥ α and
R(y, x) ≥ α. We can take R(y, x) = α so that R(x, y) ≥ R(y, x).
Combining the two inequalities yields, R(x, y) = R(y, x)
Definition 2.1.5
If R ⊇ R2 , then R is said to be a transitive(fuzzy)relation
Definition 2.1.6
R is transitive if and only if ∀x, y, z ∈ X, R(x, z) ≥ R(x, y)∧ R(y, z)
Proof.
10
R is transitive ⇔ R ⊇ R2
Definition 2.1.7
R is transitive if and only if ∀α ∈ [0, 1], Rα is transitive.
Proof. Suppose that R is transitive. Let (x, y), (y, z) ∈ Rα , for
any fixed α ∈ [0, 1]. It follows that R(x, y) ≥ α and R(y, z) ≥ α.
Then,
11
Let R be a fuzzy equivalence relation on X. A fuzzy set [a]R for
a ∈ X defined by;
.Since R is transitive.
Similarly, [b]R (x) = R(b, x) ≥ R(b, a) ∧ R(a, x) = R(a, x) =
[a]R (x).
We have [b]R (x) ≥ [a]R (x)
Consequently [a]R = [b]R .
12
Chapter 2
FUZZY GROUPS
Definition 3.0.11
Definition 4.0.11. Let G be a group. A fuzzy subset A on G is called
a fuzzy subgroup of G if it satisfies the following conditions:
Definition 3.0.12
Let A be a fuzzy subset of a set S. For t ∈ [0, 1], the set
At = {x ∈ S | A(x) ≥ t}
1. A(x) ≤ A(e)
integer.
A(x)
13
−1 −1
≥ A x−1
2. A(x) = A x
A(x)
Therefore, A x−1 = A(x).
A xk+1 ≥ A(x) ∧ A xk
= A(x)
A xy −1 ≥ A(x) ∧ A(y)
14
A xy −1 ≥ A(x) ∧ A y −1
= A(x) ∧ A(y)
i.e.,
A(x) ≤ A(e)
i.e.,
A x−1 ≥ A(x)
−1 −1
≥ A(x) ∧ A y −1 ≥ A(x) ∧ A(y)
A(xy) = A x y
Therefore,
A is a fuzzy subgroup of G.
15
Proposition 3.0.16
Let G be a group and A be a fuzzy subgroup of G. Then the level
subset At , for t ∈ [0, 1], t ≤ A(e), is a subgroup of G, where e is the
identity of G.
Proof. We have,
At = {x ∈ G | A(x) ≥ t}
Since A(e) ≥ t, e ∈ At
Clearly, At ̸= ∅
Let x, y ∈ At . Then A(x) ≥ t and A(y) ≥ t
Since A is a fuzzy subgroup of G,
i.e.,
A(xy) ≥ t
Hence xy ∈ At
Again x ∈ At ⇒ A(x) ≥ t
Since A is a fuzzy subgroup,
A x−1 ≥ A(x)
16
x−1 ∈ At
Therefore, At is a subgroup of G
Proposition 3.0.17
Proposition 4.0.17. Let G be a group and A be a fuzzy subset of G
such that At is a subgroup of G for all t ∈ [0, 1], t ≤ A(e), then A is
a fuzzy subgroup of G.
Proof. Assume At is a subgroup of G for all t ∈ [0, 1], t ≤ A(e).
Let x, y ∈ G and let A(x) = t1 and A(y) = t2 . Then, x ∈ At1 and
y ∈ At2
Let us assume that t1 < t2 . Then it follows At2 ⊆ At1 .
So y ∈ At1 .
Thus x, y ∈ At1 and since At1 is a subgroup of G, by hypothesis,
xy ∈ At1 Therefore,
A x−1 ≥ t
And hence,
17
A x−1 ≥ A(x)
Definition 3.0.18
(Level Subgroup) Let G be a group and A be a fuzzy subgroup of G.
The subgroups At , t ∈ [0, 1] and t ≤ A(e), are called level subgroups
of A.
Particularly,
Definition 3.0.19
Let A, B ∈ F (G). Then A ◦ B is defined by:
for any z ∈ G,
_
(A ◦ B)(z) = (A(x) ∧ B(y))
z=xy
18
equivalent statement of a fuzzy subgroup.
Propostion 3.0.20
Let A ∈ F (G). Then A is a fuzzy subgroup of G if and only if
A ◦ A−1 = A
Definition 3.0.21
Let A be a fuzzy subgroup of G, and let f be an epimorphism of G
onto a group G′ . Then f (A) is a fuzzy subgroup of G′ .
Definition 3.0.22
Let f be a homomorphism from a group G to a group G′ , and let B
be a fuzzy subgroup of G′ . Then f −1 (B) is a fuzzy subgroup of G.
Proof. For any x, y ∈ G,
f −1 (B) xy −1 = B f xy −1
= B f (x)f y −1
= B(f (x)) ∧ B f y −1
= f −1 (B)(x) ∧ f −1 (B)(y)
19
Definition 3.0.23
Let A1 , A2 , . . . , An be fuzzy subgroups of G1 , G2 , . . . , Gn respectively.
Then the Cartesian product A1 × A2 × . . . × An is a fuzzy subgroup
of G1 × G2 × . . . × Gn
Proof. Form a tuple for xi , yi ∈ Gi . Since we have,
Then,
n
^
x1 y1−1 , x2 y2−1 , . . . , xn yn−1 Ai xi yi−1
(A1 × A2 × . . . × An ) =
i=1
^n
≥ Ai (xi ) ∧ Ai (yi )
i=1
= (A1 × A2 × . . . × An ) (x1 y1 , x2 y2 ,
Proposition 3.0.24
Let G be a group and A be a fuzzy subgroup of G. Two level
subgroups At1 , At2 (with t1 < t2 )of A are equal if and only if there
20
is no x ∈ G such that t1 < A(x) < t2 .
Proof. Let us consider At1 − At2 . Suppose there exists x ∈ G such
that t1 < A(x) < t2 , then At2 ⊂ At1 , since x belongs to At1 but not
in At2 , which contradicts the hypothesis.
Conversely, let there be no x ∈ G such that t1 < A(x) < t2 . Since
t1 < t2 , we have At2 ⊆ At1
Let x ∈ At1 , then A(x) ≥ t1 , and hence A(x) ≥ t2 , since A(x)
does not lie between t1 and t2 .
Therefore, x ∈ At2
So, At1 ⊆ At2
Thus, At1 = At2
Lemma 3.0.25
Let G be a finite group of order n and A be a fuzzy subgroup of G.
Let
Proposition 3.0.26
Any subgroup H of a group G can be realized as a level subgroup of
some fuzzy subgroup of G.
21
Proposition 3.0.27
Let Ā be the collection of all fuzzy subgroups of group G and B̄ be
the collection of all level subgroups of members of Ā. Then there
is a one to one correspondence between the subgroups of G and the
equivalence classes of level subgroups (under a suitable equivalence
relation on B̄ )
Definition 3.0.28
Let G be a group of prime power order. Then G is cyclic if and only
if there exists a fuzzy subgroup A of G such that for x, y ∈ G,
1. if A(x) = A(y), then < x >=< y > 2. if A(x) > A(y), then
< x >⊂< y >
Proposition 3.0.29
Let G be a cyclic p-group of order pn , where p is a prime. Let A be
a fuzzy subgroup of G then for x, y ∈ G
Definition 3.0.30
Let A and B be two fuzzy subgroups of a group G. Then A and B
are said to be conjugate fuzzy subgroups of G if for some x ∈ G,
A(y) = B x−1 yx , ∀y ∈ G
22
Proposition 3.0.31
If A and B are conjugate fuzzy subgroups of the group G, then
O(A) = O(B)
Definition 3.1.1
Let A be a fuzzy subgroup of a group G. Then for any x, y ∈ G, a
fuzzy middle coset xAy of the group G is defined by,
(xAy)(a) = A x−1 ay −1 , ∀a ∈ G
Proposition 3.1.2
If A is a fuzzy subgroup of a group G, then for any x ∈ G the fuzzy
middle coset xAx−1 of the group G is also a fuzzy subgroup of the
group G
Proposition 3.1.3
Let A be any fuzzy subgroup of a group G and xAx−1 be a fuzzy
23
middle coset of the group G. Then
O xAx−1 = O(A)
for any x ∈ G.
Proof. Let A be a fuzzy subgroup of a group G and x ∈ G. Then
by the above proposition,the fuzzy middle coset xAx−1 is a fuzzy
subgroup of the group G. By the definition of a fuzzy middle coset
of the group G,
∀a ∈ G
Hence for any x ∈ G, A and xAx−1 are conjugate fuzzy subgroups
of the group G as there exists x ∈ G such that
Proposition 3.1.4
Let A be a fuzzy subgroup of a finite group G. Then O(A) divides
O(G).
Proof. Let A be a fuzzy subgroup of a finite group G with e as
its identity element. Clearly,
H = {x ∈ G | A(x) = A(e)}
24
is a subgroup of the group G for H is a t-level subset of the group
G, where t = A(e)
By Lagrange’s theorem,
O(H) | O(G)
O(A) | O(G)
Proposition 3.1.5
Let A and B be any two improper fuzzy subgroups of a group G.
Then A and B are conjugate fuzzy subgroups of the group G if and
only if A = B
Proposition 3.1.6
Let A and B be two fuzzy subsets of an abelian group G. Then
A and B are conjugate fuzzy subsets of the group G if and only if
A = B.
Proof. Let A and B be conjugate fuzzy subsets of the group G.
Then for some x ∈ G, we have
A(a) = B x−1 ax , ∀a ∈ G
= B x−1 xa , ∀a ∈ G
= B(a), ∀a ∈ G
25
Hence A = B.
Conversely if A = B, then for the identity element e of the group
G, we have
A(a) = B e−1 ae , ∀a ∈ G
Proposition 3.1.7
A fuzzy subgroup A of G is called normal if
A(xy) = A(yx)
Proposition 3.1.8
A fuzzy subgroup A of G is normal if and only if
A xyx−1 = A(y)
26
A xyx−1 = A (xy)x−1
= A x−1 (xy)
= A x−1 xy
= A(y)
[Link],
xy = x(yx)x−1
A(xy) = A x(yx)x−1
= A(yx)
i.e., A is normal.
Proposition 3.1.9
A ∈ F (G) is a normal fuzzy subgroup of G if and only if
A ◦ A−1 = A and A ◦ B = B ◦ A
holds for all B ∈ F (G). Proof. For any fuzzy subgroup, A◦A−1 =
A. Take
27
_
(A ◦ B)(z) = A(x) ∧ B(y)
z=xy
_
A zy −1 ∧ B(y)
=
y∈G
_
A y −1 z ∧ B(y)
=
y∈G
_
= A(x) ∧ B(y)
z=yx
_
= B(y) ∧ A(x)
z=yx
= (B ◦ A)(z)
x−1 ◦ A (y)
A(xy) =
= A ◦ x−1 (y)
_
A(s) ∧ x−1 (t)
=
y=st
= A(yx)
Proposition 3.1.10
A ∈ F (G) is a normal fuzzy subgroup of G if and only if At is a
normal subgroup of G for any t ∈ [0, 1], t ≤ A(e)
Proof. A is a subgroup if and only if At is one. For normality,
take x ∈ G and y ∈ At . It follows that A xyx−1 = A(y) ≥ t.
28
Conversely, take x, y ∈ G and t = A(y). Then, t ∈ {A(x) | x ∈ G}
and y ∈
At . Hence xyx−1 ∈ At . Consequently
A xy −1 x ≥ t = A(y)
Definition 3.1.11
Let A be a fuzzy subgroup of G. For every x ∈ G, define xA, Ax ∈
F (G) by; ∀y ∈ G, (xA)(y) = A x−1 y and (Ax)(y) = A yx−1 .
Then xA and Ax are called the left coset and right coset of A with
respect to x respectively. Clearly, xA = Ax holds for any x ∈ G,
if A is a normal fuzzy subgroup of G. In this case, we simply call
xA(= Ax) a coset. Write G/A = {xA | x ∈ G}
Lemma 3.1.12
Let A be two normal fuzzy subgroups of G. Then xA ◦ yA = (xy)A
holds for any two cosets xA, yA ∈ G/A.
Proof. On the one hand, for any z ∈ G
29
_
(xA ◦ yA)(z) = ((xA) (z1 ) ∧ (yA) (z2 ))
z=z1 z2
= A x−1 x ∧ A y −1 x−1 z
= A(e) ∧ A y −1 x−1 z
= A (xy)−1 z
= ((xy)A)(z)
Proposition 3.1.13
Let A be a normal fuzzy subgroup of G. Then
1. (G/A, ◦) is a group
Proof. 1
Clearly, the operation ◦ is associative, A is the identity of G/A and
the inverse of xA is x−1 [Link], (G/A, ◦) is a group.
= xyA∗
= xA∗ yA∗
= f (xA)f (yA)
30
Hence, f is a homomorphism. In order to prove that f is injective,
suppose that xA = yA. Then A x−1 z = A y −1 z for all z ∈ G.
Definition 3.1.14
Let A be a fuzzy subgroup of a group G and x ∈ G. Then the pseudo
fuzzy coset (xA)p is defined by,
Proposition 3.1.15
Let A be a fuzzy subgroup of a group G. Then the pseudo fuzzy
coset (xA)p is a fuzzy subgroup of G, ∀x ∈ G.
Proof. Let A be a fuzzy subgroup of a group G.∀x, y ∈ G,
(aA)p xy −1 = p(a)A xy −1
31
i.e.
^
(aA)p xy −1 ≥ {(aA)p (x), (aA)p (y)} , ∀x, y ∈ G
Proposition 3.1.16
Let A be a normal fuzzy subgroup of G. Define Ā : G/A → [0, 1] by
Ā (xA)−1 = Ā x−1 A
= A x−1
= A(x)
= Ā(xA)
Ā(xAyA) = Ā(xyA)
= A(xy)
≥ A(x) ∧ A(y)
= Ā(xA) ∧ Ā(yA)
32
Ā(xA ◦ yA) = Ā(xyA)
= A(xy)
= A(yx)
= Ā(yxA)
= Ā(yA ◦ xA).
Proposition 3.1.17
Let A be a normal fuzzy subgroup of G and let f be an epimorphism
of G onto a group G. Then f (A) is a normal fuzzy subgroup of G.
Proof. We have, A is a normal fuzzy subgroup of G and f be an
epimorphism of G onto G. Then f (A) is a fuzzy subgroup of G. Let
u, v ∈ G. Then there exists x ∈ G such that f (x) = u since f is
surjective. Hence, we obtain successively
33
_
f (A) uvu−1 =
A(z)
f (z)=uvu−1
_
= A(z)
f (z)=f (x)v(f (x))−1
_
= A(z) (f is a homomorphism )
f (x−1 zx)=v
_
A xyx−1
=
f (y)=v
_
= A(y)
f (y)=v
=f (A)(v)
Proposition 3.1.18
Let f be a homomorphism from G to a group G and let B be a normal
fuzzy subgroup of G. Then f −1 (B) is a normal fuzzy subgroup of G.
Proof. We have, if f is a homomorphism from G to G and B is
a fuzzy subgroup of G, then f −1 (B) is a fuzzy subgroup of G. Now,
let x, y ∈ G. Then
34
f −1 (B)(xy) = B(f (xy))
= B(f (yx))
= f −1 (B)(yx)
Proposition 3.1.19
Let A1 , A2 , . . . , An be normal fuzzy subgroups of G1 , G2 , . . . , Gn re-
spectively. Then the Cartesian product ni=1 Ai is a normal fuzzy
Q
n
! n
!
Y Y
Ai (x1 , x2 , . . . , xn ) (y1 , y2 , . . . , yn ) = Ai (x1 y1 , x2 y2 , . . . , xn yn )
i=1 i=1
n
^
= Ai (xi yi )
i=1
^n
= Ai (yi xi )
i=1
n
!
Y
= Ai (y1 x1 , y2 x2 , . . . , yn xn )
i=1
35
Chapter 3
FUZZY SUBRINGS
In this and next subsection, we assume (R, +, ◦) is a ring. For
convenience, we write xy instead of x ◦ y for x, y ∈ R.
Definition 4.0.1
A ∈ F (R) is called a fuzzy sub ring of R if A satisfies that
Proposition 4.0.2
A ∈ F (R) is a fuzzy sub ring of R if and only if At is a sub ring of
R for every t ∈ [0, 1], t ≤ A(e)
By proposition,
A∗ = {x | A(x) = A(0)}
_
(A + B)(z) = (A(x) ∧ B(y)
x+y=z
_
(A − B)(z) = (A(x) ∧ B(y)
x−y=z
_
(A ◦ B)(z) = (A(x) ∧ B(y)
xy=z
36
Remark 4.0.3
A ∈ F (R) is a fuzzy sub ring of R if and only if A − A ⊆ A and
A◦A⊆A
Proof. Let A be a fuzzy sub ring of R. Since A is a fuzzy group
under addition, A − A ⊆ A. Moreover,
_
∀z ∈ R, A ◦ A(z) = (A(x) ∧ A(y) ≤ A(xy) = A(z)
xy=z
i.e.,
A◦A⊆A
A(x − y) ≥ (A − A)(x − y)
_
= (A(s) ∧ A(t))
s−t=x−y
≥ A(x) ∧ A(y)
Similarly,
A(xy) ≥ (A ◦ A)(xy)
_
= (A(s) ∧ A(t))
xy=st
≥ A(x) ∧ A(y).
37
Proposition 4.0.4
Let A be a fuzzy sub ring of R and let f be an epimorphism of R
onto a ring R. Then f (A) is a fuzzy sub ring of R.
Proof. Let u, v ∈ R. Then there exists x, y ∈ R such that f (x) =
u and f (y) = v since f is surjective. Hence, we obtain successively
_ _
f (A)(u) ∧ f (A)(v) = A(x) ∧ A(y)
f (x)=u f (y)=v
_
= A(x) ∧ A(y)
f (x)=u,f (y)=v
_
≤ A(x − y) (A is a fuzzy subring of R)
f (x)=u,f (y)=v
_
≤ A(x − y) (f is a homomorphism )
f (x)−f (y)=u−v
_
= A(z)
f (z)=u−v
=f (A)(u − v)
Proposition 4.0.5
Let f be a homomorphism from R to a ring R and let B be a fuzzy
sub ring of R. Then f −1 (B) is a sub ring of R. Proof. For any
x, y ∈ R,
38
f −1 (B)(xy) = B(f (xy))
= f −1 (B)(x) ∧ f −1 (B)(y)
Similarly,
Proposition 4.0.6
A non-constant fuzzy set A on R is a fuzzy ring on R if and only if
At is a sub ring of R, ∀t ∈ [0, 1]
39
_
f (A)(y) = A(x) | x ∈ f −1 (y)
= 0, iff
Proposition 4.0.7
Let R1 , R2 be rings, f : R1 → R2 be a ring homomorphism. A be a
fuzzy ring on R1 and B be a fuzzy ring on R2 . Then f (A) is a fuzzy
ring on R2 and f −1 (B) is a fuzzy ring on R1 .
Fuzzy Ideals
Definition 4.1.1
A fuzzy ring A on a ring R is said to be a fuzzy left ideal if
40
right ideal. In other words, a fuzzy set A on R is a fuzzy ideal if
∀x, y ∈ R.
V
1. A(x − y) ≥ {A(x), A(y)}
W
2. A(xy) ≥ {A(x), A(y)}
Proposition 4.1.2
A fuzzy ring on R is a fuzzy ideal if and only if At is an ideal of
R, ∀t ∈ [0, 1] Proof. Suppose that A is a fuzzy ideal of R. Then At ,
for t ∈ [0, 1] is a sub ring of R.
Let x, y ∈ At and z ∈ R. Then
and
41
A∗ = {x | A(x) = A(0)}
Proposition 4.1.3
Let A be a fuzzy ideal of R and let f be an epimorphism of R onto
a ring R. Then f (A) is a fuzzy ideal of R
If A is a fuzzy subring on R, we shall use the notation A0 for
{x ∈ R | A(x) = A(0)}
42
CONCLUSION
43
Bibliography
44
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
FUZZY MATRICES
DON BOSCO ARTS & SCIENCE COLLEGE
ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
FUZZY MATRICES
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1902)
ACKNOWLEDGEMENT
AMRUTHA P M
CONTENTS
1. INTRODUCTION .......................................................... 07
2. PRELIMINARIES .......................................................... 09
2.1 OPERATION ON MATRICES .................................. 11
5. RANKS ............................................................................... 43
7. CONCLUSION ................................................................. 58
8. BIBLIOGRAPHY ........................................................... 59
INTRODUCTION
We deal with fuzzy matrices, that is matrices over the fuzzy algebra
F= [0,1] under max-min operations (+,·) defined as a+b = max{a,b}
and a · b =min{a,b} for all a,b ∈ F and the standard order ‘≤’ of
real numbers. Let Fmn be the set of all m×n matrices over F. In
short Fn denotes Fnn . For A ∈ Fn , AT , R(A), C(A), ρr (A), ρc (A)
and ρ(A) denotes the transpose, row space, column space, row rank,
column rank and rank of A. Algebraic operations on matrices are
max-min operations, which are different from that of the standard
operations on real matrices. In practice, fuzzy matrices have been
proposed to represent fuzzy relations in a system based on fuzzy sets
theory, the behaviour of the dynamic fuzzy systems depends heavily
on the products of fuzzy matrices in the matrix representations of
the system. A ∈ Fmn is regular if there exists X such that AXA = A;
X is called a generalized (g − ) inverse of A and is denoted by A− . A− {
1} denotes the set of all g-inverses of a regular matrix A. A regular
matrix as one that has a generalized inverse lays the foundation in the
study on fuzzy relational equations. Regular fuzzy matrices play an
important role in estimation and inverse problem in fuzzy relational
equations and in fuzzy optimization problems. This motivates us
to develop the study on generalized regular fuzzy matrices. The
power of a fuzzy matrix are either convergent to a fuzzy matrix (or)
oscillating with finite period. For a fuzzy matrix A, Ak+d = Ak
for some integers k,d ≥ 0. Therefore, all fuzzy matrices have an
7
index and a period. On the other hand, most matrices over the non
negative real numbers will not have an index and a period. Spectral
inverses, such as group inverse and Drazin inverse are defined for
fuzzy matrices, analogous to that for complex matrices. For A ∈ Fn ,
The Drazin inverse of A is a solution of the equations : Ak XA =
Ak , XAX = X, AX = XA, for some positive integer k. Group inverse
is the solution of the equations : AXA = A, XAX = X, AX = XA.
Hence Drazin inverse and group inverse are identical when k = 1.
We define the regularity index of a matrix A ∈ Fn as a generalization
of the index of A. A characterization of a matrix whose regularity
index coincides with the index of A is established. It is shown that
for a matrix, regularity index is less than (or) equal to the index of
a matrix. Numerical examples are provided to illustrate the relation
between the regularity index and index of a fuzzy matrix.
8
CHAPTER 1
PRELIMINARIES
Matrices are one of the most important tools in mathematics. Also
the Matrices are not only used as a representation of the coefficients
in system of linear equations, but utility of matrices far exceeds that
use.
Definition 1.0.1
−2 5 2 + i 3 −1/2
√
A=0 B = 3.5 −1
5 2
√
3 6 3 5 5/7
3
1+x x 3
C=
cosx sinx + 2 tanx
9
and 2 columns, B has 3 rows and 3 columns while C has 2 rows and
3 columns.
Definition 1.0.2
A is a matrix of order m × n.
2. We shall consider only those matrices whose elements are real
are all 1 and rest are all zero is called an identity matrix. In other
words, the square matrix A = [aij ]n×n is an identity matrix, if
aij = 1 if i = j
0 if i ̸= j
1 0
0 1
10
1.1 Operation on Matrices
we shall introduce certain operations on matrices, namely, addition
defined only if the matrices which are being added are of the same
order. If A and B are two (m × n) matrices with elements aik and bik
respectively, then their sum A + B is the (m × n) matrix C whose
elements cik are given by cik = aik + bik
1 2 3 3 4 1
A= and B=
−1 1 2 0 2 −1
4 6 4
then A+B =
−1 3 1
Two matrices are said to be conformable to addition if they are of
plied together to form their product BA (in that order) only when
the number of columns of B is equal to the number of rows of A. A
and B are then said to be conformable to the product BA. We shall
see shortly, however, that A and B need not be conformable to the
11
product AB, and that, even when they are, the product AB does not
necessarily equal the product BA. That is, matrix multiplication is
in general non-commutative. Suppose now A is a matrix of order
(m × p) with elements aik and B is a matrix of order (p × n) with
elements bik . Then A and B are conformable to the product AB
which is a matrix C, say, of order (m × n) with elements cik defined
by,
Pp
cik = s=1 ais bsk
Now the product BA is also defined in this case since the num-
7 3 8
11 4 9
12 5 13
12
order, say m × n, then A + B = B + A.
2. Associative Law For any three matrices A = [aij ], B = [bij ], C =
1. k(A + B) = kA + kB
2. (k + l)A = kA + lA
13
Transpose of a matrix
If A = [aij ] be an m × n matrix, then the matrix obtained by in-
3 5 √
√
′ 3 3 0
If A = 3 Then A =
1
5 1 −1/3
0 −1/3 2×3
3×2
The rank of a matrix would be zero only if the matrix had no ele-
ments. If a matrix had even one element, its minimum rank would
be one.
Definition 1.1.4
14
A is called the rank of A, denoted rank(A).
Method of find the rank of a matrix
Reduce the given matrix A into the row Echolon form or row
15
Case-1: If n = r, then the system has a unique solution.
16
CHAPTER 2
FUNDAMENTAL CONCEPTS
17
2.1 Fuzzy vector
A fuzzy vector is an n-tuple of elements of the fuzzy algebra F =
[0, 1].
Definition 2.1.1
18
Definition 2.1.3
A subspace of Vn is a subset W of Vn such that O ∈ W and for x,
y ∈ W, x+y ∈ W .
Example
The set Bn of all n-tuples (a1 , a2 , ...,an ) over the two elements
is a subspace of V3 .
Definition 2.1.4
P
A linear combination of elements of set S is a finite sum ai xi where
Example
19
S = {(1,1)} is the minimal spanning set for W, since every element
(x, x) = x(1,1) with x ∈ F is a linear combination of (1,1) in S, S is
a basis for W.
Definition 2.1.7
pendent set.
Proposition 2.1.1
The set of vectors {(0.5, 1), (1, 0.6), (0.7, 0.9)} is a dependent set,
≥ 0.8 and b2 = (0.4, 0.6, 0.5). We claim that the span of B, that is,
<B> contains the set S = {a1 , a2 , a3 , a4 } be a subset of V3 given by
a1 = (0.6, 0.3, 0.6), a2 = (0.4, 0.5, 0.5),
20
a3 = (0.5, 0.6, 0.5) and a4 = (0.8, 0.6, 0.7).
a1 = (0.6, 0.3, 0.6) = 0.6(b, 0.3, 0.7) + 0.3(0.4, 0.6, 0.5),
Hence, <B> ⊇ S
Definition 2.1.9
21
P
if whenever ci = aij cj for ci , cj ∈ C and aij ∈ F then aii ci = ci .
Example
Over the fuzzy algebra F =[0,1], any two bases for a finitely gen-
We first show that for any finite basis C, there exists a standard ba-
sis having the same cardinality. Let S be the set of all fuzzy vectors
each of whose entries equals some entry of a vector C. Then S is a
finite set.
P
Suppose C is not a standard basis, then ci = aij cj for some ci ∈
C and aij ∈ [0,1] with ci ̸= aii ci , that is ci ̸= min{aii , ci }, therefore
aii ci < ci .
Let C1 be the set obtained from C by replacing ci by aii ci . Then |C|
= |C1 | and <C> = <C1 > and it can be verified that C1 is indepen-
dent set and all the vectors of C1 are all in S.
Let us define an order relation on finite subsets of S as follows; Let
the weight of a finite subset be the sum of all entries of members of
the subset, regarded as real numbers.
22
We define that F1 ≤ F2 , for finite subsets F1 and F2 of S if weight of
F1 ≤ weight of F2 . Clearly this is a partial order relation on finite
subsets of S, Since aii ci < ci , C1 ≤ C and |C1 | = |C| is finite.
If C1 is a standard basis, then C1 is the required standard basis with
the same cardinality as C. If not, then repeat the process of replacing
C1 by a basis C2 and proceed.
Therefore after replacing bases of the form C by bases of the form
C1 , the process must terminate after a finite number of steps.
This can happen only if we have obtained a standard basis with the
same cardinality as C. This proves that for any finite basis, there
exist a standard basis with the same cardinality.
Next we show that there is only one standard basis. Let C be a
standard basis.
P
Suppose for ck ∈ C, we have ck = j aj , where
aj ∈ <C> , then aj can be expressed as a linear combination of basis
P
vector in C, that is aj = bji ci with bji ∈ F and ci ∈ C. Therefore,
X
ck = aj
j
X
= bji ci
i,j
XX
= ( bji ci )
i j
P
Since C is a standard basis. We have, ( j bjk )ck = ck ;
by using the fact that the fuzzy sum is the maximum, bjk ck = ck for
23
P
some j and from aj = ij bji ci we get aj ≥ ck .
P
From ck = aj , we have ck ≥ aj .Therefore, it follows that ck = aj
for some j.
P
Thus we conclude that whenever ck = j aj , then ck equals some
summand aj .
Next to prove the uniqueness, if possible, let us assume that C and
′ ′ ′
C are two standard basis with | C | = | C |. Since C is a basis
, each element of C can be expressed as a linear combination of
′
elements of C . By proceeding argument, each element ai of C must
′
be a multiple of some element bj of C . Since fuzzy multiplication is
minimum , it follows that ai ≤ bj .
′
In the same manner, by using that each element of C is a multiple
′
of some element of C, and |C| = |C | it follows that ai = bj and
′
therefore C = C .
This proves the uniqueness of the standard basis. Hence the theorem.
Definition 2.2.2
The set {(1,0,0), (0,1,0), (0,0,1)} forms the standard basis for V3 .
dim(V3 ) = 3
24
Example
Let S = {(0.5, 0.5, 0.5), (0, 1, 0.5), (0, 0.5, 1)} be a standard basis
0.4, β ≤ 0.5 and γ = 0.6 ∈ F. Thus expression for the vector space
x is not unique. However, the unique standard basis of a finitely
generated subspace over F admits a unique representation.
Theorem 2.2.2
25
uniquely as a linear combination of the standard basis vectors.
Proof
the vector x.
Theorem 2.2.3
Let S be a vector space over F and be the linear span of the vectors
26
Pm
= j=1:j̸ =i αj xj + αi xi
Pm
αj xj + αi ( m
P
= j=1:j̸ =i j=1:j̸ =i βj xj )
Pm
= j=1:j̸ =i γj xj
Let y1 , y2 ..., yn be the unique standard basis for S. Then the set
27
Proof
If the set of (n + 1) vectors linearly independent,then by the above
theorem, we can find a basis for Vn containing the set. This is a con-
tradiction, since every basis for Vn must contain precisely n vectors.
28
CHAPTER 3
FUZZY MATRICES
By a fuzzy matrix, we mean a matrix over a fuzzy algebra. Here
we confine with matrices over the fuzzy algebra F = [0,1] under the
max-min operations and with the usual ordering on real numbers.
Fuzzy matrices have quite different properties from matrices over a
field, due to the fact that addition in a fuzzy algebra does not form
a group. Here we will develop that every fuzzy linear transformation
on Vn can be represented by a unique fuzzy matrix. One of the most
important ways to study a fuzzy matrix is to consider its row space,
that is, the subspace of Vn spanned by its rows.
Definition 3.0.4
Let A = (aij ) ∈ Fmn . Then the element aij is called the (i, j) entry
of A. Let Ai∗ (or A∗j ) denote the ith row (column) of A . The row
space R(A) of A is the subspace of Vn generated by the rows {Ai∗ }
of A. The column space C(A) of A is the subspace of Vm generated
by the columns {A∗j } of A. The null space (or) kernel of A is the set
29
{x : xA = 0}. Note that row (column) vector is just an element of
Vn (V n ).
Definition 3.0.6
The n × m zero matrix O is the matrix all of whose entries are zero.
The n × n identity matrix I is the matrix (δij ) such that
1 if i = j
δij =
0 if i ̸= j
Definition 3.1.1
Let A = (aij ) ∈ Fmn and B = (bij ) ∈ Fmn . Then the matrix A+B
30
For A = (aij ) and B = (bij ) in Fmn ,
A + B = (sup{aij , bij })
A ⊙ B = (inf{aij , bij })
Proof
31
Similarly, if aij ≥ bij (or) cij , then both cases sup{aij , inf{bij , cij }}
= aij and inf{sup{aij ,bij }, sup{aij ,cij }} = aij . Therefore ij th
entry of A + (B ⊙ C) = ij th entry of (A + B) ⊙ (A + C).
If aij ≤ bij and cij , then we have two cases aij ≤ bij ≤ cij or aij ≤
cij ≤ bij then,
sup{aij , inf{bij , cij }} = bij = inf{sup{aij , bij }, sup{aij , cij }} (or)
Proposition 3.1.2
The set Fmn is a fuzzy vector space under the operations defined as
32
Proof
For A, B, C ∈ Fmn ,
A + B = B + A ∈ Fmn (commutativity)
A + (B + C) = (A + B) + C (Associativity)
For c1 , c2 ∈ F,
(c1 + c2 )A = ( c1 + c2 )J ⊙ A (by(3.2))
= (c1 J + c2 J) ⊙ A
= (c1 J) ⊙ A + (c2 J) ⊙ A
= c1 A + c2 A
Definition 3.2.1
For A = (aij ) ∈ Fmp and B = (bij ) ∈ Fpn , the max-min product
33
conformable for multiplication.
Example
0.8 0.1 0.6 0.5
A= , B=
0.2 1 0.4 0.3
Then,
0.6 0.5
(0.8 0.1) (0.8 0.1)
0.4 0.3
AB =
0.6 0.5
(0.2 1) (0.2 1)
0.4 0.3
sup{inf {0.8, 0.6}, inf {0.1, 0.4} sup{inf {0.8, 0.5}, inf {0.1, 0.3}
=
sup{inf {0.2, 0.6}, inf {1, 0.4} sup{inf {0.2, 0.5}, inf {1, 0.3}
sup{0.6, 0.1} sup{0.5, 0.1}
=
sup{0.2, 0.4} sup{0.2, 0.3}
0.6 0.5
=
0.4 0.3
Remark 3.2.2
P2
For elements a1 , a2 ∈ F, the sum i=1 ai = a1 + a2 = sup{a1 , a2 }
In vector notation AB = (Ai∗ B∗j ) where Ai∗ is the ith row of A and
B∗j is the j th column of B.
34
Proposition 3.2.1
With the given type of matrices (AB)C and A(BC) are both defined
Proposition 3.2.2
× q respectively, A(B + C) = AB + AC
35
Proof
Let A = (aij ), B = (bjk ), C = (cJk ) such that the ranges of the
Thus A(B + C) = AB + AC
Definition 3.2.3
36
Example
0.8 0.1 0.6 0.5 0.6 0.2
Let A = , B = , C =
0.2 1 0.4 0.3 0.7 0.3
0.6 0.5
(0.8 0.1) (0.8 0.1)
0.4 0.3
AB =
0.6 0.5
(0.2 1) (0.2 1)
0.4 0.3
sup{0.6, 0.1} sup{0.5, 0.1}
=
sup{0.2, 0.4} sup{0.2, 0.3}
0.6 0.5
=
0.4 0.3
0.8 0.1
(0.6 0.5) (0.6 0.5)
0.2 1
BA =
0.8 0.1
(0.4 0.3) (0.4 0.3)
0.2 1
sup{0.6, 0.2} sup{0.1, 0.5}
=
sup{0.4, 0.2} sup{0.1, 0.3}
0.6 0.5
=
0.4 0.3
Therefore AB = BA
37
0.6 0.2
(0.6 0.5) (0.6 0.5)
0.7 0.3
BC =
0.6 0.2
(0.4 0.3) (0.4 0.3)
0.7 0.3
sup{0.6, 0.5} sup{0.2, 0.3}
=
sup{0.4, 0.3} sup{0.2, 0.3}
0.6 0.3
=
0.4 0.3
0.6 0.5
(0.6 0.2) (0.6 0.2)
0.4 0.3
CB =
0.6 0.5
(0.7 0.3) (0.7 0.3)
0.4 0.3
sup{0.6, 0.2} sup{0.5, 0.3}
=
sup{0.6, 0.3} sup{0.5, 0.3}
0.6 0.5
=
0.6 0.5
Therefore BC ̸= CB
Example
0.5 0 0 0
Let A = , B=
0.3 0 1 0.5
38
0 0
But, AB =
0 0
AB = 0
0 0
BA =
0.5 0
BA ̸= 0
Definition 3.2.5
every column contains exactly one 1 and all the other entries are 0.
Let Pn denotes the set of all n × n permutation matrices.
Definition 3.2.6
Definition 3.3.1
39
Proposition 3.3.1
Proof
If A ≤ B, then
A + B = (sup{aij , bij })
= (bij )
=B
Thus A ≤ B ⇐⇒ A + B = B
Proposition 3.3.2
Thus AC ≤ BC.
Similarly, Since A ≤ B, aik ≤ bik , for all i = 1 to n and k = 1 to p.
By fuzzy multiplication, aik ckj ≤ bik ckj for j = 1 to m.
P P
By fuzzy addition we get, k dik akj ≤ k dik bkj
Thus DA ≤ DB.
40
Proposition 3.3.3
Let A1 and A2 ∈ Fmn ; B1 and B2 ∈ Fnp . If A1 ≤ A2 and B1 ≤ B2
, then A1 B1 ≤ A2 B2 .
Proof
Thus A1 B1 ≤ A2 B2
Example
0.8 0.5 1 1
Let A1 = and A2 =
0.4 1 1 1
A1 ≤ A2
0.6 0.5 0.6 0.2
B1 = and B2 =
0.4 0.3 0.7 0.3
B1 ≰ B2
0.6 0.5 0.6 0.2
A1 B1 = ≰ = A2 B2
0.4 0.4 0.7 0.3
Proposition 3.3.4
Proof
41
AAT A =
P P
j( k aik ajk )ajl
42
CHAPTER 4
RANKS
Rank is one of the fundamental concepts for the development of
fuzzy matrix theory as it is for field based matrices. However the row
rank and column rank of a fuzzy matrix need not be equal. There is
also a third rank concept, called fuzzy rank(or) Schein rank of great
importance in fuzzy matrix theory.
Definition 4.0.2
Let A ∈ Fmn . The fuzzy rank ρf (A) is the smallest integer t such
that A = BC where B ∈ Fmt and C ∈ Ftn . This decomposition is
called the fuzzy rank factorization.
Remark 4.0.4
The row rank, column rank and the fuzzy rank of a zero matrix is
0. For a finite matrix A, ρr (A) is the maximum number linearly
independent rows of A.
43
Example
0 0.5
Let A=
0.5 1
Any element (x, y) in R(A) is of the form
(x, y) = α(0, 0.5) + β(0.5, 1) for α, β ∈ F
= (0, α ∧ 0.5) + (β ∧ 0.5, β). where, ∧ denotes the minimum.
(0.8, 0.7, 0.6)T and (1, 0.8, 0.7)T are linearly independent. Hence
ρc (A) = 2. Each row of A is not a linear combination of the other
two rows, that is, all the three rows are linearly independent. Hence
ρr (A) = 3
1 0.8
1 0.6 0
A = 0.8 0.7 = BC
0.7 0.8 0
0.7 0.6
44
factorization. Hence ρf (A) = 2.
Proposition 4.0.5
Proof
45
Proof
Remark 4.0.6
Fmr and C ∈ Frn such that ρr (A) = ρr (C) = r and A = BC. This
decomposition is called a row rank factorization of A.
Proof
and C ∈ Fsn such that ρc (A) = ρc (B) = s and A = BC. This de-
composition is called a column rank factorization of A.
46
Proof
Example
1 0.8 0
For the matrix, A = 0.8 0.7 0 , ρf (A) = ρc (A) = 2 and ρr (A)
0.7 0.6 0
= 3.
The decomposition A = BC with B ∈ F32 , C ∈ F23 is a column
rank factorization and also the fuzzy rank factorization. However A
= BC is not a row rank factorization.
Remark 4.0.7
For field based matrices A, B if R(A) ⊆ R(B) and ranks are equal
47
Example
0 0.5 0.5 0 0.5 1
Let A = and B = ;
0.3 0.5 1 1 0.5 0
0.5 0 0 0.5 1
A= = XB.
1 0.3 1 0.5 0
Hence by result, R(A) ⊆ R(B). Here , (1, 0.5, 0) ̸= α(0, 0.5, 0.5)
48
Definition 4.0.10
Let A ∈ Fmn . The fuzzy rank ρf (A) satisfy the following properties.
49
3. ρf (A) is the smallest size of a set S of vectors such that
R(A) ⊆ <S>.
4. ρf (A) is the least number of rank 1 matrices whose sum is A.
Proof
50
Let V ∈ Fmt and W ∈ Ftn be defined such that the ith column of V
is viT and ith row of W is wi .
Then A = V W is a fuzzy rank decomposition, that is ρf (A) = s.
Thus 4 holds.
Corollary 4.0.12
Proof
51
Definition 4.0.11
52
CHAPTER 5
GREEN’S RELATION
The fuzzy matrix under max-min composition, that is fuzzy mul-
tiplication form a semigroup, that is associative law holds. A fuzzy
matrix is invertible if and only if it is a permutation matrix. We
introduce Green’s equivalence classes for fuzzy matrices. Green de-
fined five equivalence relations R, LH, D, J in any semigroup. For
fuzzy matrices these five equivalence relations can be characterized
in terms of row and column spaces.
Definition 5.0.13
ax = y and by = x
3. xHy if xRy and xLy
if xRy (or) xLy. It is well known that the above relations are all
equivalence relations.
Proposition 5.0.15
53
identities 0 and 1, we have the following:
1. ARB if and only if C(A) = C(B)
54
=⇒ ALB ⇐⇒ R(B) = R(A)
B, W BY = A.
R(B) = R(ZAX) ⊆ R(AX) ⊆ R(A)X and
R(A) = R(W BY ) ⊆ R(BY ) ⊆ R(B)Y
Conversely, if R(B) ⊆ R(A)X and R(A) ⊆ R(B)Y ,
55
then R(B) ⊆ R(AX) and R(A) ⊆ R(BY ) again by the result - R(B)
⊆ R(A) if and only if B = XA for some Y ∈ Fm , we get there exist
matrices W, Z such that ZAX = B and W BY = A. Hence,AJB.
Definition 5.0.14
0 1
X =Y = .
1 0
Proposition 5.0.16
Two matrices are D-equivalent if and only if their row spaces are
Two D-equivalent matrices have the same row and column [Link]
56
Example
0 0 0 0 0 0
A = 1 0.6 0 ; B = 1 0.6 0.4
0.6 0 0 0.6 0.4 0
Proof
B, C, D.
Let K be the subset of the fuzzy algebra F = [0, 1] consisting of all
entries of X, Y, A, B, C, D.
Let S be the semigroup of all fuzzy matrices whose entries lie in K.
Then S is finite, since under max-min composition, sum of entries of
matrices AB, that is s(AB) ⊆ s(A) ∪ s(B) and XJY in S. Therefore
XDY in S and XDY is in the semigroup of all fuzzy matrices.
57
CONCLUSION
Fuzzy matrices is one of the deepest and fascinating topic in math-
ematics. Through this project we covered the basic informations
about fuzzy matrices. We were understand that one of the most
important ways to study a fuzzy matrix is to consider its raw space.
The applications of fuzzy matrix are in retrieval system, medical di-
agnosis, database management system, decision making theory and
dynamical system. Also fuzzy matrices is one of the main research
area in mathematics.
58
BIBLIOGRAPHY
59
DON BOSCO ARTS & SCIENCE
COLLEGE ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
GRAPH DOMINATION
DON BOSCO ARTS & SCIENCE COLLEGE
ANGADIKADAVU
DEPARTMENT OF MATHEMATICS
2021-2023
Project Report on
GRAPH DOMINATION
Examiners:
1.
2.
KANNUR UNIVERSITY
BONAFIDE CERTIFICATE
Date: (C1PSMM1908)
ACKNOWLEDGEMENT
SURYA CHACKO
CONTENTS
1. INTRODUCTION ................................................................. 01
2. PRELIMINARIES ................................................................ 03
7. APPLICATIONS OF DOMINATION
IN GRAPH THEORY ........................................................ 37
8. CONCLUSION ..................................................................... 39
9. BIBLIOGRAPHY ..................................................................40
INTRODUCTION
1
dominating set. A variety of new problems appears as soon as we
impose additional properties on the dominating set.
2
PRELIMINARIES
Definition 1
A graph G is an ordered triplet (V(G),E(G),IG ), where V(G) is a
nonempty set, E(G) is a set disjoint from V(G) and IG is an inci-
dence map that associates each elements of E(G) to an unordered
pair of element of V(G).
• Elements of V (G) are called vertices.
• Elements of E (G) are called edges.
• If for the edge e of G, IG (e) = {u,v} then we write e = u v.
• If IG (e) = {u,v} then u and v are called end vertices of e.
• If e is an edge with end vertices u and v then we say that e is
incident with u and v.
• A set of two or more edges of a graph G is called multiple edges
or parallel edges, if their points are the same.
• An edge with two ends are the same is called a loop.
Definition 2
A vertex u is a neighbor of v in G if uv is an edge in G an u̸=v.
• The set of all neighbors of v is the open neighborhood of v or
neighbor set of v and it is denoted by N(v).
• The set N[v] = N(v) ∪ {v} is called the closed neighborhood of
v in G. If the graph is explicit then open neighborhood and closed
neighborhood of v are denoted by NG (v), NG[v] respectively.
3
Definition 3
A sub graph H of G is said to be a spanning sub graph of G if
V(H) = V(G).
Definition 4
A subset S of the vertex set V of a graph G is called independent if
no two of its vertices are adjacent in G.
Definition 5
• Vertices u and v are adjacent to each other in G if and only if there
is an edge of G with u and v as its end.
• Two edges e and f are adjacent to each other in G if and only if
they have common end vertices.
Definition 6
• We denote number of vertices of a graph G by n (G) and it is called
order of the graph.
• The number of edges in a graph G is denoted by m(G) and it is
called the size of the graph.
Definition 7
A sub graph H of G is said to be induced sub graph of G if each
edge of G having its ends in V(H) is also an edge of H. The induced
sub graph G with vertex set S⊆V(G) is called the sub graph of G
4
induced by S and is denoted by G[S].
Definition 8
Let G be a graph and v∈V(G), then the number of edges incident
with v in the graph G is called the degree of the vertex and it is
denoted by d(v).
• The minimum degree of a graph G is denoted by δ(G).
• The maximum degree of a graph G is denoted by ∆(G).
Definition 9
A maximal independent set of G is an independent set that is not a
proper subset of another independent set of G.
5
Chapter 1
DOMINATION IN GRAPH
Definition 1.1
A vertex v in a graph G is said to dominate itself and each of its
[Link] say in other words that v dominates the vertices of
its closed neighborhood N[v].
6
Definition 1.2
Let G be a graph. A set S⊂V is called a dominating set of G if every
vertex u ∈ V|S has a neighbor v∈S. Equivalently, every vertex of G
is either in S or in the neighbor set N(S)=U v∈S N(V ) of S in G. A
vertex u is said to be dominated by a vertex v∈G if either u = v or
uv∈E (G).
Definition 1.3
A γ-set of G is a minimum dominating set of G, which is a domi-
nating set of G whose cardinality is minimum. A dominating set S
of G is minimal if S properly contains no dominating set S of G.
Definition 1.4
The domination number of G is the cardinality of a minimum dom-
inating set of [Link] is denoted by γ(G).
Example 1.1
For the Petersen graph P,γ(p)=[Link] Figure 1.2, {v1 , v8 , v9 } is a γ-set
of P while the set {v1 ,v2 ,v3 ,v4 ,v5 } is a minimal dominating set of P.
7
Figure 1.2 Petersen graph P for which γ(p)
Example 1.2
Determine the minimum number of queens that can be placed on the
chessboard (see figure 1.3) such that every square is either occupied
by one of the queens in a single move.
8
Figure 1.3 Queen Domination
Theorem 1.1
Let S be a dominating set of a graph [Link] S is a minimal domi-
nating set if and only if for each vertex u of S, one of the following
two conditions hold:
i. u is an isolated vertex of G[S],the sub graph induced by S in G.
ii. There exist a vertex v∈V|S such that u is the only neighbor of v
in S.
9
Proof
Suppose that S is a minimal dominating set of [Link] for each ver-
tex u of S, S∈{u} is not a dominating set of [Link] there exist
V|(S|u) such that v is dominated by no vertex of S|{u}.
If v = u, then u is an isolated vertex of G[S],and hence condition (i)
holds.
If v̸=u, as S is a dominating set of G, then condition (ii) holds.
Conversely, assume that S is not a minimal dominating set of [Link]
there up that in example 1.1 the set S={v1 , v2 , v3 , v4 , v5 } is a min-
imal dominating set of the Petersen graph P in which no vertex is
an isolated vertex of P[S] and for each i={1, 2, 3, 4, 5}, vi is the only
vertex of S that is adjacent to vi + 5.
Definition 1.5
10
Theorem 1.2
A dominating set S of a graph G is a minimal dominating set of G
if and only if PN (u,s)̸= ϕ for every u ∈ s.
Corollary 1.1
Let G be a graph having no isolated vertices. If S is a minimal dom-
inating set of G then V|S is a dominating set of G.
Proof
As S is a minimal dominating set, by theorem 1.2, PN (u,s) ̸= ϕ for
every u∈S. This means that for every u∈S, there exists v∈V|S such
that uv∈E(G), and consequently, V|S is a dominating set of G.
Corollary 1.2
Let G be a graph of order n≥2. If δ(G)≥1, then γ(G)≤ n2 .
Proof
Corollary 1.3
If G is a connected graph of order n ≥ 2, γ(G) ≤ n2 .
11
Proof
As G is a connected graph and n≥2, G has no isolated [Link],
by applying corollary 1.2 we get γ(G) ≤ n2 .
Definition 1.6
There are a number of variations of domination, we consider the best
known of these. In this variation, we could resist domination so that
a vertex u is only permitted to dominate a vertex v if v is a neighbour
of u. In order to distinguish this kind of domination from ordinary
domination we refer to this kind of domination as open domination,
although the term total domination is used as well.
Definition 1.7
12
Definition 1.8
The minimum cardinality of an open dominating set is the open
domination number γ◦(G) of G. An open dominating set of cardi-
nality γ◦(G) is a minimum open dominating set for G.
Example 1.3
Figure 1.4
Solution
γ(G)=3
γ◦(G)=4
13
Example 1.4
In figure 1.5, the set S={u1 ,v1 ,w, v4 } is a minimum open dominating
set of G and so,γ◦(G) = 4.
14
Chapter 2
In this section we present lower and upper bounds for the domina-
tion number γ(G).
Observation 2.1
(a) The vertex v dominates N(v) and |N(v)|≤∆G.
(b) Let v be any vertex of G. Then v|N(v) is a dominating set of G.
These two observations yield the following lower and upper bounds
for γ(G).
Theorem 2.1
n
For any graph G, 1+∆(G) ≤ γ(G) ≤ n − ∆(G).
15
Illustration of Theorem 2.1
G
Figure 2.1
n 5
1+∆(G) ≤ γ(G) ≤ n − ∆(G) ⇒ 1+2 ≤ 2 ≤ 5−2
5
⇒ 3 < 2 < 3
Theorem 2.2
Let G be a graph of order n , size m and domination number γ .
Then
16
m ≤ [ 12 (n − γ)(n − γ + 2)]..............................(a)
Proof
If γ = 1
1
2 (n − γ)(n − γ + 2) = 12 (n − 1)(n − 1 + 2)
= 12 (n − 1)(n + 1)
= 12 (n2 − 1)
n(n−1)
While the maximum value for m = 2 ( when G = Kn )
Since m = 12 n(n − 1) ≤ 12 (n2 − 1), and the result is true.
If γ = 2 ,
1
2 (n − γ)(n − γ + 2) = 12 (n − 2)(n − 2 + 2)
= 12 n(n − 2)
m ≤ 12 (n − 2)
1
m ≤ 2 n(n − 2)
( 12 (n − 2)) ≤ 1
2 n(n − 2)
17
and then the result is true.
Thus the result is true for γ = 1 and γ = 2.
We now assume that γ ≥ 3.
We apply induction on n.
Let G be a graph of order n and size m and γ ≥ 3.
If v is a vertex of maximum degree ∆ of G , again by theorem 2.1,
| N (v) |= ∆ ≤ n − γ and hence ∆ = n − γ − r, where 0 ≤ r.
Given that,
| N (v) |= n − γ − r (see fig 2.2)
Let S = V \ N [v].
Then | S |=| V | − | N (v) | −1
= n − (n − γ − r) − 1
| S |= γ + r − 1..............................................(b)
18
Let m1 be the size of G [ S ], m2 be the number of edges between S
and N(v ), and m3 be the size of G [ N [v ]].
Clearly, m = m1 + m2 + m3 . If D is a γ–set of G [ S ], then D ∪ {v}
is a dominating set of G.
Hence,
γ(G) = γ ≤ | D | +1 .............................................(c)
m1 ≤ [ 12 (| S | − | D |) (| S | − | D | +2) ]
≤ [ 21 ( γ + r − 1 ) − ( γ − 1 ) ] [ ( γ + r − 1 ) − ( γ − 1) + 2 ]
= [ 21 [ γ + r − 1 − γ + 1] [ γ + r − 1 − γ + 1 + 2]]
= [ 12 r ( r + 2 ) ]
Therefore , γ ≤ | S \ N (v) | +2
=| S | − | S ∩ N (u) | +2
i.e , | S ∩ N (u) | ≤ γ + r − 1 + 2 − γ
=γ+1
19
Consequently,
≤ | N (v) | ( r + 1 )
= ∆(r + 1) ......................................................(e)
≤ ( ∆ + 1 ) − m2
Thus,
1
m3 ≤ 2 [ ∆( ∆ + 1 ) − m2 ]..............................................(f)
= 12 r( r + 2 ) + 12 [ ∆( ∆ + 1)˙ ] + m2
2
= 12 r( r + 2 ) + 12 [ ∆( ∆ + 1 ) + m2 ]
1
≤ 2 r( r + 2 ) + 21 [ ∆( ∆ + 1 ) + ∆(r + 1 )]
1
≤ 2 ( n − γ − ∆ ) (n − γ − ∆ + 2) + 21 [ ∆(∆ + 1) + ∆(r + 1) ]
20
(As ∆ = n − γ − r )
( since ∆ = n − γ − r)
= 21 (n − γ)(n − γ + 2) + ∆2 [(∆ + r) + (∆ + r + 2) − ∆ − ∆ − 1 − r − 1]
[ n − γ = ∆ + r]
= 12 ( n − γ ) (n − γ + 2 ) − ∆
2 (γ)
1
≤ 2 ( n − γ ) ( n − γ + 2)
21
Let G be a graph with domination number γ(G), order n = 5 , size
m = 5.
Then ,
m ≤ [ 21 (n − γ)(n − γ + 2)] ⇒ 5 ≤ [ 12 ( 5 − 2) (5 − 2 + 2)]
⇒ 5 ≤ 7.5
22
Chapter 3
VARIETIES OF DOMINATION
Definition 3.1
In this topic, we will consider a variety of conditions that can be im-
posed either on the dominated set V - S , or on V , or on the method
by which the vertices in V - S are dominated . These include the
following.
23
S also dominates the vertices V - S in the complement of G.
MULTIPLE DOMINATION
Theorem 3.1
Proof
Let S be a minimum dominating set in G.
Assume that every vertex in V - S is dominated by three or more
vertices.
24
Let u ∈ V - S and let v and w be two vertices in S which dominate
u.
It follows from our assumption that every vertex in V - S is domi-
nated by at least one vertex in S - { v , w }.
Therefore, the set V - S = S - {v,w } ∪ {u} is a dominating set.
But since |V - S |<| S |, we contradicts the assumption that S is a
minimum dominating set.
Theorem 3.2
Proof
Let S be a minimum k - dominating set in G.
Let u ∈ V − S
And let v1 , v2 , ....., vk be distinct vertices in S which dominate u.
Notice that , since ∆(G) ≥ k ≥ 2.
We know that V − S ̸= ϕ because there is always a k - dominating
set, each vertex in V − S is dominated by at least one vertex in
S −{v1 , v2 , ....., vk }.
Therefore, since u dominates each vertex in {v2 , .....vk }.
We know that the set S = S − {v2 , ......, vk } − {u} is a dominating
set in G .
Therefore, γ(G) ≤ | V −S | = γK (G) − (K −1)+1 = γk (G)−k +2.
25
Theorem 3.3
Proof
LOCATING DOMINATION
26
When considering locating sets in graphs one can think of selecting
a minimum set S of vertices of a graph G to achieve the function “
location through triangulation ” .
Definition 3.2
ii) The set Nk [v] = Nk (v) ∪ {v} is caled the closed k − neighborhood
of v.
27
of the open k - neighborhoods of vertices in S , while Nk [S] is the
union of the closed k- neighborhoods of vertices in S.
28
used the more general term of factor domination.
29
A set S ≤ V is independent if no two vertices of S are joined by an
arc .
The independence number β ◦ (D) is the maximum cardinality of an
independent set in D.
Example 3.1
30
The shaded vertices in the digraph D1 in the figure above form a
kernel of D1 ; while the graph D2 , which is obtained from D1 by
reversing the directions of three arcs ,has no kernel .
Thus we observe that not every digraph has a kernel.
31
Chapter 4
INDEPENDENT DOMINATION
AND IRREDUNDANCE
Definition 4.1
(a)
32
(b)
Figure 3.1
(a) γ(G) = 2 = i(G)
(b) γ(G) = 2 while i(G) = 3
Theorem 4.1
Proof
33
Definition 4.2
Fig 4.1
34
Theorem 4.2
Proof
35
Theorem 4.3
Proof
36
APPLICATIONS OF
DOMINATION IN GRAPH
THEORY
Domination in graphs has application to several fields. Domination
arises in the facility problems, where the number of facilities (eg:
hospitals, fire stations...) is fixed and one attempts to minimize the
distance that a person needs to travel to get to the closet facility.
37
Modelling Biological Networks: Using graph theory as a
modelling tool in biologicl networks allow the utilization of the most
graphical invariants in such a way that is possible to identify sec-
ondary RNA motifs numerically. Those graphical invariants are
variations of the domination number of a graph. The results of the
research carried out in show that the variations of the domination
number can be used for correctly distinguished among the trees that
represent native structures and those that are not likely candidates
to represent RNA.
38
CONCLUSION
In this thesis my research mainly focused on domination in graphs.
Domination has many applications in the areas such as facility lo-
cation problems, planning of defence strategies, surveillance related
problems etc.
In the four chapters of the thesis, first chapter is based on the concept
of Domination, Open Domination and some examples. The main re-
sult of the chapter helps us to find Domination number by using
various methods. In the second chapter we saw and discussed about
the bounds for the Domination number with the help of suitable ex-
amples. In chapter three we discussed about the various varities of
Domination. We also introduced a new kind of Domination in the
fourth chapter namely Independent Domination.
39
BIBLIOGRAPHY