Chapter 2

Basic Structures:
Sets, Functions, Sequences, Sums and Matrices

§ Sets
§ Set Operations
§ Functions
§ Sequences and Summations
§ Cardinality sets
§ Matrices

Discrete Structures 2-1

3-1
 2.1 Sets

§ We study a fundamental discrete structure on which all other discrete

structures are built, namely, the set.

§ Sets are used to group objects together.

§ Often, the objects in a set have similar properties.

§ The language of sets is a means to study such collections in an organized

fashion.

Discrete Structures 2-2

 § Definition 1
§ A set is an unordered collection of objects.

§ Definition 2
§ The objects in a set are called the elements, or members, of the set.
§ A set is said to contain its elements.
§ Example
A = {a, b, c}
a Î A : a is an element of the set A
d Ï A : d is not an element of the set A
§ Example
Set builder : Characterize all those elements in the set by stating the property or
properties.
O = { x | x is an odd positive integer less than 10 }
O = { x Î Z+ | x is odd and x < 10 }
These sets play an important role in discrete mathematics.
N = {0,1, 2, 3, . . . }, the set of natural numbers
Z = {. . , -3, -2, -1, 0, 1, 2, 3, 4, . .}, the set of integers
Z+= {1, 2, 3,, . . . }, the set of positive integers
Q = {p/q | p Î Z, q Î Z, and q ¹ 0}, the set of rational numbers
R, the set of real numbers
Discrete Structures 2-3
 § Definition 3
§ Two sets are equal if and only if they have the same elements.
That is, A and B are equal if and only if ∀x(x Î A ↔ x Î B).
notation: A = B if A and B are equal sets.
§ Example
§ {1, 3, 5} = {3, 5, 1}
U

§ The universal set U contains all the objects under consideration V

§ Empty set : a set that has no elements.

§ denoted by { } or Ø. Venn diagram

§ Singleton set : a set with one element

§ Definition 4
§ The set A is said to be a subset of B if and only if every element of A is also an
element of B.
§ notation: A ⊆ B

Discrete Structures 2-4

 § Definition 5
§ Let S be a set.
If there are exactly n distinct elements in S where n is a nonnegative integer,
S is a finite set
Cardinality of S, |S|, is n
§ Example:
§ A = {1,3,5,7,9}
|A| = 5

§ Definition 6
§ A set is said to be infinite if it is not finite.

§ Example
§ The set of positive integers is infinite.
§ {1, 2, 3, . . . }

Discrete Structures 2-5

 The Power Set

§ Definition 7
§ Given a set S,
the power set of S is the set of all subsets of the set S. The power set of S is
denoted by P(S).

§ Example
§ The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}.
P({0, 1, 2}) = {Ø, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}

§ Example
§ The power set of the empty set : P(Ø) = {Ø}
§ The power set of the set {Ø} : P({Ø}) = {Ø, {Ø}}

Discrete Structures 2-6

 Cartesian Products

§ Definition 8
§ The ordered n-tuple (a1, a2, a3, . . . , an) is ordered collection that has a1 as its
first element, a2 as its second element, . . . , and an as its nth element.

§ ordered 2-tuples are called ordered pairs.

§ The ordered pairs (a, b) and (c, d) are equal:
(a, b) = (c, d) iff a = c, b = d.

§ Definition 9
§ Let A and B be sets. The Cartesian product of A and B is the set of all ordered
pairs (a, b), where a Î A, b Î B, denoted by AⅹB. Hence,
AⅹB = {(a, b) | a Î A, b Î B}

§ Example
§ The Cartesian product of A = {1, 2} and B = {a, b, c} :
AⅹB = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}

Discrete Structures 2-7

 § Definition 10
§ The Cartesian product of A1, A2, . . . , An is the set of ordered n-tuples (a1,
a2, . . . , an), where ai belongs to Ai for i = 1, 2, . . . , n.
§ denoted by A1ⅹA2ⅹ. . .ⅹAn.
§ A1ⅹA2ⅹ. . .ⅹAn = {(a1, a2, . . . , an) | ai Î Ai for i = 1, 2, . . . , n}

§ Example
§ The Cartesian product AⅹBⅹC
, where A={0, 1}, B={1, 2}, C={0, 1, 2}
AⅹBⅹC = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2),
(1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}.

§ A subset of the Cartesian product AⅹB is called relation from the set A to
the set B.
chapter 8
§ R = {(a, 0), (a, 1), (a, 3), (b, 1), (b, 2), (c, 0), (c, 3)}
§ a relation from the set {a, b, c} to the set {0, 1, 2, 3}

Discrete Structures 2-8

 2.2 Set Operations

Let A and B be sets.

§ Definition 1
§ The union of the sets A and B is the set that contains those elements that are
either in A or in B, or in both.
§ denoted by A∪B.
A∪B = {x | x Î A ∨ x Î B }

§ Definition 2
§ The intersection of the sets A and B is the set containing elements that belong
to both A and B.
§ denoted by A ∩ B.
A ∩ B = {x | x Î A ∧ x Î B }

§ Definition 3
§ Two sets are called disjoint if their intersection is the empty set.

§ Principle of inclusion-exclusion U

§ |A∪B| = |A| + |B| - |A ∩ B| A B

Venn diagram
Discrete Structures 2-9
 § Definition 4
§ The difference of A and B, A – B, is the set containing those elements that are
in A but not in B.
A – B = {x | x Î A ∧ x ∉ B }

§ Example
§ The difference of {1, 3, 5} and {1, 2, 3} is the set {1, 3, 5} – {1, 2, 3} = {5}.

§ Definition 5
§ Let U be the universal set.
§ The complement of the set A, denoted by A , is the complement of A with
respect to U.
A = {x | x ∉ A }
A = U–A

§ Example
§ Let A be the set of positive integers greater than 10
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Discrete Structures 2-10

 Set Identities

§ Set Identities
§ Set identities correspond to the logical equivalences

TABLE 1 Set Identities

Identity Name Identity Name
A∪∅ = A Identity laws A∪(B∪C)= (A∪B)∪C Associative
A ∩ U= A A ∩ (B ∩ C)= (A ∩ B) ∩ C laws

A∪U = U Domination laws A ∩ (B∪C)= (A ∩ B)∪(A ∩ C) Distributive

A ∩ ∅= ∅ A∪(B ∩ C)= (A∪B) ∩ (A∪C) laws

A∪A = A Idempotent laws AU B = A I B De Morgan’s

A∩ A = A laws
AI B = A U B
( A) = A Complementation A∪(A ∩ B)=A Absorption
laws A ∩ (A∪B)=A laws

A∪B = B∪A Commutative laws AU A =U Complement

A∩ B = B∩ A laws
AI A = ∅

Discrete Structures 2-11

 § Example:
§ The complement of the union is the intersection of the complements:
AU B = AI B

§ Proof:
§ To show two sets are equal, show for all x that x is a member of one set if and only if
it is a member of the other:
"x[ x Î A U B « x Î A I B ]

§ We now apply an important rule of inference

Universal Instantiation:
In a proof we can eliminate the universal quantifier which binds a variable if we do
not assume anything about the variable other than it is an arbitrary member of the
Universe. We can then treat the resulting predicate as a proposition.

Discrete Structures 2-12

 Set Identities
§ Proof: (Cont’d)
§ Let x be arbitrary. Then we can treat the predicates as propositions:

§ Hence x Î A È B « x Î A Ç B is a tautology
§ We have used only logically equivalent assertions and definitions. We apply
another rule of inference
Universal Generalization:
We can apply a universal quantifier to bind a variable if we have shown the predicate to be true for all values
of the variable in the Universe.

§ Claim the assertion is true for all x, i.e., "x[ x Î A È B « x Î A Ç B] Q. E. D.

Discrete Structures 2-13

 § As an alternative, use the identity
A = B Û [ A Í B Ù B Í A]

Example: Prove that A Ç B = A È B

§ Need to show that A Ç B Í A È B and A È B Í A Ç B

Recall: def. of subset.

Discrete Structures 2-14

 § Example: Show A ∩ (B - A) = Ø

Proof
§ The empty set is a subset of every set. Hence,
Ø ⊆ A ∩ (B - A)
§ Therefore, it suffices to show
§ A ∩ (B - A) ⊆ Ø

A = B Û [ A Í B Ù B Í A]
Discrete Structures 2-15
 § Set identities can also be proved using membership tables.

U
A B To indicate that an element is in a set, a
1 is used.

Venn diagram

§ Example :
AÈ B = AÇ B

A B A B A∪B AÈ B AÇ B
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0
2-16

Discrete Structures
 Generalized Unions and Intersections

§ Union and Intersection of Indexed Collections

§ Let A1, A2 , . . . , An be an indexed collection of sets.

UA
i =1
i = A1 È A2 È ... È An

IA
i =1
i = A1 Ç A2 Ç ... Ç An

