# Calculate the Kronecker Product

Related, but very different.

In the examples below, $$\A\$$ and $$\B\$$ will be $$\2\times2\$$ matrices, and the matrices are one-indexed.

A Kronecker product has the following properties:

A⊗B =  A(1,1)*B   A(1,2)*B
A(2,1)*B   A(2,2)*B

=  A(1,1)*B(1,1)   A(1,1)*B(1,2)   A(1,2)*B(1,1)   A(1,2)*B(1,2)
A(1,1)*B(2,1)   A(1,1)*B(2,2)   A(1,2)*B(2,1)   A(1,2)*B(2,2)
A(2,1)*B(1,1)   A(2,1)*B(1,2)   A(2,2)*B(1,1)   A(2,2)*B(1,2)
A(2,2)*B(2,1)   A(2,2)*B(1,2)   A(2,2)*B(2,1)   A(2,2)*B(2,2)


Challenge: Given two matrices, $$\A\$$ and $$\B\$$, return $$\A\otimes B\$$.

• The size of the matrices will be at least $$\1\times1\$$. The maximum size will be whatever your computer / language can handle by default, but minimum $$\5\times5\$$ input.
• All input values will be non-negative integers
• Builtin functions that calculate Kronecker products or Tensor/Outer products are not allowed
• In general: Standard rules regarding I/O format, program & functions, loopholes etc.

Test cases:

A =
1     2
3     4
B =
5     6
7     8
A⊗B =
5     6    10    12
7     8    14    16
15    18    20    24
21    24    28    32

B⊗A =
5    10     6    12
15    20    18    24
7    14     8    16
21    28    24    32
------------------------
A =
1
2
B =
1     2

A⊗B =
1     2
2     4
------------------------
A =
16     2     3    13
5    11    10     8
9     7     6    12
4    14    15     1

B =
1     1
0     1

A⊗B  =
16    16     2     2     3     3    13    13
0    16     0     2     0     3     0    13
5     5    11    11    10    10     8     8
0     5     0    11     0    10     0     8
9     9     7     7     6     6    12    12
0     9     0     7     0     6     0    12
4     4    14    14    15    15     1     1
0     4     0    14     0    15     0     1

B⊗A =
16     2     3    13    16     2     3    13
5    11    10     8     5    11    10     8
9     7     6    12     9     7     6    12
4    14    15     1     4    14    15     1
0     0     0     0    16     2     3    13
0     0     0     0     5    11    10     8
0     0     0     0     9     7     6    12
0     0     0     0     4    14    15     1
------------------------

A = 2
B = 5
A⊗B = 10


## CJam, 13 bytes

{ffff*::.+:~}


This is an unnamed block that expects two matrices on top of the stack and leaves their Kronecker product in their place.

Test suite.

### Explanation

This is just the Kronecker product part from the previous answer, therefore I'm here just reproducing the relevant parts of the previous explanation:

Here is a quick overview of CJam's infix operators for list manipulation:

• f expects a list and something else on the stack and maps the following binary operator over the list, passing in the other element as the second argument. E.g. [1 2 3] 2 f* and 2 [1 2 3] f* both give [2 4 6]. If both elements are lists, the first one is mapped over and the second one is used to curry the binary operator.
• : has two uses: if the operator following it is unary, this is a simple map. E.g. [1 0 -1 4 -3] :z is [1 0 1 4 3], where z gets the modulus of a number. If the operator following it is binary, this will fold the operator instead. E.g. [1 2 3 4] :+ is 10.
• . vectorises a binary operator. It expects two lists as arguments and applies the operator to corresponding pairs. E.g. [1 2 3] [5 7 11] .* gives [5 14 33].
ffff*  e# This is the important step for the Kronecker product (but
e# not the whole story). It's an operator which takes two matrices
e# and replaces each cell of the first matrix with the second matrix
e# multiplied by that cell (so yeah, we'll end up with a 4D list of
e# matrices nested inside a matrix).
e# Now the ffff* is essentially a 4D version of the standard ff* idiom
e# for outer products. For an explanation of ff*, see the answer to
e# to the Kronecker sum challenge.
e# The first ff maps over the cells of the first matrix, passing in the
e# second matrix as an additional argument. The second ff then maps over
e# the second matrix, passing in the cell from the outer map. We
e# multiply them with *.
e# Just to recap, we've essentially got the Kronecker product on the
e# stack now, but it's still a 4D list not a 2D list.
e# The four dimensions are:
e#   1. Columns of the outer matrix.
e#   2. Rows of the outer matrix.
e#   3. Columns of the submatrices.
e#   4. Rows of the submatrices.
e# We need to unravel that into a plain 2D matrix.
::.+   e# This joins the rows of submatrices across columns of the outer matrix.
e# It might be easiest to read this from the right:
e#   +    Takes two rows and concatenates them.
e#   .+   Takes two matrices and concatenates corresponding rows.
e#   :.+  Takes a list of matrices and folds .+ over them, thereby
e#        concatenating the corresponding rows of all matrices.
e#   ::.+ Maps this fold operation over the rows of the outer matrix.
e# We're almost done now, we just need to flatten the outer-most level
e# in order to get rid of the distinction of rows of the outer matrix.
:~     e# We do this by mapping ~ over those rows, which simply unwraps them.

• Your code almost looks like an IPv6 address Commented Apr 28, 2016 at 15:28

# MATLAB / Octave, 83 42 Bytes

Saved 41 bytes, thanks to FryAmTheEggman!

@(A,B)cell2mat(arrayfun(@(n)n*B,A,'un',0))


Test it here!

Breakdown

arrayfun is a disguised for-loop that multiplies n*B, for a variable n defined by the second argument. This works because looping through a 2D matrix is the same as looping through a vector. I.e. for x = A is the same as for x = A(:).

