User tracy hall - MathOverflow

Standard reference for equivalence of PU(2) action on $\mathbb{C}\mathbb{P}^1$ and SO(3) action on $S^2$

2011-03-29T00:39:41Z

The equivalence I describe below is well-known, but I'd like a simple standard reference for it.

Consider $\mathbb{C}\mathbb{P}^1$, the set of one-dimensional subspaces of $\mathbb{C}^2$, which has a metric given by the angle between subspaces (varying between a minimum of $0$ for identical subspaces and a maximum of $\frac\pi2$ for a subspace and its unique orthogonal complement) and which has holomorphic isometry group $\mathrm{PU}(2)$. Consider on the other hand $\frac12 S^2$, the sphere of points distance $\frac12$ from the origin in $\mathbb{R}^3$, which has a metric given by great-circle distance (varying between a minimum of $0$ for identical points and a maximum of $\frac\pi2$ for a point and its unique antipode) and which has orientation-preserving isometry group $\mathrm{SO}(3)$.

Now define a map $\varphi : \mathbb{C}\mathbb{P}^1 \to \frac12 S^2$. The subspace spanned by $(0,1)$ is sent by $\varphi$ to the north pole $p = (0,0,\frac12)$. Any other subspace is spanned by a uniquely defined vector $(1,a+bi)$, for $a$ and $b$ real and $i^2 = -1$, and $\varphi$ sends it to the point at which the open ray from $p$ through $(a, b, -\frac12)$ intersects $\frac12 S^2$. (This is a shift of the standard stereographic projection to place the center of the sphere at the origin.)

Claim: The map $\varphi$ is an isometry from $\mathbb{C}\mathbb{P}^1$ to $\frac12 S^2$, and the map from $f \in \mathrm{SO}(3)$ to $g = \varphi^{-1} f \varphi \in \mathrm{PU}(2)$ is an isomorphism of Lie groups.

The fact that the two Lie groups are isomorphic is mentioned (without reference, by a sequence of isomorphisms) in Wikipedia and the isometry also appears as a special case of something more specialized. I expect that some version of the equivalence I want is covered in any standard text on quantum computing, where $\mathbb{C}\mathbb{P}^1$ is called the Bloch sphere. If possible I would prefer not to use such specialized references for what is essentially a simple (but somewhat tedious to verify) piece of geometry.

Is there a good standard reference, ideally requiring minimal background beyond standard undergraduate mathematics, that would suffice to treat a collection of vectors in $\mathbb{C}^2$, considered up to individual scaling and simultaneous action by $\mathrm{U}(2)$, as being equivalent (under an explicit map) to a collection of points in a $2$-sphere, considered up to Euclidean geometry?

Answer by Tracy Hall for Probability, that a graph G does not contain a cycle

2011-03-02T08:01:45Z

I will assume what seems the more natural question: uniform probability over all labeled graphs with exactly $k$ edges and $n$ vertices (rather than on isomorphism classes of graphs). The number of labeled forests with $k$ edges on $n$ vertices is the integer sequence http://oeis.org/A138464 which doesn't seem to indicate that a closed form expression is known. To obtain the probability divide this number by (($n$ choose 2) choose $k$).

Answer by Tracy Hall for Complexity of random knot with vertices on sphere

2011-02-09T08:02:05Z

This is not really an answer but an over-long comment following up suggestions of Ian Agol and Bill Thurston.

Experiment suggests (with 97% confidence) that the crossing probability (in a specified or random projection, for two line segments with the four endpoints chosen independently uniformly at random with respect to Haar measure) is greater than $.2499$ and less than $.2501$. I have a motto never to compute by integrating what can be computed by symmetry, so the hope would be, for some integer $S$, to write a total of $4S$ symmetry-related expressions for the probability whose sum is identically $S$. So far any such trick eludes me; does anyone else see a way?

It would surprise me, for very large $n$, if even a constant factor improvement over a randomly chosen obvious projection is possible. I would wager, then (although I would hate to have to prove it) that $$\lim\limits_{n\rightarrow\infty} \frac{\bar{c}(n)}{n^2} = \frac18,$$ where $\bar{c}(n)$ is the expected value of crossing number for $n$ random points on the sphere.

The suggestion of a Voronoi-like spine whose dual would triangulate the knot complement is an interesting one. The individual faces are sections of hyperbolic paraboloid. It seems reasonable that their number would be strictly between linear and quadratic, although I don't yet see a good heuristic for guessing the correct order.