§ Examples
Let Ai = {i ,i + 1,i + 2 ,L}. Then
n
U Ai = {1, 2, 3, L}
i =1
n
I Ai = {n, n + 1, n + 2, L}
i =1

Discrete Structures 2-17

 Computer Representation of Sets

§ There are various ways to represent sets using a computer.

§ One method
§ Store the elements of the set in an unordered fashion. A = {3, 2, 7, 9}
B = {4, 2, 6, 9}
§ Set operations are time-consuming A∪B
A∩B

§ Alternative way
§ Assuming that the universal set U is finite,
§ first, specify an arbitrary ordering of the elements of U
§ example: a1, a2, ××× , an
§ then, represent a subset A of U with the bit string of length n
§ i-th bit in this bit string is 1 if ai belongs to A, 0 otherwise.

Discrete Structures 2-18

 § U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
§ Example
§ {1, 3, 5, 7, 9}: odd numbers in U
§ → 1010101010
§ Example
§ {1, 2, 3, 4, 5}: integers not exceeding 5
§ → 1111100000

§ Example
§ {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9}
§ union
1111100000∨1010101010 = 1111101010
→ {1, 2, 3, 4, 5, 7, 9}
§ intersection
1111100000∧1010101010 = 1010100000
→ {1, 3, 5}

Discrete Structures 2-19

 2.3 Functions

§ important in mathematics and computer science.

§ Examples
§ Used in the definition of such discrete structures as sequences and strings.
§ Used to represent how long it takes a computer to solve problems of a given
size.
§ Recursive function.
§ Many computer programs and subroutines are designed to calculate values of
functions. defined in terms of itself.

Discrete Structures 2-20

 § Definition 1
§ Let A and B be nonempty sets. A function f from A to B is an assignment of
exactly one element of B to each element of A.
§ Write f (a) = b.
§ If b is the unique element of B assigned by the function f to the element a of A.
§ If f is a function from A to B, write
f:A→ B

§ Remark : Functions are also called mappings or transformations.

§ Definition 2
§ If f is a function from A to B,
A is the domain of f, B is the codomain of f.
§ If f (a) = b,
b is the image of a, a is a preimage of b.
§ The range of f is the set of all images of elements of A.
§ A function f from A to B is said that f maps A to B.

Discrete Structures 2-21

 § If S is a subset of A then
f(S) = {f(s) | s in S}.
§ Example
§ f(a) = Z
§ the image of d is Z
§ the domain of f is A = {a, b, c, d}
§ the codomain is B = {X, Y, Z}
§ f(A) = {Y, Z}
§ the preimage of Y is b
§ the preimages of Z are a, c and d
§ f({c,d}) = {Z}

Discrete Structures 2-22

 § Two functions are equal if they
§ have the same domain.
§ have the same codomain.
§ map elements of common domain to same elements in common codomain.

§ Definition 3
§ Let f1 and f2 be function from A to R (the set of real numbers).
(f1 + f2)(x) = f1 (x) + f2 (x),
(f1 f2)(x) = f1 (x) f2 (x).

§ Example
§ f1 (x) = x2 and f2 (x) = x – x2.
(f1 + f2)(x) = f1 (x) + f2 (x) = x2 + (x – x2) = x.
(f1 f2)(x) = f1 (x) f2 (x) = x2(x – x2) = x3 – x4.

Discrete Structures 2-23

 One-to-One and Onto Functions

§ Definition 5
§ Function f is said to be one-to-one, or injective,
if and only if f (a) = f (b) implies that a = b for all a and b in the domain of f.
§ This function is also called an injection.

§ Example
§ f (x) = x2 is not one-to-one because f (1) = f (-1) = 1.

§ Definition 6
§ For a function f whose domain and codomain are subsets of the set of real
numbers,
§ whenever x < y (x and y are in the domain of f),
f is called increasing if f (x) ≤ f (y), and strictly increasing if f (x) < f (y), and
f is called decreasing if f (x) ≥ f (y), and strictly decreasing if f (x) > f (y).

§ A strictly increasing and strictly decreasing function is one-to-one.

Discrete Structures 2-24

 § Definition 7
§ A function f from A to B is called onto, or surjective,
if and only if for every element b∈B, there is an element a∈A with f(a) = b.
§ This function is also called an surjection.

§ Definition 8
§ The function f is a one-to-one correspondence, or a bijection
if it is both one-to-one and onto.

§ Example

Discrete Structures 2-25

 Inverse Functions

