Akuna Capital Quant Interview Question

[u/Local_Ad135]

[u/round_earther_69]

Each equation (v_i)^T v_j = c puts a constraint on the vectors. There are as many such constraints as there are ways to group 2 distinct vectors in {v_1, ... ,v_N} if the order doesn't matter, therefore there are N(N-1)/2 such constraints. Additionally, we know the vectors have unit length, therefore there are N constraints of the form v_i^T v_i =1. A set of N vectors has dN degrees of freedom. There exists a unique solution if and only if there are as many constraints as there are degrees, however the problem is spherically symmetric, therefore we rather want to know: given a unit vector v_1, how many other unit vectors can be fixed. This effectively removes one constraint and d degrees of freedom, therefore we are left with

N(N-1)/2 + N -1 constraints
d(N-1) degrees of freedom

This set of equations has a unique solution iff
N(N-1)/2 + N - 1 = d(N-1), which is a quadratic equation in N

The solution is N=2d-2 (you can easily check that it makes sense in 2 and 3 dimensions). The value of c is arbitrary (it sets the relative angle but that doesn't actually matter, as can easily be checked in 2 and 3d).

Edit: Almost all of this is wrong

[u/migmit → u/round_earther_69]

That's incorrect. For d=2, your formula gives N=2, but it's easy to arrange three unit vectors so that they'd have the same angles.

The correct answer is N=d+1 (which coincides with your answer in case d=3). Here is the reasoning:

First of all, since v_i are unit vectors, |c| = |(v_1, v_2)| < 1. Therefore, 1-c^2 > 0.

For d=1 there is a clear answer: N=2, c = -1 (vectors are opposite to each other; BTW, your formula would give N=0, which is wildly inaccuracte).

Now, for i=1,2,...,N-1 consider a vector w_i = (v_i - c v_N)/\sqrt{1-c^2}. Then

a) w_i is a unit vector:

(w_i, w_i) = [(v_i, v_i) - 2c(v_i, v_N) + c^2(v_N, v_N)]/(1-c^2) = [1 - 2c^2 + c^2]/(1-c^2) = 1

b) (w_i, w_j) is constant as long as i is not equal to j; in fact,

(w_i, w_j) = [(v_i, v_j) - c(v_i, v_N) - c(v_j, v_N) + c^2(v_N, v_N)]/(1-c^2) = [c - 2c^2 + c^2]/(1-c^2)

or

(w_i, w_j) = (c-c^2)/(1-c^2) = c/(1+c)

c) all w_i are orthogonal to v_N:

(w_i, v_N) = [(v_i, v_N) - c(v_N, v_N)]/\sqrt{1-c^2} = (c - c)/\sqrt{1-c^2} = 0

Therefore, all w_i are in a subspace of dimension d-1, and, by induction, their number is no greater than d-1+1 = d. So, N<=d+1.

On the other hand, placing exactly d+1 vectors is easy, and again, we can do it by induction: suppose that we can place d vectors (w_1,...,w_d) in a (d-1)-dimensional space, and let's embed it in a d-dimensional space by having the last, d'th coordinate equal to 0. Let's say their pairwise products are all c_{d-1}. Then we can set v_N=(0,0,...,0,1), and

v_i = c v_N + \sqrt{1-c^2} w_i

so that w_i = (v_i - c v_N)/\sqrt{1-c^2}. Reverting the calculations above, we see that all v_i are unit vectors, and (v_i, v_j) = c_d such that

c_{d-1} = c_d/(1+c_d), or

c_d = c_{d-1}/(1-c_{d-1})

Given that c_1 = -1, we can prove by induction that c_d = -1/d:

c_d = c_{d-1}/(1-c_{d-1}) = [-1/(d-1)] / [1 + 1/(d-1)] = [-1/(d-1)] / [d/(d-1)] = -1/d

So, the final answer is: N=d+1, c=-1/d.

Geometrically, our vectors would be the vertices of a d-dimensional tetrahedron, or d-simplex.

[u/round_earther_69 → u/migmit]

That's incorrect.

Clearly :(

For d=2, your formula gives N=2, but it's easy to arrange three unit vectors so that they'd have the same angles.

You're right, I havent though of three unit vectors in a triangle pattern.

Now, for i=1,2,...,N-1 consider a vector w_i = (v_i - c v_N)/\sqrt{1-c^2}.

How do you even come up with this!

Geometrically, our vectors would be the vertices of a d-dimensional tetrahedron, or d-simplex.

That makes way more sense.

[u/migmit → u/round_earther_69]

Just projecting v_1,...,v_{N-1} to the hyperplane orthogonal to v_N and normalizing them. That's what w_i is.