​
Matrix

​
Core Implementation

​
Basic Matrix Implementation

class Matrix:
    def __init__(self, rows, cols, default_value=0):
        self.rows = rows
        self.cols = cols
        self.matrix = [[default_value] * cols for _ in range(rows)]
    
    def __getitem__(self, key):
        row, col = key
        self._validate_indices(row, col)
        return self.matrix[row][col]
    
    def __setitem__(self, key, value):
        row, col = key
        self._validate_indices(row, col)
        self.matrix[row][col] = value
    
    def _validate_indices(self, row, col):
        if not (0 <= row < self.rows and 0 <= col < self.cols):
            raise IndexError("Matrix index out of range")
    
    def add(self, other):
        if (self.rows, self.cols) != (other.rows, other.cols):
            raise ValueError("Matrix dimensions must match")
        
        result = Matrix(self.rows, self.cols)
        for i in range(self.rows):
            for j in range(self.cols):
                result[i, j] = self[i, j] + other[i, j]
        return result
    
    def multiply(self, other):
        if self.cols != other.rows:
            raise ValueError("Matrix dimensions incompatible for multiplication")
        
        result = Matrix(self.rows, other.cols)
        for i in range(self.rows):
            for j in range(other.cols):
                sum_val = 0
                for k in range(self.cols):
                    sum_val += self[i, k] * other[k, j]
                result[i, j] = sum_val
        return result

​
Implementation Variations

​
1. Sparse Matrix

class SparseMatrix:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.elements = {}  # (row, col) -> value
    
    def __getitem__(self, key):
        return self.elements.get(key, 0)
    
    def __setitem__(self, key, value):
        if value != 0:
            self.elements[key] = value
        elif key in self.elements:
            del self.elements[key]
    
    def multiply(self, other):
        result = SparseMatrix(self.rows, other.cols)
        for (i, k), val1 in self.elements.items():
            for j in range(other.cols):
                if (k, j) in other.elements:
                    key = (i, j)
                    result[key] = result[key] + val1 * other[k, j]
        return result

​
2. Numpy-style Matrix

import numpy as np

class NumPyMatrix:
    def __init__(self, data):
        self.data = np.array(data)
    
    def add(self, other):
        return NumPyMatrix(self.data + other.data)
    
    def multiply(self, other):
        return NumPyMatrix(np.dot(self.data, other.data))
    
    def transpose(self):
        return NumPyMatrix(self.data.T)

​
Time Complexities

OperationDense MatrixSparse MatrixNumPy Matrix
AccessO(1)O(1)O(1)
AdditionO(mn)O(k)*O(mn)
MultiplicationO(mnp)**O(kp)***O(mnp)
TransposeO(mn)O(k)O(1)****
* k is number of non-zero elements ** For m×n and n×p matrices *** k is number of non-zero elements in first matrix **** View only, actual transpose is O(mn)

​
Space Complexities

ImplementationSpace ComplexityAdditional Notes
Dense MatrixO(mn)All elements stored
Sparse MatrixO(k)Only non-zero elements
NumPy MatrixO(mn)Contiguous memory allocation

​
Common Matrix Patterns

  1. Matrix Traversal
    • Row-wise
    • Column-wise
    • Diagonal
    • Spiral
  2. Matrix Operations
    • Addition/Subtraction
    • Multiplication
    • Transpose
    • Inverse
  3. Matrix Transformations
    • Rotation
    • Reflection
    • Scaling
    • Translation
  4. Matrix Search
    • Binary search
    • Row-column search
    • Sorted matrix search
  5. Matrix Decomposition
    • LU decomposition
    • QR decomposition
    • Eigenvalues
    • SVD
  6. Special Matrices
    • Identity matrix
    • Triangular matrix
    • Diagonal matrix
    • Symmetric matrix

​
Edge Cases to Consider

  1. Empty Matrix
def handle_empty_matrix(self):
    return self.rows == 0 or self.cols == 0
  1. Single Element
def is_single_element(self):
    return self.rows == 1 and self.cols == 1
  1. Invalid Dimensions
def validate_dimensions(self, other):
    if (self.rows, self.cols) != (other.rows, other.cols):
        raise ValueError("Matrix dimensions must match")

​
Optimization Techniques

  1. Block Matrix Multiplication
def block_multiply(self, other, block_size=32):
    result = Matrix(self.rows, other.cols)
    for i in range(0, self.rows, block_size):
        for j in range(0, other.cols, block_size):
            for k in range(0, self.cols, block_size):
                # Multiply block
                for bi in range(min(block_size, self.rows - i)):
                    for bj in range(min(block_size, other.cols - j)):
                        sum_val = result[i + bi, j + bj]
                        for bk in range(min(block_size, self.cols - k)):
                            sum_val += self[i + bi, k + bk] * other[k + bk, j + bj]
                        result[i + bi, j + bj] = sum_val
    return result
  1. Strassen’s Algorithm
