Matrix multiplication using only addition
One thing I highly recommend is trying it for yourself, just with pen and paper.  Think of ten two-digit numbers under 40 for it to work nicely.  Just numbers under 40, 1-100 would require like 20 numbers for it to work as well as it does in realistic examples.  Write them in one line, then write them sorted on the next line, with lines connecting them to where they were before.  Then underneath each number write down the difference between that number n the one before it, this is called taking the first differences.  Repeat the sorting followed by taking first differences until you have only two numbers, two being an arbitrary limit.  You may then pretend the row and column are the same, so expand with the same vector using the lines drawn, and prefix sum where first difference was performed.<p>So:<p>11 39 23 28 31 19 32 05 01 09<p>sort<p>01 05 09 11 19 23 28 31 32 39<p>first differences<p>1  4  4  2  8  4  5  3  1  7<p>sort and remove duplicates<p>1 2 3 4 5 7 8<p>first differences<p>1 1 1 1 1 2 1<p>sort and remove duplicates<p>1 2<p>reduction complete