# Check if no linear combination is within a hypercube

Shapes

• Let $$C$$ be the unit hypercube in $$\mathbb{R}^{n}$$.

• Let $$\vec{o}$$ be a point in $$\mathbb{R}^{n}$$.

• Let $$B$$ be a $$n \times m$$ matrix. The columns of $$B$$ are a set of linearly independent vectors in $$\mathbb{R}^{n}$$.

• $$m \le n$$

• $$n$$ is about 15 to 20.

• Let $$O$$ be a $$m$$ dimensional coordinate with columns of $$B$$ as axes and $$o$$ as the origin.

Projection

• Given point $$\vec{x}$$ in $$\mathbb{R}^{n}$$.
• $$\textit{proj}_{O}(\vec{x}) = B\vec{y}$$ where vector $$\vec{y}$$ minimizes square norm of $$B\vec{y} - (\vec{x} - \vec{o})$$.
• That is solving a least square problem.
• $$B\vec{y} = QQ^{T}\vec{x}$$ where $$B = QR$$.
• QR factorization would need $$2n^3$$ flops. The two matrix-vector multiplications would each need $$2n^{2}$$ flops. (source).

Goal

I want to know if there exists any point ($$\vec{z}$$) within the hypercube such that $$\vec{z} = \textit{proj}_{O}(\vec{z})$$. That means $$\vec{z}$$ can be exactly represented by the coordinate system $$O$$.

Method

1. The center of the hypercube is $$\vec{c} = \frac{1}{2}\vec{1}$$.
2. Find $$\vec{u} = \textit{proj}_{O}(\vec{c})$$
3. If $$\vec{u}$$ is within the hypercube, return true.
4. Otherwise, find corner $$\vec{v}$$ of the hypercube that is closest to $$\vec{u}$$
5. Find $$\vec{w} = \textit{proj}_{O}(\vec{v})$$
6. If $$\vec{w}$$ is within the hypercube, return true.
7. Otherwise, return false.

Question

Is the method correct? Is there a faster way?