4
$\begingroup$

I want to generate a list of vectors $\{\mathbf{v}_i\}, i\in[1,N]$ such that

$$\mathbf{v}_i\cdot\mathbf{v}_i = 1, \forall i$$

$$\mathbf{v}_i\cdot\mathbf{v}_j = \cos\theta, \forall i\neq j$$

$$\sum_{i=1}^N \mathbf{v}_i = 0$$

$$\mathbf{v}_1=(1,0,0)$$

$$\mathbf{v}_2=(\cos\theta,0,\sin\theta)$$

For $N=2$, we have $\mathbf{v}_1=(1,0,0), \mathbf{v}_2=(-1,0,0), \theta=\pi$.

For $N=3$, we have $\mathbf{v}_1=(1,0,0), \mathbf{v}_2=(-1/2,0,\sqrt{3}/2), \mathbf{v}_2=(-1/2,0,-\sqrt{3}/2),\theta=2\pi/3$.

etc.

I would like to be able to generate this list of vectors for arbitrary $N$. I can do it by hand, but I want to add this to some python code. I tried to come up with an iterative way of doing it, but I lose track of all the vector components I have to solve for pretty quickly. What is the simplest way to do this?

$N$ is not going to be huge -- let's say $N=30$ at most. Because of this, and because this generation will be done once in my code, I'm not super worried about the performance of the python code that I will implement.

$\endgroup$
6
  • 3
    $\begingroup$ As stated, you want the $\theta$ to be the same for every pair of vectors. I believe this is impossible for $N>4$. Consider the case of $N=6$, where I imagine you would be happy with the vertices of a regular octahedron. But this has $v_i\cdot v_j = 0$ for some $i,j$, and $v_i\cdot v_j = -1$ for others. $\endgroup$ Commented May 3, 2023 at 13:28
  • 4
    $\begingroup$ This page on spherical codes by N.J.A. Sloane provides specific solutions to the problem of selecting points on a sphere such that the separation between any two points is maximized, for the $N$ you want. The actual solutions for $\Bbb R^3$ are here. This Math SE post discusses the case of very large $N$. $\endgroup$ Commented May 3, 2023 at 13:35
  • 1
    $\begingroup$ To read Sloane's solutions, see for example the packing of six points. The file contains 18 numbers, which are successively the $x,y,z$ coordinates of the six points. The last two points $\langle 0, 0, 1\rangle$ and $\langle 0,0,-1\rangle$ are the poles, and the other four points are equally spaced around the equator. $\endgroup$ Commented May 3, 2023 at 13:41
  • 1
    $\begingroup$ Right, I don't think you can get five vectors that have the property you stated, or indeed any $N>4$. In the $N=5$ case I believe the best you can do is two poles and then three equally spaced around the equator. (That is, a triangular dipyramid.) The Sloane numbers seem to agree with this. $\endgroup$ Commented May 3, 2023 at 14:47
  • 1
    $\begingroup$ If you really want to code this, one way is with a sort of physics simulation. Pretend that the points are charged particles. Put them on the sphere at random. Simulate the repulsive forces on the particles: if two particles are close together, they will repel until the whole system is in equilibrium. When it settles down, that is your answer. (Not necessarily the optimal answer, but at least locally optimal.) $\endgroup$ Commented May 3, 2023 at 14:54

1 Answer 1

4
$\begingroup$

One way to handle the problem is to let $V$ be a matrix whose columns are the desired vectors. Then the Gram matrix $M=V^\top V$ satisfies $M_{ij}=\mathbf{v}_i\cdot \mathbf{v}_j$, so the constraints specify $M_{ij}=\cos\theta$ if $i\neq j$ and $1$ otherwise. The assumption that $\sum_{i}\mathbf{v}_i=0$ further amounts to the claim that $Vu=0$ where $u$ is a column vector of 1s. But then $Mu=V^\top Vu=0$, whereas one can show that the characteristic polynomial of $M$ is $$\det(M-\lambda I_N)=(1-\cos\theta-\lambda)^{N-1} (1+(N-1)\cos\theta-\lambda).$$ So if we assume the vectors are not collinear, we must have $\cos\theta=-1/(N-1)$ for $M$ to have a zero eigenvalue. The determinant furthermore shows that $M$ will have $N-1$ eigenvectors of eigenvalue $\lambda=1-\cos\theta=N/(N-1)$. This gives us $N-1$ of the needed vectors, with the last vector being deduced from $\sum_i \mathbf{v}_i=0$. Hence the $N$ vectors must be at least $(N-1)$-dimensional, e.g., we must go up to at least dimension 29 if we want 30 such vectors.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.