Symbolic matrix multiplication

Question

There are lots of different ways to explain matrix multiplication. I'll stick with a single figure since I believe most people here are familiar with it (and the figure is very descriptive). If you want more detailed information, I suggest you visit the Wikipedia-article, or the explanation on WolframMathWorld.

Simple explanation:

Suppose you have two matrices, A and B, where A is 3-by-2, and B is 2-by-3. If you perform matrix multiplication on these to matrices, either AB, or BA you'll get the results below:

Challenge:

Implement symbolic matrix multiplication in you language. You shall take two matrices as input, where each element in the matrices are represented by an non-whitespace ASCII-character (code points 33-126). You must output the product of these matrices.

Rules regarding output:

A product of two entries shall not have any symbols in between. It's ab, not a*b, a·b, times(a,b) or something similar. It's aa, not a^2.

The sum of terms should have a space (ASCII code point 32) in between. It's a b, not a+b, plus(a,b) or something similar.

The rationale for those two rules is: All non white space characters are allowed as symbols in the matrices, thus using them as mathematical symbols would be messy. So, what you could normally write as a*b+c*d will be ab cd.

You may choose the order of the terms. ab cd, dc ab and cd ba are mathematically speaking the same, so you can choose the order here too. The order need not be consistent as long as it's mathematically correct.

Rules regarding matrix formatting:

A matrix can be entered in whatever format you like, except a single string with no delimiters between rows (this is because the output would be completely messed up). Both matrices must be inputted on the same format. All the examples below are valid ways of entering and outputting a matrix.

"ab;cd"     <- This will look awful, but it's still accepted.

"a,b\nc,d"

[[a,b],[c,d]] 

[a, b]
[c, d]

