Do Matrix Multiplication!

Question

In mathematics, matrix multiplication or the matrix product is a binary operation that produces a matrix from two matrices. The definition is motivated by linear equations and linear transformations on vectors, which have numerous applications in applied mathematics, physics, and engineering. In more detail, if A is an n × m matrix and B is an m × p matrix, their matrix product AB is an n × p matrix, in which the m entries across a row of A are multiplied with the m entries down a columns of B and summed to produce an entry of AB. When two linear transformations are represented by matrices, then the matrix product represents the composition of the two transformations.

^{Source: Wikipedia}

In other words, to multiply two matrices, for example:

1 2 3   1 4
2 3 4 × 3 1 = 
3 4 5   4 6

First, take row number 1 in the first matrix, column number 1 in the second matrix, and multiply 1 by 1, 2 by 3, and 3 by 4.

1 × 1 = 1
2 × 3 = 6
3 × 4 = 12

Now add them together to get your first item:

1 2 3   1 4   19
2 3 4 × 3 1 = 
3 4 5   4 6

For the second number in the first column of the result, you will need to take row number 2 instead of row number 1 and do the same thing.

1 × 2 = 2
3 × 3 = 9
4 × 4 = 16
      = 27

After you do the entire first column, the result looks like this:

1 2 3   1 4   19
2 3 4 × 3 1 = 27
3 4 5   4 6   35

Now, do the same exact thing again, but take the second column instead of the first column, resulting in:

1 2 3   1 4   19 24
2 3 4 × 3 1 = 27 35
3 4 5   4 6   35 46

Your task

Given two matrices (max dimensions 200x200), containing numbers in the range -10000 to 10000, where the number of columns on the first one equals the number of rows on the second, multiply the first one by the second one. (Matrix multiplication is non-commutative.)

You may take input and give output as an array of arrays (or equivalent), a matrix (if your language has that format) or a multiline string.

You may not use any built-ins for matrix multiplication.

Test cases

1 2   1 2 3 4 5    13 16 19 22 25
3 4 × 6 7 8 9 10 = 27 34 41 48 55
5 6                41 52 63 74 85

2 3   3 5   15 13
3 4 × 3 1 = 21 19

5 3            11    27
1 3      1 3   7     15
9 3    × 2 4 = 15    39
1 -1000        -1999 -3997

Remember, this is code-golf, so the code with the fewest bytes wins.

Answer 1

Jelly, 7 5 bytes

Z×þḅ1

Takes B and A as arguments and returns A × B.

Try it online!

How it works

Z×þḅ1  Main link. Left argument: B. Right argument: A

Z      Zip; transpose B's rows and columns.
 ×þ    Table multiplication; multiply all columns of B (rows of B's transpose) by
       all rows of A, element by element. Results are grouped by the rows of A.
   ḅ1  Unbase 1; compute the sum of all flat arrays in the result.

Answer 2

05AB1E, 13 bytes

vyU²øvyX*O})ˆ

Try it online!

Explanation

v               # for each row in the first matrix
 yU             # save the row in X
   ²øv          # for each row in the transposition of the second matrix
      yX*       # multiply the rows
         O      # sum the elements of the resulting row
          }     # end inner loop
           )    # wrap elements of the new row in a list
            ˆ   # push to global list
                # implicitly output global list

Answer 3

Python 2, 69 66 Bytes

This just follows the standard formula, but lambda-d for conciseness :) The ungolfed code is extremely straightforward!

lambda x,y:[[sum(map(int.__mul__,r,c))for c in zip(*y)]for r in x]

^{Thanks to Alexi Torhamo for saving 3 bytes! :)}

Ungolfed code:

x = [[1,2],[3,4],[5,6]]
y = [[1,2,3,4,5],[6,7,8,9,10]]

output = []
for row in x:
    nrow = []
    for col in zip(*y):                             # zip(*[]) transposes a matrix
        nrow += [sum(a*b for a,b in zip(row,col))]  # multiplication for each pair summed
    output += [nrow]

print output

Answer 4

J, 13 9 bytes

Saved 4 bytes thanks to miles!

