4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 29, 2021 at 8:28
  • 2
    $\begingroup$ 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 cstheory.stackexchange.com/q/32444/5038. I don't know whether that is helpful. $\endgroup$
    – D.W.
    Mar 29, 2021 at 8:40
  • $\begingroup$ 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$). $\endgroup$
    – Gamow
    Mar 29, 2021 at 9:20
  • $\begingroup$ 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} $\endgroup$
    – luciano
    Mar 29, 2021 at 10:28
  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Mar 31, 2021 at 1:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.