Let $m, n \in \mathbb{N}^+$ such that $$1 \leq m \leq \frac12 n < n \leq 100$$ denote the known numbers of rows and columns of an unknown matrix $A \in \Bbb R^{m \times n}$. Though one does not have access to the matrix $A$, for any given vector $x \in \mathbb{R}^n$ one can get $\| Ax \|_2$ by sending $x$ to a server that knows $A$. Given two vectors $x, y \in \mathbb{R}^n$, find a unit vector $x' = ax + by$ for any $a, b \in \mathbb{R}$ such that $Ax' \perp Ay$. One guarantee we have is that $\|A \|_2 \leq \frac32$.
I am working on this problem and struggling to find a way to deduce a formula for $a, b$ such that $x'$ satisfies the constraints.
Since for every $x \in \mathbb{R}^n$, you have an the knowledge of $\| Ax \|$, you also have the knowledge of $\langle Ax, Ay \rangle$ for every $x, y \in \mathbb{R}^n$ (due to the polarization identity).
With this, the problem is to find $a, b \in \mathbb{R}$ such that the following equations hold:
$$a^2 \| x \|^2 + 2ab \langle x, y \rangle + b^2 \| y \|^2 = 1.$$
$$a \langle Ax, Ay \rangle + b \| Ay \|^2 = 0.$$
Considering that the only unknowns in these equations are $a, b$, this could be solvable. The simplest case is when $y \in \ker A$, for which the problem is under-determined, and particularly, any unit vector (any values of $a, b$ that make $x'$ into a unit vector) works!
For the non-trivial case of $y \notin \ker A$, we have from the second equation $b = - a \frac{\langle Ax, Ay \rangle}{\| Ay \|^2}$, and hence
$$a^2 \| x \|^2 - 2a^2 \frac{\langle Ax, Ay \rangle \langle x, y \rangle}{\| Ay \|^2} + a^2 \frac{\langle Ax, Ay \rangle^2}{\| Ay \|^4} = 1.$$
This gives you your solution!
Polarization Identity: Let $V$ be a real vector space with inner product $\langle \cdot, \cdot \rangle$. Then, for every $x \in V$, we have
$$\langle x, y \rangle = \frac{1}{4} \left( \| x + y \|^2 - \| x - y \|^2 \right),$$
where $\| \cdot \|$ is the norm on $V$ induced by the inner product.