The Algorithms - Python Python TheAlgorithms/Python

Matrix Algorithms in TheAlgorithms/Python

Six matrix operations from elementwise addition to Pascal's triangle generation.

6 stops ~12 min Verified 2026-05-05

What you will learn

How the add function uses nested zip and sum to handle any number of same-size matrices in one expression
How rotation by 90 degrees decomposes into transpose followed by row reversal
How spiral traversal peels the first row, then rotates the remaining submatrix into position for the next recursive call
How the staircase search exploits sorted row and column order to eliminate a row or column per step
How the 2x2 matrix inverse uses the adjugate formula with Decimal arithmetic to avoid float rounding errors
How Pascal's triangle is built row by row using the relation that each interior element equals the sum of the two elements above it

Prerequisites

Familiarity with Python list comprehensions and zip
Basic understanding of matrix concepts: rows, columns, transpose
Comfort with recursion and index arithmetic

1 / 6

Matrix addition: nested zip and sum handle any number of matrices

matrix/matrix_operation.py:10

Matrix addition zips corresponding rows across all input matrices and sums each column position in a single nested comprehension.

Adding matrices element by element is straightforward for two matrices, but this function handles any number at once. The variadic parameter collects all arguments into a tuple. Before summing, the guard checks that all inputs are properly nested lists with matching dimensions. The double-zip idiom on line 26 is the core: the outer zip groups corresponding rows across all matrices, producing a tuple of rows for each row index. The inner zip then groups corresponding elements within those row tuples, producing a tuple of column values. sum(t) adds those column values together. The doctest with three matrices confirms that three 2x2 matrices can be added in one call. A dimension mismatch triggers the _verify_matrix_sizes check. The multiply function later in the same file uses a similar zip-based comprehension for the dot product.

Key takeaway

The double-zip idiom groups corresponding rows first, then corresponding column elements, so sum(t) adds all matching positions across any number of matrices.

def add(*matrix_s: list[list[int]]) -> list[list[int]]:
    """
    >>> add([[1,2],[3,4]],[[2,3],[4,5]])
    [[3, 5], [7, 9]]
    >>> add([[1.2,2.4],[3,4]],[[2,3],[4,5]])
    [[3.2, 5.4], [7, 9]]
    >>> add([[1, 2], [4, 5]], [[3, 7], [3, 4]], [[3, 5], [5, 7]])
    [[7, 14], [12, 16]]
    >>> add([3], [4, 5])
    Traceback (most recent call last):
      ...
    TypeError: Expected a matrix, got int/list instead
    """
    if all(_check_not_integer(m) for m in matrix_s):
        for i in matrix_s[1:]:
            _verify_matrix_sizes(matrix_s[0], i)
        return [[sum(t) for t in zip(*m)] for m in zip(*matrix_s)]
    raise TypeError("Expected a matrix, got int/list instead")

2 / 6

Matrix rotation: transpose plus reversal implements 90-degree turns

matrix/rotate_matrix.py:28

A 90-degree counterclockwise rotation equals transpose followed by reversing each row; each of the three rotation angles is a different combination of transpose and reversal.

Rotating a matrix by 90 degrees clockwise can be achieved with two simple operations: transpose (flip along the main diagonal) and then reverse each row. The three functions in this file implement all three standard rotation angles using different combinations of the same primitives. Rotate 90 transposes then reverses rows. Rotate 180 reverses rows then reverses columns, which is equivalent to a point reflection through the center. Rotate 270 transposes then reverses columns. Each function body is one line, and each has a doctest asserting equality with an alternative composition, which proves that both paths produce the same result. The transpose function modifies the matrix in place using matrix[:] slice assignment with zip(*matrix), which pivots rows into columns. The make_matrix helper generates a sequential 4x4 integer grid for testing.

Key takeaway

All three rotation angles compose from two primitives: transpose swaps rows with columns, and row or column reversal flips an axis.

def rotate_90(matrix: list[list[int]]) -> list[list[int]]:
    """
    >>> rotate_90(make_matrix())
    [[4, 8, 12, 16], [3, 7, 11, 15], [2, 6, 10, 14], [1, 5, 9, 13]]
    >>> rotate_90(make_matrix()) == transpose(reverse_column(make_matrix()))
    True
    """

    return reverse_row(transpose(matrix))
    # OR.. transpose(reverse_column(matrix))


def rotate_180(matrix: list[list[int]]) -> list[list[int]]:
    """
    >>> rotate_180(make_matrix())
    [[16, 15, 14, 13], [12, 11, 10, 9], [8, 7, 6, 5], [4, 3, 2, 1]]
    >>> rotate_180(make_matrix()) == reverse_column(reverse_row(make_matrix()))
    True
    """

    return reverse_row(reverse_column(matrix))
    # OR.. reverse_column(reverse_row(matrix))