'un',0 is equivalent to the more verbose 'UniformOutput', False, and specifies that the output contains cells instead of scalars.

cell2mat is used to convert the cells back to a numeric matrix, which is then outputted.

• You should clarify that arrayfun loops linearly as you say, as if the matrix were a vector, but for does not (it loops over columns of the array) Commented Apr 28, 2016 at 16:58

# Jelly, 10 9 bytes

×€€;"/€;/


Uses Büttner's Algorithm (ü pronounced when trying to make an ee sound [as in meet] in the mouth-shape of an oo sound [as in boot]).

The ;"/€;/ is inspired by Dennis Mitchell. It was originally Z€F€€;/ (which costs one more byte).

• Or, in IPA, /y/ Commented Apr 28, 2016 at 13:42
• Not every person knows IPA. Commented Apr 28, 2016 at 13:42
• Thanks for the explanation of how to pronounce Martin's last name. It's super relevant. :P Commented Apr 28, 2016 at 15:08
• Well it's how I show respect... Commented Apr 28, 2016 at 15:09
• ;/ can be Ẏ now. (feature postdates challenge?) Commented Mar 25, 2018 at 2:27

# Pyth, 1412 11 bytes

JEsMs*RRRRJ


Translation of Jelly answer, which is based on Büttner's Algorithm (ü pronounced when trying to make an ee sound [as in meet] in the mouth-shape of an oo sound [as in boot]).

Try it online (test case 1)!

### Bonus: calculate B⊗A in the same number of bytes

JEsMs*LRLRJ


Try it online (test case 1)!

# Julia, 4039 37 bytes

A%B=hvcat(sum(A^0),map(a->a*B,A')...)


Try it online!

### How it works

• For matrices A and B, map(a->a*B,A') computes the Kronecker product A⊗B.

The result is a vector of matrix blocks with the dimensions of B.

We have to transpose A (with ') since matrices are stored in column-major order.

• sum(A^0) computes the sum of all entries of the identity matrix of A's dimensions. For an n×n matrix A, this yields n.

• With first argument n, hvcat concatenates n matrix blocks horizontally, and the resulting (larger) blocks vertically.

# R, 98 86 bytes

function(x,y,+=array)aperm(apply(x,1:2,*,y)+c(w<-dim(y),v<-dim(x)),c(1,3,2,4))+v*w


Try it online!

Reimplementation of .kronecker and outer for matrices. I do think there's a golfier approach out there, maybe using apply? 6 bytes golfed using apply and array thanks to Dominic van Essen!

The builtins are %x% for kronecker(A,B,"*") and %o% for outer(A,B,"*").

# R, 120 bytes

function(A,B){l=list()
a=dim(A)
for(i in 1:a[2]-1)l[[i+1]]<-do.call(rbind,lapply(A,"*",B)[1:a+a[2]*i])
do.call(cbind,l)}


Try it online!

Naive approach: calculate the subarrays $$\a_{ij}B\$$ and bind them together in the appropriate order. There are probably golfs here too, but I don't think it'll be shorter than the one above.

• This is funny! I got almost exactly the same answer yesterday (when your edit put this post to the top), but it seemed so un-golfy I didn't even submit it...! My best attempt was 92 bytes... Commented Nov 20, 2020 at 15:46
• @DominicvanEssen there's the better version with apply. I knew it was out there, just couldn't wrap my head around it. Feel free to post it yourself. Commented Nov 20, 2020 at 15:49
• @DominicvanEssen PS 86 bytes Commented Nov 20, 2020 at 15:52
• Hmm... That's getting good, but... I think you should just incorporate these into your answer, instead of outgolfing yourself in your own comments...! Commented Nov 20, 2020 at 15:54
• @DominicvanEssen fair enough! But I do think it's a shame such a matrix-friendly language is longer than the JS answer... Commented Nov 20, 2020 at 16:10

# J, 10 bytes

This is one possible implementation.

[:,./^:2*/


# J, 13 bytes

This is a similar implementation, but instead uses J's ability to define ranks. It applies * between each element on the LHS with the entire RHS.

[:,./^:2*"0 _


## Usage

   f =: <either definition>
(2 2 $1 2 3 4) f (2 2$ 5 6 7 8)
5  6 10 12
7  8 14 16
15 18 20 24
21 24 28 32
(2 1 $1 2) f (1 2$ 1 2)
1 2
2 4
2 f 5
10


# JavaScript (ES6), 79

Straightforward implementation with nested looping

(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t


Test

f=(a,b)=>a.map(a=>b.map(b=>a.map(y=>b.map(x=>r.push(y*x)),t.push(r=[]))),t=[])&&t

console.log=x=>O.textContent+=x+'\n'

function show(label, mat)
{
console.log(label)
console.log(mat.join\n)
}

;[
{a:[[1,2],[3,4]],b:[[5,6],[7,8]] },
{a:[[1],[2]],b:[[1,2]]},
{a:[[16,2,3,13],[5,11,10,8],[9,7,6,12],[4,14,15,1]],b:[[1,1],[0,1]]},
{a:[[2]],b:[[5]]}
].forEach(t=>{
show('A',t.a)
show('B',t.b)
show('A⊗B',f(t.a,t.b))
show('B⊗A',f(t.b,t.a))
console.log('-----------------')
})
<pre id=O></pre>

# APL (Dyalog Unicode), 10 bytes

{⍪/,/⍺×⊂⍵}


Try it online!

### How it Works

{  ...   }  ⍝ dfn that takes ⍺=A and ⍵=B
⍺×⊂⍵   ⍝ Product of each element of A with all of matrix B
⍝ Gives a nested array: an matrix of matrices
./       ⍝ Join rows
⍪/         ⍝ Join columns