Out there

Brilli the Ant is tripping out in 7-dimensional space (don't ask me how she got there). She recalled looking at a kaleidoscope, and seeing pretty patterns through reflections, because the pairs of lines all met at 6 0 60^\circ . This led her to wonder, what is the most number of (non-parallel) lines in R 7 \mathbb{R}^7 such that the angle between any two of them is the same?

Details and assumptions

Since we're only interested in the angle between the lines, you may assume that they all pass through the origin.

The angle between 2 intersecting lines in n n dimensions can be determined by just looking at the plane containing both lines.

There is no requirement that the angle must be 6 0 60^\circ .


The answer is 28.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Sep 30, 2013

Suppose that we can find n n lines in R k \mathbb{R}^k which are inclined at the same angle α \alpha to each other. If α = 0 \alpha = 0 then n = 1 n=1 , and so certainly n 1 2 k ( k + 1 ) n \le \tfrac12k(k+1) . Assume now that 0 < sin α < 1 0 < \sin\alpha < 1 . This means that we can find n n unit vectors v 1 , v 2 , , v n R k v_1,v_2,\ldots,v_n \in \mathbb{R}^k such that v i v j = ± cos α v_i \cdot v_j \,=\, \pm\cos\alpha for 1 i < j < n 1\le i < j < n . Consider the k × k k \times k symmetric matrix V i = v i v i T 1 i n V_i \; = \; v_i v_i^{\mathsf{T}} \qquad 1 \le i \le n We note that V i V j = ( v i v j ) v i v j T V_iV_j \,=\, (v_i\cdot v_j)v_iv_j^{\mathsf{T}} for all 1 i , j n 1 \le i,j \le n , so that T r ( V i V j ) = ( v i v j ) 2 = { 1 i = j cos 2 α i j \mathrm{Tr}(V_iV_j) \; = \; (v_i \cdot v_j)^2 \; = \; \left\{ \begin{array}{lll} 1 & \qquad & i = j \\ \cos^2\alpha & \quad & i \neq j \end{array} \right.

Suppose now that c 1 , c 2 , , c n R c_1,c_2,\ldots,c_n \in \mathbb{R} and that W = i = 1 n c i V i = 0 W \; = \; \sum_{i=1}^n c_i V_i \; = \; 0 Then 0 = T r ( W 2 ) = i , j = 1 n c i c j T r ( V i V j ) = i = 1 n c i 2 + cos 2 α i j c i c j = sin 2 α i = 1 n c i 2 + cos 2 α ( i = 1 n c i ) 2 \begin{array}{rcl} 0 \; = \; \mathrm{Tr}(W^2) & = & \displaystyle\sum_{i,j=1}^n c_ic_j \mathrm{Tr}(V_iV_j) \\ & = & \sum_{i=1}^n c_i^2 + \cos^2\alpha\sum_{i \neq j} c_ic_j \\ & = & \displaystyle\sin^2\alpha \sum_{i=1}^n c_i^2 + \cos^2\alpha\left(\sum_{i=1}^n c_i\right)^2 \end{array} and so we deduce that c 1 = c 2 = = c n = 0 c_1=c_2=\cdots=c_n=0 . Thus we have shown that the collection of matrices { V 1 , V 2 , , V n } \{V_1,V_2,\ldots,V_n\} is a linearly independent set in the vector space of symmetric k × k k \times k matrices, which is 1 2 k ( k + 1 ) \tfrac12k(k+1) -dimensional. Thus we deduce that n 1 2 k ( k + 1 ) n \le \tfrac12k(k+1) .

Putting k = 7 k=7 , we can find at most 28 28 lines which are equally inclined to each other. It remains to find a specific set of 28 28 lines in R 7 \mathbb{R}^7 .

Consider the 28 28 vectors in R 8 \mathbb{R}^8 consisting of 1 24 ( 3 3 1 1 1 1 1 1 ) T \tfrac{1}{\sqrt{24}}\big(\begin{array}{cccccccc}3&3&-1&-1&-1&-1&-1&-1\end{array}\big)^{\mathsf{T}} and all vectors obtained by permuting its components. Each of these 24 24 vectors is a unit vector, and the inner product of any distinct two of them is equal to 1 3 \tfrac13 if the two vectors have a 3 3 in the same position, and is equal to 1 3 -\tfrac13 if the two vectors do not have a 3 3 in the same position. Thus each of these 24 24 vectors define a line, and any two of these lines are inclined at the angle cos 1 1 3 \cos^{-1}\tfrac13 to each other. Since all 24 24 vectors are orthogonal to ( 1 1 1 1 1 1 1 1 ) T (1\;1\;1\;1\;1\;1\;1\;1)^{\mathsf{T}} , these 28 28 vectors reside in a 7 7 -dimensional subspace of R 8 \mathbb{R}^8 which is isomorphic to R 7 \mathbb{R}^7 , and hence we have found 28 28 lines in R 7 \mathbb{R}^7 which are all inclined at the same angle to each other.

Could you share the motivation/process of such a construction? Captivated by its beauty, I attempted at finding 45 vectors for 9 dimensions, but still could not succeed... Thank for a bit of inspiration.

Yezi Joy - 7 years, 8 months ago

Log in to reply

I don't know a lot about the general problem; I do not believe that it is completely solved. It is easy to find an upper bound on the number of such lines in R k \mathbb{R}^k , as I showed, but it seems that you can achieve 1 2 k ( k + 1 ) \tfrac12k(k+1) comparatively rarely. The maximum numbers of lines that can be found in R k \mathbb{R}^k are, for k = 1 , 2 , . . . , 18 , k = 1,2,...,18,\ldots , 1 , 3 , 6 , 6 , 10 , 16 , 28 , 28 , 28 , 28 , 28 , 28 , 28 , 28 , 36 , 40 , 48 , 48 , . . . 1, 3, 6, 6, 10, 16, 28, 28, 28, 28, 28, 28, 28, 28, 36, 40, 48, 48, ... There is still ongoing research on finding better upper bounds, and lower bounds, for the later terms in this sequence.

The construction of 28 28 lines in R 7 \mathbb{R}^7 works due to some connections with the Lie algebra E 7 E_7 , I read.

Mark Hennings - 7 years, 8 months ago

Log in to reply

Indeed. Apart from the cases k = 1 , 2 , 3 , 7 k = 1, 2, 3, 7 , the rest of the maximums are incredibly hard to justify. Also, the sequence almost certainly doesn't grow quadratically.

Calvin Lin Staff - 7 years, 8 months ago

Log in to reply

@Calvin Lin Apparently we can find 276 276 lines in R 23 \mathbb{R}^{23} , so we can add k = 23 k=23 to the list of "good" cases.

Mark Hennings - 7 years, 8 months ago

Ok, my reasoning was much simpler, but apparently wrong; In two dimensions the maximum number of lines is 3 (equilateral triangle).

Adding a dimension, we find a point so that all angles with the equilateral triangle are 60 degrees. Connecting this point to all previous ones adds three lines.

Another dimension further, we make a hypertetrahedron, adding 4 lines. And so on.

Total amount of lines is therefore 3+3+4+5+6+7=28.

Ton de Moree - 7 years, 8 months ago

Good work. Thinking in 3 dimensions is tough enough, I spent most of the week thinking whether we could get more than 3 lines in 3 dimensions, and eventually came up with a way to get 4 lines. But even extending that to 4 dimensions was mind-boggling, let alone 7.

Matt McNabb - 7 years, 8 months ago

There are three obvious typos - in three places I refer to 24 24 vectors, when I mean 28 28 ,

Mark Hennings - 7 years, 8 months ago

See Equiangular Lines for more information on the problem.

Jon Haussmann - 7 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...