How Matrix Multiplication Is Implemented in TheAlgorithms/Python

TheAlgorithms/Python implements matrix multiplication through both an object-oriented Matrix class in matrix/matrix_class.py and a procedural multiply function in matrix/matrix_operation.py, using dot-product calculations and dimension validation to ensure mathematical correctness.

TheAlgorithms/Python provides educational implementations of fundamental linear algebra operations, with matrix multiplication serving as a core building block for more complex algorithms. The repository offers two distinct approaches: an object-oriented interface that wraps matrices in a feature-rich class, and a lightweight functional API for direct list-of-lists manipulation. Both implementations validate dimensions rigorously and compute the standard row-by-column dot product, as found in production linear algebra libraries.

Object-Oriented Matrix Multiplication in matrix/matrix_class.py

The Matrix class encapsulates matrix arithmetic through operator overloading, allowing intuitive expressions like A * B.

Dimension Validation and Column Extraction

The __mul__ method first validates that the left matrix's column count matches the right matrix's row count. If dimensions align, the method invokes other.columns() to generate column vectors on-the-fly.

def __mul__(self, other: Matrix | float) -> Matrix:
    if isinstance(other, (int, float)):
        # scalar multiplication handled elsewhere

        ...
    elif isinstance(other, Matrix):
        if self.num_columns != other.num_rows:
            raise ValueError(
                "The number of columns in the first matrix must "
                "be equal to the number of rows in the second"
            )
        return Matrix(
            [
                [Matrix.dot_product(row, column) for column in other.columns()]
                for row in self.rows
            ]
        )

The columns() helper builds column vectors using [[row[i] for row in self.rows] for i in range(len(self.rows[0]))], preparing the data for dot-product computation.

The Dot Product Calculation

Each entry in the result matrix equals the dot product between a row from the first matrix and a column from the second. The Matrix.dot_product classmethod handles this computation:

@classmethod
def dot_product(cls, row: list[int], column: list[int]) -> int:
    return sum(row[i] * column[i] for i in range(len(row)))

The nested list comprehension constructs the final product matrix, which is wrapped in a new Matrix instance to preserve the class API for further chained operations.

Procedural Implementation in matrix/matrix_operation.py

For users preferring raw data structures, the multiply function operates directly on nested lists without class encapsulation.

Input Validation with Helper Functions

The function begins with strict dimension checking via _verify_matrix_sizes, which extracts row and column counts and raises a ValueError if the inner dimensions mismatch:

def multiply(matrix_a: list[list[int]], matrix_b: list[list[int]]) -> list[list[int]]:
    if _check_not_integer(matrix_a) and _check_not_integer(matrix_b):
        rows, cols = _verify_matrix_sizes(matrix_a, matrix_b)

    if cols[0] != rows[1]:
        raise ValueError(f"Cannot multiply matrix of dimensions ({rows[0]},{cols[0]}) "
                         f"and ({rows[1]},{cols[1]})")

List Comprehension Approach

Rather than explicit triple loops, the implementation uses Python's zip function to transpose the second matrix lazily via zip(*matrix_b). The core computation employs a generator expression within a sum:

    return [
        [sum(m * n for m, n in zip(i, j)) for j in zip(*matrix_b)]
        for i in matrix_a
    ]

Here, i represents a row from the first matrix and j represents a column from the transposed second matrix, maintaining the mathematical row-by-column multiplication pattern.

Practical Code Examples

Using the Matrix Class

from matrix.matrix_class import Matrix

A = Matrix([[1, 2, 3],
            [4, 5, 6]])
B = Matrix([[7, 8],
            [9, 10],
            [11, 12]])

C = A * B          # Matrix multiplication

print(C)           # → [[58. 64.]

                   #    [139. 154.]]

Using the Functional API

from matrix.matrix_operation import multiply

A = [[1, 2, 3],
     [4, 5, 6]]
B = [[7, 8],
     [9, 10],
     [11, 12]]

C = multiply(A, B)
print(C)           # → [[58, 64], [139, 154]]

Both snippets produce identical numerical results; the first returns a Matrix object supporting further operations, while the second yields a plain list-of-lists.

Summary

• TheAlgorithms/Python provides dual implementations of matrix multiplication: an object-oriented Matrix class and a procedural multiply function.
• Both approaches enforce dimension compatibility—columns of the first matrix must equal rows of the second—raising ValueError on mismatch.
• The dot product serves as the fundamental operation, implemented via sum(row[i] * column[i] ...) in the class method and sum(m * n for m, n in zip(...)) in the functional version.
• File locations: Core logic resides in matrix/matrix_class.py and matrix/matrix_operation.py, with applications in linear_algebra/matrix_inversion.py and dynamic_programming/matrix_chain_multiplication.py.

Frequently Asked Questions

What is the difference between the Matrix class and the multiply function?

The Matrix class provides an object-oriented interface with operator overloading (using * for multiplication), stateful matrix objects, and additional methods like inversion and exponentiation. The multiply function offers a stateless, functional approach that operates directly on nested Python lists, making it suitable for lightweight scripts or educational demonstrations without class overhead.

How does the repository handle invalid matrix dimensions?

Both implementations validate dimensions before computation. The Matrix.__mul__ method checks self.num_columns != other.num_rows, while the procedural multiply function uses _verify_matrix_sizes to compare extracted dimensions. Both raise explicit ValueError messages indicating the incompatible matrix sizes.

Where can I find examples of matrix multiplication used in algorithms?

The repository demonstrates practical applications in linear_algebra/matrix_inversion.py, which uses Matrix multiplication during Gaussian elimination, and dynamic_programming/matrix_chain_multiplication.py, which applies the operation within an optimization context to find the most efficient multiplication order.

Why does the procedural implementation use zip(*matrix_b)?

The expression zip(*matrix_b) unpacks and transposes the second matrix, converting columns into rows that can be iterated alongside rows from the first matrix. This elegant Python idiom eliminates explicit index-based column extraction while maintaining the mathematical row-by-column multiplication pattern.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}