Multiplication of Two Matrices

Difficulty Level Easy
Frequently asked in Amazon Apple Facebook Wish
Array MatrixViews 2512

Problem Statement

In the “Multiplication of Two Matrices” problem we have given two matrices. We have to multiply these matrices and print the result or final matrix. Here, the necessary and sufficient condition is the number of columns in A should be equal to the number of rows in matrix B. If this condition not true then we can’t multiply these matrices.

Input Format

The first line containing four integer values r1, c1, r2, c2. Where r1 and c1 denote the number of rows and columns of the first matrix. And r2, c2 denotes the number of rows, columns of the second matrix.

Next r1 lines containing c1 integer values.

And next r2 lines containing c2 integer values.

Output Format

Print the final matrix after multiplication in such a way every row starts from the new line and every element separated by space in each row.

Constraints

  • 1<=r1, c1, r2, c2<=2000.
  • 1<= |m[i][j]| <=10^9 where m is the matrix and the position of element at ith row and jth column.

Example

4 4 4 4
1 1 1 1
1 6 7 6
6 3 7 12
4 4 4 4
1 1 1 1
2 2 2 2
3 3 3 3
4 9 1 7
10 15 7 13
58 88 40 76
81 141 45 117
40 60 28 52

Explanation: In the above example, we got the first element in output by multiplying all the respective elements in the first row of matrix A with the elements in the first column of matrix B and adding them. Similarly, for the second element in the first row of the output, we need to take the first row of matrix A and the second column of matrix B. In this way, we got all the elements in the output matrix.

Below is the random example for matrix multiplication.

Multiplication of Two Matrices

Algorithm for Multiplication of Two Matrices

1. Simply run three loops.
2. Loop for each row in matrix A with variable i.
3. Inside the above loop, Loop for each column in matrix B with variable j.
4. Inside the above two loops, Loop for each row element in matrix A with variable k and each column element in matrix B with variable k  ie, A[i][k] and B[k][j].
5. we will find the product of each row element in A with each column element in B. ie, A[i][k] * B[k][j] and add all the products and store in new matrix C ie, C[i][j].
6. matrix C is the multiplication output.

Implementation

C++ Program for Multiplication of Two Matrices

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    int a[r1][c1];
    int b[r2][c2];
    if(c1!=r2)
    {
        cout<<"We can’t multiply these matrices.";
    }
    else
    {
    for(int i=0;i<r1;i++)
    {
        for(int j=0;j<c1;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=0;i<r2;i++)
    {
        for(int j=0;j<c2;j++)
        {
            cin>>b[i][j];
        }
    }
    int c[r1][c2];
    for(int i=0; i <r1; i++)
    {
        for(int j=0; j<c2; j++)
        {
            int sum = 0;
            for(int k=0;k<c1;k++)
            {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum;
            cout<<c[i][j]<<"  ";
        }
        cout<<endl;
    }
    }
    return 0;
}

Java Program for Multiplication of Two Matrices

import java.io.*; 
import java.util.Scanner;

class TutorialCup
{
    // Function to print Matrix 
    static void print_matrix(int output[][], int r, int c) 
    { 
        for(int i=0;i<r;i++) 
        { 
            for(int j=0;j<c;j++)
            {
                System.out.print(output[i][j] + " "); 
            }
            System.out.println(); 
        } 
    } 
    // Function to multiply two matrices a[][] and b[][] 
    static void multiply(int r1, int c1, int r2, int c2, int a[][], int b[][]) 
    { 
        int i, j, k; 
        // Check if multiplication is Possible 
        if(r2!=c1) 
        { 
            System.out.println("\nWe can’t multiply these matrices."); 
            return; 
        } 
        // Matrix to store the result 
        //The product matrix will be of size row1 x col2 
        int c[][] = new int[r1][c2];  
        // Multiply the two marices 
        for(i=0;i<r1;i++) 
        { 
            for(j=0;j<c2;j++) 
            { 
                for(k=0;k<r2;k++) 
                {
                    c[i][j]+=a[i][k]*b[k][j];
                } 
            } 
        } 
        print_matrix(c,r1,c2); 
    } 
    // Driver code 
    public static void main(String[] args) 
    { 
        int r1,c1,r2,c2;
        Scanner inp = new Scanner(System.in);
        r1 = inp.nextInt();
        c1 = inp.nextInt();
        r2 = inp.nextInt();
        c2 = inp.nextInt();
        int a[][] = new int[r1][c1];
        for(int i=0;i<r1;i++)
        {
            for(int j=0;j<c1;j++)
            {
                a[i][j]=inp.nextInt();
            }
        }
        int b[][] = new int[r2][c2];
        for(int i=0;i<r2;i++)
        {
            for(int j=0;j<c2;j++)
            {
                b[i][j]=inp.nextInt();
            }
        }
        multiply(r1,c1,r2,c2,a,b); 
    } 
}
2 3 3 2
1 2 3
4 5 6
7 8
9 10
11 12
58 64 
139 154

Complexity Analysis for Multiplication of Two Matrices

Time Complexity

O(n^3) where n is the maximum of r1,c2, and r2. Here we simply run three loops first loop run r1 times, the second loop runs c2 times, and the final loop runs r2 times.

Space Complexity

O(m*m) where m is the maximum of r1 and c2. Here we create extra space for storing the result of the multiplication of matrices. Here we also declared r1*c1 size for taking input the first matrix and r2*c2 size for taking input the second matrix.

Reference

Translate »