Tensor Product/Kronecker product

Tensor Product / Kronecker product is a way of creating a vector space from other vectors (like dot produt, cross product). The operation is defined as follows. It is hard for me to explain on mathematical meaning of Tensor product and I would focus more on the application of Tensor product. For the detailed explanation with mathematical point of view, refer to Ref [1].

Kronecker product of a 2 x 1 vector and a 1 x 1 vector

Kronecker product of a 1 x 1 vector and a 2 x 1 vector

Kronecker product of two 2 x 1 vectors giving a 4 x 1 vector

Kronecker product of three 2 x 1 vectors giving an 8 x 1 vector

Kronecker product of two 2 x 2 matrices giving a 4 x 4 matrix

The pattern in all six cases is the same. Every element of the left operand multiplies the whole right operand, and the resulting blocks are placed where that element sat. I'll first write that pattern as a set of rules, then look at the intuition behind it, and then work through the examples.

What rules does the Kronecker product follow ?

The definition above is easy to apply by hand, but you need a few rules to use it inside a longer calculation. The most useful ones tell you the size of the result, whether the order matters, and how the product works together with ordinary matrix multiplication.

Let's start with the size. If A is m x n and B is p x q, then A ⊗ B is mp x nq. It is a block matrix of m x n blocks, and the block in row i and column j is a_ijB. So the 2 x 2 by 2 x 2 case above gives a 4 x 4 result, and three 2 x 1 vectors give an 8 x 1 result.

The order matters. For example, [1 2]^T ⊗ [3 4]^T = [3 4 6 8]^T, but [3 4]^T ⊗ [1 2]^T = [3 6 4 8]^T. Both results hold the same four products, only in a different order. The grouping, on the other hand, does not matter. (A ⊗ B) ⊗ C equals A ⊗ (B ⊗ C), which is why the three-vector case can be worked from either end.

The rule that makes the product useful is the mixed product rule. If the sizes allow the ordinary products AC and BD, then (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD). Several other rules follow from it. The transpose is (A ⊗ B)^T = A^T ⊗ B^T, in the same order, unlike (AB)^T. The inverse is (A ⊗ B)^-1 = A^-1 ⊗ B^-1. The eigenvalues of A ⊗ B are all the products λ_iμ_j of an eigenvalue of A and an eigenvalue of B.

In code you rarely build the blocks yourself. Matlab and Octave provide kron(A,B), and Python provides numpy.kron(A,B).

The size multiplies : An m x n matrix and a p x q matrix give an mp x nq matrix.
The order changes the result : A ⊗ B and B ⊗ A hold the same products in a different arrangement.
The mixed product rule carries the rest : (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD), and the transpose, inverse and eigenvalue rules follow from it.

Some Intuition

When I first saw this operation and being used very often in my field (wireless communication), I asked myself 'what would be the original motivation that triggered invention of this operator? what this operator really do ? what is the practical meaning of this operation ?'. I searched quite a lot on the web trying to find the answers to these questions but failed to find any clear answers. So even as of now, I don't the answer.

However, while I was writing the examples of this operator many times, an intuition struck myself. My intuition goes like this. If I express a vector or matrix in a set, this operator gives all the possible mapping between the elements of the sets, meaning giving all the possible combinations of the elements of the sets.

Let me illustrate some examples based on this intuition.

Let's suppose we have two vectors and represents the two vectors into sets as shown below.

Two 2 x 1 vectors drawn as two sets of elements

Then the kreonecker product of the two vectors can be represented as all the possible mapping between the two vectors as represented by arrows shown below.

Arrows from every element of the x set to every element of the y set

Each elements in the result of the kronector product corresponds to each cases of mapping as illstrated below.

The four mappings x0y0, x0y1, x1y0 and x1y1 drawn one by one

The order of the four mappings above is also the order of the elements in the result. The left element changes slowly and the right element changes fast, the same way the digits of a binary counter do.

Now let's consider the case where three vectors are involved. Consider a case where we have three vectors that is represented in sets as shown below.

Three 2 x 1 vectors drawn as three sets of elements

The kronecker product of these three vectors can be represented as a mapping among the three vectors as shown below.

Arrows through the x, y and z sets covering every path

Each elements in the resulting matrix of the kronecker product of the three vectors can be illustrated as each mapping among the three sets as shown below.

The four paths starting at x0, from x0y0z0 to x0y1z1

The four paths starting at x1, from x1y0z0 to x1y1z1

Now let's think of a cases where two matrices (not vector) are used. Consider we have two matrices that are represented as sets as shown below. Here, I just flatten out the matrix into a set. This mean that I lose the structural information of the matrix (i.e, lose the information of colums, rows). This would imply that my intuition is not correct in terms of strict mathematical definition, but I think it still be useful to understand the basic nature of the operation.

Two 2 x 2 matrices flattened into sets a to d and e to h