[:+/*"#:~

This is a capped fork:

[: +/ *"#:~

Which is equivalent to:

[: +/ (*"#:)~
[: +/ (*"_ 1 0)~

Which performs the desired multiplication; these are then summed.

With a dot product built in, 5 bytes: +/ .*

Test cases

   f =: [: +/ *"#:~
   (3 3$1 2 3 2 3 4 3 4 5)f(3 2$1 4 3 1 4 6)
19 24
27 35
35 46
   (3 3$1 2 3 2 3 4 3 4 5);(3 2$1 4 3 1 4 6)
+-----+---+
|1 2 3|1 4|
|2 3 4|3 1|
|3 4 5|4 6|
+-----+---+
   (2 2$2 3 3 4)f(2 2$3 5 3 1)
15 13
21 19
   (2 2$2 3 3 4);(2 2$3 5 3 1)
+---+---+
|2 3|3 5|
|3 4|3 1|
+---+---+

Answer 5

Haskell, 57 56 54 bytes

e=[]:e
z=zipWith
a!b=[sum.z(*)r<$>foldr(z(:))e b|r<-a]

Try it online!

Usage:

Prelude> [[1,2],[3,4],[5,6]] ! [[1,2,3,4,5],[6,7,8,9,10]]
[[13,16,19,22,25],[27,34,41,48,55],[41,52,63,74,85]]

foldr(zipWith(:))e with e=[]:e is a shorter form of transpose.

Answer 6

Haskell, 45 bytes

map.(foldr1(z(+)).).flip(z$map.(*))
z=zipWith

Try it online!

Takes arguments in reversed order.

Answer 7

MATL, 12 11 bytes

7L&!*Xs6Be!

Matrices are input using ; as row separator.

Try it online!

Matrix multiplication without the builtin was part of my answer to Showcase of languages. However, when trying to reuse the original code for this answer I realized it had a bug (row vector output was incorrectly converted to a column vector). This is now corrected, both here and there. For an explanation of how the code works, see the referred post (length-11 snippet).

Answer 8

C#, 168 167 bytes

(A,B)=>{int n=A.Length,p=B[0].Length,i=0,j=0,k=0,s;var R=new int[n,p];while(i++<n)for(j=0;j<p;){s=0;for(k=0;k<A[0].Length;)s+=A[i][k]*B[k++][j];R[i,j++]=s;}return R;};

Thank you @Mukul Kumar for saving 1 byte, the while loop was actually shorter this time :P

Full program with test cases:

using System;
class Matrix
{
    static void Main()
    {
        Func<int[][], int[][], int[,]> a = null;

        a = (A,B)=>
        {
            int n=A.Length,p=B[0].Length,i=0,j=0,k=0,s;
            var R=new int[n,p];
            while(i++<n)
                for(j=0;j<p;)
                {
                    s=0;
                    for(k=0;k<A[0].Length;)
                        s+=A[i][k]*B[k++][j];
                    R[i,j++]=s;
                }
            return R;
        };

        int[,] t1 = a(new int[][] { new int[] { 1, 2 }, new int[] { 3, 4 }, new int[] { 5, 6 } },
            new int[][] { new int[] { 1, 2, 3, 4, 5 }, new int[] { 6, 7, 8, 9, 10 } } );
        int[,] t2 = a(new int[][] { new int[] { 2, 3 }, new int[] { 3, 4 } },
            new int[][] { new int[] { 3, 5 }, new int[] { 3, 1 } });
        int[,] t3 = a(new int[][] { new int[] { 5, 3 }, new int[] { 1, 3 }, new int[] { 9, 3 }, new int[] { 1, -1000 } },
            new int[][] { new int[] { 1, 3 }, new int[] { 2, 4 } });

        Console.WriteLine(IsCorrect(t1, new int[,] { { 13, 16, 19, 22, 25 }, { 27, 34, 41, 48, 55 }, { 41, 52, 63, 74, 85 } } ));
        Console.WriteLine(IsCorrect(t2, new int[,] { { 15, 13 }, { 21, 19 } } ));
        Console.WriteLine(IsCorrect(t3, new int[,] { { 11, 27 }, { 7, 15 }, { 15, 39 }, { -1999, -3997 } } ));

        Console.Read();
    }

    static bool IsCorrect(int[,] answer, int[,] valid)
    {
        if (answer.Length != valid.Length)
            return false;
        for (int i = 0; i < answer.GetLength(0); i++)
            for (int j = 0; j < answer.GetLength(1); j++)
                if (answer[i, j] != valid[i, j])
                    return false;
        return true;
    }
}

Answer 9

R, 66 bytes

function(A,B)apply(B,2,function(i)apply(A,1,function(j)sum(j*i)))

Unnamed function taking two R-matrices as input and returns the product. It makes use of apply which is used to apply functions across margins of arrays. It works just as a double for loop in this case: for each column of B and for each row of A, return the sum of the (vectorized) products.

Compare to the pure for loop approach (101 bytes):

function(A,B){M=matrix(NA,m<-nrow(A),n<-ncol(B));for(i in 1:n)for(j in 1:m)M[j,i]=sum(A[j,]*B[,i]);M}

Answer 10

C++14, 173 168 156 146 bytes

• -5 bytes for returning via reference parameter
• -12 bytes for using foreach and C.back() instead counting on i
• -10 bytes for dropping C.clear() and requiring C to be empty at start

As unnamed lambda:

[](auto A,auto B,auto&C){int j,k,s=B[0].size();for(auto a:A){C.emplace_back(s);for(j=-1;++j<s;)for(k=-1;++k<B.size();C.back()[j]+=a[k]*B[k][j]);}}

Requires input and output as vector<vector<int>> and output must be empty beforehand.

Ungolfed:

auto f=
[](auto A, auto B, auto&C){
 int j,k,s=B[0].size();
 for (auto a:A){
  C.emplace_back(s);
  for (j=-1;++j<s;)
   for (k=-1;++k<B.size();
    C.back()[j]+=a[k]*B[k][j]
   );
 }
}
;

Sample:

int main() {
 using M=std::vector<std::vector<int>>;
 M a = {
  {1,2,3},
  {2,3,4},
  {3,4,5},
 };
 M b = {
  {1,4},
  {3,1},
  {4,6},
 };
 M c;
 f(a,b,c);
 for (auto&r:c){
  for (auto&i:r) std::cout << i << ", ";
  std::cout << "\n";
 }
}

Answer 11

Mathematica, 20 bytes

Inner[1##&,##,Plus]&

Anonymous function. Takes two rank-2 lists of numbers as input, and returns a rank-2 list of numbers as output. For those curious, Inner is a function that does a matrix-multiplication-like application of two functions to two tensors.

Answer 12

Husk, 7 6 bytes

mMδṁ*T

Please note the argument order, try it online!

-1 byte thanks to @Zgarb!

Explanation

Basically just doing what the definition of matrix-multiplication sais:

mMδṁ*T  -- takes arguments in reverse order, eg: [[1],[0],[-1]] [[1,2,3],[4,5,6]]
     T  -- transpose the first argument: [[1,0,-1]] [[1,2,3],[4,5,6]]
m       -- map the following function (example element [1,0,-1])
 M      --   map the following function applied to [1,0,-1] (example element [1,2,3])
  δṁ    --     accumulate a sum of element-wise..
    *    --    ..multiplication: -2
          -- [[-2],[-2]]

Answer 13

JavaScript (ES6), 66 bytes

(a,b)=>a.map(c=>b[0].map((_,i)=>b.reduce((s,d,j)=>s+d[i]*c[j],0)))

Answer 14

C#, 131 bytes

(A,B)=>new List<List<int>>(A.Select(x=>new List<int>
    (B[0].Select((f,i)=>B.Select(r=>r[i])).Select(y=>x.Zip(y,(p,q)=>p*q).Sum()))));

I stole Yodle's solution with the assumption that I could write this more efficiently using LINQ (as opposed to for loops). Took a few attempts but crunched it down somewhat.

Here it is broken down somewhat:

a = (A, B) => new List<List<int>>(
            from x in A
            select new List<int>(
                from y in B.First().Select((f, i) => B.Select(r => r.ElementAt(i)))
                select x.Zip(y, (p, q) => p * q).Sum()));

The only real 'trick' here is the matrix transpose, B.First().Select((f, i) => B.Select(r => r.ElementAt(i))). Once we transpose the second matrix, we have two arrays A[i,x] and B[j,x]. Take the cartesian product (i*j) and Zip each of those x length arrays together.

Test code:

using System;
class Matrix
{
    static void Main()
    {
        Func<int[][], int[][], List<List<int>>> a = null;
        a = (A, B) => new List<List<int>>(A.Select(x => new List<int>(B[0].Select((f, i) => B.Select(r => r[i])).Select(y => x.Zip(y, (p, q) => p * q).Sum()))));

        List<List<int>> t1 = a(new int[][] { new int[] { 1, 2 }, new int[] { 3, 4 }, new int[] { 5, 6 } },
            new int[][] { new int[] { 1, 2, 3, 4, 5 }, new int[] { 6, 7, 8, 9, 10 } });
        List<List<int>> t2 = a(new int[][] { new int[] { 2, 3 }, new int[] { 3, 4 } },
            new int[][] { new int[] { 3, 5 }, new int[] { 3, 1 } });
        List<List<int>> t3 = a(new int[][] { new int[] { 5, 3 }, new int[] { 1, 3 }, new int[] { 9, 3 }, new int[] { 1, -1000 } },
            new int[][] { new int[] { 1, 3 }, new int[] { 2, 4 } });

        Console.WriteLine(IsCorrect(t1, new int[,] { { 13, 16, 19, 22, 25 }, { 27, 34, 41, 48, 55 }, { 41, 52, 63, 74, 85 } }));
        Console.WriteLine(IsCorrect(t2, new int[,] { { 15, 13 }, { 21, 19 } }));
        Console.WriteLine(IsCorrect(t3, new int[,] { { 11, 27 }, { 7, 15 }, { 15, 39 }, { -1999, -3997 } }));

        Console.Read();
    }

    static bool IsCorrect(List<List<int>> answer, int[,] valid)
    {
        if (answer.Count*answer[0].Count != valid.Length)
            return false;
        for (int i = 0; i < answer.Count; i++)
            for (int j = 0; j < answer[0].Count; j++)
                if (answer[i][j] != valid[i, j])
                    return false;
        return true;
    }

}

Answer 15

Haskell, 49 bytes

z=zipWith
m a=map(\x->foldr1(z(+))$z(map.(*))x a)

Try it online!

Input and output are lists of columns. Maps each column of the second matrix to that row, zipped with the columns of the first matrix and scaling each, summed as a vector.

I feel that there's gotta be a nice way to make this pointfree and save a handful of bytes, but I'm not seeing it yet.

Answer 16

Javascript, 128 bytes

m=(a,b)=>{$=[];q=0;for(x in b){c=[];j=0;for(y in a[0]){_=i=0;for(z in b[0]){_+=a[i][j]*b[q][i];i++}c.push(_);j++}$.push(c);q++}}

You get the result by just checking $ - it's kinda cheating, but hey, it saved a few bytes.

Answer 17

PHP, 110 bytes

function f($a,$b){foreach($a as$n=>$x)foreach($b as$m=>$y)foreach($y as$p=>$v)$z[$n][$p]+=$v*$x[$m];return$z;}

Three loops for the elven arrays. This is so straight forward ... but there´s not much to golf.

Answer 18

Actually, 14 bytes

Golfing suggestions welcome! Try it online!

┬@;l)∙`i♀*Σ`M╡

Ungolfing

         Implicit input A, then B.
┬        Transpose B's rows and columns. Call it B_T.
@        Swap A to TOS.
;l)      Get len(A) and move to BOS for later.
∙        Push the Cartesian product of A and B_T. Call it cart_prod.
`...`M   Map the following function over cart_prod. Variable xs.
  i        Flatten xs onto the stack, getting a row of A and column of B.
  ♀*       Multiply each element of A_row by each element of B_column.
  Σ        Sum the resulting list to get an element of A*B.
         The result of the map returns every element of A*B, but in one flat list.
╡        Push a list containing len(A) non-overlapping sublists of A*B.
         This separates A*B into rows.
         Implicit return.

Answer 19

C, 618 bytes

M(char*a,char*b){char*P[2];P[0]=malloc(strlen(a));P[1]=malloc(strlen(b));for(int A=0;A<strlen(a);A++){P[0][A]=a[A];};for(int B=0;B<strlen(b);B++){P[1][B]=b[B];};int H[200][200],B[200][200];int O,N,m,J;for(int Y=0;Y<2;Y++){int y=0,z=0,r=0;char j[7];int p=strlen(P[Y]);for(int i=0;i<=p;i++){if(P[Y][i]==' '||P[Y][i]==','||i==p){(Y<1)?H[y][z]=atoi(j):(B[y][z]=atoi(j));memset(j,'\0',4);(P[Y][i]==' ')?z++:y++;z=(P[Y][i]==',')?0:z;r=0;}else{j[r]=P[Y][i];r++;};};(Y<1)?O=z+1,N=y:(m=y,J=z+1);};for(int U=0;U<N;U++){for(int F=0;F<J;F++){int T=0;for(int d=0;d<O;d++){T+=H[U][d]*B[d][F];};printf("%d ",T);T=0;};printf("\n");};}

A named function and by far the longest submission here, partly due to the fact that converting the character array inputs into C 2-dimensional integer arrays is taking up the most bytes, and also because I have not golfed in C in the longest time. I am still working on shortening this as much as I can, and any tips in doing so are much appreciated.

Now, with that out of the way, this takes input through the command line with the two matrices represented by two strings, with each one containing the rows separated by commas and each row represented by space separated integers. For example, the matrices:

   1 2 3     44 52
A= 4 5 6  B= 67 -79
   7 8 9     83 90

would be input as:

./a.out "1 2 3,4 5 6,7 8 9" "44 52,67 -79,83 90"

The resulting matrix is output to STDOUT as a multiline string. For example, the output for the above input would be:

 427 164 
1009 353 
1591 542 

Answer 20

Clojure, 60 bytes

#(for[a %](for[b(apply map vector %2)](apply +(map * a b))))

Many bytes spent on transposing the 2nd argument.

Answer 21

Ruby, 59 bytes

->m,n{m.map{|r|n.transpose.map{|c|r.zip(c).sum{|i,j|i*j}}}}

Try it online!