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 &amp; 1 &amp; 1 &amp; 1 &amp; -1 &amp; -1 \\<br /> 1 &amp; 1 &amp; 1 &amp; 1 &amp; -1 &amp; -1\\<br /> 1 &amp; 1 &amp; 1 &amp; 1 &amp; -1 &amp; -1\\<br /> 1 &amp; 1 &amp; 1 &amp; 1 &amp; -1 &amp; -1\\<br /> -1&amp;-1&amp;-1&amp;-1&amp;1&amp;1\\<br /> -1&amp;-1&amp;-1&amp;-1&amp;1&amp;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!