Circulant Kronecker Product

The Circulant Kronecker Product is a generalized operation that extends the standard Kronecker product by summing over all cyclic permutations of the given vectors or matrices. This operation can be applied to any number of vectors or matrices.

Mathematical Definition

Given a sequence of vectors or matrices $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n$, the circulant Kronecker product is defined as:

\[\mathbf{x}_1 \circledast \mathbf{x}_2 \circledast \dots \circledast \mathbf{x}_n = \sum_{k=0}^{n-1} \mathbf{x}_{1+k} \otimes \mathbf{x}_{2+k} \otimes \dots \otimes \mathbf{x}_{n+k}\]

where the indices are taken modulo $n$, i.e., $\mathbf{x}_{i+n} = \mathbf{x}_i$.

Implementation

Function circulant_kronecker

julia> using UniqueKronecker
julia> x = [1, 2];
julia> y = [3, 4];
julia> z = [5, 6];
julia> circulant_kronecker(x, y, z)8×1 Matrix{Int64}:
  45
  68
  68
 100
  68
 100
 100
 144

circulant_kronecker(args::AbstractArray...)

Operator ⊛

Example 1: Two Vectors

julia> using UniqueKronecker
julia> x = [1, 2]2-element Vector{Int64}:
 1
 2
julia> y = [3, 4]2-element Vector{Int64}:
 3
 4
julia> x ⊛ y4×1 Matrix{Int64}:
  6
 10
 10
 16

Explanation:

• The circulant Kronecker product for two vectors is:

  \[\mathbf{x} \circledast \mathbf{y} = \mathbf{x} \otimes \mathbf{y} + \mathbf{y} \otimes \mathbf{x}\]

• Computation:

  x ⊗ y = [1*3, 1*4, 2*3, 2*4] = [3, 4, 6, 8]
  y ⊗ x = [3*1, 3*2, 4*1, 4*2] = [3, 6, 4, 8]
  Sum: [3+3, 4+6, 6+4, 8+8] = [6, 10, 10, 16]

Note: The output [6, 10, 10, 16] is the sum of the Kronecker products in this case.

Example 2: Three Vectors

julia> using UniqueKronecker
julia> x = [1, 2]2-element Vector{Int64}:
 1
 2
julia> y = [3, 4]2-element Vector{Int64}:
 3
 4
julia> z = [5, 6]2-element Vector{Int64}:
 5
 6
julia> ⊛(x, y, z)8×1 Matrix{Int64}:
  45
  68
  68
 100
  68
 100
 100
 144

Explanation:

• The circulant Kronecker product for three vectors is:

  \[\mathbf{x} \circledast \mathbf{y} \circledast \mathbf{z} = \mathbf{x} \otimes \mathbf{y} \otimes \mathbf{z} + \mathbf{y} \otimes \mathbf{z} \otimes \mathbf{x} + \mathbf{z} \otimes \mathbf{x} \otimes \mathbf{y}\]

• Computation involves computing each Kronecker product and summing the results.

Example 3: Matrices

julia> using UniqueKronecker
julia> A = [1 2; 3 4];
julia> B = [5 6; 7 8];
julia> C = [9 10; 11 12];
julia> result = ⊛(A, B, C)8×8 Matrix{Int64}:
 135  194  194  268  194  268  268   360
 253  312  342  416  342  416  452   544
 253  342  312  416  342  452  416   544
 431  520  520  624  562  672  672   800
 253  342  342  452  312  416  416   544
 431  520  562  672  520  624  672   800
 431  562  520  672  520  672  624   800
 693  824  824  976  824  976  976  1152

Generalization

With this implementation, you can now use the ⊛ operator or circulant_kronecker function with any number of vectors or matrices. The operation will automatically handle the necessary cyclic permutations and compute the sum of their Kronecker products.

Columnwise Operation on Snapshot Matrices

Using the function circulant_kron_snapshot_matrix, the circulant Kronecker product operation can be applied to construct a snapshot matrix with each column containing the circulant Kronecker product result computed from each column of the input matrices.

Example

julia> using UniqueKronecker
julia> X1 = [1 2; 3 4]2×2 Matrix{Int64}:
 1  2
 3  4
