16 deleted 186 characters in body

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.

Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)

Let $\{Q_{i}\}_{i=1}^{n^{2}}$ and $\{P_{j}\}$$_{j=1}^{N} be points over F[4] and F[2] \otimes F[2] respectively. Let Q, P and \Lambda be matrices of size n^{2} \times n^{4}, N \times n^{4} and n^{2} \times N respectively with entries from F[0]. The rows of Q and P be the points \{Q_{i}\}_{i=1}^{n^{2}} and \{P_{j}\}$$_{j=1}^{N}$ respectively.

Let $Q$ be known ($P$ and $\Lambda$ are unknowns) in the following equation:

$\Lambda P = Q$

What is the minimal size of $N$ so that one can expect a compatible $\Lambda$ and $P$ for a generic $Q$? Are there good lower and upper bounds for $N$?

What tools could be useful to study this problem?

With respect to Yemon Choi's comment: Regarding algortihms, a naive algorithm would run in worst case $3^{2Nn^{2}}$ complexity since it has to iterate over all possible values of of $F[0]$ as candidate entries of $\Lambda$ and $P$ for each given $N$ to check if there is a compatible solution. Even for $n=3$, this is formidable. Is there a faster algorithm to decide existence of compatibility for a given $N$? The Could the cube to sphere relaxation may help reduce complexity . However relaxing this to sphere may not give anything while giving something satisfactorysince we have to constrain ourselves to solution space where $\Lambda P$ has entries from $\{-1,0,1\}$. So the complexity could still only be exponential.?

Are there any textbooks or papers that handle something similar to this?

15 Rollback to Revision 13

# LinearRepresentingverticesofacubeusinglinear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.

Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)

Let $\{Q_{i}\}_{i=1}^{n^{2}}$ and $\{P_{j}\}$$_{j=1}^{N} be points over F[4] and F[2] \otimes F[2] respectively. Let Q, P and \Lambda be matrices of size n^{2} \times n^{4}, N \times n^{4} and n^{2} \times N respectively with entries from F[0]. The rows of Q and P be the points \{Q_{i}\}_{i=1}^{n^{2}} and \{P_{j}\}$$_{j=1}^{N}$ respectively.

Let $Q$ be known ($P$ and $\Lambda$ are unknowns) in the following equation:

$\Lambda P = Q$

What is the minimal size of $N$ so that one can expect a compatible $\Lambda$ and $P$ for a generic $Q$? Are there good lower and upper bounds for $N$?

What tools could be useful to study this problem?

With respect to Yemon Choi's comment: Regarding algortihms, a naive algorithm would run in worst case $3^{2Nn^{2}}$ complexity since it has to iterate over all possible values of of $F[0]$ as candidate entries of $\Lambda$ and $P$ for each given $N$ to check if there is a compatible solution. Even for $n=3$, this is formidable. Is there a faster algorithm to decide existence of compatibility for a given $N$? The cube to sphere relaxation may help reduce complexity. However relaxing this to sphere may not give anything satisfactory since we have to constrain ourselves to solution space where $\Lambda P$ has entries from $\{-1,0,1\}$. So the complexity could still only be exponential.

Are there any textbooks or papers that handle something similar to this?

14 deleted 24 characters in body; edited title

# RepresentingverticesofacubeusinglinearLinear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.

Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)

Let $\{Q_{i}\}_{i=1}^{n^{2}}$ and $\{P_{j}\}$$_{j=1}^{N} be points over F[4] and F[2] \otimes F[2]respectively. Let Q, P and \Lambda be matrices of size n^{2} \times n^{4}, N \times n^{4} and n^{2} \times N respectively with entries from F[0]. The rows of Q and P be the points \{Q_{i}\}_{i=1}^{n^{2}} and \{P_{j}\}$$_{j=1}^{N}$ respectively.

Let $Q$ be known ($P$ and $\Lambda$ are unknowns) in the following equation:

$\Lambda P = Q$

What is the minimal size of $N$ so that one can expect a compatible $\Lambda$ and $P$ for a generic $Q$? Are there good lower and upper bounds for $N$?

What tools could be useful to study this problem?

With respect to Yemon Choi's comment: Regarding algortihms, a naive algorithm would run in worst case $3^{2Nn^{2}}$ complexity since it has to iterate over all possible values of of $F[0]$ as candidate entries of $\Lambda$ and $P$ for each given $N$ to check if there is a compatible solution. Even for $n=3$, this is formidable. Is there a faster algorithm to decide existence of compatibility for a given $N$? The cube to sphere relaxation may help reduce complexity. However relaxing this to sphere may not give anything satisfactory since we have to constrain ourselves to solution space where $\Lambda P$ has entries from $\{-1,0,1\}$. So the complexity could still only be exponential.

Are there any textbooks or papers that handle something similar to this?

13 deleted 1118 characters in body; edited title; edited tags; [made Community Wiki]
12 added 1 characters in body
11 edited tags
10 added 200 characters in body
9 added 51 characters in body
8 added 420 characters in body
7 added 1168 characters in body; deleted 1 characters in body
6 Rollback to Revision 3
5 Rollback to Revision 2
4 fixed LaTeX a little