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.

  • $\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 '21 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 '21 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 '21 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 '21 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 '21 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.