§ Definition 9
Let f be a bijection from A to B. Then the inverse function of f,
denoted by f -1, is the function from B to A defined as
f -1 ( y ) = x iff f ( x) = y

§ Example
§ Let f be defined by the diagram

§ Note : No inverse exists unless f is a bijection.

Discrete Structures 2-26

 Compositions of Functions

§ Definition 10
§ Let f: B→C, g: A→B. The composition of the function f and g, denoted by f ◦g,
is the function from A to C defined by
f◦g(x) = f(g(x))

g f f◦g

f og
§ Example
§ If f (x) = x2 and g(x) = 2x + 1, then f (g(x)) = (2x+1)2 and g(f (x)) = 2x2 + 1

Discrete Structures 2-27

 The Graphs of Functions

§ Definition 11
§ Let f be a function from the set A to the set B. The graph of the
function f is the set of ordered pairs {(a, b) | a∈A and f(a) = b}.

Graph of f(x) = x2
from Z to Z
Graph of f(n) = 2n + 1
from Z to Z
Discrete Structures 2-28
 Some Important Functions

§ Definition 12
§ The floor function, denoted by f (x) = ëxû, is the largest integer less than or
equal to x.
§ The ceiling function, denoted f ( x) = éxù, is the smallest integer greater than or
equal to x.

§ Example
ë3.5û = 3, é3.5ù = 4.
§ Note : the floor function is equivalent to truncation for positive numbers.

Graph of (a) Floor and (b) Ceiling Functions

Discrete Structures 2-29
 2.4 Sequences and Summations

§ Sequences are ordered lists of elements.

§ example
§ 1, 2, 3, 5, 8
§ terms of sequence can be specified by
§ formula for each term
§ recurrence relation
§ combination of the previous terms
§ topics
§ sequences
§ recurrence relations
§ summations

Discrete Structures 2-30

 Sequences

§ Consider an example sequence {an}, a1, a2, a3, …

§ an = 1/n

§ Definition 1 1
a1
§ A sequence is a function from a subset of the set of integers to a set S. 2
a2
§ Notation an : the image of the integer n. 3 a3
§ Call an a term of the sequence
a1, a2, a3, a4, × × × , an, × × ×
§ Notation {an} : describe the sequence.

§ Definition 2
§ A geometric progression is a sequence of the form
a, ar, ar2, . . . , arn, . . .
§ a : initial term, r : common ratio, and both are real numbers.

mwc

Discrete Structures 2-31

 § Definition 3
§ A arithmetic progression is a sequence of the form
a, a + d, a + 2d, . . . , a + nd, . . .
§ a : initial term, d : common difference, and both are real numbers.

§ Sequences of the form a1, a2, . . . , an are often used in computer science.
strings
§ This string is also denoted by a1a2 . . . an.
§ The length of the string is the number of terms in this string.
§ Example
String abcd: string of length four

§ The empty string is the string that has no terms.

§ denoted by λ.

Discrete Structures 2-32

 Recurrence Relations
§ Definition
A recurrence relation (or difference equation) for the sequence {an}:
an equation that expresses an in terms of one or more of the previous terms of the
sequence, namely, a0, a1,…, an-1, for all integers n with n ≥ n0

an = an-1 – an-2 for n = 2, 3, 4, …

A sequence is called a solution of a recurrence relation if its terms satisfy the

recurrence relation.

§ Example
A sequence {an}:
recurrence relation an = an-1 – an-2 for n = 2, 3, 4, …
a0 = 3 and a1 = 5.
What are a2 and a3?

§ Initial conditions
§ For instance, in example above, a0 = 3 and a1 = 5
Discrete Structures 7-33
 Recurrence Relations

§ Example : Fibonacci sequence

f0 = 0 , f1 = 1
fn = fn-1 + fn-2 for n ≥ 2

Find the Fibonacci numbers f2 , f3 , f4 , f5

§ Example : a sequence of integers, an = n!

in recurrence relation form,
an = n an-1
initial condition a0 = 1.

è an = n! is the solution of the recurrence relation, an = n an-1

with initial condition a0 = 1.

Discrete Structures 7-34

 Recurrence Relations

§ Example : Compound Interest

Compute the amount of money after n years assuming an initial amount of $10,000
and an interest rate of 11% compounded annually.
§ Solution
Let Pn denote the amount on the account after n years. Then the sequence {Pn} satisfies
the recurrence relation
Pn = Pn-1 + 0.11Pn-1 = (1.11)Pn-1

The initial condition is P0 = 10,000.

