menu
William and Mary
search

Summer Matrix Analysis REU

For Summer 2014 (Subsequent years will be similar)
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 2014. This represents more than 25 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.  See his article "Research with Pre-Mathematicians" in the AMS volume Proc. of the Conf. on Promoting Undergraduate Research in Mathematics, 2007, for some background.

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 nearly 400 publications on MathSciNet to get a feel for the subject.

The 2014 program will begin at 9:00 on June 2 (arrival by June 1) and run through July 25 (with July 26 as departure date).

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 $3,000 toward pay and expenses, plus 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.  Professor Johnson will be involved in many projects.

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 25 years, matrix analysis has proved to be an ideal theme for undergraduate research at William and Mary because it

  1. offers a wide range of attractive projects at many levels of complexity,
  2. has research problems that can be explored by undergraduates, and
  3. has linkages with other mathematical disciplines, e.g., graph theory, combinatorics, operator theory, statistics, geometry, mathematical biology, and algebraic geometry, etc.

Previous summer's programs have led to student presentations at national conferences, and more than half 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," and Proc. AMS.  A list of some topics studied by students between 1998 and 2009 is given later. To insure currency, the topics to be offered in summer 2013 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 2013 program, please prepare a letter listing the following information:

  1. Full name, college address and phone, and home address and phone;
  2. e-mail address;
  3. Social security number (optional) and birth date;
  4. Citizenship (Are you a citizen or permanent resident of the United States or one of its possessions?);
  5. Current college or university, current undergraduate status (freshman, sophomore,...), academic major, and expected date of graduation;
  6. Minority status (optional): Woman, Native American, African-American, Hispanic, Pacific Islander;
  7. A list of college mathematics courses completed, including textbook titles and authors, and the grades received;
  8. A list of mathematics courses that will be completed before the summer of 2014, including textbook titles;
  9. 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.);
  10. A personal statement about your own interest in mathematics and your own goals for the REU program.
Please arrange for all of the above materials to be sent to

Ms E R Leland

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 ER  at erlela@wm.edu  Applications and supporting letters should arrive no later than March 3, 2014. Review of applications and possible offers may begin earlier.

 

Charles Johnson:  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.

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 2013 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 2013

During the summers between 1998 and 2013, REU students in the Matrix Analysis and Applications program wrote reports on the following topics. Many of these reports resulted in publications in established journals or are now being revised for submission to journals.

  1. Totally positive pattern completions
  2. Nonzero patterns in orthogonal matrices
  3. Almost positive semidefinite matrices.
  4. Semipositive and minimally semipositive completions
  5. The Hadamard core for totally non-negative matrices
  6. Ratios of principal minors of totally non-negative matrices
  7. Completely positive matrices and their graphs
  8. Eigenvalues of words in two positive definite letters
  9. Critical points of the SSTRESS criterion in metric multidimensional scaling
  10. Coxeter graphs, groups, and Weyl chambers
  11. Statistical analysis of the determinants of certain sign pattern matrices
  12. A generalization of the classical numerical range
  13. Eigenvalues and boundary curvature of the numerical range
  14. Reflections on Coxeter groups
  15. Symmetric sign patterns allowing symmetric and skew-symmetric matrices with given row and column sums
  16. Spectral ranges of sign pattern
  17. On the diagonal scaling of squared distance matrices to doubly stochastic matrices
  18. The list of eigenvalue multiplicities for an Hermitian matrix whose graph is a tree
  19. Numerical ranges of tridiagonal matrices
  20. Central groupoids, central digraphs, and zero-one matrices satisfying $A^2 = J$.
  21. Absolutely flat idempotent matrices
  22. Positive definite extension problems for structured matrices
  23. Divisor tournament matrices
  24. Ray non-singularity of matrices
  25. Relations between matrix theory and function theory
  26. Commutativity of matrix patterns
  27. Determinental inequalities in matrix classes.
  28. Reconstruction of matrices from minors
  29. Doubly nonnegative matrices
  30. The Relative Gain Array
  31. Matrix completion problems.