Matrix

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

Operation	Dense Matrix	Sparse Matrix	NumPy Matrix
Access	O(1)	O(1)	O(1)
Addition	O(mn)	O(k)*	O(mn)
Multiplication	O(mnp)**	O(kp)***	O(mnp)
Transpose	O(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

Implementation	Space Complexity	Additional Notes
Dense Matrix	O(mn)	All elements stored
Sparse Matrix	O(k)	Only non-zero elements
NumPy Matrix	O(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

2. Single Element

def is_single_element(self):
    return self.rows == 1 and self.cols == 1

3. 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

2. 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)

2. 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

2. 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

2. 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

3. 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