Matrix Multiplication Algorithm and Program

Matrix multiplication is a process of combining two matrices to produce a new matrix based on specific mathematical rules. A matrix is simply a 2D array arranged in rows and 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. For multiplication to work, the number of columns in the first matrix must match the number of rows in the second.

Each value in the result matrix is found by multiplying a row of the first matrix with a column of the second and adding the products. This operation is widely used in computer science, graphics, data processing, and scientific calculations.

Rules for Matrix Multiplication

First, consider two matrices:

• M1 with dimensions r1 × c1
• M2 with dimensions r2 × c2

For matrix multiplication to be valid, the number of columns in the first matrix (c1) must equal the number of rows in the second matrix (r2).

The result will be stored in a third matrix M3 with dimensions r1 × c2.

Important Note: Matrix multiplication is not commutative. This means that:

M1 × M2 ≠ M2 × M1

Matrix Multiplication Algorithm

matrixMultiplication(M1, M2):
    Dimension of M1 = (r1 × c1)
    Dimension of M2 = (r2 × c2)

    Begin
        if c1 is not equal to r2, then
            exit   // multiplication not possible

        otherwise
            define a new matrix M3 of dimension (r1 × c2)

            for i in range 0 to r1-1, do
                for j in range 0 to c2-1, do
                    M3[i, j] = 0
                    for k in range 0 to c1-1, do
                        M3[i, j] = M3[i, j] + (M1[i, k] * M2[k, j])
                    done
                done
            done

        return M3
    End

Matrix Multiplication Algorithm Explanation

The pseudocode above describes the standard matrix multiplication algorithm. Let’s analyze its steps and computational complexity.

Algorithm Steps

1. Check Dimension Compatibility
   • Matrix multiplication requires that c1 == r2
   • Complexity: O(1) (constant time operation)
2. Initialize Result Matrix M3
   • Create matrix M3 with dimensions r1 × c2
   • Complexity: O(r1 × c2) (memory allocation)
3. Perform Multiplication
   • Three nested loops control the computation:
     • Outer loop runs r1 times (rows of M1)
     • Middle loop runs c2 times (columns of M2)
     • Inner loop runs c1 times (common dimension)
   • Each inner loop iteration performs: M3[i][j] = M3[i][j] + (M1[i][k] × M2[k][j])

Time Complexity of Matrix Multiplication

The time complexity is determined by the three nested loops:

• Outer loop: r1 iterations
• Middle loop: c2 iterations
• Inner loop: c1 iterations

Total operations: r1 × c2 × c1.

Each operation involves one multiplication and one addition.

Time Complexity: O(r1 × c2 × c1)

For square matrices where all dimensions equal n, this simplifies to O(n³).

Space Complexity of Matrix Multiplication

Apart from the input matrices M1 and M2, the algorithm requires space for the output matrix M3 with dimensions r1 × c2.

Space Complexity: O(r1 × c2)

This standard matrix multiplication algorithm has cubic time complexity, which can be computationally expensive for large matrices. Advanced algorithms like Strassen’s algorithm or the Coppersmith-Winograd algorithm offer better theoretical time complexities but are more complex to implement.

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[c][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[c][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[c][k]*second[k][d];
                }
                multiply[c][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[c][d]);
      printf("\n");
    }
  }
}

Output

Enter number of rows and columns of first matrix
2
2
Enter elements of first matrix
1
2
3
4
Enter number of rows and columns of second matrix
2
2
Enter elements of second matrix
1
2
3
4
Product of the matrices:
7       10
15      22