<p>Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V).</p>
<p>Example:
Input: V={8,4,18,9,12,24,36,16,48}.
Output: v1={4,9,12}, v2={2,4,1}</p>
<p>Kronecker product of v1 and v2 is {8,16,4,18,36,9,24,48,12}
which is a permutation of V.</p>
<p>I do not know whether this problem is NP-hard or can be solved in polynomial time.</p>

CC BY-SA 4.0
2021-03-29T08:28:06.597Z
What's p?  Is p given as an input?  Do you mean to say "such that there exists p so that the Kronecker product..."?  Are all vectors required to be over the positive integers?  the rationals?  something else?
D.W.
CC BY-SA 4.0
2021-03-29T08:40:54.567Z
There is always a trivial solution where $v_1=(1)$ and $v_2=v$.  I suspect you mean to ask about non-trivial solutions.  If you factor each number $x$ as $x=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ where $p_1,\dots,p_k$ are the set of primes that divide at least one of the numbers of $v$, and then map the number $x$ to the vector $(e_1,\dots,e_k)$, then your problem reduces to a similar one about inverting Minkowski sums: see https://cstheory.stackexchange.com/q/32444/5038.  I don't know whether that is helpful.
D.W.
CC BY-SA 4.0
2021-03-29T09:20:26.823Z
Can you please state your definition of the Kronecker product of two vectors? The definition I know yields an $n\times m$ matrix (if one vector has length $n$ and the other one has length $m$).
Gamow
CC BY-SA 4.0
2021-03-29T10:28:12.543Z
reply to comments: 
- p is a permutation and is not given . the problem is indeed to find the right permutation such that the input vector can be written as the Kronecker product of two other smaller vectors
- vectors are of positive integers and solutions must be of positive integers
- trivial solution with v1={1} is not of interest
- Kronecker product: v1={a,b,c}, v2={d,e},  v1 x v2={ad,ae,bd,be,cd,ce}
luciano
CC BY-SA 4.0
2021-03-31T01:39:16.903Z
I assume v1 and v2 have to be integer vectors?  Now, what about the case where $|V|=1$?  So $V=\{q\}$ for some integer $q$.  Then it seems you are asking to find a non-trivial factor of $q$.  If this is your intended meaning in this case, then isn't your problem is at least as hard as factoring?
Neal Young
<np-hardness><permutations>
Inverting Kronecker product on vectors is in P?
luciano
# Inverting Kronecker product on vectors is in P?

(Asked by: username_0 on 2021-03-29)

Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V).

Example:
Input: V={8,4,18,9,12,24,36,16,48}.
Output: v1={4,9,12}, v2={2,4,1}

Kronecker product of v1 and v2 is {8,16,4,18,36,9,24,48,12}
which is a permutation of V.

I do not know whether this problem is NP-hard or can be solved in polynomial time.

**Tags:** np-hardness, permutations

> **Comments:**
> **username_1**: What's p?  Is p given as an input?  Do you mean to say "such that there exists p so that the Kronecker product..."?  Are all vectors required to be over the positive integers?  the rationals?  something else?  
> **username_1**: There is always a trivial solution where $v_1=(1)$ and $v_2=v$.  I suspect you mean to ask about non-trivial solutions.  If you factor each number $x$ as $x=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ where $p_1,\dots,p_k$ are the set of primes that divide at least one of the numbers of $v$, and then map the number $x$ to the vector $(e_1,\dots,e_k)$, then your problem reduces to a similar one about inverting Minkowski sums: see https://cstheory.stackexchange.com/q/32444/5038.  I don't know whether that is helpful.  
> **username_2**: Can you please state your definition of the Kronecker product of two vectors? The definition I know yields an $n\times m$ matrix (if one vector has length $n$ and the other one has length $m$).  
> **username_0**: reply to comments:  - p is a permutation and is not given . the problem is indeed to find the right permutation such that the input vector can be written as the Kronecker product of two other smaller vectors - vectors are of positive integers and solutions must be of positive integers - trivial solution with v1={1} is not of interest - Kronecker product: v1={a,b,c}, v2={d,e},  v1 x v2={ad,ae,bd,be,cd,ce}  
> **username_3**: I assume v1 and v2 have to be integer vectors?  Now, what about the case where $|V|=1$?  So $V=\{q\}$ for some integer $q$.  Then it seems you are asking to find a non-trivial factor of $q$.  If this is your intended meaning in this case, then isn't your problem is at least as hard as factoring?  

---

## 0 answers

