Introduction
In Part 2A, we learned how to write a complete Java program for matrix multiplication. We also understood the purpose of each loop and how the program validates the dimensions before performing multiplication.
In this final part, we will:
- Perform a complete dry run of the program.
- Understand how each loop executes.
- Analyze the Time and Space Complexity.
- Learn common mistakes to avoid.
- Solve interview-style questions.
- Practice programming exercises.
Dry Run of the Program
Suppose the user enters the following matrices.
First Matrix (2 × 3)
1 2 3
4 5 6
Second Matrix (3 × 2)
7 8
9 10
11 12
The result matrix will be
2 × 2
Initially,
0 0
0 0
First Iteration
row = 0
column = 0
We are calculating
resultMatrix[0][0]
Initially,
resultMatrix[0][0] = 0
Now the inner loop begins.
common = 0
resultMatrix[0][0] +=
firstMatrix[0][0]
*
secondMatrix[0][0]
Calculation
0 + (1 × 7)
= 7
Result becomes
7
common = 1
resultMatrix[0][0] +=
2 × 9
Calculation
7 + 18
= 25
common = 2
resultMatrix[0][0] +=
3 × 11
Calculation
25 + 33
= 58
The first element is completed.
58
Second Iteration
Now
row = 0
column = 1
The program calculates
resultMatrix[0][1]
Initially,
0
common = 0
1 × 8
= 8
common = 1
2 × 10
= 20
Current total
28
common = 2
3 × 12
= 36
Final answer
64
Third Iteration
row = 1
column = 0
Multiply
4×7
5×9
6×11
Answer
139
Fourth Iteration
row = 1
column = 1
Multiply
4×8
5×10
6×12
Answer
154
The final matrix becomes
58 64
139 154
Understanding the Loop Execution
The loops execute in the following order.
for(row)
↓
for(column)
↓
for(common)
Think of it as follows.
The outer loop selects
One Row
The middle loop selects
One Column
The inner loop performs
All Multiplications
and finally adds them together.
Why Do We Use Three Loops?
Each loop has a specific responsibility.
Loop 1
for(row)
Responsible for selecting each row of the first matrix.
Loop 2
for(column)
Responsible for selecting each column of the second matrix.
Loop 3
for(common)
Responsible for multiplying corresponding elements and calculating the dot product.
Without the third loop, the program would multiply only one pair of elements instead of the entire row and column.
Time Complexity
Suppose
First Matrix
m × n
Second Matrix
n × p
The loops execute as follows.
Outer loop
m times
Middle loop
p times
Inner loop
n times
Therefore,
Time Complexity
O(m × n × p)
Square Matrix
If both matrices are
N × N
then
O(N³)
This is the standard matrix multiplication algorithm.
Space Complexity
Suppose
Result Matrix
m × p
Additional variables
row
column
common
occupy constant space.
Ignoring the output matrix,
Auxiliary Space
O(1)
Including the output matrix,
O(m × p)
Why Do We Use += ?
Notice the statement.
resultMatrix[row][column] +=
firstMatrix[row][common]
*
secondMatrix[common][column];
Suppose we wrote
resultMatrix[row][column] =
firstMatrix[row][common]
*
secondMatrix[common][column];
Then every new multiplication would overwrite the previous answer.
Instead,
+=
keeps adding all products.
Example
1×7
+
2×9
+
3×11
Without
+=
only the last multiplication would remain.
Common Programming Mistakes
Mistake 1
Forgetting to check
firstMatrixColumns == secondMatrixRows
Always validate the dimensions before multiplying.
Mistake 2
Using the wrong size for the result matrix.
Incorrect
new int[firstMatrixRows][firstMatrixColumns]
Correct
new int[firstMatrixRows][secondMatrixColumns]
Mistake 3
Writing
common < secondMatrixColumns
The correct loop is
common < firstMatrixColumns
because
firstMatrixColumns
=
secondMatrixRows
Mistake 4
Using
=
instead of
+=
This produces incorrect answers.
Mistake 5
Mixing row and column indices.
Correct
firstMatrix[row][common]
secondMatrix[common][column]
Incorrect
firstMatrix[common][row]
secondMatrix[column][common]
Always remember the Row × Column rule.
Interview Questions
Question 1
What is the condition for matrix multiplication?
Answer
The number of columns of the first matrix must be equal to the number of rows of the second matrix.
Question 2
How many loops are required?
Answer
Three nested loops.
Question 3
Why is the third loop required?
Answer
It calculates the dot product of one row and one column.
Question 4
What is the Time Complexity?
Answer
O(m × n × p)
or
O(N³)
for square matrices.
Question 5
Can two matrices having different sizes be multiplied?
Answer
Yes.
Provided
Columns of First Matrix
=
Rows of Second Matrix
Practice Programs
Now that you understand matrix multiplication, try solving the following programs on your own.
Easy
- Matrix Addition
- Matrix Subtraction
- Matrix Transpose
- Identity Matrix
- Diagonal Sum
Medium
- Symmetric Matrix
- Upper Triangular Matrix
- Lower Triangular Matrix
- Sparse Matrix
Advanced
- Matrix Rotation
- Matrix Chain Multiplication
- Determinant of Matrix
- Inverse of Matrix
- Strassen Matrix Multiplication
Revision Notes
Remember these five important formulas.
Formula 1
Matrix Size
Rows × Columns
Formula 2
Condition
Columns of First Matrix
=
Rows of Second Matrix
Formula 3
Result Size
Rows of First Matrix
×
Columns of Second Matrix
Formula 4
Time Complexity
O(m × n × p)
Square matrix
O(N³)
Formula 5
Space Complexity
Auxiliary
O(1)
Including Result Matrix
O(m × p)
Key Takeaways
Before moving on, make sure you can answer these questions confidently.
- What is a matrix?
- What is the condition for multiplication?
- Why do we multiply a row by a column?
- Why are three nested loops required?
- Why do we use
+=instead of=? - Why is the result matrix size Rows of First Matrix × Columns of Second Matrix?
- What is the Time Complexity?
- What is the Space Complexity?
If you can answer all of these, you have mastered the fundamentals of matrix multiplication.
Conclusion
Matrix multiplication is one of the most important topics in Data Structures and Algorithms. Although it may seem difficult at first, it follows a simple and consistent pattern:
- Check whether the matrices can be multiplied.
- Create a result matrix with the correct dimensions.
- Select one row from the first matrix.
- Select one column from the second matrix.
- Multiply corresponding elements.
- Add the products together.
- Store the result in the appropriate position.
- Repeat until every element of the result matrix is calculated.
The Java implementation uses three nested loops, where each loop has a specific responsibility:
- The outer loop selects a row from the first matrix.
- The middle loop selects a column from the second matrix.
- The inner loop traverses the common dimension and computes the dot product.
Once you understand this logic, matrix multiplication becomes straightforward and forms the foundation for many advanced topics in computer science, including graphics, machine learning, scientific computing, and artificial intelligence.
In the next article, we’ll explore another important matrix operation: Transpose of a Matrix in Java, where you’ll learn how to swap rows and columns efficiently and understand its real-world applications.
