Lab 11 : Matrix Inverses

In this lab, we will continue to write programs to carry out matrix operations. As we did last lab, we will implement matrices using lists of lists of numbers. For example,

$$\begin{split}\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\end{split}$$

will be implemented by

[[1, 2], [3 , 4]]

We view each list of numbers as a row of the matrix. We assume that every list of numbers (row) in a list of list of numbers (matrix) has the same length. We also assume that every matrix has at least one row and one column. You need not check for correct inputs when you write your programs.

In today’s lab, we will learn how to calculate the inverse of a $2\times 2$ matrix, when it exists. We will further learn how to calculate the inverse of a $2\times 2$ matrix when the entries are in the integers modulo $n$.

To simplify life, we will assume that all matrices in this lab are $2\times 2$.

0 Preliminaries

To run doctests, add the following to the bottom of your file:

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

1 Warm up

Exercise 0 Write a function that can print out a $2\times 2$ matrix.

def print_2x2(m):
    """
    >>> print_2x2([[1, 2],[4, 5]])
    1 2
    4 5

    """

2 Matrix Inverse

Exercise 1 Write a function that determines whether or not a $2\times 2$ matrix is invertible.

def invertible_2x2(m):
    """
    >>> invertible_2x2([[0, 1],[0, 1]])
    False
    >>> invertible_2x2([[1, 0],[0, 1]])
    True

    """

Exercise 2 Write a function to compute the inverse of a $2\times 2$ matrix. Use the formula from lecture (or the book).

def invert_2x2(m):
    """
    Assumes that m is invertible.

    >>> invert_2x2([[1, 2], [3, 4]])
    [[-2.0, 1.0], [1.5, -0.5]]

    """

3 Checking the inverse

Have we implemented the matrix inversion correctly? We will now test its correctness. To do so, we need a function to perform $2\times 2$ matrix multiplication.

Exercise 3 Write a function to compute the multiplication of two $2\times 2$ matrices.

def mult_2x2(m1, m2):
    """
    >>> mult_2x2([[1, 2], [3, 4]], [[-2.0, 1.0], [1.5, -0.5]])
    [[1.0, 0.0], [0.0, 1.0]]

    """

4 Modular arithmetic

To implement matrix inversion modulo n, we will make use of the basic operations of modular arithmetic.

Exercise 4 Write functions to calculate modular addition, subtraction and multiplication.

def add_mod(x, y, n):
    """
    >>> add_mod(23, 21, 26)
    18

    """

def sub_mod(x, y, n):
    """
    >>> sub_mod(23, 21, 26)
    2

    """

def mult_mod(x, y, n):
    """
    >>> mult_mod(23, 21, 26)
    15

    """

5 Modular inverse

Next we will calculate the multiplicative inverse of a number a in the integers modulo n, if it exists. Recall that this means we want to find an integer x such that $xa \equiv 1 \pmod{n}$. By definition, this amounts to asking for an integer x such that for some y, $xa + yn = 1$.

How do we find such x and y? The extended Euclidean algorithm was such a way. So to compute the inverse of a modulo n (if it exists), we just run the extended Euclidean algorithm and output x.

Here is a definition for a program which implements the extended Euclidean algorithm.

def ext_eucl(a, b):
    """Assume b > 0.

    >>> ext_eucl(20, 16)
    (4, 1, -1)
    """
    q = [0,0]
    r = [a,b]
    x = [1,0]
    y = [0,1]

    while r[-1] > 0:
        q.append(r[-2] // r[-1])
        r.append(r[-2] % r[-1])
        x.append(x[-2] - x[-1] * q[-1])
        y.append(y[-2] - y[-1] * q[-1])

    return (r[-2], x[-2], y[-2])

Exercise 5 Write a function to compute the multiplicative inverse. Use ext_eucl.

def inv_mod(x, n):
    """
    Assumes that x is invertible mod n.

    >>> inv(15, 4)
    3

    """

6 Matrix inverse modulo n

Now let’s compute the inverse of a $2\times 2$ matrix with entries in the integers modulo n, if it exists. If indeed the inverse does exist, we may compute it by adapting invert_2x2: simply replace the ordinary arithmetic operations in the definition of invert_2x2 with the corresponding modular operations.

Exercise 6 Write a function to compute the inverse of a $2\times 2$ matrix modulo n.

def invert_2x2_mod(matrix, n):
    """
    Assumes that (a*d - b*c) is invertible mod n.

    >>> invert_2x2_mod([[1, 2], [3, 4]], 7)
    [[5, 1], [5, 3]]

    """

7 Checking the matrix inverse mod n

Finally let’s check the correctness of this implementation of matrix inversion modulo n.

Exercise 7 Write a function which computes the multiplication of two $2\times 2$ matrices with entries in the integers modulo n. (Again, you may simply replace the ordinary arithmetic operations in mult_2x2 with the corresponding modular operations.)

def mult_2x2_mod(m1, m2, n):
"""
>>> mult_2x2_mod([[1, 2], [3, 4]], [[5, 1], [5, 3]], 7)
[[1, 0], [0, 1]]

"""