def rotate_270(matrix: list[list[int]]) -> list[list[int]]:
    """
    >>> rotate_270(make_matrix())
    [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]]
    >>> rotate_270(make_matrix()) == transpose(reverse_row(make_matrix()))
    True
    """

    return reverse_column(transpose(matrix))
    # OR.. transpose(reverse_row(matrix))


def transpose(matrix: list[list[int]]) -> list[list[int]]:
    matrix[:] = [list(x) for x in zip(*matrix)]
    return matrix

3 / 6

Spiral traversal: peel the first row, then rotate the remainder

matrix/spiral_print.py:82

Spiral traversal peels one edge per recursion level by popping the first row, then rotating the remaining matrix so the next edge aligns at the top.

A naive spiral traversal tracks four boundary pointers and updates them after each edge is collected, requiring careful bookkeeping. This recursive version uses a different insight: after peeling the top row, the right column of the remaining matrix becomes the top row if the matrix is transposed and then reversed. The two-line body of the function does exactly that. matrix.pop(0) removes and returns the first row. zip(*matrix) transposes the remaining rows into columns, and [::-1] reverses the resulting list so the former right column is now first. Passing this transformed matrix back into spiral_traversal collects the former right column next, then the former bottom row reversed, then the former left column reversed. The dry run comments in the docstring trace each stage explicitly, making the recursion concrete. The base case returns an empty list when the matrix is exhausted.

Key takeaway

Spiral traversal reduces to: pop the first row, transpose the remainder, reverse it, recurse. No boundary pointers needed because rotation realigns the next edge at the top.

def spiral_traversal(matrix: list[list]) -> list[int]:
    """
    >>> spiral_traversal([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
    [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

    Example:
    matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
    Algorithm:
        Step 1. first pop the 0 index list. (which is [1,2,3,4] and concatenate the
                output of [step 2])
        Step 2. Now perform matrix's Transpose operation (Change rows to column
                and vice versa) and reverse the resultant matrix.
        Step 3. Pass the output of [2nd step], to same recursive function till
                base case hits.
    Dry Run:
    Stage 1.
    [1, 2, 3, 4] +   spiral_traversal([
        [8, 12], [7, 11], [6, 10], [5, 9]]
     ])
    Stage 2.
    [1, 2, 3, 4, 8, 12] + spiral_traversal([
        [11, 10, 9], [7, 6, 5]
    ])
    Stage 3.
    [1, 2, 3, 4, 8, 12, 11, 10, 9] + spiral_traversal([
        [5], [6], [7]
    ])
    Stage 4.
    [1, 2, 3, 4, 8, 12, 11, 10, 9, 5] + spiral_traversal([
        [5], [6], [7]
    ])
    Stage 5.
    [1, 2, 3, 4, 8, 12, 11, 10, 9, 5] + spiral_traversal([[6, 7]])
    Stage 6.
    [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] + spiral_traversal([])
    """
    if matrix:
        return list(matrix.pop(0)) + spiral_traversal(
            [list(row) for row in zip(*matrix)][::-1]
        )
    else:
        return []

4 / 6

Sorted matrix search: eliminate a row or column per step

matrix/searching_in_sorted_matrix.py:4

Staircase search starts at the bottom-left corner and moves left when the target is smaller or down when larger, eliminating one row or column per comparison.

Naive search in a 2D matrix scans every element in O(mn) time. When rows are sorted left-to-right and columns are sorted top-to-bottom, the staircase algorithm exploits both orderings to eliminate one row or column per comparison. Starting at the bottom-left corner, the algorithm uses the current element as a pivot. If the target is smaller, all elements to the right in this row are also too large, so the row is eliminated by moving up. If the target is larger, all elements above in this column are too small, so the column is eliminated by moving right. Each step eliminates one row or column, giving O(m + n) total comparisons. The doctests confirm correct behavior for a hit, a miss beyond the maximum, and a floating-point key.

Key takeaway

Staircase search achieves O(m+n) by starting at the corner where moving in one direction decreases the value and moving in the other increases it.

def search_in_a_sorted_matrix(mat: list[list[int]], m: int, n: int, key: float) -> None:
    """
    >>> search_in_a_sorted_matrix(
    ...     [[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]], 3, 3, 5)
    Key 5 found at row- 1 column- 2
    >>> search_in_a_sorted_matrix(
    ...     [[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]], 3, 3, 21)
    Key 21 not found
    >>> search_in_a_sorted_matrix(
    ...     [[2.1, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]], 3, 3, 2.1)
    Key 2.1 found at row- 1 column- 1
    >>> search_in_a_sorted_matrix(
    ...     [[2.1, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]], 3, 3, 2.2)
    Key 2.2 not found
    """
    i, j = m - 1, 0
    while i >= 0 and j < n:
        if key == mat[i][j]:
            print(f"Key {key} found at row- {i + 1} column- {j + 1}")
            return
        if key < mat[i][j]:
            i -= 1
        else:
            j += 1
    print(f"Key {key} not found")

