I ran across an interesting problem recently while studying some recursive algorithms: the N Queens Problem. Given an $N$-by-$N$ chessboard, the problem is to determine the number of configurations of $N$ queens on the chessboard that do not attack each other. That is, for a valid configuration (solution) no two queens share the same row (rank), column (file), or diagonal.

For $N = 1$ there is a trivial solution, but none exist for $N = 2$ or $3$. $N = 4$ has two solutions:

And they grow quickly from there. For $N = 8$ there are $92$ solutions (many related by symmetry) -- here's one:

and for $N = 15$ there are $2279184$ solutions. It appears the number of solutions has not been computed for more than $N = 26$, where there are more than $22$ quadrillion solutions! No general formula for the number solutions is known, nor is the asymptotic behavior.

Read more…

If you've ever flown between the East coast and West coast, you know the feeling: going west takes soooo much longer! The difference in flight times is about an hour, which can be painful if it's tacked onto the end of a long trip.

Let's run some basic numbers. Suppose we between SFO and BOS on a 737, which has a cruising speed of $v_{\rm cruise} \sim 500$ mph. It's $d \sim 2700$ miles between the two cities, so with no wind the flight time would be $t_{\rm flight} = $ 5 hours and 24 minutes. If it takes $\Delta t = 1$ hour longer for the eastward trip, then the average jet stream velocity, $\bar{v}$, is given by the relation

$$ \begin{align} &\frac{d}{v_{\rm cruise} - \bar{v}} - \frac{d}{v_{\rm cruise} + \bar{v}} = \Delta t \\ & \qquad \Rightarrow \; \bar{v} = \frac{d}{\Delta t} \Biggl( \sqrt{1 + \frac{\Delta t^2 v_{\rm cruise}^2}{d^2} } - 1 \Biggr) \approx \frac{v_{\rm cruise} \Delta t}{2d} \, v_{\rm cruise} = \frac{\frac12 \Delta t}{t_{\rm flight}} v_{\rm cruise}, \end{align} $$

so that in this case $\bar{v} \approx 46 \text{ mph}$. This is the average jet stream velocity over the flight path (as experienced by the flight), but what if we want to get finer grained than this? Can we use this basic idea to build a map of the jet stream across the US?

It turns out, the answer is yes! And we can do so via a nice linear algebra problem, mixed in with some spherical geometry. Here's how it goes.

Read more…

Particle physicists like to represent things with diagrams. The popular example is Feynman diagrams, and there are rules to draw and evaluate diagrams for different scattering processes. Diagrams also arise in the large scale structure of cosmology, where matter fluctuations can be described using perturbation theory (see this Wikipedia article).

Diagrams for cosmological perturbation theory (specifically large scale structure): they are basically functions of directed graphs. That is:

• The value of the diagram is the product of weights of edges and vertices.
• Each edge in the diagram is associated with a momentum flow, which enters through the vertices.
• The weight of and edge is a scalar function of the momentum flow in the edge.
• The weight of a vertex is a scalar function of the momentum flow in the edges connecting to the vertex.

These diagrams have two types of symmetry factors:

• The internal symmetry factor $-$ the number of topologically-invariant permutations of the edges of the graph.
• The external symmetry factor $-$ if the vertices are labeled, the number of permutations of vertices that produce topologically distinct graphs.

Read more…

Interpolation is a great technique to convert discrete data into continuous data. It's useful if you want to sample the domain at points other than the original data, or make continuous plots, or do operations convenient on a function (like integration or differentiation). I'll talk about two types of interpolation of 1-D functions: the standard cubic spline and the less-known Steffen interpolation. Along the way we'll encounter interesting relations in linear algebra and for the Lucas sequence (a generalization of the Fibonacci sequence).

Read more…

This blog is a place for me to collect some of the explorations into different topics that I run across in my work, side projects, or just everyday life.

When I'm working on a project I'll often run across a mathematical technique that I want to understand better. A great time for learning something new! Or sometimes I'll use this blog to describe a project, or some key part, that I'm working on.

If you've found your way here for something specific, or just to poke around, I hope you find it useful!