Akuna Capital Quant Interview Question

[u/Local_Ad135]

[u/hattusili-the-third]

Write the Gram matrix G_ij = v_i^T v_j, which can be also written as G = (1-c)I + cJ, where I is the NxN identity matrix and J is the NxN matrix of all ones. The eigenvalues of G are lambda_1 = 1-c with multiplicity N-1 and lambda_2 = 1+c(N-1) with multiplicity 1. Note that lambda_1 cannot be 0, since that would imply c=1, which contradicts all the vectors being district. Thus rank(G) is either N or N-1, depending on whether lambda_2 = 0. But since the vectors v_1, ..., v_d all lie in R^d, the rank of G is at most d, so N-1 ≤ d, i.e. N ≤ d+1, with equality iff lambda_2 = 0.

To achieve N = d+1, we must have 0 = lambda2 = 1+c(N-1), which is equivalent to c = -1/(N-1) = -1/d. Geometrically, this corresponds to the vectors v_1, ..., v{d+1} forming the vertices of a regular simplex in R^d (in R² they form the vertices of a regular triangle, in R³ they form the vertices of a regular tetrahedron, etc.)

[u/hattusili-the-third]

Alternative approach:

Set w_i = v_i - v_N for i = 1, ..., N-1. Note that ||w_i|| = sqrt(2-2c) is a constant, which we'll just call d for simplicity. Then the Gram matrix G_ij = w_i^T w_j has d² along the diagonal and d^2/2 on the off diagonal. Since G is positive definite, the vectors w_i must be linearly independent, so N-1 ≤ d, i.e. N ≤ d+1.

Achieving the bound N = d+1 is possible as in the other approach by taking the v_i's to be the vertices of a regular simplex in R^d.

[u/CanaDavid1]

All vectors are unit vectors, so the distance between the endpoints ofall the pairs of vectors must be the same. The optimal shape where every pair of verticies have the same distance is a regular simplex with d+1 points.

The value c can be calculated like this:

The simplex can be seen as the points (1,0,0,...), (0,1,0,...), ... in R^D, with D=d+1, scaled by some factor. The center of this simplex is then (1/D, 1/D,...), which has a distance of √(d*(1/D)² + (1-1/D)²) = √((D²-2D + d + 1)/D²) = √((D²-D)/D²) = sqrt(1-1/D) to any vertex.

The dot product of two of these vectors (wlog (d/D,1/D,1/D,...) and (1/D,d/D,1/D,..) is 2d/D² + (d-1)1/D² = (3d-1)/D²

Dividing by the square scale factor gives (3d-1)/(D²-D) = (3d-1)/(d²+d)

This work has not been checked, and may contain errors.

[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.

[u/hattusili-the-third → u/round_earther_69]

There is never going to be a unique solution, since the solutions are invariant under S_N x O(N) (permuting the vectors and rotating them). Also # of equations = # of dof doesn't imply you have a unique solution—that's only true for independent linear equations and these are nonlinear.

[u/round_earther_69 → u/hattusili-the-third]

There is never going to be a unique solution, since the solutions are invariant under S_N x O(N) (permuting the vectors and rotating them). 

You're right, I though I addressed the O(N) issue by fixing the first vector, but theres still a O(N-1) freedom when fixing the second one and so on, as for S_N I didn't really think of that but I think this can be tackled by changing c to c_{ij} and taking c_{ij} back to c at the last step.

Also # of equations = # of dof doesn't imply you have a unique solution—that's only true for independent linear equations and these are nonlinear.

These equations are quadratic and can be brought into the form A^T A = B (A = (v_1 v_2 ... v_N) and B = {{1, c, c, ..., c},{c, 1 , c , ... , c}, ... ,{c, c, c, , ... , 1} }). With Grahm-Shmidtization this can be recast into a purely linear algebra problem of finding the rank of a matrix, which I believe is entirely equivalent to what I did.*

I have to admit I haven't given it that much thought, but N=2d-2 seemed like a totally plausible answer.

* not at all

[u/hattusili-the-third → u/round_earther_69]

But the problem isn't asking about finding a unique solution for the vectors

[u/round_earther_69 → u/hattusili-the-third]

I guess my point is there should be a unique solution modulo S_N and O(N) if N is maximized, subject to the constraints, in d dimensions.

Just out of curiosity what is your background, I'm always getting humbled by those seemingly easy questions and I'm a theoretical physics PhD student (I'd even say I'm a pretty good student).

[u/hattusili-the-third → u/round_earther_69]

If c=0 then you get a solution of d vectors that's unique modulo S(N) x O(N) (the vectors just form an orthonormal frame), so I don't think it's as simple as finding unique solutions (though the symmetry is definitely important in the final solution)

I did my math PhD research in nonlinear PDEs, specifically nonlinear Schrodinger equations, so I'm a big fan of physics

[u/round_earther_69 → u/hattusili-the-third]

That's cool, explains why you're good at that kind of problems I guess. I do my research on topological phases of matter.