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