Page 202 - Discrete Mathematics and Its Applications

2.6 Matrices 181

t
DEFINITION 6 Let A =[a ij ] be an m × n matrix. The transpose of A, denoted by A ,isthe n × m matrix
t
obtained by interchanging the rows and columns of A. In other words, if A =[b ij ], then
b ij = a ji for i = 1, 2,...,n and j = 1, 2,...,m.

⎡ ⎤
1 4
1 2 3
EXAMPLE 5 The transpose of the matrix is the matrix 2 5 ⎦ .
⎣
4 5 6 ▲
3 6
Matrices that do not change when their rows and columns are interchanged are often im-
portant.

t
DEFINITION 7 A square matrix A is called symmetric if A = A . Thus A =[a ij ] is symmetric if a ij = a ji
for all i and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n.

Note that a matrix is symmetric if and only if it is square and it is symmetric with respect to its
main diagonal (which consists of entries that are in the ith row and ith column for some i). This
symmetry is displayed in Figure 2.
⎡ ⎤
1 1 0
EXAMPLE 6 The matrix 1 0 1 ⎦ is symmetric. ▲
⎣
0 1 0
a ji

Zero–One Matrices
a ij

A matrix all of whose entries are either 0 or 1 is called a zero–one matrix. Zero–one matrices
FIGURE 2 A are often used to represent discrete structures, as we will see in Chapters 9 and 10. Algorithms
Symmetric Matrix. using these structures are based on Boolean arithmetic with zero–one matrices. This arithmetic
is based on the Boolean operations ∧ and ∨, which operate on pairs of bits, defined by

1 if b 1 = b 2 = 1
b 1 ∧ b 2 =
0 otherwise,
1 if b 1 = 1or b 2 = 1

b 1 ∨ b 2 =
0 otherwise.

DEFINITION 8 Let A =[a ij ] and B =[b ij ] be m × n zero–one matrices. Then the join of A and B is the
zero–one matrix with (i, j)th entry a ij ∨ b ij . The join of A and B is denoted by A ∨ B. The
meet of A and B is the zero–one matrix with (i, j)th entry a ij ∧ b ij . The meet of A and B is
denoted by A ∧ B.

EXAMPLE 7 Find the join and meet of the zero–one matrices

1 0 1 0 1 0
A = , B = .
0 1 0 1 1 0