Still by the same logic as above, the kronecker product of the two matrix can be represented as all the possible mapping between the elements of each matrices as shown below. Again, this mapping would not show the structural information (i.e, column and row position) of the operation, but it still gives you all the elements in the resulting matrix of the operation.

Sixteen arrows from every element of the first matrix to every element of the second

The count of arrows is a quick check on the intuition. Two sets of 2 give 4 mappings, three sets of 2 give 8, and two sets of 4 give 16. Those are exactly the numbers of elements in the 4 x 1, 8 x 1 and 4 x 4 results of the definition. The positions that the sets lose come back from the block rule of the previous section. The element a_ijb_kl sits in row (i-1)p + k and column (j-1)q + l, when B is p x q.

Every combination appears exactly once : The result holds one product for each way of picking one element from each operand.
The order is that of a counter : The index of the left operand changes slowest and the index of the right operand changes fastest.
The block rule restores the positions : The set picture gives the elements, and the block rule tells where each element goes.

Examples

The five examples go from plain numbers to three applications. Examples 1 and 2 check the definition with numbers. Example 3 builds a quantum state, Example 4 builds a Hadamard matrix, and Example 5 builds a MIMO channel correlation matrix.

Example 1

Example 1 puts numbers into the case of two 2 x 1 vectors. The second line uses unit vectors, and its result has a single 1, at the position that the pair of 1s picks.

Kronecker product of [1 2] and [3 4] giving [3 4 6 8]

Kronecker product of [1 0] and [0 1] giving [0 1 0 0]

Example 2

Example 2 chains three vectors with numbers. The product is associative, so you can work from the right as the calculation below does, or from the left, and you get the same 8 x 1 vector.

Kronecker product of three 2 x 1 vectors giving the 8 x 1 vector 15 to 48

Example 3

This is the way by which we can represent multiple quantum bits into a vector. (See this page for the details of Quantum bit(Q bit) representation).

The qubit state |0> is [1 0]^T and |1> is [0 1]^T. So the product below is the three-qubit state |100>. Its single 1 sits at position 4, counting from 0, because the binary number 100 is 4.

Kronecker product of [0 1], [1 0] and [1 0] giving a unit vector with 1 in position 4 counting from 0

Example 4

Derivation of Hamadard Matrix. This is a method that are commonly used to generate othogonal code sequence in communication system. Walsh Code is an example of this.

See Hamadard Matrix page

The idea fits in one step. Start from H₂ = [1 1; 1 -1], whose two rows are orthogonal. Then H₄ = H₂ ⊗ H₂ is the 4 x 4 matrix below.

H4 = [ 1   1   1   1 ]
     [ 1  -1   1  -1 ]
     [ 1   1  -1  -1 ]
     [ 1  -1  -1   1 ]

Its rows are orthogonal too, because the mixed product rule gives H₄H₄^T = (H₂H₂^T) ⊗ (H₂H₂^T) = 2I ⊗ 2I = 4I. Repeating the step gives H₈, H₁₆ and so on, and each row is one orthogonal code.

Example 5

Antenna Correlation Matrix in MIMO Fading. Following is an exmple of applying Tensor Product Operation. This shows how MIMO correlation matrix between UE and eNB can be derived from UE and eNB antenna correlation coefficient.

36.101 table of Rspat correlation matrices for the 1x2 and 2x2 cases

Kronecker product of the eNB and UE correlation matrices giving the 4 x 4 Rspat

The table above is a screenshot from 36.101 Annex B. In 36.101 v20.0.0 it is numbered Table B.2.3.1-3, and the screenshot carries an older number. α is the correlation between the two eNB antennas, and β is the correlation between the two UE antennas. The Kronecker product assumes that the two ends are independent. So every entry of R_spat is one eNB correlation times one UE correlation.

36.101 Table B.2.3.2-1 gives the values. Low correlation is α = 0 and β = 0. Medium Correlation is α = 0.3 and β = 0.9, and High Correlation is α = 0.9 and β = 0.9. With the Medium values, the eigenvalues of the two 2 x 2 matrices are 0.7 and 1.3 for the eNB and 0.1 and 1.9 for the UE. By the eigenvalue rule, R_spat has the four products 0.07, 0.13, 1.33 and 2.47. The small ones show how weak two of the four spatial eigenmodes become when the UE antennas are strongly correlated.

A product of unit vectors is a unit vector : This is how a register of qubits becomes one long state vector.
The Kronecker product preserves orthogonality : H₂ ⊗ H₂ gives the orthogonal rows used as Walsh codes.
R_spat = R_eNB ⊗ R_UE separates the two ends : The eNB and UE correlations are set independently, and their eigenvalues multiply.

Reference

[1] The Tensor Product, Demystified

3GPP TS 36.101 v20.0.0 : Annex B.2.3, Definition of MIMO Correlation Matrices