Matrix Multiplication

Java coding interview problem for Matrix Problems: Matrix Multiplication.

Matrix multiplication is one of the fundamental operations in mathematics, computer science, and software engineering.

It is widely used in:

Machine Learning
Artificial Intelligence
Computer Graphics
Data Science
Scientific Computing
Game Development

From a programming perspective, matrix multiplication helps developers understand:

Nested loops
2D array manipulation
Dimension handling
Mathematical transformations
Algorithm optimization

What is Matrix Multiplication?

Matrix multiplication is an operation where two matrices are combined to produce a new matrix.

Given:

Matrix A

×

Matrix B

The result is:

Matrix C

The important rule:

The number of columns in the first matrix must equal the number of rows in the second matrix.

Matrix Multiplication Rule

If:

Matrix A:

m × n

Matrix B:

n × p

Then:

Result Matrix C:

m × p

Example

Matrix A:

2 × 3

1 2 3

4 5 6

Matrix B:

3 × 2

Result:

2 × 2

58 64

139 154

Understanding Matrix Dimensions

A matrix dimension is represented as:

Rows × Columns

Example:

3 × 2 Matrix

means:

3 rows

2 columns

Example:

Matrix Multiplication Condition

For multiplication:

A × B

is possible only when:

Columns of A

=

Rows of B

Valid Example

Matrix A:

2 × 3

Matrix B:

3 × 4

Result:

2 × 4

Valid.

Invalid Example

Matrix A:

2 × 3

Matrix B:

2 × 4

Cannot multiply.

Reason:

3 != 2

Mathematical Concept Behind Matrix Multiplication

For every result cell:

C[i][j]

we calculate:

Row i of Matrix A

×

Column j of Matrix B

Row × Column Rule

Example:

Matrix A:

1 2

3 4

Matrix B:

5 6

7 8

Calculate:

C[0][0]

Take:

First row of A:

1 2

First column of B:

5
7

Multiply and add:

(1×5) + (2×7)

Formula

For every element:

C[i][j] =
Σ A[i][k] × B[k][j]

Matrix Multiplication Visualization

Matrix A:

      Columns

       0  1  2

Row 0  a  b  c

Row 1  d  e  f

Matrix B:

      Columns

       0  1

Row 0  g  h

Row 1  i  j

Row 2  k  l

Result:

      Columns

       0  1

Row 0

Row 1

Why Is Matrix Multiplication Asked in Interviews?

This problem tests:

1. Nested Loop Understanding

Matrix multiplication requires:

Three loops

2. Index Handling

Understanding:

matrix[row][column]

is critical.

3. Mathematical Translation

Can you convert:

mathematical formula

into

code?

4. Optimization Skills

Can you improve:

O(n³)

solutions?

Real-World Applications

Machine Learning

Neural networks use matrix multiplication heavily.

Example:

Input Features

×

Weights

=

Output

Computer Graphics

3D transformations use matrices for:

Rotation
Scaling
Translation

Image Processing

Images are matrices:

Pixel Matrix

Operations:

Filters
Transformations
Convolution

Data Science

Large datasets are represented as matrices.

Operations include:

Feature transformation
Regression calculations
Statistical analysis

Problem Statement

Given two matrices:

A

B

multiply them and return the result matrix.

Example

Input:

Matrix A:

1 2

3 4

Matrix B:

5 6

7 8

Output:

19 22

43 50

Constraints

Example:

1 <= rows <= 100

1 <= columns <= 100

Approach 1 — Brute Force Triple Loop

The standard matrix multiplication algorithm uses three nested loops.

Algorithm

For every result position:

result[i][j]

calculate:

sum of A[i][k] * B[k][j]

Three Loops Explanation

Loop 1

Select row from Matrix A:

Loop 2

Select column from Matrix B:

Loop 3

Multiply corresponding elements:

Example

1 2

3 4

5 6

7 8

For:

C[0][0]

Calculation:

1×5 + 2×7

For:

C[0][1]

Calculation:

1×6 + 2×8

Java Program

import java.util.Arrays;

public class MatrixMultiplication {


    public static int[][] multiply(
            int[][] matrixA,
            int[][] matrixB) {


        int rowsA =
                matrixA.length;


        int colsA =
                matrixA[0].length;


        int colsB =
                matrixB[0].length;


        int[][] result =
                new int[rowsA][colsB];


        for(int i = 0;
            i < rowsA;
            i++) {


            for(int j = 0;
                j < colsB;
                j++) {


                for(int k = 0;
                    k < colsA;
                    k++) {


                    result[i][j] +=
                            matrixA[i][k]
                            *
                            matrixB[k][j];

                }

            }

        }


        return result;

    }


    public static void main(String[] args) {


        int[][] A =
                {
                    {1,2},
                    {3,4}
                };


        int[][] B =
                {
                    {5,6},
                    {7,8}
                };


        int[][] result =
                multiply(A,B);


        for(int[] row : result) {

            System.out.println(
                    Arrays.toString(row));

        }

    }

}

Output

[19, 22]

[43, 50]

Step-by-Step Code Explanation

Input:

Matrix A:

1 2

3 4

Matrix B:

5 6

7 8

Create result:

2 × 2

Calculate result[0][0]

1×5 + 2×7

Calculate result[0][1]

1×6 + 2×8

Calculate result[1][0]

3×5 + 4×7

Calculate result[1][1]

3×6 + 4×8

Complexity Analysis

For matrices:

A = m × n

B = n × p

The loops run:

m × p × n

times.

Time Complexity:

O(m × n × p)

For square matrices:

O(n³)

Space Complexity:

O(m × p)

because result matrix is created.

Advantages

Simple and reliable.
Works for all valid matrices.
Easy to implement.
Standard algorithm.

Drawbacks

Slow for very large matrices.
Requires three nested loops.
Not optimized for sparse matrices.

Matrix Multiplication Optimization Concepts

For large-scale systems, standard multiplication may not be enough.

Optimization techniques:

Cache optimization
Blocking / Tiling
Sparse matrix multiplication
Parallel computation
Divide and conquer algorithms

Optimized Matrix Multiplication Concepts

The standard matrix multiplication algorithm:

O(n³)

works well for small matrices.

However, large-scale systems such as:

Machine Learning frameworks
Scientific computing
Graphics engines
Big data processing

require optimized approaches.

Optimization Technique 1 — Loop Optimization

The traditional multiplication:

for(i)
    for(j)
        for(k)

can be optimized by changing loop order.

Standard Order

for(int i = 0; i < rowsA; i++) {

    for(int j = 0; j < colsB; j++) {

        for(int k = 0; k < colsA; k++) {

            result[i][j] += 
                A[i][k] * B[k][j];

        }
    }
}

Cache-Friendly Order

Computers store arrays row-wise in memory.

Changing loop order improves cache usage.

Example:

for(int i = 0; i < rowsA; i++) {

    for(int k = 0; k < colsA; k++) {

        for(int j = 0; j < colsB; j++) {


            result[i][j] +=
                    A[i][k] * B[k][j];

        }

    }

}

Why Does This Improve Performance?

Modern CPUs use:

Cache Memory

Accessing nearby memory locations is faster.

Better memory locality:

Higher Cache Hit Rate

↓

Better Performance

Optimization Technique 2 — Blocking / Tiling

For very large matrices:

10000 × 10000

processing the complete matrix at once is inefficient.

Instead, divide matrices into smaller blocks.

Example:

Large Matrix
      |
      |
Small Blocks

Example:

Matrix:

8 × 8

Split into:

4 × 4 blocks

Process:

Block A × Block B

Benefits

Better CPU cache utilization.
Faster execution.
Used in high-performance libraries.

Examples:

BLAS
NumPy
Tensor libraries

Optimization Technique 3 — Sparse Matrix Multiplication

A sparse matrix contains many zero values.

Example:

Most elements are:

Normal multiplication wastes operations:

0 × value

Sparse multiplication stores only non-zero values.

Example:

Instead of:

Store:

(row,column,value)

(0,2,5)

(1,1,8)

(2,2,3)

Advantages

Less memory.
Faster computation.
Useful for large sparse datasets.

Java Example — Sparse Matrix Representation

class Element {

    int row;

    int column;

    int value;


    Element(int row,
            int column,
            int value) {

        this.row = row;

        this.column = column;

        this.value = value;

    }

}

Optimization Technique 4 — Recursive Matrix Multiplication

Divide the matrix into smaller submatrices.

Example:

Matrix

      |
      |
Divide

      |
      |
Multiply smaller parts

      |
      |
Combine results

This approach is useful for:

Divide and conquer algorithms.
Parallel processing.

Divide and Conquer Concept

Matrix:

