# Calculate the Kronecker sum of two matrices

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)


A Kronecker sum has the following properties:

A⊕B = A⊗Ib + Ia⊗B


Ia and Ib are the identity matrices with the dimensions of A and B respectively. A and B are square matrices. Note that A and B can be of different sizes.

A⊕B =  A(1,1)+B(1,1)  B(1,2)         A(1,2)         0
B(2,1)         A(1,1)+B(2,2)  0              A(1,2)
A(2,1)         0              A(2,2)+B(1,1)  B(1,2)
0              A(2,1)         B(2,1)         A(2,2)+B(2,2)


Given two square matrices, A and B, calculate the Kronecker sum of the two matrices.

• The size of the matrices will be at least 2-by-2. The maximum size will be whatever your computer / language can handle by default, but minimum 5-by-5 input (5 MB output).
• All input values will be non-negative integers
• Builtin functions that calculate the Kronecker sum or Kronecker 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    10
7     9

A⊕B =
6    10     2     0
7    10     0     2
3     0     9    10
0     3     7    13

----

A =
28    83    96
5    70     4
10    32    44
B =
39    19    65
77    49    71
80    45    76

A⊕B =
67    19    65    83     0     0    96     0     0
77    77    71     0    83     0     0    96     0
80    45   104     0     0    83     0     0    96
5     0     0   109    19    65     4     0     0
0     5     0    77   119    71     0     4     0
0     0     5    80    45   146     0     0     4
10     0     0    32     0     0    83    19    65
0    10     0     0    32     0    77    93    71
0     0    10     0     0    32    80    45   120

----

A =
76    57    54
76     8    78
39     6    94
B =
59    92
55    29

A⊕B =
135    92    57     0    54     0
55   105     0    57     0    54
76     0    67    92    78     0
0    76    55    37     0    78
39     0     6     0   153    92
0    39     0     6    55   123


# Jelly, 262120 19 bytes

æ*9Bs2¤×€€/€S;"/€;/


Input is a list of two 2D lists, output is a single 2D list. Try it online! or verify all test cases.

### How it works

æ*9Bs2¤×€€/€S;"/€;/  Main link.
Argument: [A, B] (matrices of dimensions n×n and m×m)

¤              Evaluate the four links to the left as a niladic chain.
9B                 Convert 9 to base 2, yielding [1, 0, 0, 1].
s2               Split into sublists of length 2, yielding [[1, 0], [0, 1]].
æ*                   Vectorized matrix power.
This yields [[A¹, B⁰], [A⁰, B¹]], where B⁰ and A⁰ are the
identity matrices of dimensions m×m and n×n.
/€         Reduce each pair by the following:
€€             For each entry of the first matrix:
×                 Multiply the second matrix by that entry.
S        Sum the two results, element by element.
This yields the Kronecker sum, in form of a n×n matrix of
m×m matrices.
/€    Reduce each row of the outer matrix...
;"        by zipwith-concatenation.
This concatenates the columns of the matrices in each row,
yielding a list of length n of n×nm matrices.
;/  Concatenate the lists, yielding a single nm×nm matrix.

• So many euros... your program is rich! – Luis Mendo Apr 27 '16 at 12:11

## CJam, 4039 38 bytes

9Yb2/q~f{.{_,,_ff=?}:ffff*::.+:~}:..+p


Input format is a list containing A and B as 2D lists, e.g.

[[[1 2] [3 4]] [[5 10] [7 9]]]


Output format is a single CJam-style 2D list.

Test suite. (With more readable output format.)

### Explanation

This code is an exercise in compound (or infix) operators. These are generally useful for array manipulation, but this challenge exacerbated the need for them. Here is a quick overview:

• 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].

Note that : itself is always a unary operator, whereas f and . themselves are always binary operators. These can be arbitrarily nested (provided they have the right arities). And that's what we'll do...

9Yb      e# Push the binary representation of 9, i.e. [1 0 0 1].
2/       e# Split into pairs, i.e. [[1 0] [0 1]]. We'll use these to indicate
e# which of the two inputs we turn into an identity matrix.
q~       e# Read and evaluate input, [A B].
f{       e# This block is mapped over the [[1 0] [0 1]] list, also pushing
e# [A B] onto the stack for each iteration.
.{     e#   The stack has either [1 0] [A B] or [0 1] [A B]. We apply this
e#   block to corresponding pairs, e.g. 1 A and 0 B.
_,   e#     Duplicate the matrix and get its length/height N.
,_   e#     Turn into a range [0 1 ... N-1] and duplicate it.
ff=  e#     Double f on two lists is an interesting idiom to compute an
e#     outer product: the first f means that we map over the first list
e#     with the second list as an additional parameter. That means for
e#     the remaining operator the two arguments are a single integer
e#     and a list. The second f then maps over the second list, passing
e#     in the the number from the outer map as the first parameter.
e#     That means the operator following ff is applied to every possible
e#     pair of values in the two lists, neatly laid out in a 2D list.
e#     The operator we're applying is an equality check, which is 1
e#     only along the diagonal and 0 everywhere else. That is, we've
e#     created an NxN identity matrix.
?    e#     Depending on whether the integer we've got along with the matrix
e#     is 0 or 1, either pick the original matrix or the identity.
}
e#   At this point, the stack contains either [A Ib] or [Ia B].
e#   Note that A, B, Ia and Ib are all 2D matrices.
e#   We now want to compute the Kronecker product of this pair.
:ffff* e#   The ffff* 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#   The leading : is a fold operation, but it's a bit of a degenerate
e#   fold operation that is only used to apply the following binary operator
e#   to the two elements of a list.
e#   Now the ffff* works essentially the same as the ff= above, but
e#   we have to deal with two more dimensions now. The first ff maps
e#   over the cells of the first matrix, passing in the second matrix
e#   as an additional argument. The second ff then maps over the second
e#   matrix, passing in the cell from the outer map. We multiply them
e#   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.
}
e# Phew: we've now got a list containing the two Kronecker products
e# on the stack. The rest is easy, just perform pairwise addition.
:..+     e# Again, the : is a degenerate fold which is used to apply a binary
e# operation to the two list elements. The ..+ then simply vectorises
e# addition twice, such that we add corresponding cells of the 2D matrices.
p        e# All done, just pretty-print the matrix.

