s
Section 5.7 Matrices
467
48. For Boolean matrices
a = £
0 0 1
1 1 0
1 0 0
§
b = £
0 1 1
0 0 0
1 0 0
§
find a ` b, a ~ b, a × b, and b × a.
49. For Boolean matrices
a = £
0 1 0
1 0 1
0 0 1
§
b = £
0 1 1
0 0 1
1 0 0
§
find a ` b, a ~ b, a × b, and b × a.
50. For Boolean matrices
a = £
1 1 0
0 1 1
0 0 1
§ b = £
1 0 1
0 1 1
1 1 1
§
find a ` b, a ~ b, a × b, and b × a.
51. For Boolean matrices a and b, can it ever be the case that a ~ b = a ` b? If so, when?
52. For Boolean matrices a and b, prove that a ~ b = b ~ a and that a ` b = b ` a.
53. How many distinct symmetric n × n Boolean matrices are there?
54. Strassen’s algorithm reduces the amount of work to compute the product of two n × n matrices of sufficient size. For simplicity, assume that n = 2
m
for some m ≥ 0. First consider a simple case of multiplying
two 2 × 2 matrices.
a = c
a 11 a 12
a 21 a 22
d
b = c
b 11 b 12
b 21 b 22
d
The product
C = c
a 11 b 11 + a 12 b 21 a 11 b 12 + a 12 b 22
a 21 b 11 + a 22 b 21 a 21 b 12 + a 22 b 22
d
(1)
can also be written (check the calculations) as
C = c
p 1 + p 4 − p 5 + p 7
p 3 + p 5
p 2 + p 4
p 1 + p 3 − p 2 + p 6
d
(2)
where
p 1 = (a 11 + a 22 )(b 11 + b 22 )
p 2 = (a 21 + a 22 )b 11
p 3 = a 11 (b 12 − b 22 )
p 4 = a 22 (b 21 − b 11 )
p 5 = (a 11 + a 12 )b 22
p 6 = (a 21 − a 11 )(b 11 + b 12 )
p 7 = (a 12 − a 22 )(b 21 + b 22 )