Matrix

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

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");
    }
};

Basic Matrix Operations

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;
}

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

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