Section 2.
6
Section Summary
! Definition of a Matrix
! Matrix Arithmetic
! Transposes and Powers of Arithmetic
! Zero-One matrices
Matrices
! Matrices are useful discrete structures that can be used in many
ways. For example, they are used to:
! describe certain types of functions known as linear transformations.
! Express which vertices of a graph are connected by edges (see
Chapter 10).
! In later chapters, we will see matrices used to build models of:
! Transportation systems.
! Communication networks.
! Algorithms based on matrix models will be presented in later
chapters.
! Here we cover the aspect of matrix arithmetic that will be needed
later.
Matrix
Definition: 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.
3 2 matrix
Notation
! Let m and n be positive integers and let
! The ith row of A is the 1 n matrix [ai1, ai2,…,ain]. The jth
column of A is the m 1 matrix:
! The (i,j)th element or entry of A is the
element aij. We can use A = [aij ] to denote the matrix with
its (i,j)th element equal to aij.
Matrix Arithmetic: Addition
Defintion: Let A = [aij] and B = [bij] be m n matrices.
The sum of A and B, denoted by A + B, is the m n
matrix that has aij + bij as its (i,j)th element. In other
words, A + B = [aij + bij].
Example:
Note that matrices of different sizes can not be added.
Matrix Multiplication
Definition: Let A be an n k matrix and B be a k n
matrix. The product of A and B, denoted by AB, is the
m n matrix that has its (i,j)th element equal to the sum of
the products of the corresponding elments from the ith row
of A and the jth column of B. In other words, if AB = [cij]
then cij = ai1b1j + ai2b2j + … + akjb2j.
Example:
The product of two matrices is undefined when the number
of columns in the first matrix is not the same as the number
of rows in the second.
Illustration of Matrix Multiplication
! The Product of A = [aij] and B = [bij]
Matrix Multiplication is not
Commutative
Example: Let
Does AB = BA?
Solution:
AB ≠ BA
Identity Matrix and Powers of Matrices
Definition: The identity matrix of order n is the m n
matrix In = [δij], where δij = 1 if i = j and δij = 0 if i≠j.
AIn = ImA = A
when A is an m n matrix
Powers of square matrices can be defined. When A is an
n × n matrix, we have:
A0 = In Ar = AAA∙∙∙A
r times
Transposes of Matrices
Definition: Let A = [aij] be an m n matrix. The
transpose of A, denoted by 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.
Transposes of Matrices
Definition: A square matrix A is called symmetric if
A = At. Thus A = [aij] is symmetric if aij = aji for i and j
with 1≤ i≤ n and 1≤ j≤ n.
Square matrices do not change when their rows and
columns are interchanged.
Zero-One Matrices
Definition: A matrix all of whose entries are either 0
or 1 is called a zero-one matrix. (These will be used in
Chapters 9 and 10.)
Algorithms operating on discrete structures
represented by zero-one matrices are based on
Boolean arithmetic defined by the following Boolean
operations:
Zero-One Matrices
Definition: Let A = [aij] and B = [bij] be an m × n
zero-one matrices.
! The join of A and B is the zero-one matrix with (i,j)th
entry aij ∨ bij. The join of A and B is denoted by A ∨ B.
! The meet of of A and B is the zero-one matrix with
(i,j)th entry aij ∧ bij. The meet of A and B is denoted
by A ∧ B.
Joins and Meets of Zero-One Matrices
Example: Find the join and meet of the zero-one
matrices
Solution: The join of A and B is
The meet of A and B is
Boolean Product of Zero-One Matrices
Definition: Let A = [aij] be an m k zero-one
matrix and B = [bij] be a k n zero-one matrix. The
Boolean product of A and B, denoted by A ⊙ B, is the
m n zero-one matrix with(i,j)th entry
cij = (ai1 ∧ b1j)∨ (ai2 ∧ b2j) ∨ … ∨ (aik ∧ bkj).
Example: Find the Boolean product of A and B, where
Continued on next slide !
Boolean Product of Zero-One Matrices
Solution: The Boolean product A ⊙ B is given by
Boolean Powers of Zero-One Matrices
Definition: 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 factors of A, denoted
by A[r] . Hence,
We define A[r] to be In.
(The Boolean product is well defined because the
Boolean product of matrices is associative.)
Boolean Powers of Zero-One Matrices
Example: Let
Find An for all positive integers n.
Solution:
