Matrix Multiplication

Problem Statement

Write a Java program that implements a method to multiply two 2D arrays (matrices) and return the result as a new 2D array. The program should handle matrix multiplication for matrices of compatible sizes (i.e., the number of columns in the first matrix equals the number of rows in the second matrix) and test the implementation with matrices of different compatible sizes, including square and non-square matrices, and edge cases like single-row or single-column matrices. You can visualize this as combining two grids of numbers, where each cell in the resulting grid is computed by pairing rows from the first grid with columns from the second grid, summing the products of corresponding elements.

Input: Two 2D arrays (matrices) A (m × n) and B (n × p), where m is the number of rows in A, n is the number of columns in A and rows in B, and p is the number of columns in B (e.g., A = [[1, 2], [3, 4]], B = [[5, 6], [7, 8]]). Output: A new 2D array (m × p) representing the product of A and B (e.g., [[19, 22], [43, 50]]). Constraints:

• 1 ≤ m, n, p ≤ 100.
• Elements are integers between -10^4 and 10^4.
• The number of columns in A equals the number of rows in B (matrices are compatible). Example:
• Input: A = [[1, 2], [3, 4]], B = [[5, 6], [7, 8]]
• Output: [[19, 22], [43, 50]]
• Explanation: For element [0][0] in the result: 15 + 27 = 19; for [0][1]: 16 + 28 = 22; for [1][0]: 35 + 47 = 43; for [1][1]: 36 + 48 = 50.
• Input: A = [[1, 2, 3]], B = [[4], [5], [6]]
• Output: [[32]]
• Explanation: For element [0][0]: 14 + 25 + 3*6 = 32.

Pseudocode

FUNCTION multiplyMatrices(A, B)
    IF A is null OR B is null OR A is empty OR B is empty OR columns of A not equal to rows of B THEN
        RETURN null
    ENDIF
    SET m to number of rows in A
    SET n to number of columns in A
    SET p to number of columns in B
    CREATE result matrix of size m × p
    FOR i from 0 to m - 1
        FOR j from 0 to p - 1
            SET sum to 0
            FOR k from 0 to n - 1
                SET sum to sum + A[i][k] * B[k][j]
            ENDFOR
            SET result[i][j] to sum
        ENDFOR
    ENDFOR
    RETURN result
ENDFUNCTION

FUNCTION main()
    SET testCases to pairs of matrices
    FOR each (A, B) in testCases
        CALL multiplyMatrices(A, B)
        PRINT result
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if matrices A or B are null, empty, or incompatible (number of columns in A ≠ number of rows in B). If so, return null.
2. Get dimensions: m (rows of A), n (columns of A/rows of B), p (columns of B).
3. Create a result matrix of size m × p, initialized to zeros.
4. For each element result[i][j] in the result matrix: a. Initialize a sum to 0. b. For each k from 0 to n-1, compute A[i][k] * B[k][j] and add to the sum. c. Set result[i][j] to the computed sum.
5. Return the result matrix.
6. In the main method, create test cases with different compatible matrix sizes and call multiplyMatrices to verify correctness.

Java Implementation

public class MatrixMultiplication {
    // Multiplies two matrices and returns the result
    public int[][] multiplyMatrices(int[][] A, int[][] B) {
        // Check for null, empty, or incompatible matrices
        if (A == null || B == null || A.length == 0 || B.length == 0 || A[0].length != B.length) {
            return null;
        }
        // Get dimensions
        int m = A.length; // Rows of A
        int n = A[0].length; // Columns of A, rows of B
        int p = B[0].length; // Columns of B
        // Initialize result matrix
        int[][] result = new int[m][p];
        // Compute matrix multiplication
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < p; j++) {
                int sum = 0;
                for (int k = 0; k < n; k++) {
                    sum += A[i][k] * B[k][j];
                }
                result[i][j] = sum;
            }
        }
        return result;
    }

    // Main method to test multiplyMatrices with various inputs
    public static void main(String[] args) {
        MatrixMultiplication multiplier = new MatrixMultiplication();

        // Test case 1: 2x2 matrices
        int[][] A1 = {{1, 2}, {3, 4}};
        int[][] B1 = {{5, 6}, {7, 8}};
        System.out.println("Test case 1:");
        System.out.println("Matrix A1:");
        printMatrix(A1);
        System.out.println("Matrix B1:");
        printMatrix(B1);
        int[][] result1 = multiplier.multiplyMatrices(A1, B1);
        System.out.println("Result:");
        printMatrix(result1);

        // Test case 2: 1x3 and 3x1 matrices
        int[][] A2 = {{1, 2, 3}};
        int[][] B2 = {{4}, {5}, {6}};
        System.out.println("Test case 2:");
        System.out.println("Matrix A2:");
        printMatrix(A2);
        System.out.println("Matrix B2:");
        printMatrix(B2);
        int[][] result2 = multiplier.multiplyMatrices(A2, B2);
        System.out.println("Result:");
        printMatrix(result2);

        // Test case 3: 3x2 and 2x3 matrices
        int[][] A3 = {{1, 2}, {3, 4}, {5, 6}};
        int[][] B3 = {{7, 8, 9}, {10, 11, 12}};
        System.out.println("Test case 3:");
        System.out.println("Matrix A3:");
        printMatrix(A3);
        System.out.println("Matrix B3:");
        printMatrix(B3);
        int[][] result3 = multiplier.multiplyMatrices(A3, B3);
        System.out.println("Result:");
        printMatrix(result3);

        // Test case 4: Incompatible matrices
        int[][] A4 = {{1, 2}};
        int[][] B4 = {{3, 4}};
        System.out.println("Test case 4 (incompatible):");
        System.out.println("Matrix A4:");
        printMatrix(A4);
        System.out.println("Matrix B4:");
        printMatrix(B4);
        int[][] result4 = multiplier.multiplyMatrices(A4, B4);
        System.out.println("Result:");
        printMatrix(result4);
    }

    // Helper method to print matrix
    private static void printMatrix(int[][] matrix) {
        if (matrix == null) {
            System.out.println("null");
            return;
        }
        System.out.println("[");
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("  [");
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j]);
                if (j < matrix[i].length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
        System.out.println("]");
    }
}

Output

Running the main method produces:

Test case 1:
Matrix A1:
[
  [1, 2]
  [3, 4]
]
Matrix B1:
[
  [5, 6]
  [7, 8]
]
Result:
[
  [19, 22]
  [43, 50]
]
Test case 2:
Matrix A2:
[
  [1, 2, 3]
]
Matrix B2:
[
  [4]
  [5]
  [6]
]
Result:
[
  [32]
]
Test case 3:
Matrix A3:
[
  [1, 2]
  [3, 4]
  [5, 6]
]
Matrix B3:
[
  [7, 8, 9]
  [10, 11, 12]
]
Result:
[
  [27, 30, 33]
  [61, 68, 75]
  [95, 106, 117]
]
Test case 4 (incompatible):
Matrix A4:
[
  [1, 2]
]
Matrix B4:
[
  [3, 4]
]
Result:
null

Explanation:

• Test case 1: Multiplies 2×2 matrices, resulting in [[19, 22], [43, 50]].
• Test case 2: Multiplies 1×3 and 3×1 matrices, resulting in [[32]].
• Test case 3: Multiplies 3×2 and 2×3 matrices, resulting in a 3×3 matrix.
• Test case 4: Incompatible matrices (1×2 and 1×2) return null.

How It Works

• Step 1: The multiplyMatrices method checks for null, empty, or incompatible matrices. For A = [[1, 2], [3, 4]], B = [[5, 6], [7, 8]], it proceeds (2×2 and 2×2 are compatible).
• Step 2: Initialize m = 2, n = 2, p = 2, and create a 2×2 result matrix.
• Step 3: Compute each element:
  • result[0][0]: 1*5 + 2*7 = 19.
  • result[0][1]: 1*6 + 2*8 = 22.
  • result[1][0]: 3*5 + 4*7 = 43.
  • result[1][1]: 3*6 + 4*8 = 50.
• Example Trace: For test case 1, computes [[19, 22], [43, 50]] by summing products of rows of A with columns of B.
• Main Method: Tests with square (2×2), non-square (1×3 × 3×1, 3×2 × 2×3), and incompatible matrices, printing inputs and results.
• Matrix Multiplication: Each element result[i][j] is the dot product of row i of A and column j of B.

Complexity Analysis Table

Note:

• m is the number of rows in A, n is the number of columns in A/rows in B, p is the number of columns in B.
• Time complexity: O(mnp), as the algorithm iterates m*p times, each performing n multiplications and additions.
• Space complexity: O(m*p), for the result matrix. Temporary variables use O(1) space.
• Best, average, and worst cases are O(mnp).

✅ Tip: Always check matrix compatibility before multiplication to avoid errors. Test with various sizes, including single-row/column matrices, to ensure robustness.

⚠ Warning: Ensure matrices are not null and have consistent row/column sizes to avoid NullPointerException or ArrayIndexOutOfBoundsException. Be cautious with large matrices, as O(mnp) time complexity can be slow.