Matrix Multiplication in C

«
»

Matrix multiplication is a technique of producing a single matrix from two matrices by multiplying them together.

Constraint: For Multiplication of two matrices, the columns of the first matrix must be equal to the rows of the second matrix.

Suppose the first matrix is of the order of [m ,n], so the second matrix should be of the order of [n ,p], else the two matrices can’t be multiplied. The new matrix produced in the above case would be of the order of [m,p].

Examples:

If the first matrix is of order [1,3] and second is of order [3,5], the two matrices can be multiplied together and the new matrix will be of order [1,5]. However, if the first matrix is of order [1,3] and the second is of order [1,5], they cannot be multiplied together.

Example 1:

\( \begin{bmatrix}
1 & 3\\
4 & 2
\end{bmatrix}\) * \( \begin{bmatrix}
1 & 2\\
2 & 1
\end{bmatrix}\) = \( \begin{bmatrix}
1*1 + 3*2 & 1*2 + 3*1\\
4*1 + 2*2 & 4*2 + 2*1
\end{bmatrix}\) = \( \begin{bmatrix}
7 & 5\\
8 & 10
\end{bmatrix}\)

advertisement
advertisement

Example 2:

\( \begin{bmatrix}
1 & 4 & 2\\
3 & 3 & 2
\end{bmatrix}\) * \( \begin{bmatrix}
1\\
2\\
3
\end{bmatrix}\) = \( \begin{bmatrix}
1*1 + 4*2 + 2*3\\
3*1 + 3*2 + 2*3
\end{bmatrix}\) = \( \begin{bmatrix}
15\\
15
\end{bmatrix}\)

Problem Description

Write a C program for multiplication of two matrices.

Problem Solution

There are Several ways to perform matrix multiplication in C. Let us look at two of the approaches:

Method 1: Matrix Multiplication in C using Iterative Approach

The idea is to find all the elements of the multiplied matrix by iterating over the row of the first matrix and column of the second matrix. For example, for finding the element at [0,0], we will multiply the first row elements in the first matrix to the corresponding first column matrix in the second matrix.

Program/Source Code

Here is the source code of the C program to perform matrix multiplication. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C program to perform matrix multiplication using iterative
  3.  */
  4. #include<stdio.h>    
  5. int main()
  6. {
  7.     int r1,r2,c1,c2;
  8.     printf("Enter number of rows for First Matrix:\n");    
  9.     scanf("%d",&r1);    
  10.     printf("Enter number of columns for First Matrix:\n");     
  11.     scanf("%d",&c1); 
  12.     printf("Enter number of rows for Second Matrix:\n");    
  13.     scanf("%d",&r2);    
  14.     printf("Enter number of columns for Second Matrix:\n");     
  15.     scanf("%d",&c2);
  16.     if(c1!=r2)
  17.     {
  18.         printf("Matrices Can't be multiplied together");
  19.     }
  20.     else
  21.     {
  22.         int m1[r1][c1],m2[r2][c2];
  23.         printf("Enter first matrix elements \n");    
  24.         for(int i=0;i<r1;i++)    
  25.         {    
  26.             for(int j=0;j<c1;j++)    
  27.             {    
  28.                 scanf("%d",&m1[i][j]);    
  29.             }    
  30.         }    
  31.         printf("Enter Second matrix elements\n");    
  32.         for(int i=0;i<r2;i++)    
  33.         {    
  34.             for(int j=0;j<c2;j++)    
  35.             {    
  36.                 scanf("%d",&m2[i][j]);    
  37.             }    
  38.         }    
  39.         int mul[r1][c2];
  40.         for(int i=0;i<r1;i++)    
  41.         {    
  42.             for(int j=0;j<c2;j++)    
  43.             {    
  44.                 mul[i][j]=0; 
  45.  
  46.                 // Multiplying i’th row with j’th column
  47.                 for(int k=0;k<c1;k++)    
  48.                 {    
  49.                     mul[i][j]+=m1[i][k]*m2[k][j];    
  50.                 } 
  51.             }    
  52.         }    
  53.         printf("Multiplied matrix\n");     
  54.         for(int i=0;i<r1;i++)    
  55.         {    
  56.             for(int j=0;j<c2;j++)    
  57.             {    
  58.                 printf("%d\t",mul[i][j]);    
  59.             }    
  60.             printf("\n");    
  61.         } 
  62.     }
  63.     return 0;  
  64. }
Program Explanation

1. Input the size of both matrices
2. If matrix can’t be multiplied print that they can’t be multiplied
3. Else, take input of elements of both matrices
4. Declare a resultant matrix
5. Fill the matrix using formula mul[i][j]+=m1[i][k]*m2[k][j].
6. Print the multiplied matrix.

advertisement

Example:
Given, first Matrix = \( \begin{bmatrix}
1 & 3\\
5 & 6
\end{bmatrix}\), second matrix = \( \begin{bmatrix}
2 & 1\\
4 & 4
\end{bmatrix}\)

Multiplied Matrix = \( \begin{bmatrix}
1 & 3\\
5 & 6
\end{bmatrix}\) * \( \begin{bmatrix}
2 & 1\\
4 & 4
\end{bmatrix}\) = \( \begin{bmatrix}
1*2 + 3*4 & 1*1 + 3*4\\
5*2 + 6*4 & 5*1 + 6*4
\end{bmatrix}\) = \( \begin{bmatrix}
14 & 13\\
34 & 29
\end{bmatrix}\)

