Summer Matrix Analysis REU
For Summer 2009
In Matrix Analysis and its Applications
at William & Mary
I. PROGRAM SUMMARY
The Mathematics Department of the College of William and Mary will run an NSF-funded REU program on "Matrix Analysis and its Applications ," in the summer of 2009. This represents more than 20 years of REU at William and Mary, and the program will be run by Professor Charles R. Johnson who has been a fixture throughout its history.
Matrix analysis is a more advanced version of linear algebra. It is deeply related to all parts of mathematics and most areas to which mathematics is applied. See the Cambridge University Press text/ monograph "Matrix Analysis" by R. Horn and Johnson or look at Johnson’s list of more than 300 publications on MathSciNet to get a feel for the subject.
The 2009 program will begin at 9:00 am June 8 (with the 7th as arrival day) and run throughout July 31 (with August 1 as departure date).
Eight students will be competitively selected to participate in the program. NSF requires that funded participants be US citizens or permanent residents who have begun undergraduate study prior to the program and have not yet graduated by the September following. Each eligible participant will receive $2,900 toward pay and expenses, and free housing in one of the College’s residence halls. In addition, in case of extraordinary merit, foreign or younger participants will be considered and, if admitted, given free on-campus housing in the same dormitory.
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. Early 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 20 years, matrix analysis has proved to be an ideal theme for undergraduate research at William and Mary because it
- offers a wide range of attractive projects at many levels of complexity,
- has research problems that can be explored by undergraduates, and
- has linkages with other mathematical disciplines, e.g., graph theory, combinatorics, operator theory, statistics, geometry, and mathematical biology.
Previous summer's programs have led to student presentations at national conferences, and more than 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 list of some topics studied by students between 1998 and 2008 is given later. To insure currency, the topics to be offered in summer 2009 will be chosen shortly before the program begins. They will offer wide variety, depth and novelty.
II. HOW AND WHEN TO APPLY
There will be no special application form for our REU program. Instead, to apply for the summer 2009 program, please prepare a letter listing the following information:
- 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 2009, 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
Mathematics Department REU Program
College of William and Mary
P.O. Box 8795
Williamsburg, VA 23187-8795.
E-mail letters and applications are welcome; they should be sent to Ms Williamson at [mkwill]
Applications and supporting letters should arrive no later than March 4, 2009. Review of applications and possible offers may begin earlier.
If you have questions or need more information, please contact the Program Assistant, Shahla Nasserasr, by mail, telephone (757-221-4627), or e-mail ([naserasr]).
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.
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. In addition, part of one day will be devoted to discussion of the graduate application and admissions process. In the past a graduate admissions officer from a major mathematics department has been a guest for this discussion.
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 2009 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 shortly before the program begins.
1. Sign pattern matrix equations
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 = | + - | 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.
2. Determinental probabilities associated with sign patterns
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.
3. Linear preserver problems
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.
4. Isometry problems
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.
5. Determinants of special matrices
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:
i) every entry in the matrix is either 0 or 1, and
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.)
6. Numerical ranges of matrices
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.
7. Matrix semipositivity and generalizations
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 2008
During the summers between 1998 and 2008, 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.
- Totally positive pattern completions
- Nonzero patterns in orthogonal matrices
- Almost positive semidefinite matrices.
- Semipositive and minimally semipositive completions
- The Hadamard core for totally non-negative matrices
- Ratios of principal minors of totally non-negative matrices
- Completely positive matrices and their graphs
- Eigenvalues of words in two positive definite letters
- Critical points of the SSTRESS criterion in metric multidimensional scaling
- Coxeter graphs, groups, and Weyl chambers
- Statistical analysis of the determinants of certain sign pattern matrices
- A generalization of the classical numerical range
- Eigenvalues and boundary curvature of the numerical range
- Reflections on Coxeter groups
- Symmetric sign patterns allowing symmetric and skew-symmetric matrices with given row and column sums
- Spectral ranges of sign pattern
- On the diagonal scaling of squared distance matrices to doubly stochastic matrices
- The list of eigenvalue multiplicities for an Hermitian matrix whose graph is a tree
- Numerical ranges of tridiagonal matrices
- Central groupoids, central digraphs, and zero-one matrices satisfying $A^2 = J$.
- Absolutely flat idempotent matrices
- Positive definite extension problems for structured matrices
- Divisor tournament matrices
- Ray non-singularity of matrices
- Relations between matrix theory and function theory
- Commutativity of matrix patterns
- Determinental inequalities in matrix classes.
