Orientation consistency of a group

[SanDiegoMike]

Hello,

I apologise if this has been asked before. I did a search, but quite frankly, I'm not even sure what to search for.

My gut feeling is that this problem has already been well defined and solved, so if someone could point me in the proper direction, that would be great.


Consider a set of n vectors which can point in the positive or negative direction: {A1, A2, ... An }

if Ax and Ay point in the same direction, then d(Ax,Ay) = 1.

Similarly, if they point in the opposite direction, then d(Ax,Ay) = -1.

Now if d(A1,A2) = 1, and d(A2,A3) = 1, then d(A1,A3) must equal 1 to be consistent.

Similarly, if d(A1,A4) = 1 and d(A4,A5) = -1, then d(A1,A5) must equal -1 to be consistent.

[I'm guessing for the trivial case of d(Ax,Ax), the answer would be 1]

the problem:

Assume that I'm given all d(Ax,Ay) for x,y = 1...n. What is an efficient way of determining if this set is consistent?

[note: I can do this brute force, but as n gets big, it becomes a mess.]

Thanks!
-Mike.

 

[Stephen Tashi]

You also want d(Ax,Ay) = d(Ay,Ax), I assume.

One thought is that if you look at d(X_i,Y_j) as an entry in a matrix, you would expect the matrix to be permutable to one that has two square blocks of the 1's along the diagonal and -1 elsewhere. For example:

$$\begin{pmatrix} 1 & 1 & 1 & 1 & -1 & -1 \\ 1 & 1 & 1 & 1 & -1 & -1\\ 1 & 1 & 1 & 1 & -1 & -1\\ 1 & 1 & 1 & 1 & -1 & -1\\ -1&-1&-1&-1&1&1\\ -1&-1&-1&-1&1&1 \end{pmatrix}$$

If you could prove the matrix had to have that form then you could test for this condition.
I'm assuming permuting a given matrix to that form is less work than "brute force".

 

[SanDiegoMike]

Thanks Stephen, I do believe you're correct. That seems to be a very clever way forward.

It's been a long time since my undergraduate course work in linear algebra. Can you point me in the direction of an efficient algorithm for testing for such a matrix?

 

[SanDiegoMike]

no worries, I figured out how to do the test. Very simple indeed. Thanks!

 

[CellCoree]

I would like to thank you for bringing up this interesting problem. It is true that the concept of orientation consistency within a group has been studied and solved in various fields, such as mathematics and computer science.

To answer your question, there are a few different approaches you could take to determine the consistency of a set of vectors. One approach would be to use graph theory, treating each vector as a vertex and the consistency relationships as edges. You could then use algorithms such as depth-first search or topological sorting to determine if the graph is consistent.

Another approach would be to use linear algebra and matrix operations. You could represent each vector as a row or column in a matrix and use operations such as matrix multiplication to determine if the resulting matrix has consistent relationships between vectors.

Of course, as you mentioned, brute force is also an option, but it may become inefficient as the size of the set grows. Therefore, exploring these other methods may be more efficient and provide you with a better understanding of the problem.

I hope this helps guide you in the right direction. Best of luck in your research!