# Intuition on matrix multiplication and algorithms

Yesterday, I was watching Strang's lectures on Matrix multiplication. He mentioned five different ways of looking at the multiplication $\mathbf{AB} = \mathbf{C}.$

1. Classic way (Row of $\mathbf{A} \cdot$ Column of $\mathbf{B}$).

2. Column of $\mathbf{B}$ at a time.

Column of $\mathbf{C}$ are combinations of Column of $\mathbf{A}$.

3. Row of $\mathbf{A}$ at a time.

Rows of $\mathbf{C}$ are combinations of rows of $\mathbf{}$.

4. Column of $\mathbf{A} \cdot$ Row of $\mathbf{B}$

$\mathbf{AB}$ = $\sum$ Column of $\mathbf{A} \cdot$ Row of $\mathbf{B}$

5. By blocks

The column at a time way reminded me of the the Johnson–Lindenstrauss lemma and the improvement by Achlioptas. One key insight of the idea of the embedding is that each column of B in the multiplication $\mathbf{AB}$ gives a testimony (linear combination) of the elements in a row of A. The theorems in these seminal works examine the conditions that should apply to B in order to minimize the distortion of A’s projection to a lower dimensional space. The forth way made me think of low rank approximations.

Can you think of other algorithms that use one of the intuitions above in matrix multiplication?

-