Page 204 - Discrete Mathematics and Its Applications

2.6 Matrices 183

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 factors of A. The rth Boolean product of A is denoted by A .
[r]
Hence

A [r] = A A A ··· A.

r times
(This is well defined because the Boolean product of matrices is associative.) We also define
A [0] to be I n .

⎡ ⎤
0 0 1
EXAMPLE 9 Let A = ⎣ 1 0 0 ⎦ . Find A [n] for all positive integers n.
1 1 0

Solution: We find that
⎡ ⎤
1 1 0
A [2] = A A = ⎣ 0 0 1 ⎦ .
1 0 1

We also find that

⎡ ⎤ ⎡ ⎤
1 0 1 1 1 1
A [3] = A [2] A = ⎣ 1 1 0 ⎦ , A [4] = A [3] A = ⎣ 1 0 1 ⎦ .
1 1 1 1 1 1

Additional computation shows that

⎡ ⎤
1 1 1
A [5] = ⎣ 1 1 1 ⎦ .
1 1 1

The reader can now see that A [n] = A [5] for all positive integers n with n ≥ 5. ▲

Exercises

⎡ ⎤
1 1 1 3 −1 0 5 6
b) A = ,
2 0 4 6 . −4 −35 −2
⎦
1. Let A = ⎣
1 1 3 7
−3 9 −3 4
a) What size is A? B = 0 −2 −12 .
b) What is the third column of A?
c) What is the second row of A? 3. Find AB if

d) What is the element of A in the (3, 2)th position? a) A = 2 1 , B = 0 4 .
t
e) What is A ? 32 1 3
⎡ ⎤
2. Find A + B, where 1 −1
⎡ ⎤ 3 −2 −1
1 0 4 b) A = ⎣ 0 1 ⎦ , B = 1 0 2 .
a) A = ⎣ −1 2 2 ⎦ , 2 3
0 −2 −3 ⎡ 4 −3 ⎤

⎡ ⎤ ⎢ 3 −1 3 2 −2
−1 3 5 c) A = ⎣ 0 −1⎥ 0 −1 4 −3 .
⎦ , B =
−2
B = ⎣ 2 2 −3 ⎦ . −1 5
2 −3 0