Matrix Multiplication Algorithm and Program

In this tutorial, we’re going to learn an algorithm for Matrix multiplication along with its Program. Matrix is basically a two-dimensional array that can have any number of rows and any number of columns. Matrix multiplication procedure is not the same as a simple multiplication of numbers but it follows certain distinct rules
which must be followed during matrix multiplication.

Rules for matrix multiplication

  • First, declare two matrix M1 which has r1 rows and c1 columns, and M2 that has r2 rows and c2 columns.
  • To perform successful matrix multiplication r1 should be equal to c2 means the row of the first matrix should equal to a column of the second matrix.
  • Also, define a third matrix of size r2 rows and c1 columns to store the final result.
  • The order of the product of two matrices is distinct. When two matrices are of order r1 x c1 and r2 x c2, the order of product will be r2 x c1.
  • The matrix multiplication does not follow the Commutative Property. It means that, if M1 and M2 are two matrices then the product M1M2 is not equal to the product M2M1 i.e. M1M2 ≠ M2M1.

Matrix Multiplication Algorithm

matrixMultiplication(M1, M2):
 Matrix dimension of M1 is (r1 x c1) and dimension of M2 is (r2 x c2)
 Begin
    if r1 is not equal to c2, then exit
    otherwise define a new matrix M3 of dimension (r1 x c2)
    for i in range 0 to r1, do
       for j in range 0 to c2, do
          for k in range 0 to r2, do
             C[i, j] = C[i, j] + (A[i, k] * A[k, j])
          done
       done
    done
 End

Matrix Multiplication Program in C

#include <stdio.h>
int main()
{
  int m, n, p, q, c, d, k, sum = 0;
  int first[10][10], second[10][10], multiply[10][10];
  
  printf("Enter number of rows and columns of first matrix\n");
  scanf("%d%d", &m, &n);
  printf("Enter elements of first matrix\n");
  
  for (c = 0; c < m; c++)
    for (d = 0; d < n; d++)
      scanf("%d", &first[d]);
  
  printf("Enter number of rows and columns of second matrix\n");
  scanf("%d%d", &p, &q);
   printf("Enter elements of second matrix\n");
  for (c = 0; c < p; c++)
      for (d = 0; d < q; d++)
        scanf("%d", &second[d]);
  
  if (n != p)
    printf("The multiplication isn't possible.\n");
  else
  {
   for (c = 0; c < m; c++) {
      for (d = 0; d < q; d++) {
        for (k = 0; k < p; k++) {
          sum = sum + first[k]*second[k][d];
        }
        multiply[d] = sum;
        sum = 0;
      }
    }
  
    printf("Product of the matrices:\n");
  
    for (c = 0; c < m; c++) {
      for (d = 0; d < q; d++)
        printf("%d\t", multiply[d]);
  
      printf("\n");
    }
  }
 
}

Output: