Learn matrix multiplication with clear conditions, step-by-step examples, algorithm, time and space complexity, and real-world applications in computer science and machine learning.
Matrix Multiplication
Matrix multiplication is the process of multiplying two matrices to obtain a third matrix. This operation is very important in fields such as computer science, computer graphics, machine learning, signal processing, data science, and scientific computing.
Condition for Matrix Multiplication
Let:
- Matrix A be of size m × n
- Matrix B be of size p × q
Matrix multiplication A × B is possible if and only if:
Number of columns in A = Number of rows in B
i.e., n = p
The size of the resulting matrix C = A × B will be:
m × q
How Matrix Multiplication Works
To compute matrix multiplication:
- Take one row from matrix A
- Take one column from matrix B
- Multiply corresponding elements
- Add the products
This sum gives one element of the result matrix.
Mathematical Formula
If C = A × B, then each element is computed as:
Cᵢⱼ = Σ (Aᵢₖ × Bₖⱼ), where k = 1 to n
Example (Step-by-Step)
Matrix A (2 × 3)
A = \begin{bmatrix}
1 & 2 & 3 \
4 & 5 & 6
\end{bmatrix}
Matrix B (3 × 2)
B = \begin{bmatrix}
7 & 8 \
9 & 10 \
11 & 12
\end{bmatrix}
Since A is (2 × 3) and B is (3 × 2), multiplication is possible.
Resultant matrix size: (2 × 2)
Step 1: Calculate C[0][0]
Row 1 of A × Column 1 of B
(1×7) + (2×9) + (3×11) = 7 + 18 + 33 = 58
Step 2: Calculate C[0][1]
Row 1 of A × Column 2 of B
(1×8) + (2×10) + (3×12) = 8 + 20 + 36 = 64
Step 3: Calculate C[1][0]
Row 2 of A × Column 1 of B
(4×7) + (5×9) + (6×11) = 28 + 45 + 66 = 139
Step 4: Calculate C[1][1]
Row 2 of A × Column 2 of B
(4×8) + (5×10) + (6×12) = 32 + 50 + 72 = 154
Final Result Matrix
C = \begin{bmatrix}
58 & 64 \
139 & 154
\end{bmatrix}
Algorithm for Matrix Multiplication
- Read matrix A of size m × n
- Read matrix B of size n × p
- Create result matrix C of size m × p
- Perform multiplication:
- for i = 0 to m-1
- for j = 0 to p-1
- C[i][j] = 0
- for k = 0 to n-1
- C[i][j] += A[i][k] * B[k][j]
- Print matrix C
Time Complexity
- Outer loop → m times
- Middle loop → p times
- Inner loop → n times
Total Time Complexity:
O(m × n × p)
For square matrices of size n × n:
O(n³)
Space Complexity
- Space required for result matrix C: O(m × p)
- Extra space used: constant
Total Space Complexity:
O(m × p)
Applications of Matrix Multiplication
- Machine Learning Algorithms
- Neural Networks
- Computer Graphics
- Image Processing
- Scientific Computing
- Physics Simulations
- Data Transformations
Types of Matrix Multiplication
- Standard Matrix Multiplication
- Strassen’s Algorithm → O(n²·⁸¹)
- Divide and Conquer Matrix Multiplication
- Sparse Matrix Multiplication
- POP- Introduction to Programming Using ‘C’
- DS – Data structure Using C
- OOP – Object Oriented Programming
- Java Programming
- DBMS – Database Management System
- RDBMS – Relational Database Management System
- https://defineinfoloop.blogspot.com/?m=1