We can use an iterative approach to find a formula for Pn. Note that
P1 = (1.11) P0
P2 = (1.11) P1 = (1.11)2P0
P3 = (1.11) P2 = (1.11)3P0
…
Pn = (1.11) Pn-1 = (1.11)nP0
When we insert the initial condition P0 = 10,000, Pn = (1.11)n10,000

Discrete Structures 7-35

 Special Integer Sequences

§ Finding a formula or a general rule for constructing the terms of a sequence.

§ Only a few terms of a sequence are known.
§ The goal is to identify the sequence.

§ Example
§ 5, 11, 17, 23, 29, 35, 41, 47, 53, 59.
→ 5+6(n - 1) = 6n – 1 for 1 ≤ n ≤ 10.

§ Example
§ 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047
→ an = 3n – 2 for 1 ≤ n ≤ 10.

Discrete Structures 2-36

 Summations

§ Summation notation
§ am + am+1 + . . . + an
§ → n
n

å a j or å j =m
aj or å 1£ j £ n aj
j =m

§ j : index of summation
§ The choice of letter j is arbitrary.
§ m : lower limit
§ n : upper limit
§ å : denote summation

§ Example
§ The sum of the first 100 terms of the sequence {1/n} for n = 1, 2, 3, . . .
§ → 100
1
åj =1 j

Discrete Structures 2-37

 § Theorem 1
§ If a and r are real numbers and r ≠ 0, then
n
ar n +1 - a
å ar j = if r ¹ 1
j =0 r -1
(n + 1)a if r = 1

§ Example
4 3 4 4

åå ij = å (i + 2i + 3i) = å 6i = 6 + 12 + 18 + 24 = 60
i =1 j =1 i =1 i =1

§ Example
ås = 0+2+4 = 6
sÎ{0 , 2 , 4}

§ Example
100 100 100 49
åk2 →
k = 50
åk 2
= åk -åk22

k = 50 k =1 k =1

Discrete Structures 2-38

 2.5 Cardinality of Sets
§ The cardinality of a finite set tells us
§ whether two finite sets are the same size.
§ whether one is bigger than the other.

§ The notion of cardinality is extend to an infinite set.

§ Definition
A set S is finite with cardinality nÎN if there is a bijection from
the set {0, 1, …, n - 1} to S. Otherwise, infinite.

§ Thm
The set N of natural numbers is an infinite set.
Proof: skip

§ Definition
The sets A and B have the same cardinality if and only if there is
a one-to-one correspondence from A to B. |A| = |B|

Discrete Structures 2-39

 § Definition
If there is a one-to-one function from A to B, |A| £ |B|.

§ Definition
A set is called countable if it is either finite or has the same cardinality as the set
of positive integers. Otherwise, it is called uncountable.

§ Definition
When an infinite set S is countable, |S| = À0, “aleph null”.

§ An infinite set is countable iff it is possible to list the elements in a

sequence.

Discrete Structures 2-40

 § Example
§ The set of odd positive integers is countable.
§ can show the 1:1 correspondence from this set to the set of positive integers.

§ The set of all integers is countable.

§ can show the 1:1 correspondence.

0 1 -1 2 -2 3 -3 × × ×

1 2 3 4 5 6 7×××

mwc

Discrete Structures 2-41

 § Example
§ The set of rational numbers is countable.
§ The set of positive rational numbers is countable.

§ can show that the set of real numbers is an uncountable set.

Discrete Structures 2-42

 2.6 Matrices

§ Matrices are used throughout discrete mathematics to express

relationships between elements in sets.

§ Definition 1
§ A matrix is a rectangular array of numbers.
§ A matrix with m rows and n columns is called an mⅹn matrix.
§ The plural of matrix is matrices.
§ A matrix with the same number of rows as columns is called square.
§ Two matrices are equal if they have
§ the same number of rows and the same number of columns and
§ the corresponding entries in every position are equal.

Discrete Structures 3-43

 § Definition 2
§ Let éa11 a12 L a1n ù
ê ú
êa 21 a 22 L a2n ú
ê. . . ú
A =ê ú
ê. . . ú
ê. . . ú
ê ú
ëêa n1 a n 2 L a nn ûú

§ The ith row of A is the 1ⅹn matrix [ai1 , ai 2 ,L , ain ] .

§ The jth column of A is the nⅹ1 matrix éa1 j ù
ê ú
ê a2 j ú
ê. ú
ê ú
ê. ú
ê. ú
ê ú
êëanj úû

§ The (i, j)th element or entry of A is the element aij, that is, the number in the ith
row and jth column of A.
§ A = [aij], which indicates that A is the matrix with its (i, j)th element equal to aij.