• fffffffffff what on earth... I hope that survives golfing so that you explain it eventually :P – FryAmTheEggman Apr 26 '16 at 14:25
• @FryAmTheEggman :ffff* might be the longest (compound) operator I've ever used in CJam... For one more byte one could go even crazier though: 9Yb2/Q~f.{\{,,_ff=}&}::ffff*:::.+::~:..+p (and yeah, will add an explanation when I'm done golfing). – Martin Ender Apr 26 '16 at 14:27

# J - 3833 31 bytes

i=:=@i.@#
[:,./^:2(*/i)+(*/~i)~


## Usage

   f =: [:,./^:2(*/i)+(*/~i)~
(2 2 $1 2 3 4) f (2 2$ 5 10 7 9)
6 10 2  0
7 10 0  2
3  0 9 10
0  3 7 13
(3 3 $28 83 96 5 70 4 10 32 44) f (3 3$ 39 19 65 77 49 71 80 45 76)
67 19  65  83   0   0 96  0   0
77 77  71   0  83   0  0 96   0
80 45 104   0   0  83  0  0  96
5  0   0 109  19  65  4  0   0
0  5   0  77 119  71  0  4   0
0  0   5  80  45 146  0  0   4
10  0   0  32   0   0 83 19  65
0 10   0   0  32   0 77 93  71
0  0  10   0   0  32 80 45 120
(3 3 $76 57 54 76 8 78 39 6 94) f (2 2$ 59 92 55 29)
135  92 57  0  54   0
55 105  0 57   0  54
76   0 67 92  78   0
0  76 55 37   0  78
39   0  6  0 153  92
0  39  0  6  55 123

• Using matrix division will fail if one of the matrices is singular. For example, (2 2 $1 2 3 4) f (2 2$ 1 1 1 1) will raise a domain error. – Dennis Apr 27 '16 at 0:20
• @Dennis good catch, I was only testing against random values ? 4 4 \$ 100 . I'm not sure if there's a way to make use of dyad compose x f&g y = (g x) f (g y) or something else here. – miles Apr 27 '16 at 1:18

# Julia, 605958 56 bytes

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


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.

• Since bitwise NOT with two's complement satisfies the identity ~n = -(n + 1) for all integers n, we have that -~-n = -(~(-n)) = --((-n) + 1) = 1 - n, so -~-0 = 1 and -~-1 = 0.

This way the anonymous function i->map(a->a*B^i,A'^-~-i) applies the above map to B⁰ (the identity matrix with B's dimensions) and A¹ = A when i = 0, and to and A⁰ when i = 1.

• sum(i->map(a->a*B^i,A'^-~-i),0:1) sums over {0,1} with the above anonymous function, computing the Kronecker sum A⊕B as A¹⊗B⁰ + A⁰⊗B¹.

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

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

• Finally, hvcat(sum(A^0),sum(i->map(a->a*B^i,A'^-~-i),0:1)...) concatenates the matrix blocks that form A⊕B.

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

# Ruby, 102

->a,b{r=0..-1+a.size*q=b.size
r.map{|i|r.map{|j|(i/q==j/q ?b[i%q][j%q]:0)+(i%q==j%q ?a[i/q][j/q]:0)}}}


In test program

f=->a,b{r=0..-1+a.size*q=b.size
r.map{|i|r.map{|j|(i/q==j/q ?b[i%q][j%q]:0)+(i%q==j%q ?a[i/q][j/q]:0)}}}

aa =[[1,2],[3,4]]
bb =[[5,10],[7,9]]
f[aa,bb].each{|e|p e}
puts

aa =[[28,83,96],[5,70,4],[10,32,44]]
bb =[[39,19,65],[77,49,71],[80,45,76]]
f[aa,bb].each{|e|p e}
puts

aa =[[76,57,54],[76,8,78],[39,6,94]]
bb =[[59,92],[55,29]]
f[aa,bb].each{|e|p e}
puts


Requires two 2D arrays as input and returns a 2D array.

There are probably better ways of doing this: using a function to avoid repetition; using a single loop and printing the output. Will look into them later.

# JavaScript (ES6), 109

Built upon the answer to the other challenge

(a,b)=>a.map((a,k)=>b.map((b,i)=>a.map((y,l)=>b.map((x,j)=>r.push(y*(i==j)+x*(k==l))),t.push(r=[]))),t=[])&&t


Test

f=(a,b)=>a.map((a,k)=>b.map((b,i)=>a.map((y,l)=>b.map((x,j)=>r.push(y*(i==j)+x*(k==l))),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,10],[7,9]]},
{a:[[28,83,96],[5,70,4],[10,32,44]], b:[[39,19,65],[77,49,71],[80,45,76]]},
{a:[[76,57,54],[76,8,78],[39,6,94]], b:[[59,92],[55,29]]}
].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>