5 / 6

Matrix inverse: Decimal arithmetic avoids float rounding in the adjugate formula

matrix/inverse_of_matrix.py:64

The 2x2 matrix inverse uses the adjugate formula: swap the diagonal elements, negate the off-diagonal ones, then divide all by the determinant.

A 2x2 matrix has a closed-form inverse: swap the two diagonal elements, negate both off-diagonal elements, and divide every element by the determinant. This implementation follows that formula exactly. The determinant is ad - bc for elements [[a, b], [c, d]]. A zero determinant means the matrix is singular and has no inverse. The Decimal type wraps all arithmetic to avoid the accumulated rounding errors that float multiplication can introduce when computing determinants of near-singular matrices. The alias d = Decimal keeps the arithmetic expressions readable. After building swapped_matrix with the adjugate elements, each value is divided by the determinant using a list comprehension. The or 0.0 guards against -0.0 from float division. The function also handles 3x3 matrices using the Sarrus rule and cofactor expansion lower in the same file.

Key takeaway

Using Decimal for determinant arithmetic prevents the float rounding drift that accumulates when multiplying and subtracting floating-point matrix elements.

    d = Decimal

    # Check if the provided matrix has 2 rows and 2 columns
    # since this implementation only works for 2x2 matrices
    if len(matrix) == 2 and len(matrix[0]) == 2 and len(matrix[1]) == 2:
        # Calculate the determinant of the matrix
        determinant = float(
            d(matrix[0][0]) * d(matrix[1][1]) - d(matrix[1][0]) * d(matrix[0][1])
        )
        if determinant == 0:
            raise ValueError("This matrix has no inverse.")

        # Creates a copy of the matrix with swapped positions of the elements
        swapped_matrix = [[0.0, 0.0], [0.0, 0.0]]
        swapped_matrix[0][0], swapped_matrix[1][1] = matrix[1][1], matrix[0][0]
        swapped_matrix[1][0], swapped_matrix[0][1] = -matrix[1][0], -matrix[0][1]

        # Calculate the inverse of the matrix
        return [
            [(float(d(n)) / determinant) or 0.0 for n in row] for row in swapped_matrix
        ]

6 / 6

Pascal's triangle: each row derives from the row above

matrix/pascal_triangle.py:35

Pascal's triangle is built by defining each interior element as the sum of the two elements directly above it in the previous row.

Pascal's triangle encodes binomial coefficients: each interior element equals the sum of the two elements directly above it. This property means each new row can be computed purely from the previous one, making a sequential loop natural. The generate_pascal_triangle function handles validation then delegates row construction to populate_current_row, which initializes the first and last elements to 1 and calls calculate_current_element for each interior position. calculate_current_element reads triangle[current_row_idx - 1][current_col_idx - 1] and triangle[current_row_idx - 1][current_col_idx] and writes their sum into the new row. The doctests trace the output from 0 rows (empty) through 5 rows, confirming the familiar triangular shape. The file also contains generate_pascal_triangle_optimized, which uses symmetry to halve the number of element computations per row by reflecting the first half.

Key takeaway

Each row is computed from the previous one: first and last elements are 1, and each interior element is the sum of its two upper neighbors.

def generate_pascal_triangle(num_rows: int) -> list[list[int]]:
    """
    Create Pascal's triangle for different number of rows
    >>> generate_pascal_triangle(0)
    []
    >>> generate_pascal_triangle(1)
    [[1]]
    >>> generate_pascal_triangle(2)
    [[1], [1, 1]]
    >>> generate_pascal_triangle(3)
    [[1], [1, 1], [1, 2, 1]]
    >>> generate_pascal_triangle(4)
    [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
    >>> generate_pascal_triangle(5)
    [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
    >>> generate_pascal_triangle(-5)
    Traceback (most recent call last):
        ...
    ValueError: The input value of 'num_rows' should be greater than or equal to 0
    >>> generate_pascal_triangle(7.89)
    Traceback (most recent call last):
        ...
    TypeError: The input value of 'num_rows' should be 'int'
    """

    if not isinstance(num_rows, int):
        raise TypeError("The input value of 'num_rows' should be 'int'")

    if num_rows == 0:
        return []
    elif num_rows < 0:
        raise ValueError(
            "The input value of 'num_rows' should be greater than or equal to 0"
        )

    triangle: list[list[int]] = []
    for current_row_idx in range(num_rows):
        current_row = populate_current_row(triangle, current_row_idx)
        triangle.append(current_row)
    return triangle

Your codebase next

Create code tours for your project

Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.

Install Intraview Free