Discrete Structures 3-44

 Matrix Arithmetic

§ Definition 3
§ Let A = [aij] and B = [bij] be mⅹn matrices.
§ sum of A and B, A + B, is the mⅹn matrix that has aij + bij as its (i, j)th
element.
§ A + B = [aij + bij].
§ Matrices of different sizes cannot be added.

§ Example

é1 0 - 1ù é 3 4 - 1ù é4 4 - 2ù
ê2 2 - 3ú + ê 1 - 3 0 ú = ê3 - 1 - 3ú
ê ú ê ú ê ú
êë3 4 0 úû êë- 1 1 2 úû êë2 5 2 úû

Discrete Structures 3-45

 Matrix Arithmetic

§ Definition 4
§ Let A be an mⅹk matrix and B be a kⅹn matrix.
§ product of A and B, AB, is the mⅹn matrix with its (i, j)th entry equal to the
sum of the products of the corresponding elements from the ith row of A and
the jth column of B.
§ AB = [cij],
cij = ai1b1j + ai2b2j + . . . + aikbkj.

k
§ C = AB = [cij]m×n = [ å ait btj ].
t =1

§ Example

é1 0 4ù é14 4ù
ê2 é 2 4 ù
1 1 úú ê ê8 9 úú
ê ´ ê1 1 úú = ê
ê3 1 0ú ê7 13ú
ê ê
ú 3 0û ê ú ú
ë0 2 2û ë ë8 2 û

Discrete Structures 3-46

 Transposes and Powers of Matrices

§ Definition 5
§ The identity matrix of order n is the nⅹn matrix In = [d ij ], where d ij = 1 if i =
j and d ij = 0 if i ≠ j. Hence
é1 0 L 0ù
ê0 1 L 0 ú
ê. . . ú
In = ê ú
ê. . .ú
ê ú
ê . . . ú
êë0 0 L 1úû
§ Multiplying a matrix by an appropriately sized identity matrix does not change
this matrix (matrix A is mⅹn matrix).
AIn = ImA = A
§ Powers of square matrices can be defined. When A is an nⅹn matrix, we have
A0 = In, Ar = AAA . . . A.
r times

Discrete Structures 3-47

 § Definition 6
§ Let A = [aij] be an mⅹn matrix.
§ transpose of A, At, is the nⅹm matrix obtained by interchanging
the rows and columns of A.
§ if At = [bij] , then bij = aji for i = 1, 2, . . . , n and j = 1, 2, . . . , m.

§ Example
t é1 4 ù
é 1 2 3ù ê ú
ê 4 5 6ú = ê 2 5 ú
ë û ê
ë3 6 úû
§ Definition 7
§ A square matrix A is symmetric if A = At.
§ A = [aij] is symmetric if aij = aji for all i and j with i = 1, 2, . . . , n
and j = 1, 2, . . . , n.

Discrete Structures 3-48

 Zero-One Matrices

§ zero-one matrix: A matrix with entries that are either 0 or 1

§ The arithmetic is based on the Boolean operations ∧ and ∨.
b1 ∧ b2 = 1 if b1 = b2 = 1
0 otherwise,
b1 ∨ b2 = 1 if b1 = 1 or b2 = 1
0 otherwise,

§ Definition 8
§ Let A = [aij] and B = [bij] be mⅹn zero-one matrices.
§ The join of A and B is the zero-one matrix with (i, j)th entry aij ∨ bij.
A∨B
§ The meet of A and B is the zero-one matrix with (i, j)th entry aij ∧ bij.
A∧B

Discrete Structures 3-49

 § Definition 9
§ Let A = [aij] be an mⅹk zero-one matrix and B = [bij] be a kⅹn zero-one
matrix.
§ Boolean product of A and B, A ⊙ B , is the mⅹn matrix with (i, j)th entry cij
where
cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j ) ∨ . . . ∨ (aik ∧ bkj ).

§ Example: Boolean Product

é1 0ù é ù
ê0 1 ú é1 1 0ù ê ú
ê ú ê0 1 1 ú = ê ú
êë1 0úû ë û ê úû
ë

¤

Discrete Structures 3-50

 § Definition 10
§ Let A be a square zero-one matrix and let r be a positive integer.
§ The rth Boolean power of A is the Boolean product of r copies of A.

A[r] = A ⊙ A ⊙ A ⊙ . . . ⊙ A.
r times

§ We also define A[0] to be In.

Discrete Structures 3-51