julia> X2 = [5 6; 7 8]2×2 Matrix{Int64}:
 5  6
 7  8
julia> X3 = [9 10; 11 12]2×2 Matrix{Int64}:
  9  10
 11  12
julia> X = circulant_kron_snapshot_matrix(X1, X2, X3)8×2 Matrix{Int64}:
 135   360
 253   544
 253   544
 431   800
 253   544
 431   800
 431   800
 693  1152

circulant_kron_snapshot_matrix(Xmat::AbstractArray{T}...) where {T<:Number}

Derivative of Kronecker products

This circulant Kronecker product is useful because it is a well-known result that the derivative of Kronecker products hold the circulant Kronecker structure. For example, if $\mathbf{x}\in\mathbb{R}^2$ then

\[\frac{\partial}{\partial \mathbf{x}}(\mathbf{x} \otimes \mathbf{x}) = \mathbf{I}_2 \otimes \mathbf{x} + \mathbf{x} \otimes \mathbf{I}_2\]

and

\[\frac{\partial}{\partial \mathbf{x}}(\mathbf{x} \otimes \mathbf{x} \otimes \mathbf{x}) = \mathbf{I}_2 \otimes \mathbf{x} \otimes \mathbf{x} + \mathbf{x} \otimes \mathbf{I}_2 \otimes \mathbf{x} + \mathbf{x} \otimes \mathbf{x} \otimes \mathbf{I}_2\]

which can be reformulated using the circulant Kronecker product as, e.g.,

\[\frac{\partial}{\partial \mathbf{x}}(\mathbf{x} \otimes \mathbf{x}) = \mathbf{I}_2 \circledast \mathbf{x}\]

Symmetry and Conversion using Elimination and Duplication Matrices

The circulant Kronecker product inherently captures the symmetric structure present in Kronecker products involving permutations of vectors or matrices. This symmetry can be leveraged to simplify computations, reduce redundancy, and improve efficiency in mathematical operations, particularly when dealing with higher-order tensors or polynomial systems.

Role of Elimination and Duplication Matrices

When working with circulant Kronecker products, especially in the context of symmetric tensors or polynomial dynamical systems, you may need to convert between the full Kronecker product and its unique representation.

From Full Kronecker Product to Unique Representation

1. Compute the Full Circulant Kronecker Product: Use the circulant_kronecker function to compute the sum over all cyclic permutations.

2. Apply the Symmetrizer Matrix: Multiply the result by the symmetrizer matrix $\mathbf{S}_{n,k}$ to make the redundant elements symmetric. Unlike the unique Kronecker product, this must be explicitly applied for circulant Kronecker products.

3. Apply the Elimination Matrix: Multiply the result by the elimination matrix $\mathbf{L}_{n,k}$ to extract the unique elements.

   \[\text{Unique Elements} = \mathbf{L}_{n,k} \times \mathbf{S}_{n,k} \times \left( \mathbf{x}_1 \circledast \mathbf{x}_2 \circledast \dots \circledast \mathbf{x}_n \right)\]

From Unique Representation to Full Kronecker Product

1. Start with Unique Elements: Obtain the vector containing the unique monomials.

2. Apply the Duplication Matrix: Multiply the unique elements by the duplication matrix $\mathbf{D}_{n,k}$ to reconstruct the full symmetric tensor.

   \[\text{Full Kronecker Product} = \mathbf{D}_{n,k} \times \text{Unique Elements}\]

Example

Consider vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^2$:

1. Compute the Circulant Kronecker Product:

   \[\mathbf{x} \circledast \mathbf{y} = \mathbf{x} \otimes \mathbf{y} + \mathbf{y} \otimes \mathbf{x}\]

2. Apply the Symmetrizer and Elimination Matrix:

   • Use $\mathbf{S}_{2,2}$ and $\mathbf{L}_{2,2}$ to extract unique terms:

     \[\text{Unique Elements} = \mathbf{L}_{2,2}~\mathbf{S}_{2,2} (\mathbf{x} \circledast \mathbf{y})\]

3. Result:

   • The unique elements correspond to the monomials $x_1 y_1$, $x_1 y_2 + x_2 y_1$, and $x_2 y_2$.