Applied Math Colloquium

This talk will present an elementary introduction to the Galois theory of linear difference equations, motivate and give a formal definition of solving linear difference equations in finite terms and give an exposition of an algorithm that finds those solutions that can be expressed in finite terms.

Let A be a collection of hyperplanes in a Euclidean space. This talk concerns a family of random walks on the regions of A, i.e., on the connected components left when the hyperplanes are removed from the Euclidean space. These random walks, which are called BHR shuffles, have applications to dynamic file maintenance, modeling of changes to genetic material, as well as to various abstract mathematical problems. We will discuss applications as well as properties of these random walks. In particular, we will give a complete spectral resolution of the transition matrices and use that information to bound convergence rates. We will discuss results about the stable distribution.

One of the goals of Numerical Linear Algebra is the accurate computation of eigenvalues of matrices. This is quite successful in the symmetric case but the situation is different for non-self adjoint matrices. These arise in the discretisation of engineering or physical problems involving friction or dissipation, and it is an important problem to compute their eigenvalues.

It has been observed long time ago that the obstruction to accurately computing eigenvalues of nonselfadjoint matrices is inherent in the problem, and cannot be circumvented by using more powerful computers. The basic idea is that algorithms for locating the eigenvalues may also find some 'false eigenvalues.'

These false eigenvalues also explain one of the most surprising phenomena in linear PDEs, namely the fact (discovered by Hans Lewy in 1957, in Berkeley) that one cannot always locally solve the PDE $Pu = f$ . Local solvability is always possible if $P$ is self-adjoint or has constant coefficients, but non-self-adjointness can destroy that property: Lewy's example was a simple vector-field with complex, non-constant coefficients arising in the study of several complex variables.

Almost immediately after that discovery, Hormander provided an explanation of Lewy's example showing that almost all non-self-adjoint operators are not locally solvable. That was done by considering the essentially dual problem of existence of non-propagating singularities. I will give an elementary quantum mechanical interpretation of these issues of local solvability and non-propagation of singularities in terms of creation and annihilation operators.

Finally, I will explain how the non-propagating singularities are the source of (at least some of) the computational problems in finding eigenvalues of non-self adjoint matrices arising in discretisation of high energy or semi-classical operators.

Toeplitz matrices enjoy the dual virtues of beauty and ubiquity. We begin this talk by surveying some of the interesting spectral properties of such matrices, emphasizing the distinctions between infinite-dimensional Toeplitz matrices and the large-dimensional limit of the corresponding finite matrices.

These basic results utilize the algebraic Toeplitz structure, but in many applications, one is forced to spoil this structure with some perturbations (e.g., by imposing boundary conditions upon a finite difference discretization of an initial-boundary value problem). How do such perturbations affect the eigenvalues?

This talk will address this question for "localized" perturbations, i.e., perturbations that are restricted to a single entry, or a block of entries whose size remains fixed as the matrix dimension grows. One can show, for a broad class of matrices, that sufficiently small perturbations fail to alter the spectrum, though the spectrum is exponentially sensitive to other kinds of perturbations. For larger real single-entry perturbations, one observes the perturbed eigenvalues trace out curves in the complex plane. We'll show a number of illustrations of this phenomenon for tridiagonal Toeplitz matrices, which arise in many applications.

This talk describes collaborative work with Albrecht Boettcher, Marko Lindner, and Viatcheslav Sokolov of TU Chemnitz.

Many complex networks in nature exhibit two properties that are seemingly at odds. They are clustered---neighbors of neighbors are very likely to be neighbors---and they are small worlds---any two nodes can typically be connected by a relatively short path. Watts and Strogatz [Nature, Vol. 393, 1998] referred to this as the small world phenomenon and proposed a network model, in the form of a partially random graph, that was shown through simulation to capture the two properties. The model incorporates a parameter that interpolates between fully local and fully global regimes. As the parameter is varied the small world property is roused before the clustering property is lost.

I will show that the small world phenomenon observed by Watts and Strogatz for randomized networks also arises in the context of Markov chains. The Markov chain model interpolates between local and global periodic, one-dimensional, random walks. The small world property may be measured by expressing the average mean hitting time in terms of the average number of shortcuts per random walk. The calculation uses ideas from numerical analysis and provides rigorous asymptotic error estimates. The resulting cutoff diagram agrees closely with that arising from the mean-field network theory of Newman, Moore and Watts [Phys. Rev. Lett., Vol. 84, 2000].

We consider a continuous space that models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature (i.e., it is CAT(0) in the sense of Gromov), giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or otherwise doing statistical analyses on sets of trees on a common set of species.

This geometric model of tree space provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.

This is joint work with Susan Holmes and Karen Vogtmann.

Consider a shallow layer of high Prandtl number fluid in a large aspect ratio elliptical container with heated sidewalls. The Rayleigh number is in the range for which rolls/stripes are the stable local planform. The heated sidewalls mean that the rolls next to the boundary will be parallel to it. The challenge is to fill in the rest of the pattern.

This problem is one of the simpler examples of natural patterns, namely patterns in translationally and rotationally invariant two-dimensional systems with preferred wavelength but orientational degeneracy. The resulting textures are complicated, consisting of a mosaic of patches of rolls with almost constant orientation mediated by line and point defects.

The goal of theory is to describe such patterns and their defects from a macroscopic viewpoint. Using the example of convection in an elliptical container, we will see how the theory gives a fairly accurate prediction of the stationary patterns which are realized and how it makes contact with and extends the class of minimization problems associated with harmonic maps.

In 1964, state and local legislative bodies were, for the first time, required by law to meet the "one person, one vote" standard. Rather than reapportion themselves, a number of such bodies introduced alternative methods of representation, such as allowing certain legislator's votes to carry more weight than others, or to have multiple representatives from the same district. The question then arose, was this sufficient to meet the constitutional requirement "one person, one vote." And what does "one person one vote" even mean in this context?

To answer these questions, techniques from cooperative game theory are brought to bear, principally the Banzhaf index, which measures voting power in these voting system. I will introduce these ideas and show what they tell us about a mathematical interpretation of "one person, one vote."

These techniques have rather broad application, including to the Electoral College, and the Supreme Court, itself. In addition I will describe how the mathematical arguments fared in the courts. A number of open problems, both mathematical and jurisprudential, will be discussed, as well.

Let the edges of the complete graph Kn be assigned independent uniform [0,1] random edge weights. Let TSP and 2FAC be the weights of the minimum length traveling salesman tour and minimum weight 2-factor respectively. We show that with high probability |TSP-2FAC|=o(1). The proof is via by the analysis of a polynomial time algorithm that finds a tour only a little longer than 2FAC.

Random walks have intrigued us for a long time. In recent years, they have also played a crucial role in the discovery of polynomial-time algorithms. The first part of the talk will illustrate this using random walks in Euclidean space, showing how they lead to a simple algorithm for the fundamental problem of convex optimization. The second part of the talk will focus on a particularly engaging way to walk randomly --- called "hit-and-run" --- and show how it solves the problem of sampling from a log-concave distribution. Along the way, the geometry of these walks will be highlighted.