Matrix

Matrix is the fundamental data structure used in various applications, from image processing to graph algorithms.

Introduction

A matrix is a two-dimensional arrangement of elements (typically numbers) organized in rows and columns. In computer science, matrices are fundamental data structures used in various applications, from image processing to graph algorithms.

Visual Representation

Visualization of Matrix Representation

Basic Terminology

As shown in the reference image:

Matrix: A rectangular array A of size m×n where m represents rows and n represents columns
Element: Each entry aij where i is the row index and j is the column index
Cell: The intersection of a row and column containing an element
Order/Dimension: The size of matrix specified as m×n (rows × columns)

Types of Matrices

1. Square Matrix

Number of rows equals number of columns (n×n)
Example: The reference image shows a 3×3 square matrix

2. Rectangular Matrix

Number of rows and columns are different (m×n where m≠n)
Used in various applications like image processing

3. Special Matrices

Diagonal Matrix: All elements outside the main diagonal are zero
Identity Matrix: Diagonal matrix with all diagonal elements as 1
Sparse Matrix: Most elements are zero
Dense Matrix: Most elements are non-zero
Triangular Matrix: Either upper or lower half contains all zeros

Implementation in Programming

class Matrix {
private:
    vector<vector<int>> matrix;
    int rows, cols;

public:
    Matrix(int r, int c) : rows(r), cols(c) {
        matrix.resize(rows, vector<int>(cols, 0));
    }
    
    void setElement(int i, int j, int value) {
        if (i >= 0 && i < rows && j >= 0 && j < cols)
            matrix[i][j] = value;
        else
            throw out_of_range("Matrix indices out of range");
    }
    
    int getElement(int i, int j) {
        if (i >= 0 && i < rows && j >= 0 && j < cols)
            return matrix[i][j];
        throw out_of_range("Matrix indices out of range");
    }
};

class Matrix:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.matrix = [[0 for j in range(cols)] for i in range(rows)]
    
    def set_element(self, i, j, value):
        if 0 <= i < self.rows and 0 <= j < self.cols:
            self.matrix[i][j] = value
        else:
            raise IndexError("Matrix indices out of range")
    
    def get_element(self, i, j):
        if 0 <= i < self.rows and 0 <= j < self.cols:
            return self.matrix[i][j]
        raise IndexError("Matrix indices out of range")

class Matrix {
    constructor(rows, cols) {
        this.rows = rows;
        this.cols = cols;
        this.matrix = Array(rows).fill().map(() => Array(cols).fill(0));
    }
    
    setElement(i, j, value) {
        if (i >= 0 && i < this.rows && j >= 0 && j < this.cols) {
            this.matrix[i][j] = value;
        } else {
            throw new Error("Matrix indices out of range");
        }
    }
    
    getElement(i, j) {
        if (i >= 0 && i < this.rows && j >= 0 && j < this.cols) {
            return this.matrix[i][j];
        }
        throw new Error("Matrix indices out of range");
    }
}

Basic Matrix Operations

Matrix Creation

First, initialize a matrix with the desired dimensions (rows × columns). All elements are typically initialized to zero or a default value.

Element Access

Access elements using row and column indices (i, j). Remember that array indices typically start at 0 in most programming languages.

Basic Operations

Implement fundamental operations like addition, subtraction, and multiplication following matrix arithmetic rules.

Matrix Operations Implementation

// Matrix Addition
vector<vector<int>> addMatrices(const vector<vector<int>>& A, 
                               const vector<vector<int>>& B) {
    int rows = A.size(), cols = A[0].size();
    vector<vector<int>> C(rows, vector<int>(cols));
    
    for(int i = 0; i < rows; i++)
        for(int j = 0; j < cols; j++)
            C[i][j] = A[i][j] + B[i][j];
            
    return C;
}

// Matrix Multiplication
vector<vector<int>> multiplyMatrices(const vector<vector<int>>& A,
                                    const vector<vector<int>>& B) {
    int m = A.size(), n = A[0].size(), p = B[0].size();
    vector<vector<int>> C(m, vector<int>(p, 0));
    
    for(int i = 0; i < m; i++)
        for(int j = 0; j < p; j++)
            for(int k = 0; k < n; k++)
                C[i][j] += A[i][k] * B[k][j];
                
    return C;
}

def add_matrices(A, B):
    rows, cols = len(A), len(A[0])
    C = [[0 for j in range(cols)] for i in range(rows)]
    
    for i in range(rows):
        for j in range(cols):
            C[i][j] = A[i][j] + B[i][j]
    return C

def multiply_matrices(A, B):
    m, n, p = len(A), len(A[0]), len(B[0])
    C = [[0 for j in range(p)] for i in range(m)]
    
    for i in range(m):
        for j in range(p):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

function addMatrices(A, B) {
    const rows = A.length, cols = A[0].length;
    const C = Array(rows).fill()
        .map(() => Array(cols).fill(0));
    
    for(let i = 0; i < rows; i++)
        for(let j = 0; j < cols; j++)
            C[i][j] = A[i][j] + B[i][j];
            
    return C;
}

function multiplyMatrices(A, B) {
    const m = A.length, n = A[0].length, p = B[0].length;
    const C = Array(m).fill()
        .map(() => Array(p).fill(0));
    
    for(let i = 0; i < m; i++)
        for(let j = 0; j < p; j++)
            for(let k = 0; k < n; k++)
                C[i][j] += A[i][k] * B[k][j];
                
    return C;
}

Time Complexity Analysis

Matrix operations can be computationally expensive. Be mindful of the following complexities:

Access: O(1)
Insertion: O(1)
Deletion: O(1)
Traversal: O(m×n)
Addition/Subtraction: O(m×n)
Multiplication: O(m×n×p)
Transpose: O(m×n)

Applications in DSA

Matrices are widely used in:

Graph representation (Adjacency Matrix)
Dynamic Programming
Image Processing
Machine Learning
Path Finding Algorithms

Best Practices

Always validate matrix dimensions before operations
Check for array bounds when accessing elements
Consider memory constraints for large matrices
Handle edge cases properly
Use appropriate data types for elements

Matrix

On this page