13
\$\begingroup\$

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 , so the code with the fewest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can we use built-in dot products? They operate on vectors, not matrices. \$\endgroup\$ – Dennis Nov 17 '16 at 18:06
  • 1
    \$\begingroup\$ Is the input order fixed or can we take a and b in that order and output b × a? \$\endgroup\$ – Dennis Nov 17 '16 at 18:15
  • \$\begingroup\$ @Dennis You can reverse the input, but no dot products \$\endgroup\$ – Oliver Ni Nov 17 '16 at 19:53
  • 4
    \$\begingroup\$ Challenges about doing X without Y are discouraged. \$\endgroup\$ – flawr Nov 18 '16 at 0:30
  • \$\begingroup\$ Can the input matrices contain floating point numbers? If so, I recommend adding a test case with some. \$\endgroup\$ – R. Kap Nov 21 '16 at 21:31

18 Answers 18

4
\$\begingroup\$

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.
\$\endgroup\$
  • 3
    \$\begingroup\$ So wait, the built-in and the manual way to multiply matrices end up being the same number of bytes in Jelly? That's confusing, but cool. \$\endgroup\$ – Yodle Nov 17 '16 at 20:37
  • \$\begingroup\$ @Yodle The built-in is æ×, which is 2 bytes. \$\endgroup\$ – Erik the Outgolfer Dec 23 '17 at 16:58
  • \$\begingroup\$ @EriktheOutgolfer That was in reference to revision 2, which used the æ. atom. \$\endgroup\$ – Dennis Dec 23 '17 at 17:39
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You could use sum(map(int.__mul__,r,c)) to save 3 bytes. (Won't work with floating point, but that wasn't required, either) \$\endgroup\$ – Aleksi Torhamo Nov 18 '16 at 3:29
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ Not at my desktop at the moment, but couldn't you do something like outer(A,B,`*`) rather than the embedded apply calls? \$\endgroup\$ – rturnbull Nov 18 '16 at 6:02
  • \$\begingroup\$ @rturnbull I'm not sure how outer works in conjunction with matrices but it would produce a 4-D array in a this case. \$\endgroup\$ – Billywob Nov 18 '16 at 6:37
  • \$\begingroup\$ Ah yes, that is a little problematic. Linearizing the matrices would likely take more bytes than your approach here \$\endgroup\$ – rturnbull Nov 18 '16 at 12:22
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I believe Inner[1##&,##]& is equivalent to Inner[1##&,##,Plus]&...? And so 1##&~Inner~##& would be even better. \$\endgroup\$ – Greg Martin Jan 12 '17 at 8:36
2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ You can trim a few bytes by using while loops.... \$\endgroup\$ – Mukul Kumar Nov 17 '16 at 22:07
  • \$\begingroup\$ @MukulKumar Wait, I don't think so. At most, they break even right? for(;i<n;) -> while(i<n) are both 10 bytes. \$\endgroup\$ – Yodle Nov 18 '16 at 15:16
  • 1
    \$\begingroup\$ for (;i <n;i++) -> while (i++<n) saves 1 byte \$\endgroup\$ – Mukul Kumar Nov 18 '16 at 16:15
  • \$\begingroup\$ Not sure of the etiquette when I have a fairly different answer, but my alternative was definitely inspired by this. \$\endgroup\$ – Kirk Broadhurst Nov 18 '16 at 16:18
2
\$\begingroup\$

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|
+---+---+
\$\endgroup\$
  • \$\begingroup\$ I just stumbled upon [:+/*"#:~ for 9 bytes \$\endgroup\$ – miles Jan 12 '17 at 1:33
  • \$\begingroup\$ @miles spectacular! \$\endgroup\$ – Conor O'Brien Jan 12 '17 at 2:49
2
\$\begingroup\$

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).

\$\endgroup\$
2
\$\begingroup\$

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";
 }
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 66 bytes

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

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;
    }

}
\$\endgroup\$
  • \$\begingroup\$ Nice :P I've never really used Linq all that much, so I'm not fully aware of all the capabilities of it so I tend to just use standard loops and stuff. However, I think you have to include the using System.Linq; line in your byte count, not sure how much that effects it. \$\endgroup\$ – Yodle Nov 18 '16 at 16:22
  • \$\begingroup\$ @Yodle yes I would have to include using System.Linq; I'm not sure if solutions here need to include boilerplate like using System and static void Main() \$\endgroup\$ – Kirk Broadhurst Nov 18 '16 at 16:28
  • \$\begingroup\$ I've been answering for a bit now, and from what I've seen, basically your answer (whatever you're including in your byte count) has to work if you just pasted it into a program. For C# specifically, if you're writing just a function then you don't need to include class definitions or the static void Main() stuff, but if your solution uses any library stuff like Console.WriteLine() then you have to do System.Console.WriteLine() or using System; since one may be shorter. \$\endgroup\$ – Yodle Nov 18 '16 at 17:38
1
\$\begingroup\$

Haskell, 57 56 bytes

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

Try it online! Usage:

Prelude Data.List> [[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.

\$\endgroup\$
1
\$\begingroup\$

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]]
\$\endgroup\$
  • 1
    \$\begingroup\$ oΣz can be δṁ \$\endgroup\$ – Zgarb Dec 23 '17 at 13:11
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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 
\$\endgroup\$
0
\$\begingroup\$

Clojure, 60 bytes

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

Many bytes spent on transposing the 2nd argument.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.