# Exercise 1: Determinant of a matrix

``````

In [36]:

def get_submatrix(m, i=None, j=None):
'''
This function returns a submatrix for a given matrix
which does not contain the row i and/or column j.

>>> get_submatrix([[1,2,3],[4,5,6],[7,8,9]], 1, 1)
[[1, 3], [7, 9]]

>>> get_submatrix([[2, 5], [2, 5]], 0, 0)
[[5]]

>>> get_submatrix([[1,2,3],[4,5,6],[7,8,9]], i=1)
[[1, 2, 3], [7, 8, 9]]

>>> get_submatrix([[1,2,3],[4,5,6],[7,8,9]], j=1)
[[1, 3], [4, 6], [7, 9]]
'''

# Remove row
if type(i) == int:
m = m[:i] + m[i+1:]
# Remove col
if type(j)==int:
m = [row[:j]+row[j+1:] for row in m]

return m

def matrix_det(m):
'''
This function returns the determinant of a given
square matrix.

>>> matrix_det([[1,2,3],[4,5,6],[7,8,9]])
0

>>> matrix_det([[1,3],[7,9]])
-12

>>> matrix_det([[1,2,3,4,6],[2,2,3,4,5],[1,3,3,4,5], \
[1,2,4,4,5],[1,2,3,5,5]])
16
'''
i = len(m)
j = len(m[0])
assert i == j, 'Matrix is not a square matrix.'

if i == 1:
return m[0][0]

return sum([m[0][ind]*(-1)**(0+ind)*
matrix_det(get_submatrix(m,i=0,j=ind))
for ind in range(j)])

if __name__ == '__main__':
import doctest
doctest.testmod()

``````

# Exercise 2: Strassen matrix multiplication

``````

In [115]:

def matrix_sub(a, b):
'''
This funciton returns the difference of matrix a minus matrix b

>>> matrix_sub([[1,2],[3,4]],[[1,2],[3,4]])
[[0, 0], [0, 0]]

'''

assert len(a) == len(b) ,\
'Matrices a and b have to have the same dimensions'
assert len(a[0]) == len(b[0]) , \
'Matrices a and b have to have the same dimensions'

m = len(a)
n = len(a[0])

return [[a[i][j] - b[i][j] for j in range(n)]
for i in range(m)]

'''
This function returns the sum of two matrices a and b.

[[2, 4], [6, 8]]

'''

assert len(a) == len(b) ,\
'Matrices a and b have to have the same dimensions'
assert len(a[0]) == len(b[0]) , \
'Matrices a and b have to have the same dimensions'

m = len(a)
n = len(a[0])

return [[a[i][j] + b[i][j] for j in range(n)]
for i in range(m)]

def matrix_get_part(m, i, j, a, b):
'''
This function returns a part of a given matrix which is defined
by the coordinates i and j and the x and y size of the part (a and b).

>>> matrix_get_part([[1,2,2,1], \
[3,4,5,4], \
[1,3,4,5], \
[3,4,5,4]], 2, 2, 2, 2)
[[4, 5], [5, 4]]
'''
# Remove row
if type(i) == int:
m = m[i:i+a]
# Remove col
if type(j)==int:
m = [row[j:j+b] for row in m]

return m

def matrix_split(m):
'''
This function splits a square matrix into four parts
and returns the parts in a list.

>>> matrix_split([[1,2],[3,4]])
[[[1]], [[2]], [[3]], [[4]]]

'''
len_m = len(m)
mid = len_m // 2
splitted = []

splitted.append(matrix_get_part(m, 0, 0, mid, mid))
splitted.append(matrix_get_part(m, 0, mid, mid, len_m))
splitted.append(matrix_get_part(m, mid, 0, len_m, mid))
splitted.append(matrix_get_part(m, mid, mid, len_m, len_m))

return splitted

def matrix_concat(a, b, axis=0):
'''
This function concatenates two 2D matrices horizontally (default)
or vertically if you set axis=1

>>> a = [[1,2],[3,4]]
>>> b = [[1,2],[3,4]]
>>> matrix_concat(a,b, axis=0)
[[1, 2, 1, 2], [3, 4, 3, 4]]

>>> matrix_concat(a,b, axis=1)
[[1, 2], [3, 4], [1, 2], [3, 4]]
'''

assert axis in [0,1]
if axis==0:
return [x[0] + x[1] for x in zip(a,b)]
if axis==1:
return a[:] + b[:]

def matrix_mul(a,b):
'''
This function multiplies two matrices a and b.

>>> matrix_mul([[3,2],[4,5]], [[1,-1],[-2,-3]])
[[-1, -9], [-6, -19]]

>>> matrix_mul([[2,0,-1],[3,4,5]], [[4,1],[5,0],[-2,-1]])
[[10, 3], [22, -2]]

>>> matrix_mul([[1,2,4],[2,1,3]], [[1,2,3],[8,3,2],[2,1,4]])
[[25, 12, 23], [16, 10, 20]]
'''
assert len(a[0]) == len(b)
mout = []

m = len(a)      # Len of rows (a)
n = len(b[0])   # Len of cols (b)

for x in range(m):

colres =[]
for y in range(n):
row = [e for e in a[x]]
col = [e[y] for e in b]
num = sum([q*w for q,w in zip(row, col)])
#print(num)
colres.append(num)

mout.append(colres)

return mout

def matrix_mul_strassen(a, b):
'''
This function multiplies two matrices a and b using the
Strassen algorithm.

>>> matrix_mul_strassen([[3,2],[4,5]], [[1,-1],[-2,-3]])
[[-1, -9], [-6, -19]]

>>> matrix_mul_strassen([[2,0,-1],[3,4,5]], [[4,1],[5,0],[-2,-1]])
[[10, 3], [22, -2]]

>>> matrix_mul_strassen([[1,2,4],[2,1,3]], [[1,2,3],[8,3,2],[2,1,4]])
[[25, 12, 23], [16, 10, 20]]

'''

if (len(a) % 2 != 0 or
len(a) != len(a[0]) or
len(b) != len(b[0])):
return matrix_mul(a,b)

a11, a12, a21, a22 = matrix_split(a)
b11, b12, b21, b22 = matrix_split(b)

m3 = matrix_mul_strassen(a11, matrix_sub(b12,b22))
m4 = matrix_mul_strassen(a22, matrix_sub(b21,b11))

return matrix_concat(matrix_concat(c11, c12, axis=0),
matrix_concat(c21, c22, axis=0),
axis=1)

if __name__ == '__main__':
import doctest
doctest.testmod()

``````