# 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
M3[i, j] = M3[i, j] + (M1[i, k] * M2[k, j])
done
done
done
End```

### Matrix Multiplication Algorithm Explanations

Above pseudocode is provided for a basic matrix multiplication algorithm. To analyze its complexity, let’s break down the steps and their respective computational costs.

### Algorithm Steps:

1. Check Dimensions: The algorithm first checks if the number of rows in matrix M1 (`r1`) is equal to the number of columns in matrix M2 (`c2`) or not. This step is crucial to perform the matrix multiplication. Matrix multiplication is only possible when `r1 == c2` otherwise not. The complexity of this step is O(1) since it’s a single conditional check.
2. Initialize Result Matrix M3: We will create a new matrix M3 with dimensions `r1 x c2`. The complexity for initializing this matrix is O(r1 * c2), as it involves setting up a grid of `r1` rows and `c2` columns.
3. Perform Multiplication: To Perform matrix multiplication, we are using three for loop:
• The outer loop runs `r1` times.The middle loop runs `c2` times.The innermost loop runs `r2` (or `c1`, since `c1 == r2`) times.
In each iteration of the innermost loop, the algorithm performs a multiplication and an addition operation: `<strong>M3[i, j] = M3[i, j] + (M1[i, k] * M2[k, j])</strong>`.

### Complexity Analysis:

The time complexity of the algorithm is primarily determined by the nested loops:

• The outer loop runs `r1` times.
• The middle loop runs `c2` times for each iteration of the outer loop.
• The inner loop runs `r2` times for each iteration of the middle loop.

Hence, the total number of iterations for the innermost statement is `r1 * c2 * r2`. Since each iteration involves a constant amount of work (a multiplication and an addition), the time complexity of the algorithm is O(r1 * c2 * r2).

### Space Complexity:

The space complexity of the algorithm is determined by the amount of additional memory it needs. Apart from the input matrices M1 and M2, it only requires space for the output matrix M3, which has dimensions `r1 x c2`. Therefore, the space complexity is O(r1 * c2).

### Conclusion:

• Time Complexity: O(r1 * c2 * r2)
• Space Complexity: O(r1 * c2)

This matrix multiplication algorithm is a straightforward implementation with cubic time complexity, which can be computationally expensive for large matrices. Advanced algorithms like Strassen’s algorithm or the Coppersmith-Winograd algorithm can multiply matrices in faster time complexities, though they 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[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:

```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```