Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.