4.49 min read

The Entry Perspective: Dot Products

The computational formula for matrix multiplication: the $(i,j)$ entry of $C = AB$ is the dot product of row $i$ of $A$ with column $j$ of $B$ : $c_{ij} = \sum_k a_{ik} b_{kj}$ .

This is the "two-finger rule" — point one finger at row $i$ of $A$ and the other at column $j$ of $B$ , multiply corresponding entries, and sum. Slide fingers to compute each entry.

While this formula is less geometric than the column perspective, it is essential for computation and for understanding why the time complexity is $O(n^3)$ : there are $mp$ entries to compute, each requiring a dot product of length $n$ .

Formal View

Theorem 4.4 (Entry Form)

For

C = AB

with

A \in \mathbb{R}^{m \times n}

B \in \mathbb{R}^{n \times p}

c_{ij} = \sum_{k=1}^n a_{ik} b_{kj} = \mathbf{a}_{i \cdot} \cdot \mathbf{b}_{\cdot j}

where

\mathbf{a}_{i\cdot}

is row

i

A

and

\mathbf{b}_{\cdot j}

is column

j

B

Remark 4.4 — Complexity

Computing

C = AB

naively requires

O(mnp)

multiplications. For square

n \times n

matrices, this is

O(n^3)

. Strassen's algorithm achieves

O(n^{2.81})

; current theoretical best is

O(n^{2.37...})

Why This Matters

The entry formula is the basis for all numerical linear algebra implementations.

BLAS (Basic Linear Algebra Subprograms) implements this formula with SIMD optimizations
GPU matrix multiplication runs the entry formula in massively parallel fashion
Understanding $O(n^3)$ cost helps design algorithms that avoid recomputing products

Learning Resources

Matrix multiplication algorithm

Khan Academy

Step-by-step computation of matrix products.

13 min

Quiz

Question 1

For $C = AB$ with $A \in \mathbb{R}^{2 \times 3}$ and $B \in \mathbb{R}^{3 \times 2}$ , the entry $c_{21}$ is computed as:

Common Mistakes

Using the wrong row/column pairing — $c_{ij}$ is row $i$ of $A$ dotted with column $j$ of $B$ .
Forgetting to sum over the inner index $k$ from 1 to $n$ .