I. PROGRAM SUMMARY
The Mathematics Department of the College of William and Mary plans to run an NSF-funded REU program in the summer of 2006. The theme of our REU program will be "Matrix Analysis and its Applications."
Matrix analysis is a more advanced version of the linear algebra course that mathematics majors typically take in their first or second year of college. Examples of matrix analysis problems that are suitable for an REU program are outlined below.
The 2006 program will begin on June 5 and end on July 28, 2006.
Up to eight students will be selected on a competitive basis to participate in the program. NSF rules require that participants be citizens or permanent residents of the United States who have not (and will not) receive an undergraduate degree prior to September, 2006. Each student will receive a total of $2,600 and free housing in one of the College's residence halls.
The first week of the program will contain a series of background seminars to establish a common language for the entire program and to introduce students to eight or ten open and accessible research problem areas. At the end of the first week, each student will select a topic among the many presented. Students may work in small teams, or in a 1-1 fashion, with their research mentors.
To help students explore some of their research problems, they will be introduced to mathematical software such as MAPLE, MATLAB, and LATEX that are available to REU students on the department's Linux workstations and Windows labs.
Over the last fifteen years, matrix analysis has proved to be an ideal theme for undergraduate research at William and Mary because it
Previous summer's programs have led to student presentations at national conferences, and about 50% of student participants have co-authored papers that have appeared in refereed professional journals such as "Linear Algebra and its Applications," and "Linear and Multilinear Algebra." A listing of topics studied by students between 1998 and 2005, as well as several broad topics that might be offered in the summer of 2006, is given below. So is a listing of refereed papers that have grown out of summer REU programs at William and Mary.
II. HOW AND WHEN TO APPLY
There will be no special application form for our REU program. Instead, to apply for the summer 2006 program, please prepare a letter listing the following information:
Please arrange for all of the above materials to be sent to
- Full name, college address and phone, and home address and phone;
- e-mail address;
- Social security number and birth date;
- Citizenship (Are you a citizen or permanent resident of the United States or one of its possessions?);
- Current college or university, current undergraduate status (freshman, sophomore,...), academic major, and expected date of graduation;
- Minority status (optional): Woman, Native American, African-American, Hispanic, Pacific Islander);
- A list of college mathematics courses completed, including textbook titles and authors, and the grades received;
- A list of mathematics courses that will be completed before the summer of 2006, including textbook titles;
- Names and titles of two people who will be sending letters of recommendation on your behalf. (Choose mathematics instructors who are well-qualified to comment on your mathematical ability and experience.);
- A personal statement about your own interest in mathematics and your own goals for the REU program.
Ms Marianna Williamson
Applications and supporting letters should arrive no later than March 7, 2006. Review of applications and possible offers may begin earlier.
If you have questions or need more information, please contact the Program Director, Professor Charles Johnson, by mail, telephone (757-221-2014), or e-mail (crjohnso@math.wm.edu).
III. THEME AND GOALS OF OUR PROGRAM
The William and Mary REU program's objective is to provide talented undergraduates with the experience of how research in mathematics is done, something that is quite different from the way in which undergraduate mathematics is usually taught and learned.
Close contact between REU students and program faculty is the key to our past successes. Our plan is that the relationship between REU students and faculty mentors should be a smaller-scale version of the relationship between Ph.D. students and their thesis advisors. Our experience has shown the importance of daily faculty guidance in undergraduate research. During the REU program, each student's faculty advisor will attempt to pose a progressive series of problems that are of increasing difficulty and generality and that lead towards the overall goal of the student's program. This strategy allows for positive reinforcement of the student as he or she advances in incremental steps to more difficult and unknown territory.
In addition to the interaction of students with their advisors about their research problems, a number of other activities are planned to expand the undergraduates' appreciation of mathematics, its beauty, and its elegance and interconnections. Periodic lectures will bring the participants in contact with a number of visiting researchers and enable students to witness the excitement of research at close hand. We also anticipate having speakers from other departments at William and Mary and from nearby academic institutions and government facilities who will report on recent progress in a variety of modern areas that use matrix analysis in an important way: cryptosystems, linear control, computational geometry, robotics, mathematical biology, scientific computation, econometrics, and ecological models are a few examples of possible topics.
IV. A SAMPLER OF PROBLEMS
What follows is an overview of several broad mathematical themes that have run through previous years' REU programs. We suspect that faculty members will propose related problems for the 2006 REU program, and probably many others as well, and that next summer's REU students will build upon the discoveries of REU students in previous summers. However we will not make final decisions about next summer's problems until April or May.
A "sign pattern" is a matrix each of whose entries is +, -, or 0. Associated with an m-by-n sign pattern A is the set Q(A) of all matrices whose signs conform to the pattern A. We say that sign pattern A requires (allows) matrix property P if H has property P whenever H is in Q(A) (respectively, if there is a H in Q(A) with property P). "Qualitative matrix theory", with roots in economics, biology, chemistry, and computer science, seeks to characterize those sign patterns that require or allow a given property.
We say that the triple of sign patterns A (m-by-p), B (p-by-n) and C (m-by-n) is globally consistent if there exist H in Q(A), J in Q(B), and K in Q(C) such that HJ=K.
A fundamental and large-scale question is: Which triples of sign patterns are globally consistent? Many problems are special cases and there are many interesting variants; results on any portion of the large-scale problem would be of interest. An obvious necessary condition is the following. Say that A, B and C, as above, are locally consistent if for each pair i,j with i < m+1 and j < n+1, the i-th row of A, the j-th column of B and the i,j entry of C are globally consistent. (It is quite easy to determine this.) Since local consistency is obviously necessary for global consistency, a good way to view the large problem is the following: which locally consistent triples are not globally consistent? To see that this is an interesting question, you may wish to verify that the triple
A = | + - | B = | + + | C = | + - |
| - + |, | + + |, | + - |,
is locally, but not globally, consistent. In fact, for m=n=p=2, this is the only such example up to obvious symmetries.
Definitions and notation remain as above. It is well understood for which sign patterns A it is true that "B in Q(A) implies det(B)=0." It is also known for which sign patterns A it is true that "B in Q(A) implies det(B) is not 0" (though the computational complexity of deciding this question is open). In the latter case, the sign of det(B) (+ or -) is determined by A. In all other cases, some matrices in Q(A) will have positive determinant and some negative. The following question has recently arisen: How may one compute the probability that det(B) will be positive for B in Q(A)? To make this precise, assume that positive (resp. negative) entries are chosen uniformly and independently from (0,1] (resp. [-1,0)). Several particular questions may be raised about the relation between this probability and A. This problem fits into the general area of qualitative matrix theory, an active area of research, and there are many more open questions about the relation between sign patterns and matrix properties.
Ecology is concerned with understanding how the distribution and abundance of populations change over time. When used properly, mathematical models act as a powerful and relatively inexpensive virtual laboratory in which one can conduct thought and computational experiments that tease apart competing ecological hypotheses. Reflecting the diversity of mathematics, modelling approaches in ecology range from difference equations to cellular automata to partial differential equations to stochastic processes. For several of these approaches (e.g. difference equations, ordinary differential equations, branching processes) rely on tools from linear algebra. Two areas of particular interest are random matrix products and the use of eigenvalues to study species extinction.
Random products of matrices
The goal of this project is to understand the spectral properties of random products of matrices. Imagine two matrices, A H and A T , representing population growth for two different sets of environmental conditions. Every day or week or year, a flip of the coin determines determines the environmental condition. The long-term population growth is determined by the random product of the matrices A H and A T corresponding to the sequence of observed Heads and Tails. Associated with this random product is a Lyapunov number k, which is analogous to the dominant eigenvalue of a matrix. The importance of this number is that the population tends (asymptotically) to grow like k^n. By understanding how k depends on the matrices and on the form of the ``coin flipping'' it is possible to address questions such as ``under what conditions does dispersal evolve for populations living in patchy environments?'' and ``how do spatial-temporal correlations in patchy environments influence population persistence?''
Extinction and eigenvectors
The goal of this project is understanding quasi-stationary distributions and absorbtion likelihoods for (non-linear) branching processes. Branching processes are stochastic models that explicitly account for finite population sizes and the underlying uncertainty this discreteness generates. For closed systems (e.g. no immigration), these models predict that the populations eventually go extinct. Thus the questions of interest are: How long before extinction occurs? If the time to extinction is very long, what is the behavior of the system on the event of non-extinction? Answering these question reduces to inverting and finding dominant eigenvectors of appropriate matrices. By understanding these inversions and dominant eigenvectors it is possible to address various questions in conservation biology such as ``how do species interactions influence population viability?''
Linear preserver problems are an active research area in matrix theory. These problems concern the structure of linear transformations on matrix spaces that preserve some special properties. For example, it is easy to check that if M and N are square matrices such that det(MN) = 1, then the transformation defined by T(A) = MAN satisfies "det(T(A)) = det(A) for all A." The transformation defined by T(A) = MA'N (where A' denotes the transpose of A) also satisfies "det(T(A)) = det(A) for all A." It is somewhat surprising that the converse of this statement is also true, namely, if T is a linear transformation on square matrices such that det(T(A)) = det(A) for all A, then T must be one of the two forms described above. One may study transformations preserving other properties such as rank, invertibility, etc. and obtain similar results.
Let V be a normed vector space, i.e., a vector space equipped with a norm (length) function. For example, the Euclidean norm for R^n (defined by ||x|| = (x'x)^{1/2}) is one possible example. Starting with a given norm, it is of interest to characterize those linear transformations T from V to V such that ||T(v)|| = ||v|| for all v in V. Such a T is called an isometry for ||.||. For example, T is an isometry for the Euclidean norm on R^n if and only if T is orthogonal, i.e., T'T = I. But there are also other important norms on V and it is interesting to study isometries of V with such norms.
While the study of determinants has a long history, there are still many interesting unsolved problems. Here are two examples.
a) For fixed values of n > k > 1, consider the class of all n by n matrices satisfying:
ii) the sum of every row is k, and
iii) the sum of every column is k.
What are the possible determinant values for such matrices? What is the largest possible determinant value of such a matrix? Bounds are known, and complete solutions are known for special values of $n$ and $k$, but the general case is open.
b) Consider a real symmetric matrix A with singular values a_1, ..., a_n, and a real skew-symmetric matrix B with singular values b_1,..., b_n. What are the possible determinant values of A+B? (The singular values of X are the nonnegative square roots of the eigenvalues of X'X.)
Given a complex matrix A, the numerical range of A is the set W(A) = { x*Ax: x in C^n, x*x = 1}. Clearly, A determines W(A), but the geometry of W(A) is not yet understood. It is known that W(A) is a convex set that contains all of the eigenvalues of A, but W(A) is usually much bigger than the convex hull of those eigenvalues. For example, if A is a 2 by 2 matrix, then W(A) is an ellipse with the eigenvalues of A as foci, and the geometric shape of W(A) for a 3 by 3 matrix has also been described. An open problem is to describe the possible geometric shapes of W(A) for matrices of higher dimension, at least in some particular cases.
What does the set W(A) tell us about A? Suppose we do not have full information about A, but only have W(A). It turns out that we can still get important information about A. For example, W(A) = {z} if and only if A = zI, and W(A) is a subset of real line if and only if A is hermitian. An interesting problem is to determine the relationships between properties of the subset W(A) of C^n and properties of A.
We say that an m-by-n matrix B is semipositive provided there is an entry-wise nonnegative n-vector x (i.e., every entry of x is greater than or equal to zero) such that the m-vector Bx is entry-wise positive. Such matrices arise in the study of convergence of matrix sets and we know that a certain subclass of the semipositive matrices, namely the class of minimally semipositive matrices, is particularly important. A matrix B is minimally semipositive provided B is semipositive and no matrix obtained from B by deleting one or more columns is semipositive. It turns out that when B is square, B is minimally semipositive if and only if B is invertible and its inverse has only nonnegative entries. This generalizes to a slightly more complicated statement in the case that B is not square.
Although the class of minimally semipositive matrices has been studied extensively, many questions remain that form appropriate REU projects. Some examples are:
a) Completion problems: Given a "partial matrix", in which some entries are specified and others remain to be determined, under what circumstances can the unspecified entries be chosen so that the resulting matrix is semipositive? or minimally semipositive? The answer is fairly easy for the semipositive case, but is not known for minimally semipositive matrices.
b) Detecting semipositivity: Known results suggest an algorithm for determining whether or not a given matrix is semipositive, but the algorithm has not yet been investigated carefully.
c) Generalizations: A number of generalizations of semipositivity can be suggested. The nonnegative vectors in R^n form a "cone" in R^n whose "interior" is the set of positive vectors. We might replace R^n and R^m with arbitrary vector spaces, replace the nonnegative and positive vectors with arbitrary "cones" and their "interiors", and see what results on semipositivity and minimal semipositivity can be carried over to this more general setting. For example, is there a condition for minimal semipositivity analogous to the inverse nonnegativity mentioned above?
V. REU student topics 1998 to 2005
During the summers between 1998 and 2005, REU students in the Matrix Analysis and Applications program wrote reports on the following topics. Some of these reports are now being revised for submission to journals. Our REU program took a sabatical in the summer of 2001 -- consequently there are no entries for last year.
VI. Publications by REU students at William and Mary
For a list of publications involving William and Mary faculty and their REU students, please go to
Publications with undergraduates
In addition to the articles in that listing, perhaps a dozen more articles are at various states of preparation and review by journals.