Orientation consistency of a group

  • #1
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.
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,581
1,470
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:

[tex] \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} [/tex]

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".
 
  • #3
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?
 
  • #4
no worries, I figured out how to do the test. Very simple indeed. Thanks!
 

Related Threads on Orientation consistency of a group

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
13
Views
420
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
8
Views
4K
Replies
3
Views
5K
  • Last Post
Replies
3
Views
10K
Replies
3
Views
2K
Replies
1
Views
1K
Replies
8
Views
859
Top