Matrix multiplication

Product of two matrices A (m x n) and B (n x p) is matrix C (m x p) defined elementwise:

C[i][j] = sum_{k=1}^{n} A[i][k] * B[k][j]

Fundamental condition: number of COLUMNS of A must equal number of ROWS of B. Cornerstone of linear algebra, basis for linear systems, geometric transformations, deep learning.

Numerical example

A = [[1, 2], [3, 4]] (2x2), B = [[5, 6], [7, 8]] (2x2):

• C[1][1] = 1*5 + 2*7 = 19.
• C[1][2] = 1*6 + 2*8 = 22.
• C[2][1] = 3*5 + 4*7 = 43.
• C[2][2] = 3*6 + 4*8 = 50.

C = [[19, 22], [43, 50]].

Properties

• Associative: (A B) C = A (B C).
• Left distributive: A (B + C) = A B + A C.
• Right distributive: (A + B) C = A C + B C.
• NOT commutative: A B != B A in general.
• Identity: A I = I A = A.
• Transpose: (A B)^T = B^T A^T (reversed order).

Computational complexity

Naive algorithm: O(n^3) for n x n matrices. Faster algorithms:

• Strassen (1969): O(n^2.807) - recursive, divide and conquer.
• Coppersmith-Winograd (1990): O(n^2.376) - theoretical.
• Le Gall (2014): O(n^2.3729).
• Williams (2024): O(n^2.371552).

Sub-cubic algorithms rarely used in practice due to high constants. Naive with BLAS standard.

Matrix identity

Identity matrix I_n is square n x n with 1s on main diagonal and 0s elsewhere. Satisfies A I = I A = A. Generalization: diagonal matrix D = diag(d_1, ..., d_n).

Matrix inverse

For square A n x n, inverse A^(-1) (if exists) satisfies A A^(-1) = A^(-1) A = I_n. Exists iff det(A) != 0 (non-singular). Computation:

• 2x2 case: det = ad - bc, A^(-1) = (1/det) [[d,-b],[-c,a]].
• General: Gauss-Jordan elimination, O(n^3).
• LU decomposition: A = LU, then solve.

Matrix powers

A^n = A * A * ... * A (n times). A^0 = I, A^1 = A. Fast computation: square-and-multiply, O(log n) matrix multiplications. For diagonalizable A = P D P^(-1): A^n = P D^n P^(-1).

Markov chains

Markov chain has transition matrix P (n x n) where P[i][j] = probability from state i to j. Distribution after n steps: pi_n = pi_0 P^n. Steady state: pi P = pi.

Geometric transformations

2x2 and 3x3 matrices represent linear transformations. Examples:

• Rotation theta: R = [[cos t, -sin t],[sin t, cos t]].
• Reflection x-axis: [[1, 0], [0, -1]].
• Scale (sx, sy): [[sx, 0], [0, sy]].
• Composition: T_1 T_2.

Deep learning

Neural networks essentially chains of matrix multiplications with non-linearities. Fully connected: y = sigma(W x + b). Forward pass = matrix-vector products. Backprop = transposes (chain rule). GPU/TPU specialized for matrix multiply (cuBLAS, MKL, TensorRT).

Gram matrix

A * A^T (m x m, always symmetric) is positive semi-definite. Diagonal: row norm squares. Off-diagonal: dot products. Used in: least squares (X^T X), kernel methods, PCA covariance, GANs.

Applications

• Linear systems: A x = b via x = A^(-1) b or Gauss.
• 3D graphics: 4x4 homogeneous matrices.
• Neural networks: forward pass.
• Linear filters: convolutions as products.
• Markov chains: P^n distribution.
• Eigenvalue problems: A v = lambda v.
• SVD: A = U Sigma V^T compression.
• Quantum computing: gates as unitary matrices.

History

Cayley (1858): introduces matrix algebra. Sylvester (1850): coins "matrix". Frobenius (1878): systematic study. Strassen (1969): first sub-cubic algorithm. von Neumann, Wilkinson (1940-50): numerical analysis. BLAS (1979): library standardization. Modern: GPU optimization (cuBLAS), deep learning frameworks.

Matrices as transformations: why order matters

The key to understanding matrix multiplication is to see matrices not as tables of numbers, but as transformations of space. Each matrix represents a linear transformation: a rotation, a dilation, a reflection or a combination of these. Multiplying two matrices means applying the two corresponding transformations in succession, which is why the product of matrices is the composition of their geometric operations.

From this interpretation immediately follows the reason multiplication is not commutative, that is, AB differs from BA in general. Rotating an object and then enlarging it produces a different result from enlarging it and then rotating it, when the two operations are not along the same axes. The order of the transformations matters, and this is reflected in the arithmetic of matrices. Understanding this geometry turns multiplication from a mechanical rows-times-columns rule into an intuitive idea: composing movements of space, the heart of computer graphics, robotics and deep learning.

The hunt for the omega exponent: from Strassen to today

Multiplying two n by n matrices with the elementary method requires about n cubed operations, summing the row-by-column products. For decades this was believed to be the optimal complexity, until in 1969 Volker Strassen discovered an algorithm that reorganizes the computations, reducing the exponent to about 2.807, a revolutionary result that showed one could do better than the obvious.

Since then a real mathematical hunt for the optimal exponent, called omega, has been underway. The Coppersmith-Winograd algorithm of the 1980s and subsequent refinements have lowered the record to about 2.37 with the most recent techniques. Many mathematicians conjecture that the true exponent is exactly 2, the theoretical minimum, but no one has yet proved it or reached it with a practical algorithm. The question is of enormous importance: since matrix multiplication underlies the training of neural networks and countless scientific computations, every reduction of the exponent has repercussions across all of computational science.

Updated July 2026