Unique Kronecker Powers
One unique feature of this package is the generalization of the unique Kronecker product for any n-dimensional vector with any Kronecker product of order k. This allows significant computational efficiency in higher-order polynomial systems.
Definition
The unique Kronecker power of order $k$ of a vector $\mathbf{x} \in \mathbb{R}^n$, denoted by $\mathbf{x}^{\langle k \rangle}$, is a vector containing all the unique monomials of degree $k$ formed by the elements of $\mathbf{x}$. Unlike the standard Kronecker power $\mathbf{x}^{[k]}$, which includes all possible combinations (including duplicates due to commutativity), the unique Kronecker power includes each distinct monomial only once.
Formally, the unique Kronecker power is defined as:
\[\mathbf{x}^{\langle k \rangle} = \mathrm{vec}_{\text{unique}} \left( \mathbf{x}^{[k]} \right) \in \mathbb{R}^{\tbinom{n + k - 1}{k}}\]
where:
- the term $\mathbf{x}^{[k]} = \underbrace{\mathbf{x} \otimes \mathbf{x} \otimes \cdots \otimes \mathbf{x}}_{k \text{ times}}$ is the $k$-th Kronecker power of $\mathbf{x}$.
- and $\mathrm{vec}_{\text{unique}}$ extracts only the unique monomials, considering that the variables commute (e.g., $x_i x_j = x_j x_i$).
The length of $\mathbf{x}^{\langle k \rangle}$ is given by the multiset coefficient (number of combinations with repetition):
\[\mathrm{length}(\mathbf{x}^{\langle k \rangle}) = \tbinom{n + k - 1}{k}\]
Properties
- Efficiency: By considering only unique monomials, the unique Kronecker power significantly reduces the dimensionality compared to the standard Kronecker power, which has length $n^k$.
- Symmetry: The unique Kronecker power leverages the commutative property of multiplication, avoiding redundant terms.
- Polynomial Representation: Each element corresponds to a unique monomial of degree $k$ in the variables $x_1, x_2, \dots, x_n$.
Computation
To compute the unique Kronecker power of a vector $\mathbf{x}$, generate all combinations of indices with replacement and compute the products corresponding to those combinations.
Example for $n = 2$ and $k = 2$:
Let $\mathbf{x} = [x_1, x_2]^\top$. The unique Kronecker power is:
\[\mathbf{x}^{\langle 2 \rangle} = \begin{bmatrix} x_1^2 \\ x_1 x_2 \\ x_2^2 \end{bmatrix}\]
Example for $n = 3$ and $k = 2$:
\[\mathbf{x}^{\langle 2 \rangle} = \begin{bmatrix} x_1^2 \\ x_1 x_2 \\ x_1 x_3 \\ x_2^2 \\ x_2 x_3 \\ x_3^2 \end{bmatrix}\]
Conversion Between Standard and Unique Kronecker Powers
The package provides tools to convert between the standard Kronecker power $\mathbf{x}^{[k]}$ and the unique Kronecker power $\mathbf{x}^{\langle k \rangle}$ using the elimination matrix $\mathbf{L}_{n,k}$ and the duplication matrix $\mathbf{D}_{n,k}$.
From Standard to Unique:
\[\mathbf{x}^{\langle k \rangle} = \mathbf{L}_{n,k} \mathbf{x}^{[k]}\]
From Unique to Standard:
\[\mathbf{x}^{[k]} = \mathbf{D}_{n,k} \mathbf{x}^{\langle k \rangle}\]
UniqueKronecker.UniqueCombinationIterator
— TypeCombinationIterator(n::Int, p::Int)
Iterator for generating all combinations with repetition of n
elements from {1, 2, ..., n}.
Fields
n::Int
: number of elementsp::Int
: number of elements in each combination