EDIT: I was able to satisfy myself that the crossing probability is exactly $\frac14$, through a fairly (and probably unnecessarily) involved process. At most stages one can reduce to simpler calculations using symmetries or nice facts such as the probability-preserving projection map from a $(d-1)$-sphere in $\mathbb{R}^d$ onto the ball of its first $d-2$ components. For the final step I did have to compute an integral, though—the same one that tells you the angular momentum of a spinning coin (whose axis of rotation is in the plane of the coin).

I have started to suspect that in a certain precise sense an integral is unavoidable—that the boundary of crossing configurations is curved in ways that prevent abutment, just as the region north of $30^\circ$ latitude carries exactly $\frac14$ of the surface area of a perfect globe, but no finite collection of $4S$ rotated copies of it can be an exact $S$-fold cover. (The transcendental answer to the usual Sylvester's four-point problem in the disc also discourages the finite cover approach.)

Answer by Tracy Hall for Which platonic solids can form a topological torus?

2011-01-28T22:12:21Z

All but the tetrahedron.

As noted in a comment, ultimately referencing a 1972 paper, for tetrahedra this cannot be done. I haven't looked at the paper, but the proof may go as follows: Let the vertices of your base tetrahedron be the standard basis vectors in $\mathbb R^4$ times 4, so their center point is the all-ones vector. Construct the four matrices which reflect through the faces of your tetrahedron (while fixing the sum-to-4 hyperplane). Observe that some entries of these matrices equal $\frac23$. Apply a reduced word in the reflection group to the all-ones vector, and prove by induction that the first generator in the word is always indicated by which entry has the lowest power of 3 in the denominator, with a predictable pattern mod 3 in the numerators. Conclude that no nontrivial product of reflections takes the center point back to itself.

For the octahedron, attaching a pair along opposite faces allows you to continue in the pattern of carbon atoms in the diamond crystal structure, where each atom has tetrahedral bonds in directions all four of which are the negatives of any neighbor's bonds. It is thus possible to glue together 12 octahedra positioned like the carbons and C-C bonds of the "chair" conformation of cyclohexane. Since eight of the twenty faces of an icosahedron are inclined like the faces of an octahedron, the exact same arrangement is possible with icosahedra.

EDIT: In fact, you can do better. Given any polytope that has two pairs of opposite parallel facets such that reflected polytopes may be attached to all four facets simultaneously without overlapping, a thickened parallelogram may be constructed by attaching eight identical polytopes along facets. This works because a pair of parallel reflections amounts to a pure translation, making the same possible attachment directions available at both ends of the double reflection.

Answer by Tracy Hall for Adjacency matrices of graphs

2011-01-19T02:55:28Z

Yes.

Consider the adjacency matrices $$ A = \left[\begin{array}{rrrrrrrrrrr} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right] $$ and $$ B = \left[ \begin{array}{rrrrrrrrrrr} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right]. $$ These are both the adjacency matrices of trees, and both have characteristic polynomial $$\lambda^{11}-10\lambda^9+34\lambda^7-47\lambda^5+25\lambda^3-4\lambda.$$ Each tree has exactly two vertices of degree 3, separated by a path of length 1 in the case of $A$ but length 2 in the case of $B$. In particular, the trees are not isomorphic.

Now consider the [EDIT: improved, much nicer] matrix $$ C = \left[\begin{array}{rrrrrrrrrrr} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ \end{array}\right] $$ with determinant $-1$.

Since $C^{-1}AC = B$, the two trees (on 11 vertices) are non-isomorphic but have adjacency matrices that are conjugate over $\mathbb Z$.

Now to explain the where the example comes from. The pair of graphs was constructed by a method, attributed to Schwenk, that I found in Doob's chapter of Topics in algebraic graph theory (edited by Beineke and Wilson). The first 9 rows and columns of $A$, in common with $B$, come from a particular tree on 9 vertices that has a pair of attachment points such that extending the tree in the same way from either point gives isomorphic spectra. Adding a single pendant vertex cannot work for this problem, as I found using Brouwer and van Eijl's trick, mentioned by Chris Godsil, of comparing the Smith normal forms of (very) small polynomials in $A$ and $B$, in this case $A+2I$ and $B+2I$. When a path of length two is added at either of the two special vertices, however, there doesn't seem to be any obstruction of this type.

I then set about trying to conjugate both $A$ and $B$, separately, to the companion matrix of their mutual characteristic polynomial, by looking for a random small integer vector $x$ for which the matrix $X_A = [ x\ Ax\ A^2x\ \ldots\ A^{10}x]$ has determinant $\pm 1$, and similarly $y$ giving $Y_B$. (The fact that I succeeded fairly easily may have something to do with the fact that $A+I$ is invertible over $\mathbb Z$.) The matrix $X_AY_B^{-1}$ then acts like the $C$ above.

[EDIT: The actual matrix $C$ I found at random and first posted was not nearly so pretty, with a Frobenius norm nearly ten times the current example. But taking powers 0 to 10 of $A$ times $C$ gave a $\mathbb Q$-basis for the full space of conjugators, whose Smith normal form (as 11 vectors in $\mathbb R^{121}$) was all 1's down the diagonal, so in fact it was a $\mathbb Z$-basis. Performing an LLL reduction on this lattice basis then gave a list of smaller-norm matrices, the third of which is the more illuminating $C$ given above, of determinant $-1$. The other determinants from the reduced basis were all $0$ and $\pm 8$.]

Taking rational $x$ and not restricting the determinant of $X_A$ gives a space of possible rational matrices $C$ of dimension 11, which are generically invertible; varying $y$ gives the same space [EDIT: as does multiplying on the left by powers (or in the more general case commutants) of $A$]. Since the spectrum of $A$ has no repeated roots, this is also the dimension of the commutant of $A$, and every matrix conjugating $A$ to $B$ lies in this space. Starting with a rational basis, it is not hard to find an exact basis for the integer sublattice, and taking the determinant of a general point in the integer lattice gives an integer polynomial in 11 variables which takes the value $1$ or $-1$ if and only if the matrices $A$ and $B$ are conjugate over $Z$. If there are repeated roots, you have to work a little harder; in general the full space has dimension the sum of the squares of the multiplicities, and is generated by multiplying on the left by a basis for the commutator space of $A$. A basis for the commutant can be produced (for a diagonalizable matrix) by first conjugating $A$ to a direct sum of companion matrices for the irreducible factors of the characteristic polynomial, and then one at a time, for each $k$-by-$k$ block corresponding to a $k$-times repeated factor of degree $m$, replacing each of the $k^2$ blocks with powers $0$ to $m-1$ of the companion matrix for that factor, with $0$ everywhere elsewhere.

Answer by Tracy Hall for Optimal knot placement for fitting piecewise-continuous linear functions to a nonlinear function

2010-11-12T05:29:41Z

In the limit of fine subdivision, the local goodness of fit depends on only two things: the absolute value of the local second derivative, and the local density of knots. For a segment of constant second derivative $a$ over an interval of length $c$, the integrated squared error over the interval comes out to $a^2c^5/120$. Given a small approximation interval (small enough that the second derivative does not vary by much over its length) whose squared error contribution is $E$, replacing that interval by two approximation intervals of half the width reduces the total squared error by approximately $E- 2(E/32)=(15/16)E$. The best segment to subdivide (according to this approximation) is thus whichever one contributes the most to the error. It follows that in the limit of many knots the optimum will have an equal contribution to the error coming from each segment. This is true, in the limit, when the local density of knots at $f(x)$ is proportional to $f^{\prime\prime}(x)^{2/5}$. A very good approximation to your optimal assignment problem can thus be obtained by making a plot, from $L$ to $U$, of $\int_L^x f^{\prime\prime}(s)^{2/5}\ ds$, dividing it into equally spaced horizontal strips, and placing your knots at the horizontal values where the integral plot crosses from one horizontal strip to the next.

Incidentally, if you keep the same number of straight-line approximations but allow them to cross the function (and back) in their interiors rather than at their endpoints, you can improve the integrated squared error by (in the limit) a factor of 6.

Answer by Tracy Hall for Number of unique sortings of subset-sums

2010-09-21T02:27:02Z

As David Speyer points out in a comment, this is equivalent to the number of regions resulting when $\mathbb{R}^n$ is divided by hyperplanes of the form $\sum_{i \in I}a_i = \sum_{i \in J}a_i$ for all disjoint pairs of subsets $I,J \subseteq [n]$. Dual to this description, it is the number of ways that the $3^n-1$ nonzero vectors in $\{-1,0,1\}^n$ can be divided into "positive" and "negative" by a hyperplane (in general position) passing through the origin, which makes it easy to see that the answer is indeed $8$ for $n=2$.

As I mentioned in a comment, the total is always $2^n$ times what you get when making the assumption $a_i > 0$ for all $i$. There is another symmetry that can also be exploited: making the assumption $a_1 < a_2 < \cdots < a_n$ reduces the total by a further factor of $n!$, which gives a known sequence:

http://www.research.att.com/~njas/sequences/A009997

http://arxiv.org/abs/math.CO/9809134

Various key words are "coherent boolean term order", "coherent generalized term order", and "additive antisymmetric comparative probability order". It doesn't look like anyone knows the values beyond $n=7$. You'll want to check Maclagan's reference to Fine and Gill 1976 to see if they give any asymptotics.

Including the $2^nn!$ symmetries gives these values:

$2$
$8$
$96$
$5$ $376$
$1$ $981$ $440$
$5$ $722$ $536$ $960$
$138$ $430$ $238$ $607$ $360$

Answer by Tracy Hall for Random products of projections: bounds on convergence rate?

2010-09-18T02:01:53Z

If you only care about the bound having the correct form, and don't mind obtaining constants that are much worse than the actual asymptotic convergence, then all you have to do is apply [BGM] to a subsequence. Specifically, let $k$ be the number of projections from which you sample, and let $p_0, p_1, \ldots, p_{k-1}, p_k = p_0$ be a particular circular ordering of them. Given a random sequence $X_i$ of projections, consider the initial segment $S(n)$ of $n$ projections, and define $L(n)$ such that $L(n) \ge 1$ if and only if $(p_0, p_1)$ occurs consecutively in $S(n)$, such that $L(n) \ge 2$ if and only if the consecutive pair $(p_1,p_2)$ occurs somewhere after $(p_0, p_1)$ in $S(n)$, such that $L(n) \ge 3$ if and only if that is somewhere followed by $(p_2, p_3)$, and so forth. For large values of $n$, the random variable $L(n)$ is tightly concentrated around a value close to $n/k^2$, and the convergence of, say, the segment $S(2k^2n)$ will, with high probability, be at least as good as the fixed cyclic ordering of length $n$.

The one technical lemma to prove is that you cannot lose by replacing each $p_i$ in the fixed sequence by a product of projections that both starts and ends with $p_i$.

Answer by Tracy Hall for What is your favorite isomorphism?

2010-09-02T21:39:49Z

The set of positive reals under multiplication is isomorphic to the set of reals under addition, which is the isomorphism underlying the operation of a slide rule. This is the only isomorphism I can think of important enough that its explicit (approximate) values used to be published in 1000-page books. The positive reals under multiplication is also a standard pedagogical example of an interesting one-dimensional abstract real vector space, where there is some content to verifying the axioms. (The other standard example is the reals with addition given by $x+y-1$ and multiplication by scalar $a$ given by $ax + 1 - a$.)

Answer by Tracy Hall for What is your favorite isomorphism?

2010-09-02T21:58:05Z

The whole subject of non-commutative geometry arises from extending to non-commutative algebras the isomorphism that exists between commutative $\mathrm{C}^*$-algebras and locally compact Hausdorff topological spaces.

Answer by Tracy Hall for Combining DAGs into an acyclic tournament

2010-08-19T23:03:32Z

The problem you pose, of finding a bipartition if one exists, is of polynomially equivalent difficulty to the decision problem of determining whether a bipartition exists. The decision problem in turn is NP-complete, by reduction from 3-SAT (and the fact that a solution is easily checked.)

Given an instance of 3-SAT with $n$ clauses, we construct a family of DAGs on $4n$ vertices. All edges in the complement of $n$ disjoint $4$-cycles will be singleton DAGs. One "universal" DAG consists of a single edge in each $4$-cycle, and establishes a potential (forbidden) orientation on each $4$-cycle. Then for every variable in the 3-SAT instance we define a DAG consisting of an edge in each of the $4$-cycles corresponding to the clauses in which that variable appears, with the direction depending on whether the variable appears negated in the clause, in such a way that the forbidden orientation imposed by the universal DAG is achieved in a given $4$-cycle if and only if no literal in the corresponding clause is true, where a variable is considered true when its DAG lies on the same side of the bipartition as the universal DAG and is considered false otherwise. Then an acyclic bipartition of the DAGs exists if and only if the instance of 3-SAT has a satisfying assignment.

Answer by Tracy Hall for Which came first: the Fibonacci Numbers or the Golden Ratio?

2010-08-15T15:06:39Z

What is the significance? Most of the nice properties of the golden mean can be attributed to the fact that its continued fraction coefficients are uniformly bounded, as will be true in particular for any periodic continued fraction, which is to say any quadratic irrational, such as arises as the spectral radius of an indecomposable two-term linear recurrence relation. Among such continued fractions, the unique one with the minimum possible upper bound of 1 naturally exhibits these effects most prominantly, and it arises from (arguably) the simplest such recurrence.

Answer by Tracy Hall for How fast can the base-bumping function in Goodstein's theorem grow?

2010-08-13T20:00:02Z

As long as your fast-growing "base-bumping" function still takes every natural number to a natural number (instead of, say, an infinite ordinal)--and the busy beavers do--the Goodstein iterations are still upper-bounded by the strictly-decreasing sequence of ordinals in "base" $\omega$, which must be of finite length as a decreasing sequence in a well-ordered set.

Answer by Tracy Hall for Minimally 2-vertex-connected graphs?

2010-08-13T19:11:49Z

Here is a more general family:

Draw your favorite tree in the plane, with circles for the nodes and "thick" lines for the edges. Now turn every circle into a cycle, and every thick line into a pair of parallel paths $p_1, \ldots, p_m$ and $q_1, \ldots, q_n$ with various crossbraces. The crossbraces just have to follow the rule that if $p_i$ is connected to $q_\ell$ and $p_j$ is connected to $q_k$, for $i<j$ and $k<\ell$, then $j =i+1$ or $\ell=k+1$.

This is probably still not close to a complete characterization, but at least shows that the class is a lot broader than the small class you posited to promote discussion.

Answer by Tracy Hall for Correlation in graph coloring

2010-08-13T04:08:50Z

As regards question 3: Chromatic polynomials provide the answer quite directly--but calculating them is anything but efficient.

Naturally if $u$ and $v$ are joined by an edge, the proportion you are asking about is 0. If they are not adjacent, then let $q$ be the chromatic polynomial of $G$ and $p$ be the chromatic polynomial of $G/\{u,v\}$, i.e. the result of identifying $u$ and $v$. The proportion you seek is then the rational function $p/q$ evaluated at $k$, which as you point out is only defined for $k$ at least the chromatic number.

Answer by Tracy Hall for Naturally occuring groups with cardinality greater than the reals.

2010-08-13T01:31:19Z

Does a group showing up in a College Algebra (pre-calculus) course count as arising naturally? I'm pretty sure we teach students to add two functions (from the reals to the reals) pointwise to get a new function, even there. Of course, on the one hand really we only ask them to deal with the countable subset of functions with a finite description, and on the other hand Abelian groups are not as interesting, but technically that defines a group with cardinality greater than the continuum. (We also define inverse functions and composition, but at first glance it seems that strictly monotone functions must have only continuum cardinality.)

Answer by Tracy Hall for Sorting a binary matrix diagonal in polynomial time while preserving rows

2010-08-13T00:10:21Z

The rows and columns of your matrix are the two sides of a bipartite graph, with the entries equal to 1 representing edges. What you are looking for is a maximal matching, for which there are many algorithms known; in particular, you can do it pretty easily in $n^3$ time using one of the methods in the link provided.

Answer by Tracy Hall for Cover time of weighted graphs

2010-08-06T11:06:26Z

A search for "algebraic connectivity" of a graph may be helpful, as well as the extensive literature on rapid mixing.

The problems mainly occur when the graph is nearly disconnected because different component-like sets have too few edges between them, or edges with weights too close to zero (which is the weight of a non-edge). If you make certain edges exponentially small, the cover time also becomes exponential.

Your adjacency matrix has Perron root and spectral radius $W$, and the usual bounds on mixing or covering time are in terms of the eigenvalue of second-highest magnitude, as a fraction of $W$. (Bipartite graphs are a special case, where $-W$ is also an eigenvalue.) The limiting distribution, in this case uniform, is the $W$ eigenvector, and is the only all-positive eigenvector. Convergence to uniform is exponential, but with base the ratio of $W$ to other eigenvalues, by the spectral decomposition theorem. Sometimes you can actually get a clue to the worst component-like pieces from the positive and negative parts of large eigenvectors.

Answer by Tracy Hall for A differential inclusion relating to the slope of a convex function

2010-08-04T18:13:01Z

Unfortunately the lemma is false. Given a candidate $C$, let $\varepsilon = 1$ and $F(t) = \ln(te^C+1)$. Then the hypotheses of Lemma B hold but the conclusion fails.

Answer by Tracy Hall for Roulette probability

2010-08-04T16:58:06Z

(It's true that this question will probably be closed soon.)

Ask yourself this question: Does the roulette ball or table have a memory? If not, then past events cannot possibly affect the next probability. "No memory", or more technically independent outcomes, is a standard hypothesis in probability problems like the one you are interested in.

The deeper question (but still not at the research level) is how statistics always seem to even out in the long term, even if there is no memory forcing them to do so. This is the content of the Central Limit Theorem of probability theory, and is closely related to the Second Law of Thermodynamics, whose rigorous treatment comes from statistical mechanics. The short answer is this: Statistics always even out in practice because in the long term there are many, many, many combinations with nearly even statistics, compared to just a handful of combinations that are greatly skewed. To be more concrete: (black, red, black, black, red, black, red, red, red) has precisely the same probability as (black, black, black, black, black, black, black, black, black), but no one ever asks about that precise first sequence; instead it gets lumped together with the 125 other sequences that have the same overall statistics, whereas all-black has no statistical compadres to share the burden of occurring more than one time in 512.

Answer by Tracy Hall for When is an algebra of commuting matrices (contained in one) generated by a single matrix?

2010-08-03T04:58:07Z

For symmetric matrices over the reals, the answer is yes: if $A$ and $B$ commute, then they can be simultaneously diagonalized. That is to say, there exists an orthogonal matrix $U$ ($U^TU = I$) such that $U^TAU$ and $U^TBU$ are both diagonal. It follows that for any diagonal matrix $D$ with distinct diagonal entries, both $A$ and $B$ are polynomials in $C = UDU^T$.

In general it is instructive, and loses no generality, to assume that $A$ is in a normal (Jordan, Smith, etc.) form. Over a field, for example, the dimension of the space of polynomials in $A$ is the same as the degree of the minimal polynomial of $A$, which is the sum, over all eigenvalues $\lambda$, of the size of the largest Jordan block for $\lambda$ in the Jordan normal form of $A$ over the algebraic closure of the field. It's not too hard to verify that every matrix commuting with $A$ is a polynomial in $A$ if and only if the minimal polynomial is the characteristic polynomial, that is if every eigenvalue has a single Jordan block (as happens automatically for example if there are $n$ distinct eigenvalues).

I can't remember the precise statement of something that surprised me, some unsolved problem related to the dimension of a commuting set in terms of Jordan block sizes. Someone please comment if you are familiar with this open problem and can state it precisely.

Answer by Tracy Hall for Eigenvalues of A+B where A is symmetric positive definite and B is diagonal

2010-08-02T15:16:43Z

The work that you have put into finding the eigenvalues of $A$ is not going to save you time, except that it does give you a bound (together with the maximum eigenvalue of $B$) for how large you have to make $\alpha$ to find the maximum eigenvalue of $\alpha I - A -B$ iteratively--and the row sums would give you a bound on that anyway. In any case finding the extremal eigenvalues of $A+B$ shouldn't be any harder than for $A$, since they are both the same size and equivalently sparse, but if you are repeating this many times with the same $A$ and different $B$ I don't see any shortcuts to iterating each one.

Answer by Tracy Hall for Math puzzles for dinner

2010-07-29T05:50:42Z

You are the captain of a team of N players, in charge of choosing a strategy that your adversary will overhear (and therefore rig the game for you to lose unless the strategy is perfect). To play the game, the adversary writes a distinct name on each player's forehead and you are brought into a situation where each of you can learn the name given to every other player, but not your own. Naturally you cannot communicate once the game has started. Each of you is blindfolded and given a single invertible glove. On a signal, each of you silently places your glove on one hand or the other. You are then lined up in alphabetical order by the names on your foreheads, all facing the same direction, and you join hands in one long chain. If any of you touches another player's glove with your bare hand the team loses, but if it is always hand-to-hand and glove-to-glove, you are victorious.

For what values of N can you give your team a winning strategy, and what is it?

Answer by Tracy Hall for Lattice Stick Number vs. Stick Number of Knot

2010-07-28T04:40:52Z

I wouldn't be surprised by something like a quadratic bound, or possibly something reasonable in terms of another complexity measure for the knot, but I see no hope for making $m$ constant. Consider the following construction: given $m$, choose some large number like $N=(10m)^6$ of points uniformly at random in the unit sphere, and connect them sequentially in a cycle with straight line segments to define a knot $K$. By construction $K$ has stick number no more than $N$, but each stick has a long narrow tunnel that it must traverse in a very precise direction, which is difficult to do with only $m$ lattice sticks. Of course any one tunnel can be made shorter and wider with an affine transformation (or any small collection of tunnels, with a piecewise affine transformation) but I am convinced (without attempting a rigorous proof) that with probability approaching $1$ a knot so constructed has a lattice stick number much higher than $mS_L(K)$.

Answer by Tracy Hall for Linear Algebra Proofs in Combinatorics?

2010-07-27T13:22:40Z

Here is an example I learned about this month: The edges of the complete graph cannot be partitioned into fewer than $n-1$ complete bipartite graphs. Apparently the only known proofs involve linear algebra.

Answer by Tracy Hall for How to generate a net on a 8-dimensional sphere

2010-07-27T12:30:55Z

If it's really important for the points to be evenly distributed, and you don't mind doing a lot of calculation to get them that way, you can start with a randomly distributed set and then iterate over the entire set repeatedly, allowing each point in turn to make whatever small adjustment improves your chosen definition of uniformity, and repeat this until the set of points converges. If you're even pickier than that, and not satisfied by just a locally optimal arrangement, the canonical next thing to try is simulated annealing.

For picking points at random, I agree with Peter Shor that taking the time to implement a one-to-one volume-preserving map from a product of intervals to a high-dimensional sphere would be much more wasteful (of time; you would learn a lot) than throwing away 98% of your random numbers. It's an interesting question, though, whether systematically chosen points in a product of intervals can be well-distributed under one of these volume-preserving (but distance-destroying) maps. The first interesting case of such a map is the axial projection from the curved surface of a cylinder of height 2 and radius 1 to the surface of the unit sphere it contains: projecting straight to the axis, one direction gets stretched out in exact counterbalance to the compression of the other direction. Call the coordinates of the cylinder surface z ∈ [$-1$, $1$] and θ ∈ [$0$, $2\pi$]. Choosing an ordinary regular rectangular grid in z and θ does terrible things to the projection. On the other hand, for any $N$, setting z_i = $(-N+2 i - 1)$/$N$ and θ_i = $2\pi (\phi i$ mod $1$), where $\phi$ is the golden mean, actually gives a very nice distribution of points after projection. It's possible that in any dimension there is such a lattice in the cube that projects nicely, for any N, to the sphere.

Answer by Tracy Hall for How to prove that a set of facets are all the facets of a convex polytope.

2010-07-27T11:15:54Z

The unhelpful suggestion is to perform the complete dual cone calculation (using available software) and then see if the answer matches your initial guess. Unfortunately, my pessimistic intuition is that in the general case, you cannot expect to do much better than this, even in the case where the initial guess is correct. You might get lucky optimizing in random directions in the dual space and find a hyperplane you missed, but in high dimensions there are too many directions and things are just subtle and elusive.

Three things that make the problem easier:

If the polytope P is known to be simple,
if the intersection of half-spaces Q is known to be simplicial, or
if the dimension is small.

The first case was covered by the answer given by Hugh Thomas: just verify that each vertex is a vertex of Q. In the second case the same verification suffices by duality, where the roles of facet-defining hyperplanes and extreme points (genuine vertices) are exchanged. In the third case you can construct the entire face lattice inductively. The hard case is when the dimension is high, which means that even if there are relatively few vertices and facets, the number of intermediate faces can be unmanageable.

Unfortunately it is not even easy in general to verify whether one of the first two conditions holds. An instructive example is the case where Q is a cube and P is obtained by deleting a pair of opposite vertices from Q (giving a flattened octahedron). In this case every vertex of P is a vertex of Q, every facet of Q restricts to a facet of P, P looks simple when checked by Q, and Q looks simplicial when checked by P, but they are not equal, P is not simple, and Q is not simplicial. (Fortunately, the dimension is low!)

Having expressed pessimism about there being any good solution, let me at least offer a bad one—likely to run much too slowly on any interesting example—that essentially does construct the face lattice (inefficiently) as suggested for low dimensions. We assume that it has already been verified (not difficult) that every vertex defining P does lie within Q (and therefore that every hyperplane defining Q lies outside the interior of P) but for the purposes of induction we will not insist that every every "vertex" is an extreme point of P or that every hyperplane gives a facet of Q; when we encounter such redundancies we will silently discard them for the purposes of that stage of the algorithm. (On the other hand, we do require that vertices are distinct and hyperplanes are distinct, and we delete repetitions before doing anything else.) What we will verify instead is that every vertex of Q is in the list for P, and that every facet of P comes from the list of hyperplanes for Q. If that ever fails, we report it and quit.

Firstly, every polygon is both simple and simplicial, which makes the case of two dimensions easy: Recursively eliminate any vertex of P that does not lie on two lines of Q, or any line of Q that does not contain two vertices of P. If anything is left when you are done (again, assuming P was contained in Q), they were always equal.

Now, suppose you have a solution in dimension d with which you are happy. In dimension $d+1$ , you do as follows: For each hyperplane H in turn, identify the set of vertices incident to it, and verify that they span it affinely. (Otherwise H is redundant, so just continue on to the next hyperplane.) The convex hull of these vertices defines a polytope P' of dimension d within H, and the (largely redundant) intersection of all other halfspaces with H defines a polytope Q' which contains P'. The polytopes P and Q are equal if and only if P' and Q' are equal for every non-redundant hyperplane H.

Lather, rinse, repeat.

Comment by Tracy Hall

2011-04-04T04:02:56Z

Is it even clear that this is a group? If the order of $(lc_i lc_j)$ depends on whether $i$ and $j$ are adjacent, then it changes depending on the action of other generators. How precisely do you decide when a product of generators is trivial, if it sometimes results in the starting graph and sometimes doesn't?

Comment by Tracy Hall

2011-03-29T01:15:11Z

I guess a simpler title would have been "Standard reference for the Hopf fibration".

Comment by Tracy Hall

2011-03-16T17:53:21Z

As answered below: No, unless $S$ is star-shaped around some point of its interior. On the other hand, it seems like this should always be possible if you just ask for $S$ to be contained in an $\epsilon$-neighborhood of the region bounded by $P$.

Comment by Tracy Hall

2011-03-15T22:50:25Z

The obvious first thing to try is a rational pyritohedron, but that fails: at one of the eight vertices with threefold rotational symmetry, the adjacent edges lie along directions which are the even permutations of $(p^2, -pq, q^2)$ for positive coprime integers $p \gt q$, giving $(p^3+q^3)^2$ for a determinant, rather than $1$.

Comment by Tracy Hall

2011-02-20T14:06:28Z

Assume your surfaces are smooth, of codimension one in a Euclidean ambient space. At the point of tangency, by the implicit function theorem the surfaces are locally graphs of two functions $f \le g$ with gradients both vanishing at the origin. If the Hessian matrix of $f$ is positive definite, then so is the Hessian matrix of $g$. That is all you need.

Comment by Tracy Hall

2011-02-19T05:10:49Z

That's a nice way to precisely (up to an additive constant depending on the model of computation) state Occam's razor. (Yes, I realize that I have just perpetrated the mother of all split infinitives.)

Comment by Tracy Hall

2011-02-16T19:27:01Z

Without mentioning any $x_i$, you can just say that $S_i$ is a sequence of sets in $\mathcal C$ whose series of unions is strictly increasing (starting with the empty union; i.e. $S_1$ is non-empty) or whose series of intersections is strictly decreasing (starting with the empty intersection $X$; i.e. $S_1$ is not all of $X$). If you make a $\{0,1\}$ incidence matrix $M$ with columns indexed by $X$ and rows indexed by $\mathcal C$, you are asking for the size of the largest square submatrix in $M$ or its complement which is permutation equivalent to lower triangular invertible.

Comment by Tracy Hall

2011-02-16T02:00:10Z

I did check your nice explicit example, and it works, so I was wrong: you have given an example with strictly fewer than $m+n-d$ vertices in common when $m=3$, $n=2$, and $d=4$. I wonder what the correct bound is.

Comment by Tracy Hall

2011-02-10T20:55:43Z

@Igor: Apply it to $tI -A-D$ for large enough positive $t$, such as $t=\mathrm{tr}(A)+K$.

Comment by Tracy Hall

2011-02-10T20:36:29Z

Wrong on three counts: The smallest eigenvalue is real, by Perron-Frobenius. The convention chosen in the question has row sum zero, so actually the all-ones vector is a right eigenvector. Choosing equal diagonal entries is not always the best you can do, as you can see by the example $A = \left[\begin{array}{rr}1 & -1\\\\ 0 & 0 \end{array}\right]$ and $K=1$.

Comment by Tracy Hall

2011-02-10T01:30:35Z

@Douglas Zare: Yes, in fact this is exactly how the experiment was run: the proportion of convex positions, divided by 3. The name of Sylvester's problem for the same question (with uniform measure) in a convex region of the plane is helpful. Apparently the problem is usually stated as the probability that the four points are $\textit{not}$ in convex position, so the crossing probability would be $\frac{1-p}3$ where $p$ is the Sylvester's problem for the sphere projection measure in a circle. (Conjecturally $p=\frac14$, with non-convex as likely as each of the 3 ways of crossing.)

Comment by Tracy Hall

2011-02-05T21:04:03Z

The first 4-letter word in the boustrophedonic dictionary is "waxy", since the only things that would beat it are $\{a < x < y < z\}$ and $\{a < w < x < z\}$, neither of which has any anagrams.

Comment by Tracy Hall

2011-02-04T03:24:13Z

Does running LaTeX count as an important operation?

Comment by Tracy Hall

2011-02-04T01:28:05Z

It's not on this page, but found in the top answer to math.stackexchange.com/questions/19386/… that Willie Wong linked to in a comment to the question.

Comment by Tracy Hall

2011-02-04T01:16:37Z

Agreed, this is certainly not a research-level question, and closing it was the correct response. Hoping to strike a balance between friendliness and the risk of encouraging inappropriate questions, I will pose a question to the original poster: What do you get when you add together an odd number of odd numbers?