Python Program to Multiply Two Matrices
FreeOverview
In this blog post, we are going to learn about matrix multiplication and the various possible ways to perform matrix multiplication in Python. First, we will learn about some mathematical theory first to understand how matrix multiplication works, following which we will look at how to perform the same in Python, with and without using inbuilt or library functions. The version of Python used for code implementation in this article is Python 3.
Before reading this article, you should have some understanding of the following Python programming topics:
Introduction
Matrices are one of the most basic mathematical constructs widely used across various fields of mathematics, physics, engineering, and computer science etc. For example, matrices and their operations (multiplication and addition) are often used in deep learning and related statistical tasks to generate predictions based on inputs.
Matrix multiplication (first described in 1812 by Jacques Binet) is a binary operation that takes 2 matrices of dimensions (a×b) and (b×c) and produces another matrix, the product matrix, of dimension (a×c) as the output. Steps to multiply 2 matrices are described below. Though it may seem complicated at first, the method to multiply two matrices is very simple.
To obtain the product of two matrices A and B, that is AB:
-
Check that the first matrix, A, has the same number of rows as the number of columns present in the second matrix, B. That is, their dimensions must be of the form (a×b) and (b×c) respectively. If that is not the case, the matrices cannot be multiplied.
-
Initialize an empty product matrix C
-
Repeat the following for all i and j, 0<=i<a, 0<=j<b:
- Take the ith row from A and the jth row from B. Multiply their elements present at the same index. For example, multiply the first element of the ith row with the first element of the jth column, and so on.
- Take the sum of the products calculated in the previous step
- Put this sum at cell [i, j] of the product matrix C
- Just as a last check, make sure that the product matrix that was calculated has dimensions (a×c)
The following animation will help you understand the entire process visually:
IMPORTANT:
Matrix multiplication is not commutative. That is AB and BA are not necessarily equal. Moreover, many times it is also possible only one or none of these products is defined (because of constraints on dimensions discussed earlier).
For discussion in the further section(s), we will always consider A to be the first matrix, and B to be the second matrix, that is, we’ll be calculating the product C = AB.
Ways to Implement Matrix Multiplication in Python
Using Nested Loops
Nested loops are the simplest and slowest method with which we can implement the matrix multiplication program. Roughly speaking, we iterate over each row of the first matrix in the outer loop, then we iterate over each column of the second matrix in the second loop (present inside the first loop), and finally, we use another loop to perform the operation used to evaluate C[i][j] for a summation.
Algorithm:
- Store the matrix dimensions in different variables
- Check if the matrices are multiplication compatible. If no, terminate the program, otherwise continue.
- Iterate over the rows of matrix A using an index-variable i
- Inside the first loop, iterate over the columns of matrix B using the index-variable j
- Now initialize a variable curr_val to 0
- Create another loop iterating over the column dimension of A (or equivalently the row dimension of B) using a variable k
- For each iteration of the innermost loop, add the value of A[i][k]×B[k][j] to the variable curr_val
- After each iteration of the innermost loop, assign the value of curr_val to C[i][j]
A sample program is shown below using predefined matrices. The matrices can also be input by the user.
Output
Explanation:
Here our 2 matrices, A (3⨯3) and B (3⨯2) are first checked for dimension compatibility. Since they are in the form (a⨯b) and (b⨯c), they can be multiplied in the form AB. The triple nested for loop executes the algorithm described above to calculate the product matrix C = AB.
Using List Comprehensions
List comprehensions are a concise and more readable method for creating lists in python from some other iterables, like lists, tuples, strings, etc. List comprehension statement consists of 2 sub-expressions:
- The first sub-expression defines what will go in the list (for example, some transformation, such as increment by 1, on each element of the iterable).
- The second part is for actually fetching the data from the iterable which can be acted upon/ transformed/evaluated by the first part. This second part consists of one or more for statements combined with zero or more if statements.
A few examples will make it clear. The first part and the second part are highlighted with green and orange respectively:
- Increments = [x+3 for x in range(10)]
Output:
Explanation:
The orange sub-expression iterates over the numbers 0 to 9 using an iterator variable named x. The green sub-expression adds 3 to each such x and adds it to the resultant list Increments.
Important:
If the first sub-expression consists of tuples, then it must be parenthesized. For example, not using parentheses in the first sub-expression in the code snippet given below will result in an error.
Output:
Explanation:
The orange subexpression is like a nested for loop which generates all possible pairs (x,y) from the two given lists under the condition that x and y are different in value. Subsequently, the green sub-expression casts x and y to a tuple and adds them to the resultant list Coordinates.
Please note:
Code samples showing the multiplication of matrices, from now on, will not be checking for multiplication compatibility and will focus mainly on the implementation of the algorithm. Still, the programmer should always make this check while performing multiplication to avoid errors.
Before moving further along, one more thing which needs to be learnt is the zip() function in Python .
The zip() function, put simply, is used to group (or pack) and ungroup (or unpack) the data given in iterables (such as lists, tuples, strings, list of strings, etc), by index.
For example, during packing, all the data present at index 0 across all the input iterables will be combined into a single tuple, the data present at index 1 will be combined into another tuple and so on. All these tuples are then returned collectively in the form of a zip object. The reverse of this process is called unpacking. See the code examples for a better understanding.
Note:
If all the input iterables are not of the same length, then the shortest of all lengths is used by the function.
Example 1:
The Packing Operation
Input:
1 or more iterables (such as lists, tuples, strings, list of strings, etc.)
Output:
A zip object which can be type casted into lists or tuples for random access. Note that zip objects are also iterables, but they don’t provide random access.
Code:
Output:
Explanation:
Here, we have passed a list of lists and a list of strings as input. The zip function combines the elements of both the lists present at the same index into a single tuple. For example, the 0th element of mat ([1,2,3]) and the 0th element of mat2 (“aman”) are combined together into a single tuple : ([1, 2, 3], 'aman'). Similar operation is performed for all indices and finally a zip object is returned. For printing to the console, we convert it into a list.
Example 2:
The Unpacking Operation
Input:
A single argument,** an iterable consisting of iterable (for example, a list of lists, a tuple of lists, a list of strings, etc) along with “*” operator (see code)
Output:
A zip object which can be type casted into lists or tuples for random access.
Code:
Output:
Explanation:
A list of lists is given as input, and as the output, we get tuples which consist of the elements of the nested sublists taken out (unpacked) index wise. For instance, the 0th element of 1st sublist (3), the 0th element of 2nd sublist (12), and the 0th element of 3rd sublist (8), are all combined together to form the tuple (3, 12, 8). The same is done for all valid indices.
NOTICE:
In the above example for unzipping, we gave input of a row-wise matrix, and it returned tuples of columns. We are going to use this observation for matrix multiplication.
Having understood the list comprehensions and the zip function, let’s see how they can help us in implementing the matrix multiplication in Python:
Output:
Let’s understand the code bit by bit:
for A_row in A
This represents our movement from row to row in the first matrix in the product AB, that is A.
for B_col in zip(*B)
This iterates over the columns in B (because, as we saw earlier, zip(*B) returns columns)
Now we have each row in A and each column in B. Now we have to multiply their contents and sum over them.
zip(A_row, B_col)
Combine the elements of row and column into a single entity based on the index
for row_el, col_el in zip(A_row, B_col)
Taking tuples out from the single entity one by one
row_el*col_el
Multiply the contents of those tuples
sum(row_el*col_el for row_el, col_el in zip(A_row, B_col))
Sum over these products and assign them to the current list. This current list will form one row.
More such rows will be formed for all valid indices as the outermost for statement proceeds, filling the product matrix C.
Vectorization in Python
An important concept in Python which we should learn before moving on to the next method for implementing our matrix multiplication program is vectorization.
Vectorization refers to a process by which we execute loops without explicitly creating them. We use Numpy methods which take the advantage of pre-compiled and optimized C - code as well as some parallel processing (if the hardware allows it) to perform fast and efficient looping operations. Benchmarking on large data shows vectorization can yield significant improvement in performance as compared to conventional Python loop. It is highly recommended that readers check out the performance results of vectorization and their contrast with loops.
Methods for vectorization:
- Using numpy.vectorize() method
- Using matrix multiplication methods in numpy
As given in the documentation of numpy.vectorize()
“The vectorize function is provided primarily for convenience, not for performance. The implementation is essentially a for loop.”
Using vectorize() in a nested manner complicates the code, and hence should be avoided when it starts to hamper the readability. Since the matrix multiplication makes use of 3 nested loops, it is advisable to not use the np.vectorize() method for this purpose, and hence we would be implementing our code using the second method listed for vectorization.
Matrix Multiplication Using Numpy Library
NumPy is a Python library that is highly optimized to perform calculations on large, multi-dimensional arrays and matrices, and also provides a large collection of high-level mathematical functions to operate on these arrays. Thus it is not surprising that it should provide some functionality for such a basic matrix operation as multiplication.
The Numpy library provides 3 methods that are relevant to matrix multiplication and which we will be discussing ahead:
- numpy.matmul() method or the “@” operator
- numpy.dot()
- numpy.multiply() method
Numpy also provides some methods which are relevant to vector multiplications. We won’t be discussing these functions here. It is left to the reader to explore more about them:
- numpy.inner()
- numpy.outer()
It is important to remember that all the methods defined in the NumPy module are vectorized by implementation and therefore are much more efficient than pure Python loops. You should try to use them wherever you can to replace multiple for-loops.
numpy.matmul() or “@” operator
The matmul() method takes 2 multiplication compatible matrices and returns the product matrix directly. Although, for you to use the “@”, it is important that the operands must be already present in, or be explicitly typecast to the type numpy.array. The following code represents the above methods:
Code:
Output:
Explanation:
We have calculated the product AB using both numpy.matmul as well as @ operator. Notice the fact that we have cross-checked our claim that np.matmul() and @ operator give the same result (and hence are equivalent) using the assert statement on the resultant matrices, C1 and C2. Further notice that the output type of both the results is the same, that is np.ndarray.
numpy.dot() method
This method has various behaviors/use cases based on input parameters but is recommended that it should be used only when we want to have the dot product of 2 1D vectors.
Let us look at the documentation once:
The dot product of two arrays. Specifically,
- If both a and b are 1-D arrays, it is the inner product of vectors (without complex conjugation)
- If both a and b are 2-D arrays, it is matrix multiplication, but using matmul or a @ b is preferred.
- If either a or b is 0-D (scalar), it is equivalent to multiplying and using numpy.multiply(a, b) or a * b is preferred.
IMPORTANT:
For 2D matrices, both numpy.matmul() and numpy.dot() give exactly the same result. It is for higher dimension matrix multiplication that their answers differ.
Let us look at 2 ways we can code our matrix multiplication program using np.dot()
Code:
Output:
Notice that we have used the assert statement again to confirm the fact that both C1 and C2 are equal matrices, and therefore, cross checking our claim that for 2D arrays, they behave exactly the same. Here we have used the numpy.dot() method in yet another way to calculate the product of matrices A and B.
Code:
Output:
Notice the difference in the type of the resultant matrices in the first and second code samples, although the matrices themselves are the same in terms of cell-values.. The second method makes use of the fact that C[i][j] is that dot product of the ith row of A and the jth column of B.
Finally, one method worth mentioning here (although it bears little relevance to our topic) is the np.multiply method.
C. numpy.multiply()
This method does not perform the usual matrix multiplication (refer the code examples). This method works only when the operands are
- Scalar and a matrix
- 2 matrices with the same dimensions
In the first case, this method multiplies the scalar with each element of the matrix, as shown in the output C of the code given below.
In the second case, this method computes what is called the Hadamard Product, a matrix consisting of element wise products of two matrics A and B. That is, C[i][j] = A[i][j]*B[i][j] for all valid i and j, where C is the Hadamard product matrix.
In any other case, it will result in an error.
The following code snippet shows the execution of these cases:
Code:
Output:
Another interesting point to note is that similar to the np.dot() operation, np.multiply() operation can also be substituted with an “*” operator. But here too, the operands must be of the NumPy array types or must be explicitly typecast into it. Failing to meet this condition will result in an error when using this operator. Let us look at the code sample given below to understand its usage:
Code:
Also notice that the type of both the outputs, C and D, is still the same and is numpy.ndarray
Output:
Conclusion
Let us recapitulate all the points about matrix multiplication in Python we learned in the article.
- Matrix multiplication is a binary operation on two matrices which yields yet another matrix, which is referred to as the product matrix.
- Matrix multiplication can only take place between compatible matrices and also that it is not commutative in nature.
- For performing the matrix multiplication of matrices A and B in Python without using any in-built functions or library functions, we iterate over all the rows of A, and all the columns of B, and find the sum of their element wise products.
- To get rid of the nested for loops, we can use the zip function in Python which helps us perform the same task as above in a lesser amount of code.
- List comprehension is yet convenient method to perform matrix multiplication in Python as compared to the nested loop method
- List comprehensions are generally faster for list creation than the zip method, but not in the case when computations are involved.
- Matrix multiplication in Python can also be done much more efficiently using numpy library methods, namely:
- numpy.matmul()
- numpy.dot()
- numpy.multiply()
To write simple and readable code and to make the program efficient, it is recommended to use NumPy library methods over writing your own code to multiply the matrices.
On a closing note, the reader should again understand the importance of vectorization in Python as well as the need to replace for-loops NumPy vectorized methods as and when possible.