[math-fun] Wilson's grid problem (for scaled, not rotated, grids)
The ultimate generalization of the result would be if, in any dimension, for any nondegenerate point lattice, for any translation and volume-preserving-affine transformation of grid G1 (result: G2), there exists a matching of the points of G1 to the points of G2, such that each distance is bounded by a constant (but this constant may vary depending on the lattice, etc -- but for any particular choice of all that stuff, a finite constant exists). So far, I, following Wilson's 2D idea, proved this provided the "affine" was a "rotation." We now want to remove that restriction. The theory of the SVD (singular value decomposition) from linear algebra shows (I claim) that it will suffice to solve this problem in the (other) restricted case when the affine is a pure-scaling, i.e. a diagonal matrix. So: PROBLEM: Given a lattice G1, apply a diagonal matrix with determinant=1 to it to get lattice G2. To prove: always exists a matching of G1's to G2's points, with distance bounded by a finite constant depending on G1 and the diagonal matrix. This in turn would follow if we could show the LEMMA: there must exist some nonsingular affine transformation A, which causes both G1 and G2 to become the same (i.e. isometric) lattice, up to a rotation. I believe I can prove this in 2 dimensions, but my proof does not work in any higher dimension. This would confirm what (I think) Wilson was claiming, i.e. that he'd proved the maximally generalized claim at top, but in 2 dimensions only. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
This in turn would follow if we could show the LEMMA: there must exist some nonsingular affine transformation A, which causes both G1 and G2 to become the same (i.e. isometric) lattice, up to a rotation. I believe I can prove this in 2 dimensions, but my proof does not work in any higher dimension. This would confirm what (I think) Wilson was claiming, i.e. that he'd proved the maximally generalized claim at top, but in 2 dimensions only.
--aha, I think I see how to disprove this lemma. It comes down to this. Given nXn matrices X and Y we want to show a matrix M exists, such that MX = RMY where R is a rotation matrix. Rewrite as Minv Rinv M = Y Xinv. Now, letting C=Y*Xinv, the question becomes: PROBLEM: "for which square matrices C with detC=1, does there exist a rotation matrix Q and a general nonsingular matrix M, such that Minv Q M = C?" Equivalently Q = M C Minv. So the answer is "when and only when, C is conjugate to a rotation matrix." http://en.wikipedia.org/wiki/Matrix_similarity Now in general, a matrix C is NOT going to be conjugate to any rotation matrix, because conjugacy preserves the characteristic polynomial and hence eigenvalues. The eigenvalues of a rotation matrix always are located on the unit circle in the complex plane. The eigenvalues of a general matrix C, can be anything. But in 2 dimensions only, the eigenvalues of C are a complex-conjugate pair, which when detC=1 necessarily lies on the unit circle and then it can be done. Or, they both are real. Then it cannot be done, but the way to do it for the complex-conugate case presumably can be analytically continued to provide a solution for this case, which almost-provides a way to do it, but the "rotation matrix" you get unfortunately will have complex entries, or something bad of that nature. So... in conclusion: the proposed lemma is false in every dimension>2, and is semi-true in dimension 2.
participants (1)
-
Warren D Smith