_{I'm aware that this allows a lot of formats that will look messy, but the challenge is about multiplying matrices, not formatting the output.}

General rules:

• You may assume valid input. Matrix multiplication will always be possible with the given dimensions.
• There will only be two matrices.
• You may assume that the matrices are non-empty
• Built-in functions are accepted (but probably a bit cumbersome due to the formatting requirements).
• You may of course use escape characters in the input if necessary (\' instead of ').
• Any standard input and output method is OK.

Test cases:

The two input matrices are shown with an empty line in between. The output is shown after Output:. When there are two output matrices then it's just to show other outputs that would be accepted.

Test case #1

Inputs:
[a]

[b]

Output:
[ab]
[ba]      <- Also OK

Test case #2

Inputs:
[a, b]
[1, 4] 
[y, {]

[%, 4, 1] 
[a, b, c]

Output:    
[a% ba, a4 bb, a1 bc] 
[1% 4a, 14 4b, 11 4c] 
[y% {a, y4 {b, y1 {c]

Test case #3:

Inputs:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 1, 2, 3]
[4, 5, 6, 7]

[a]
[b]
[c]
[d]

Output:
[1a 2b 3c 4d]
[5a 6b 7c 8d]
[9a 1b 2c 3d]
[4a 5b 6c 7d]

[d4 c3 b2 a1]      <-- Also OK
[d8 c7 b6 a5]
[1b 9a c2 3d]
[a4 b5 d7 6c]

_{If your response to the rules about requiring ab cd instead of a*b+c*d is: you should avoid cumbersome input/output formats, then I'd like note that the input and output formats are very flexible. The fact that you can't use * and + for products and sums might make it harder to use a simple built-in, but I don't consider that negative thing.}

Answer 1

Haskell, 62 61 bytes

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

Try it online! Example usage:

Prelude> [["a","b"],["c","e"]] ! [["f","g"],["h","i"]]
[["af bh","ag bi"],["cf eh","cg ei"]]

I found a way to get a transpose function in one byte shorter than using the import:

import Data.List;transpose
e=[]:e;foldr(zipWith(:))e

---

Old version with import: (62 bytes)

import Data.List
a!b=[unwords.zipWith(++)r<$>transpose b|r<-a]

Try it online!

This is quite similar to my answer to non-symbolic matrix multiplication: a!b=[sum.zipWith(*)r<$>transpose b|r<-a], substituting the multiplication (*) with string concatenation (++) and sum with unwords which concatenates a list of strings with a space in between. The import is needed for the transpose function, so all in all the transposition of the second matrix uses up half of the bytes ...

---

Old version without import: (64 bytes)

a![]=[];a!b=(unwords.zipWith(++)[h|h:_<-b]<$>a):a![s:t|_:s:t<-b]

Try it online!

With the import and transpose function taking up so much bytes, I tried solving the task without import. So far this approach turned out being two bytes longer, but it might be more golfable. Edit: The other approach at the top now beats the import!

The list comprehension [s:t|_:s:t<-b] gets the non-empty tails of the lists in b, using just [t|_:t<-b] to get the tails would be 4 bytes shorter (even beating the import version) but append an empty row like ["","",""] to the matrix which I suppose is not allowed.

Answer 2

Ruby, 61 bytes

->a,b{a.map{|x|b.transpose.map{|y|x.zip(y).map(&:join)*' '}}}

Sample run:

main(0):007> ->a,b{a.map{|x|b.transpose.map{|y|x.zip(y).map(&:join)*' '}}}[[[?a, ?b], [?1, ?4], [?y, ?{]], [[?%, ?4, ?1], [?a, ?b, ?c]]]
=> [["a% ba", "a4 bb", "a1 bc"], ["1% 4a", "14 4b", "11 4c"], ["y% {a", "y4 {b", "y1 {c"]]

->a,b{
a.map{|x|            # for each row of a
b.transpose.map{|y|  # and for each column of b
x.zip(y)             # match up corresponding elements
.map(&:join)         # join each pair together
*' '                 # join the entire thing on space
}}}

Answer 3

Mathematica, 36 bytes

Inner[#<>#2&,##,StringRiffle@*List]&

Inner is a generalisation of Mathematica's Dot (i.e. the usual matrix/vector product). It generalises the dot product by letting you provide two function f and g, which will be used in place of the usual multiplication and addition, respectively. We're replacing the multiplication with #<>#2& (which joins the the two characters into a single string) and the addition with StringRiffle@*List, which first wraps all the summands in a list, and then StringRiffle joins them together with spaces.

One could potentially use the Dot operator . and then transform the result, but the trouble is that things like "a"*"a" would immediately get transformed into "a"^2 (same for sums), which would be annoying to pick apart again.

Answer 4

Clojure, 53 bytes

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

Running with arguments [["a" "b"]["c" "e"]] and [["f" "g"]["h" "i"]] returns ((("af" "bh") ("ag" "bi")) (("cf" "eh") ("cg" "ei"))). This is actually shorter than the numeric version.

Answer 5

Dyalog APL, 10 bytes

Takes matrices of characters as left and right arguments. Returns matrix of lists of characters. (APL represents strings as lists of characters.)

{∊⍺' '⍵}.,

TryAPL online!

Normal inner product is in APL +.×, but the addition and multiplication can be any functions, in particular:

Addition has been replaced by
{ an anonymous function:
 ∊ the flattened
 ⍺ ' ' ⍵ list consisting of the left argument, a space, and the right argument ⍵
}

Multiplication has been replaced by concatenation, ,

Answer 6

Jelly, 7 bytes

Z;"þK€€

This is a dyadic link that takes B and A as arguments (in that order) and returns AB. Input and output are in the form of 2D arrays of strings, which are actually 3D arrays of characters. A further byte could be saved by taking 2D arrays of characters as input. I'm not sure if that's allowed.

Try it online!

It's a bit hard to determine what Jelly does under the hood when strings are involved, since it does a lot of splattening before printing. This is how Jelly represents input and output internally.

How it works

Z;"þK€€  Dyadic link. Left argument: B. Right argument: A

Z        Zip/transpose B.
 ;"þ     Table vectorized concatenation; for each row in B' and each row in A,
         concatenate the corresponding strings.
    K€€  Join the arrays that correspond to the rows of A by spaces.

Answer 7

Prolog, >256 Bytes

I am using { _ | _ } which is a findall/3, _ [ _ , _ ] which is some arg/3, and sum(_) which is some aggregate. They can all be used inside is/2:

*(X, Y, Z) :- functor(Y, matrice, _), L is len(X[1]), L =:= len(Y), !,
   M is len(X), N is len(Y[1]),
   Z is { { sum({ X[J,K] * Y[K,I] | between(1,L,K) })
                                  | between(1,N,I) }
                                  | between(1,M,J) }.

Together with the extra definitions for the aforementioned predicates and the non-standard is/2 that can return more than numbers, its sure >256 bytes.

Answer 8

JavaScript (ES6), 65 bytes

(a,b)=>a.map(c=>b[0].map((_,j)=>c.map((e,i)=>e+b[i][j]).join` `))

Takes input as two 2D arrays of characters and returns a 2D array of strings. Add 10 bytes to support input as two 1D arrays of strings.

Answer 9

Pyth, 14 bytes

clQmj;sMCd*QCE

A program that takes input of two newline-separated two-dimensional lists of characters and prints a two dimensional list of strings.

Test suite

How it works

[Explanation coming later]

Answer 10

Pip, 17 bytes

{Y Zb{a._JsMy}Ma}

This is a function that takes two nested lists of (single-character) strings and returns a nested list of strings. Try it online! (with two test cases).

Explanation

Arguments to a {}-delimited function are assigned to the local variables a to e. The first argument of a lambda function is represented by _.

{               }  Define a function:
   Zb              Zip rows of b, transposing it
 Y                 Yank into global variable y for access in nested function
     {       }Ma   To the rows of a, map this function:
           My       To the rows of y (i.e. columns of b), map this function:
      a._           Concatenate, itemwise, the current row of a and row of y
         Js         Join the resulting list on space
                   The result of the outer map operation is returned