Time Complexity: O(r1*c1*c2)
While finding elements of multiplied matrix, we use two loops for iterating over all elements of matrix and one loop to find the elements, so O(r1*c1*c2).

Space Complexity: O(r1*c1 + r2*c2 + r1*c2)
Since 3 matrices are used, so complexity is O(r1*c1 + r2*c2 + r1*c2).

Runtime Testcases

Testcase 1: In this case, the columns of the first matrix must be equal to the rows of the second matrix.

advertisement
 
Enter number of rows for First Matrix:
2
Enter number of columns for First Matrix:
2
Enter number of rows for Second Matrix:
2
Enter number of columns for Second Matrix:
2
Enter first matrix elements 
1 3
5 6
Enter Second matrix elements
2 1 
4 4
Multiplied matrix
14	13	
34	29

Testcase 2: In this case, the columns of the first matrix are not equal to the rows of the second matrix.

 
Enter number of rows for First Matrix:
3
Enter number of columns for First Matrix:
4
Enter number of rows for Second Matrix:
1
Enter number of columns for Second Matrix:
2
Matrices Can't be multiplied together

Method 2: Matrix Multiplication in C using Recursive Approach

In the recursive approach, we will use function calls to find the elements of the multiplied matrix.

Program/Source Code

Here is the source code of the C program to perform matrix multiplication using Recursive approach. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C program to perform matrix multiplication using recursive
  3.  */
  4. #include<stdio.h>
  5. #define m 100
  6. void multiply (int r1, int c1, int m1[m][m], int r2, int c2, int m2[m][m], int mul[m][m])
  7. {
  8.     //Declaring Static because we want them to same in all function calls
  9.     static int i = 0, j = 0, k = 0;
  10.  
  11.     if (i >= r1)
  12.     {
  13.         return;
  14.     }
  15.     else if (i < r1)
  16.     {
  17.         if (j < c2)
  18.         {
  19.             if (k < c1)
  20.             {
  21.                 mul[i][j] += m1[i][k] * m2[k][j];
  22.                 k++;
  23.                 //Function call for multiplying all row element with column element
  24.                 multiply(r1, c1, m1, r2, c2, m2, mul);
  25.             }
  26.             k = 0;
  27.             j++;
  28.             //Function call for all elements of row of multiplied matrix
  29.             multiply(r1, c1, m1, r2, c2, m2, mul);
  30.         }
  31.         j = 0;
  32.         i++;
  33.         //Function call for all rows
  34.         multiply(r1, c1, m1, r2, c2, m2, mul);
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40.     int r1,r2,c1,c2;
  41.     printf("Enter number of rows for First Matrix:\n");    
  42.     scanf("%d",&r1);    
  43.     printf("Enter number of columns for First Matrix:\n");     
  44.     scanf("%d",&c1); 
  45.     printf("Enter number of rows for Second Matrix:\n");    
  46.     scanf("%d",&r2);    
  47.     printf("Enter number of columns for Second Matrix:\n");     
  48.     scanf("%d",&c2);
  49.     if(c1!=r2)
  50.     printf("Multiplication Not Possible");
  51.     else
  52.     {
  53.         int m1[m][m], m2[m][m], mul[m][m] = {0};
  54.         printf("Enter first matrix elements \n");
  55.         for(int i=0;i<r1;i++)    
  56.         {    
  57.             for(int j=0;j<c1;j++)    
  58.             {    
  59.                  scanf("%d",&m1[i][j]);    
  60.              }    
  61.         }    
  62.         printf("Enter Second matrix elements\n");    
  63.         for(int i=0;i<r2;i++)    
  64.         {    
  65.             for(int j=0;j<c2;j++)    
  66.             {    
  67.                 scanf("%d",&m2[i][j]);    
  68.             }    
  69.         }    
  70.         multiply(r1,c1,m1,r2,c2,m2,mul);
  71.         printf("Multiplied Matrix:\n");
  72.         for(int i=0;i<r1;i++)    
  73.         {    
  74.             for(int j=0;j<c2;j++)    
  75.             {    
  76.                 printf("%d ",mul[i][j]);   
  77.             }    
  78.             printf("\n");
  79.         } 
  80.     }
  81.     return 0;  
  82. }
Program Explanation

1. Input the size of both matrices
2. If matrix can’t be multiplied print that they can’t be multiplied
3. Else, Take input of elements of both matrices
4. Declare function multiply for matrix multiplication
5. In multiply function,there are 3 function calls

  • First, multiply all row elements with all column elements. (basic step of matrix multiplication)
  • Second, repeat step one for all row elements.
  • Third, repeatsecond step for all rows.

6. Print Multiplied Matrix.

Time Complexity: O(r1*c1*c2)
The first function call will make c1 function calls to find corresponding elements, the second function call will make c2 function calls to find all elements in a row, and the third function call will make r1 function calls to find all rows.

Space Complexity: O(r1*c1 + r2*c2 + r1*c2)
Since 3 matrices are used, so complexity is O(r1*c1 + r2*c2 + r1*c2).

Program output
 
Enter number of rows for First Matrix:
2
Enter number of columns for First Matrix:
2
Enter number of rows for Second Matrix:
2
Enter number of columns for Second Matrix:
2
Enter first matrix elements 
1 3
5 6
Enter Second matrix elements
2 1 
4 4
Multiplied matrix
14	13	
34	29

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.