3 ms·

It's amazing to see all of this described in such detail. Very nice presentation! Also, I'm going to mildly hijack this thread with a question since I know pe

It's amazing to see all of this described in such detail. Very nice presentation! Also, I'm going to mildly hijack this thread with a question since I know people familiar with this kind of problem will be looking at the comments ;) The TSP is essentially trying to find the correct permutation of an ordered list of cities (up to a cycle) that minimizes the total distance traveled. I have a somewhat similar problem. Given a set of vectors (in R^3), I am trying to find a way to generate a permutationally invariant representation of these vectors that is also rotationally invariant. The rotational invariance is easily solved by constructing the Gram matrix of the set of vectors (each element M_ij in the matrix is the inner product between vector x_i and vector x_j). Of course, the Gram matrix is overcomplete now (redundant), so I take the Cholesky decomposition to get a unique representation that has 3 less degrees of freedom (all the rotational degrees) than the original set. For permutational invariance though, I'm having a heck of a time. I've been extensively searching the academic literature on this topic, and maybe I'm just not using the right search terms, but I can't find anything. Recently I've been reading about symmetric groups and trying to figure out if there's some kind of linear basis that I can construct its elements out of, but I'm not having much luck. Anyone have any ideas? If that problem is too hard, consider this simpler problem: Given a metric between two sets of vectors (of the same order), I want to find the permutation of the second set that minimizes this metric. So basically, min(|| A - P A' P' ||), where ||X|| denotes the metric, and P is a permutation matrix. I feel like there is some kind of relation between this question and the TSP, but I can't quite figure out what.

tribe 12y ago
I know it is computationally a bit of a pain, but if you have points v_1,v_2,v_3 does the Jordan Canonical Form of the matrix [v_1 v_2 v_3] not satisfy your requirements? I believe that the original matrix is similar to both its permutations and rotations, so the JCF should be invariant. My linear algebra is a bit rusty, so I might be wrong
psb217 12y ago
This is just the problem of forming automorphism-invariant encodings of a graph, but extended to permit weighted graphs. First, given the Gram matrix for your vectors, interpret its entries (read from left-to-right and top-to-bottom) as defining a cumulative sum. Next, order your vectors such that the values in the order-induced cumulative sum are maximal for as many of the partial sums as possible, compared with the cumulative sums induced by any other possible ordering. This produces the same "canonical ordering" and hence the same "canonical Gram matrix" for any set of vectors that have the same collection of pair-wise relationships, as measured by dot-products. For graphs with binary adjacency matrices this can be stated more simply as sorting the vertices such that the resulting adjacency matrix, when read l-to-r and t-to-b, produces the largest binary number. This encoding uniquely identifies the automorphism group of the encoded graph (i.e. all isomorphic graphs produce the same encoding). If you were willing to represent your pair-wise dot-products u sing fixed-precision binary representations, then you could just use the "matrix as binary number" approach directly. Though, each matrix entry would now contribute multiple bits to the binary number, rather than just one. Note that this approach is not efficient. But, your problem subsumes standard graph isomorphism, so a polynomial-time solution would be noteworthy. All of what I've said makes no assumption about the vectors' dimensions. There's probably a more efficient approach for vectors constrained to a relatively low-dimensional space.

tribe 12y ago

I know it is computationally a bit of a pain, but if you have points v_1,v_2,v_3 does the Jordan Canonical Form of the matrix [v_1 v_2 v_3] not satisfy your requirements? I believe that the original matrix is similar to both its permutations and rotations, so the JCF should be invariant. My linear algebra is a bit rusty, so I might be wrong

psb217 12y ago

This is just the problem of forming automorphism-invariant encodings of a graph, but extended to permit weighted graphs. First, given the Gram matrix for your vectors, interpret its entries (read from left-to-right and top-to-bottom) as defining a cumulative sum. Next, order your vectors such that the values in the order-induced cumulative sum are maximal for as many of the partial sums as possible, compared with the cumulative sums induced by any other possible ordering. This produces the same "canonical ordering" and hence the same "canonical Gram matrix" for any set of vectors that have the same collection of pair-wise relationships, as measured by dot-products. For graphs with binary adjacency matrices this can be stated more simply as sorting the vertices such that the resulting adjacency matrix, when read l-to-r and t-to-b, produces the largest binary number. This encoding uniquely identifies the automorphism group of the encoded graph (i.e. all isomorphic graphs produce the same encoding). If you were willing to represent your pair-wise dot-products u sing fixed-precision binary representations, then you could just use the "matrix as binary number" approach directly. Though, each matrix entry would now contribute multiple bits to the binary number, rather than just one. Note that this approach is not efficient. But, your problem subsumes standard graph isomorphism, so a polynomial-time solution would be noteworthy. All of what I've said makes no assumption about the vectors' dimensions. There's probably a more efficient approach for vectors constrained to a relatively low-dimensional space.