Matrix Multiplication - Linear Algebra

Definition and Basic Concept

Matrix Product

Matrix multiplication: operation producing new matrix from two matrices. Each element: dot product of row from first matrix and column from second matrix. Result: matrix with dimensions based on input matrices.

Notation

Given matrices A (m×n) and B (n×p), product denoted as C = AB with dimension m×p. Element c_ij = sum over k of a_ik * b_kj.

Conceptual Summary

Combines linear combinations of rows and columns. Encodes composition of linear transformations. Basis for many linear algebra operations.

Conditions for Multiplication

Dimension Compatibility

Number of columns in first matrix must equal number of rows in second matrix: if A is m×n, B must be n×p. Otherwise, multiplication undefined.

Resulting Dimensions

Result matrix dimensions: rows of A by columns of B (m×p).

Non-Commutativity

AB generally ≠ BA. Both products may be undefined or differ in dimension and values.

Calculation Method

Dot Product Computation

Each element c_ij calculated as dot product of i-th row of A and j-th column of B:

c_{ij} = Σ (k=1 to n) a_{ik} * b_{kj}

Step-by-Step Process

Select row i in A.
Select column j in B.
Multiply corresponding elements.
Sum products to get c_ij.
Repeat for all i = 1..m, j = 1..p.

Example Calculation

For A (2×3) and B (3×2):

A = [a11 a12 a13 a21 a22 a23]B = [b11 b12 b21 b22 b31 b32]C = AB with elements:c11 = a11*b11 + a12*b21 + a13*b31c12 = a11*b12 + a12*b22 + a13*b32c21 = a21*b11 + a22*b21 + a23*b31c22 = a21*b12 + a22*b22 + a23*b32

Properties of Matrix Multiplication

Associativity

(AB)C = A(BC) for compatible dimensions. Enables grouping without change in result.

Distributivity

A(B + C) = AB + AC; (A + B)C = AC + BC. Matrix multiplication distributes over addition.

Non-Commutativity

In general, AB ≠ BA. Special cases exist (e.g., diagonal matrices).

Multiplicative Identity

Existence of identity matrix I such that AI = IA = A for all conformable A.

Zero Matrix Property

Multiplying any matrix by zero matrix yields zero matrix. Nullifies information.

Algorithms for Matrix Multiplication

Standard Algorithm

Triple nested loops: iterating rows, columns, and sum indices. Complexity: O(mnp).

Strassen's Algorithm

Divide-and-conquer approach reducing multiplications. Complexity: approximately O(n^2.81). Practical for large square matrices.

Coppersmith-Winograd Algorithm

Advanced algorithm with complexity near O(n^2.376). Mainly theoretical due to implementation complexity.

Parallel and GPU-based Methods

Utilize hardware parallelism to accelerate computation. Widely used in scientific computing and machine learning.

Worked Examples

Example 1: Small Integer Matrices

Multiply A (2×2) and B (2×2):

A = [1 2 3 4]B = [5 6 7 8]C = AB = [ (1*5 + 2*7) (1*6 + 2*8) (3*5 + 4*7) (3*6 + 4*8)] = [ 19 22 43 50]

Example 2: Rectangular Matrices

Multiply A (2×3) and B (3×2):

A = [2 0 1 1 3 1]B = [1 2 0 1 4 0]C = AB = [ (2*1 + 0*0 + 1*4) (2*2 + 0*1 + 1*0) (1*1 + 3*0 + 1*4) (1*2 + 3*1 + 1*0)] = [ 6 4 5 5]

Geometric Interpretation

Linear Transformations

Matrix multiplication corresponds to composition of linear maps. Applying B then A is AB.

Change of Basis

Multiplying by change-of-basis matrix transforms coordinate representation.

Scaling, Rotation, Shear

Specific matrices perform geometric operations. Multiplication combines effects.

Applications in Mathematics and Science

Systems of Linear Equations

Matrix products represent transformations of coefficient matrices. Key in solving Ax = b.

Computer Graphics

Transformations for rendering: scaling, rotation, translation via matrix multiplication.

Data Science and Machine Learning

Matrix operations fundamental in neural networks, PCA, regression.

Physics and Engineering

State transformations, quantum mechanics operators, signal processing.

Computational Complexity

Naive Complexity

Standard algorithm: O(mnp) operations for m×n and n×p matrices.

Improved Algorithms

Strassen: O(n^2.81), Coppersmith-Winograd: O(n^2.376). Tradeoff: complexity vs. implementation overhead.

Practical Considerations

Memory hierarchy, parallelism, and sparsity affect actual performance.

Multiplication Involving Special Matrices

Diagonal Matrices

Multiplication simplifies to scaling rows or columns. Computationally efficient.

Identity Matrix

Leaves matrix unchanged. Acts as multiplicative identity.

Orthogonal Matrices

Preserve length and angles. Multiplication corresponds to rotation/reflection.

Sparse Matrices

Optimization possible by ignoring zero elements.

Common Errors and Misconceptions

Ignoring Dimension Compatibility

Attempting to multiply matrices without matching inner dimensions.

Assuming Commutativity

Believing AB = BA, leading to incorrect results.

Misinterpreting Result Dimensions

Confusing size of output matrix with input matrices.

Incorrect Element Calculation

Mixing rows and columns or summation indices.

References

Axler, S., Linear Algebra Done Right, Springer, 3rd Ed., 2015, pp. 45-78.
Horn, R. A., & Johnson, C. R., Matrix Analysis, Cambridge Univ. Press, 2nd Ed., 2012, pp. 120-158.
Cormen, T. H., et al., Introduction to Algorithms, MIT Press, 3rd Ed., 2009, pp. 983-1005.
Strang, G., Introduction to Linear Algebra, Wellesley-Cambridge Press, 5th Ed., 2016, pp. 135-170.
Demmel, J. W., Applied Numerical Linear Algebra, SIAM, 1997, pp. 90-120.

Matrix Multiplication Rules
Dimensions must satisfy: A(m×n), B(n×p) → AB(m×p) AB ≠ BA in general (non-commutative) Associative: (AB)C = A(BC) Distributive: A(B + C) = AB + AC Identity matrix I satisfies AI = IA = A

Algorithm Complexity Comparison

Algorithm	Time Complexity	Remarks
Standard (Naive)	O(n³)	Simple, inefficient for large n
Strassen's	O(n².81)	Faster, practical for large matrices
Coppersmith-Winograd	O(n^2.376)	Theoretical, complex implementation

"Matrix multiplication is the backbone of linear algebra, encoding transformations that govern countless scientific and engineering problems." -- Gilbert Strang