In this lab, youll be writing several functions that perform operations on Boolean matrices. Well use 2D lists (lists of

lists) in Python to represent matrices. For example, the matrix
0 0 ?? =[1 1 0 1	1 0] 0

would be represented in Python as:

M= [ [0, 0, 1], [1, 1, 0], [0, 1, 0] ]

1. (5 pts) Write a function matrix_print(A) that prints the elements of A in matrix format. You may assume that A is a 2D list containing only 0s and 1s. This function should only print (not return) the elements.

Example: Let

R = [ [0, 0, 0, 1], [0, 1, 1, 0], [0, 0, 0, 1], [0, 0, 1, 0] ]

Then calling matrix_print(R) should display

0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0

2. (6 pts) Write a function matrix_add_boolean(A, B) that adds the two matrices A and B using Boolean arithmetic and returns the result. You may assume that A and B are both 2D lists containing only 0s and 1s, and they are of compatible dimensions for addition.

Example: Let

A = [ [0, 1], [1, 0] ] B = [ [1, 0], [1, 0] ]

Then calling matrix_add_boolean(A, B) should return

[ [1, 1], [1, 0] ]

3. (8 pts) Write a function matrix_multiply_boolean(A, B) that multiplies the two matrices A and B using Boolean arithmetic and returns the result. You may assume that A and B are both 2D lists containing only 0s and 1s, and they are of compatible dimensions for multiplication.

Example: Let

A = [ [0, 1, 1], [1, 0, 1] ] B = [ [1, 0], [0, 0], [0, 1] ]

Then calling matrix_multiply_boolean(A, B) should return

[ [0, 1], [1, 1] ]

4. (5 pts) Write a function matrix_power(A, n) that computes the power Aⁿ using Boolean arithmetic and returns the result. You may assume that A is a 2D list containing only 0s and 1s, A is square (same number of rows and columns), and n is an integer ? 1. You should call your previously written matrix_multiply_boolean function.

Example: Let

R = [ [0, 0, 0, 1], [0, 1, 1, 0], [0, 0, 0, 1], [0, 0, 1, 0] ]

Then calling matrix_power(R, 2) should return

[ [0, 0, 1, 0], [0, 1, 1, 1], [0, 0, 1, 0], [0, 0, 0, 1] ]

5. (5 pts) Write a function transitive_closure(A) that computes and returns the transitive closure A⁺. You may assume that A is a 2D list containing only 0s and 1s, and A is square (same number of rows and columns). You should call your previously written matrix_add_boolean and matrix_power functions.

Example: Let

R = [ [0, 0, 0, 1], [0, 1, 1, 0], [0, 0, 0, 1], [0, 0, 1, 0] ]

Then calling transitive_closure(R) should return

[ [0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1] ]

Be sure to thoroughly test your functions after youve written them! You can use the matrix_print function to make your results easier to read.

Hints:

The identity matrix is the n ? n matrix consisting of 1s down the principal diagonal (where the row and column

numbers are the same) and 0s everywhere else. For example, the 3 ? 3 identity matrix is

1 0 0

[0 1 0]

0 0 1

Multiplying the identity matrix by any matrix A of the same dimensions results in A itself.

Given a 2D list A:

len(A₎ returns the number of rows in A

len(A[i]) returns the number of columns in row i of A

If A contains the same number of columns in every row (which we are assuming for this lab), _len(A[0])returns the number of columns in A

To create a 2D list A with r rows and c columns, where every element is initialized to 0, you can use this syntax:

A = [ [0]*c for i in range(r) ]