11
\$\begingroup\$

Related, but very different.


In the examples below, A and B will be 2-by-2 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⊗B.

  • The size of the matrices will be at least 1-by-1. The maximum size will be whatever your computer / language can handle by default, but minimum 5-by-5 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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Or, in IPA, /y/ \$\endgroup\$ – Luis Mendo Apr 28 '16 at 13:42
  • \$\begingroup\$ Not every person knows IPA. \$\endgroup\$ – Leaky Nun Apr 28 '16 at 13:42
  • 4
    \$\begingroup\$ Thanks for the explanation of how to pronounce Martin's last name. It's super relevant. :P \$\endgroup\$ – Alex A. Apr 28 '16 at 15:08
  • \$\begingroup\$ Well it's how I show respect... \$\endgroup\$ – Leaky Nun Apr 28 '16 at 15:09
  • \$\begingroup\$ ;/ can be now. (feature postdates challenge?) \$\endgroup\$ – user202729 Mar 25 '18 at 2:27
6
\$\begingroup\$

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.
\$\endgroup\$
  • 3
    \$\begingroup\$ Your code almost looks like an IPv6 address \$\endgroup\$ – Digital Trauma Apr 28 '16 at 15:28
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Luis Mendo Apr 28 '16 at 16:58
1
\$\begingroup\$

Pyth, 14 12 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)!

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

Julia, 40 39 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.

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

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

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>

\$\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.