Matrix Multiplication: flowchart, algorithm and program
This program reads two 2×2 matrices, a and b, and stores their product in c. Each cell c[i][j] is built by multiplying row i of a with column j of b and adding the results, which is why three nested loops are needed.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Print "Enter first matrix".
- Step 3: Set i = 0.
- Step 4: If i < 2, go to step 5; otherwise go to step 10.
- Step 5: Set j = 0.
- Step 6: If j < 2, go to step 7; otherwise go to step 9.
- Step 7: Read a[i][j].
- Step 8: Increase j by 1. Go to step 6.
- Step 9: Increase i by 1. Go to step 4.
- Step 10: Print "Enter second matrix".
- Step 11: Set i = 0.
- Step 12: If i < 2, go to step 13; otherwise go to step 18.
- Step 13: Set j = 0.
- Step 14: If j < 2, go to step 15; otherwise go to step 17.
- Step 15: Read b[i][j].
- Step 16: Increase j by 1. Go to step 14.
- Step 17: Increase i by 1. Go to step 12.
- Step 18: Set i = 0.
- Step 19: If i < 2, go to step 20; otherwise go to step 28.
- Step 20: Set j = 0.
- Step 21: If j < 2, go to step 22; otherwise go to step 27.
- Step 22: Set c[i][j] = 0; k = 0.
- Step 23: If k < 2, go to step 24; otherwise go to step 26.
- Step 24: Set c[i][j] += a[i][k] * b[k][j].
- Step 25: Increase k by 1. Go to step 23.
- Step 26: Increase j by 1. Go to step 21.
- Step 27: Increase i by 1. Go to step 19.
- Step 28: Print "Product matrix".
- Step 29: Set i = 0.
- Step 30: If i < 2, go to step 31; otherwise go to step 36.
- Step 31: Set j = 0.
- Step 32: If j < 2, go to step 33; otherwise go to step 35.
- Step 33: Print c[i][j].
- Step 34: Increase j by 1. Go to step 32.
- Step 35: Print newline; i++. Go to step 30.
- Step 36: Stop.
Pseudocode
BEGIN
PRINT "Enter first matrix"
i ← 0
WHILE i < 2 DO
j ← 0
WHILE j < 2 DO
READ a[i][j]
j++
END WHILE
i++
END WHILE
PRINT "Enter second matrix"
i ← 0
WHILE i < 2 DO
j ← 0
WHILE j < 2 DO
READ b[i][j]
j++
END WHILE
i++
END WHILE
i ← 0
WHILE i < 2 DO
j ← 0
WHILE j < 2 DO
c[i][j] ← 0; k ← 0
WHILE k < 2 DO
c[i][j] += a[i][k] * b[k][j]
k++
END WHILE
j++
END WHILE
i++
END WHILE
PRINT "Product matrix"
i ← 0
WHILE i < 2 DO
j ← 0
WHILE j < 2 DO
PRINT c[i][j]
j++
END WHILE
PRINT newline; i++
END WHILE
END
Program in C, Python and Java
Matrix Multiplication program in C
#include <stdio.h>
int main() {
int a[2][2], b[2][2], c[2][2];
int i, j, k;
printf("Enter first matrix (2x2):\n");
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
scanf("%d", &a[i][j]);
printf("Enter second matrix (2x2):\n");
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
scanf("%d", &b[i][j]);
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
c[i][j] = 0;
for (k = 0; k < 2; k++)
c[i][j] += a[i][k] * b[k][j];
}
}
printf("Product matrix:\n");
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++)
printf("%d ", c[i][j]);
printf("\n");
}
return 0;
}Matrix Multiplication program in Python
a = [[0] * 2 for _ in range(2)]
b = [[0] * 2 for _ in range(2)]
c = [[0] * 2 for _ in range(2)]
print("Enter first matrix (2x2):")
for i in range(2):
row = input().split()
for j in range(2):
a[i][j] = int(row[j])
print("Enter second matrix (2x2):")
for i in range(2):
row = input().split()
for j in range(2):
b[i][j] = int(row[j])
for i in range(2):
for j in range(2):
c[i][j] = 0
for k in range(2):
c[i][j] += a[i][k] * b[k][j]
print("Product matrix:")
for i in range(2):
for j in range(2):
print(c[i][j], end=" ")
print()Matrix Multiplication program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] a = new int[2][2];
int[][] b = new int[2][2];
int[][] c = new int[2][2];
int i, j, k;
System.out.println("Enter first matrix (2x2):");
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
a[i][j] = sc.nextInt();
System.out.println("Enter second matrix (2x2):");
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
b[i][j] = sc.nextInt();
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
c[i][j] = 0;
for (k = 0; k < 2; k++)
c[i][j] += a[i][k] * b[k][j];
}
}
System.out.println("Product matrix:");
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++)
System.out.print(c[i][j] + " ");
System.out.println();
}
}
}
Sample input: A = 1 2 3 4, B = 5 6 7 8
Output: Product matrix:
19 22
43 50
How it works
- The first two pairs of loops just read input: i walks over rows and j over columns, and scanf fills a[i][j] and then b[i][j].
- The outer loop i picks a row of a, and the middle loop j picks a column of b. Together they choose which cell c[i][j] we are computing.
- Before adding anything, c[i][j] is set to 0. This matters because c is uninitialised and += would otherwise start from garbage.
- The inner loop k runs over the shared dimension: c[i][j] += a[i][k] * b[k][j]. It pairs the k-th element of row i with the k-th element of column j.
- Dry run with A = 1 2 3 4 and B = 5 6 7 8: c[0][0] = 1*5 + 2*7 = 19, c[0][1] = 1*6 + 2*8 = 22, c[1][0] = 3*5 + 4*7 = 43, c[1][1] = 3*6 + 4*8 = 50.
- The last loops print c row by row, with printf("\n") after each row so the output looks like a matrix.
Dry run (trace table)
| Step | Line | Box | i | j | a[0][0] | a[0][1] | a[1][0] | a[1][1] | b[0][0] | b[0][1] | b[1][0] | b[1][1] | Output |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | |||||||||||
| 2 | 7 | Print "Enter first matrix" | Enter first matrix (2x2): | ||||||||||
| 3 | 8 | i = 0 | 0 | ||||||||||
| 4 | 8 | i < 2? | 0 | ||||||||||
| 5 | 9 | j = 0 | 0 | 0 | |||||||||
| 6 | 9 | j < 2? | 0 | 0 | |||||||||
| 7 | 10 | Read a[i][j] | 0 | 0 | 1 | ||||||||
| 8 | 9 | j++ | 0 | 1 | |||||||||
| 9 | 9 | j < 2? | 0 | 1 | |||||||||
| 10 | 10 | Read a[i][j] | 0 | 1 | 2 | ||||||||
| 11 | 9 | j++ | 0 | 2 | |||||||||
| 12 | 9 | j < 2? | 0 | 2 | |||||||||
| 13 | 8 | i++ | 1 | 2 | |||||||||
| 14 | 8 | i < 2? | 1 | 2 | |||||||||
| 15 | 9 | j = 0 | 1 | 0 | |||||||||
| 16 | 9 | j < 2? | 1 | 0 | |||||||||
| 17 | 10 | Read a[i][j] | 1 | 0 | 3 | ||||||||
| 18 | 9 | j++ | 1 | 1 | |||||||||
| 19 | 9 | j < 2? | 1 | 1 | |||||||||
| 20 | 10 | Read a[i][j] | 1 | 1 | 4 |
Time and space complexity
Time: O(n³) · Space: O(n²). Three nested loops each run n times (n = 2 here), and the matrices a, b and c each hold n² elements.
Common mistakes
- Forgetting to set c[i][j] = 0 before the k loop, so the sum starts from a garbage value and the result is wrong.
- Writing b[j][k] instead of b[k][j] (or a[k][i] for a[i][k]). That multiplies the wrong elements and gives something that looks like a matrix but is not the product.
- Multiplying element by element (c[i][j] = a[i][j] * b[i][j]). That is not matrix multiplication, which needs the sum over k.
Viva questions
Q1. Why is c[i][j] set to 0 on line 19 before the innermost loop?
Line 21 uses += to add up the dot product, so c[i][j] must start at 0. A local array is not auto-initialised in C and holds garbage, so without this the result would be wrong.
Q2. What does the innermost k loop compute?
It computes the dot product of row i of matrix a and column j of matrix b. It sums a[i][k] * b[k][j] for k = 0 and 1 to give one element of the product.
Q3. Why is the sum of a[i][k] * b[k][j] used and not a[i][j] * b[i][j]?
Matrix multiplication is not element-wise. Each result element is row i of A times column j of B, so the column index of A and the row index of B must both be k.
Q4. When can two matrices be multiplied, and does this program check that?
The number of columns of the first must equal the number of rows of the second. Here both are 2x2 so it always holds, and no check is needed.
Q5. Is matrix multiplication commutative? Would the output change if you swapped the order of the two input matrices?
No, A x B is generally not equal to B x A. Swapping the inputs usually gives a different product matrix.
Q6. What is the time complexity of this program, and what would it be for n x n matrices?
There are three nested loops, so for n x n matrices it is O(n^3). Here n = 2, so it does 2*2*2 = 8 multiplications.
Q7. What would you change to multiply a 2x3 matrix with a 3x2 matrix?
Declare a as [2][3], b as [3][2] and c as [2][2]. Change the input loops to match, and make the k loop run to 3, the shared dimension. The i loop stays at 2 (rows of A) and the j loop at 2 (columns of B).
Q8. What does the & do in scanf("%d", &a[i][j]), and what happens if the user types a non-number?
The & passes the address of the element so scanf can store the value there. If the input is not a number, scanf fails and leaves the element uninitialised. The program does not check the return value, so garbage could be used.
Frequently asked questions
Why does matrix multiplication need three nested loops?
Two loops (i and j) visit every cell of the result, and a third loop (k) adds up the products of a row of a with a column of b for that cell. For n×n matrices this takes n³ multiplications.
Why do we set c[i][j] = 0 before the inner loop?
The inner loop uses +=, so it needs a known starting value. Without the reset, c[i][j] would begin with whatever garbage was in memory.
What is the product of A = [1 2; 3 4] and B = [5 6; 7 8]?
It is [19 22; 43 50]. For example, the top-left value is 1*5 + 2*7 = 19.