Split:

A11 A12

A21 A22

Similarly:

B11 B12

B21 B22

Result:

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Strassen Matrix Multiplication

Strassen's algorithm improves multiplication complexity.

Normal:

O(n³)

Strassen:

O(n^2.81)

Main Idea

Normal multiplication requires:

8 recursive multiplications

Strassen reduces it to:

7 recursive multiplications

Strassen Advantage

For very large matrices:

Millions of operations

can be reduced significantly.

Strassen Drawbacks

Complex implementation.
More memory usage.
Not always faster for small matrices.

Java Streams Approach

Matrix multiplication is not a good candidate for Streams.

Reason:

Matrix multiplication requires:

Multiple indexes.
Nested calculations.
Mutable accumulation.

Traditional loops are clearer.

Example Stream Style

IntStream.range(0, rows)
.mapToObj(i ->
    IntStream.range(0, cols)
    .map(j -> calculate(i,j))
    .toArray()
)
.toArray(int[][]::new);

Why Loops Are Preferred?

For matrix operations:

Loops provide:

Better readability.
Better performance.
Easier debugging.
Less object creation.

Comparison of All Approaches

Approach	Time Complexity	Space	Usage
Triple Loop	O(n³)	O(n²)	Standard solution
Loop Optimization	O(n³)	O(n²)	Performance improvement
Blocking/Tiling	O(n³)	O(n²)	Large matrices
Sparse Matrix	Depends on non-zero values	Lower	Sparse data
Divide & Conquer	O(n³)	Extra recursion	Advanced
Strassen	O(n².81)	Higher	Very large matrices

Matrix Index Mapping

For multiplication:

Result:

C[i][j]

is calculated from:

A[i][k]

and

B[k][j]

Example:

Matrix A:

1 2 3

Matrix B:

Calculation:

C[0][0]

1×4 + 2×5 + 3×6

Primitive vs Object Arrays

Primitive Matrix

Example:

int[][]

Advantages:

Faster.
Less memory.
Better CPU performance.

Recommended for:

Numerical operations.
Large matrices.

Object Matrix

Example:

Integer[][]

Advantages:

Supports null values.
Works with collections.

Disadvantages:

Boxing overhead.
More memory.

Common Interview Mistakes

Mistake 1

Ignoring dimension validation.

Before multiplication:

Check:

A columns == B rows

Mistake 2

Wrong loop limits.

Incorrect:

k < rowsA

Correct:

k < colsA

Mistake 3

Incorrect indexing.

Correct:

A[i][k]

B[k][j]

Mistake 4

Initializing result incorrectly.

Default:

int[][]

is initialized with:

which is required for accumulation.

Edge Cases

Empty Matrix

Input:

[]

Handle separately.

Single Element

[5]

[2]

Result:

[10]

Identity Matrix

Example:

1 0

0 1

Multiplying by identity:

A × I = A

Zero Matrix

Any matrix multiplied by zero:

Result = Zero Matrix

Interview Follow-up Questions

Q1. Implement matrix multiplication.

Q2. Validate matrix dimensions.

Q3. Optimize matrix multiplication.

Q4. Multiply sparse matrices.

Q5. Explain Strassen algorithm.

Q6. Multiply matrices using recursion.

Q7. Rotate matrix using multiplication.

Key Takeaways

Matrix multiplication is based on:

Row × Column

The standard algorithm:

Three Nested Loops

Complexity:

O(n³)

Optimization path:

Basic Multiplication

        ↓

Loop Optimization

        ↓

Blocking

        ↓

Sparse Matrix

        ↓

Strassen Algorithm

Frequently Asked Interview Questions

Q1. What is the condition for multiplication?

Number of columns in first matrix must equal number of rows in second matrix.

Q2. What is the complexity?

For square matrices:

O(n³)

Q3. Which algorithm is commonly used?

Standard triple loop approach.

Q4. What is Strassen's complexity?

Approximately:

O(n².81)

Q5. Why use blocking?

To improve CPU cache utilization.

Interview Tip

When asked:

"Implement Matrix Multiplication."

Explain:

Validate dimensions.
Create result matrix.
Use row-column multiplication.
Discuss optimization options.

For senior-level interviews, mention:

Cache optimization.
Sparse matrices.
Parallel processing.
Strassen algorithm.

Understanding matrix multiplication builds a foundation for advanced topics like machine learning, graphics, and scientific computing.