def strassen_multiply(self, other):
    # Implementation for 2^n × 2^n matrices
    if self.rows <= 64:  # Use standard multiplication for small matrices
        return self.multiply(other)
    
    n = self.rows
    mid = n // 2
    
    # Divide matrices into quadrants
    a11 = self.submatrix(0, mid, 0, mid)
    a12 = self.submatrix(0, mid, mid, n)
    a21 = self.submatrix(mid, n, 0, mid)
    a22 = self.submatrix(mid, n, mid, n)
    
    b11 = other.submatrix(0, mid, 0, mid)
    b12 = other.submatrix(0, mid, mid, n)
    b21 = other.submatrix(mid, n, 0, mid)
    b22 = other.submatrix(mid, n, mid, n)
    
    # Compute the 7 products
    p1 = (a11 + a22).strassen_multiply(b11 + b22)
    p2 = (a21 + a22).strassen_multiply(b11)
    p3 = a11.strassen_multiply(b12 - b22)
    p4 = a22.strassen_multiply(b21 - b11)
    p5 = (a11 + a12).strassen_multiply(b22)
    p6 = (a21 - a11).strassen_multiply(b11 + b12)
    p7 = (a12 - a22).strassen_multiply(b21 + b22)
    
    # Compute quadrants of result
    c11 = p1 + p4 - p5 + p7
    c12 = p3 + p5
    c21 = p2 + p4
    c22 = p1 - p2 + p3 + p6
    
    return Matrix.combine(c11, c12, c21, c22)

​
Memory Management

  1. Memory-Efficient Storage
class CompactMatrix:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        # Use 1D array for storage
        self.data = bytearray(rows * cols * 8)  # For double precision
    
    def __getitem__(self, key):
        i, j = key
        return struct.unpack('d', self.data[8*(i*self.cols + j):8*(i*self.cols + j+1)])[0]
    
    def __setitem__(self, key, value):
        i, j = key
        self.data[8*(i*self.cols + j):8*(i*self.cols + j+1)] = struct.pack('d', value)
  1. Memory Pool
class MatrixPool:
    def __init__(self, max_size):
        self.pool = {}  # (rows, cols) -> list of available matrices
    
    def get_matrix(self, rows, cols):
        key = (rows, cols)
        if key in self.pool and self.pool[key]:
            return self.pool[key].pop()
        return Matrix(rows, cols)
    
    def return_matrix(self, matrix):
        key = (matrix.rows, matrix.cols)
        if key not in self.pool:
            self.pool[key] = []
        self.pool[key].append(matrix)

​
Performance Considerations

  1. Cache-Friendly Access
def cache_friendly_multiply(self, other):
    result = Matrix(self.rows, other.cols)
    # Transpose second matrix for better cache locality
    other_t = other.transpose()
    for i in range(self.rows):
        for j in range(other.cols):
            sum_val = 0
            for k in range(self.cols):
                sum_val += self[i, k] * other_t[j, k]
            result[i, j] = sum_val
    return result
  1. Parallel Processing
from multiprocessing import Pool

def parallel_multiply(self, other, num_processes=4):
    pool = Pool(processes=num_processes)
    result = Matrix(self.rows, other.cols)
    
    def multiply_row(i):
        return [sum(self[i, k] * other[k, j] 
                for k in range(self.cols)) 
                for j in range(other.cols)]
    
    results = pool.map(multiply_row, range(self.rows))
    for i, row in enumerate(results):
        for j, val in enumerate(row):
            result[i, j] = val
    
    pool.close()
    return result

​
Common Pitfalls

  1. Shallow Copy
# Wrong
def copy_wrong(self):
    return self.matrix[:]  # Shallow copy

# Correct
def copy_correct(self):
    result = Matrix(self.rows, self.cols)
    for i in range(self.rows):
        for j in range(self.cols):
            result[i, j] = self[i, j]
    return result
  1. Dimension Mismatch
# Wrong
def multiply_wrong(self, other):
    result = Matrix(self.rows, other.cols)
    for i in range(self.rows):
        for j in range(other.cols):
            result[i, j] = sum(self[i, k] * other[k, j] 
                             for k in range(self.cols))  # Possible IndexError

# Correct
def multiply_correct(self, other):
    if self.cols != other.rows:
        raise ValueError("Matrix dimensions incompatible for multiplication")
    # ... rest of multiplication code
  1. Memory Efficiency
# Wrong (Memory inefficient)
def add_wrong(self, other):
    return [[self[i, j] + other[i, j] 
             for j in range(self.cols)] 
             for i in range(self.rows)]

# Correct
def add_correct(self, other):
    result = Matrix(self.rows, self.cols)
    for i in range(self.rows):
        for j in range(self.cols):
            result[i, j] = self[i, j] + other[i, j]
    return result