HOMEPAGE of
Dr. R. Craigen

Welcome to my homepage.  Comments welcome; it is always under construction.

Interested in learning about research this summer?
  SUMMER RESEARCH ON ORTHOGONAL MATRICES
CURRENT COURSE WEB PAGES
OTHER WEB PAGES MAINTAINED
  • Manitoba Mathletics – a directory of information about mathletics (competitive mathematics) in this province.  Continually under development.  Some individual pages:
    • UM Math Team Home Page – this is a relatively current news page and archive of our UM mathletes' activities, training and competitions.  The UMOMC winner is current but some of our Hall of Fame archive needs updating as of Dec 2016
    • Manitoba Mathematical Competition (MMC) – as director of the provincial contest I maintain this page and keep it up to date each year.  In particular check out the annual school and individual winners, and find recent contests and solutions.
    • A directory of available school contests and misc. advice to schools running training programs and administering contests -- warning:  currently this page is hopelessly out of date!

ABOUT ME
Recent Student Undergraduate Research Assistants Graduate Students

Research Interests

My main work can be classified as Combinatorial matrix theory (CMT). What exactly is CMT, you may be asking?  I suppose there are only two people in the world who might use this term as the main theme of their work (that is, since Herb Ryser died) -- Richard Brualdi and me.  (This is a wild claim.  Honestly, thousands of people work in this field.  Most combinatorists -- certainly all design theorists and most graph theorists -- and many linear algebraists work on subjects that could well be called CMT.  But I don't know of any who, when asked what their field is, would say CMT before saying something else...)  To get a really good feel for the scope of the field you would need to pick up Brualdi's book on the subject.  But as it focuses on his particular interests, it doesn't delineate my work very well, so let me do so here.

Combinatorics is the study of configurations resulting from the discrete combinations of objects and the structure and relationships within, and between, systems of discrete elements.  Matrix theory is the study of matrices, which are rectangular arrays of numbers (or other things, like variables, expressions, or elements of arbitrary algebraic systems).

Combinatorial matrix theory, then, deals with matrices whose entries, or whose submatrix structure, satisfy some combinatorial restraints. Typically, one might study matrices whose elements are 0 or 1; (these, we call (0,1)-matrices) we also often deal with (0,1,-1)-matrices, (1,-1)-matrices or matrices whose elements are taken from a set {x1,...,xn,-x1,...,-xn}, where x1,...,xn are commuting variables.  There are many other variations.  We then ask (and try to answer) questions about such matrices that deal with existence structure, classification, relationships, and properties precipitated by the combinatorial restraints.

For example, given two lists of  positive integers, does a (0,1)-matrix exist whose row sums form the first list and whose column sums form the second list?   That is, give a simple condition from which wecan determine the answer, for any such pair of lists.  (The answer to this one is known -- see Brualdi's book).

Here is another example:  for which values of n does there exist an nxn (1,-1)-matrix whose rows are pairwise orthogonal (i.e., their dot product is 0)?  This question is the Hadamard matrix problem,stated by the great french analyst, J. Hadamard, in 1893 -- the answer is still unknown.  Such matrices are now called Hadamard matrices after him.  Hadamard conjectured that Hadamard matrices of ordern exist precistly for n=1,2 and any multiple of 4; this Hadamard matrix conjectureremains unresolved in spite of a century of work by many good mathematicians.

Here is one more:  Let A be a square (0,1)-matrix of order n2+n+1 such that AAt=nI+J (In CMT, we generally use "J" to represent the matrix of all 1's).  If you don't get the meaning of this equation, it can also be described as:  every row of A contains n+1 nonzero elements and every pair of rows shares exactly one nonzero position. Let us call any such matrix a Projective Plane of order n, or PP(n)  (I'll leave the reason for the geometric language here a mystery for you to look up and explore -- the connection to geometry is delightful, and worth the work of finding out!).  Here we might ask, for which values n does there exist a PP(n)?  It is conjectured that n must be a prime, like 2,3,5 or 7, or a prime power, like 33=27, or 52=25 (there are known planes of all such orders).

Jennifer Seberry showed, in 1974, that, for every odd number p, there exists a number T (which depends on p) such that there is a Hadamard matrix of order 2tp, for all t > T,  the first asymptotic existenceresult  of this type for Hadamard matrices, and an impressive feat.  The Hadamard conjecture would have that T=4 for any value of p; one way to view our task is to say that we must reduce the value of T to 4, for all p.  One of my big accomplishments was to provide, in 1993, the first significant improvement on Seberry's result.  How much did this result improve on the value of T?  In Seberry's result, the factor 2T is about the order of magnitude of p2.  However, in my result, T can be taken to be considerably less than p1/2 for large values of p -- an improvement of several orders of magnitude.  Still, however, we are nowhere near the magical mark of T=4 for all p.  One goal I have is to find a unform bound for T -- a value that works for all p.  By most measures this would be a giant leap ahead of anything we can do now towards solving the Hadamard matrix conjecture.

All of the above problems may be viewed as existence problems. The latter two are very well known.  To a combinatorist, they are as important as Fermat's Last Theorem was to a Number Theorist before Wiles' solution.  They are the "holy grails" of combinatorics. Both are classical problems -- easily stated, deucedly difficult to solve, and they have resisted many  clever attacks by skilled practitioners of the art of CMT over a long period of time.  Thousands of research articles, and several books, have been devoted to each one.

There are also structure problems, such as:  can a given projective plane  of order n be arranged in such a way that its matrix could be obtained by writing down one row, and shifting it (cyclically) one position to the right to give the second row, then once more to give the third row, and so on?  Such a matrix is called circulant,and such a plane is called cyclic.  Cyclic planes exist in every order (all the prime powers) for which a plane is known.  One might ask whether a Hadamard matrix can always be taken to be symmetric.  (It is unknown whether there is one such in every order, but the answer is expected to be "yes".)  Can we assume that the row and column sums of a Hadamard matrix are constant (we call such a matrix regular)?  Not in general; it is known that this can only happen if the order of the matrix is a square.  Interestingly, symmetric Hadamard matrices with constant diagonal  -- these are called graphical Hadamard matrices-- can also only exist in square orders; there has been some speculation that there is a hidden relationship between these two kinds of structures.

Most of my work can be classed as structural.  A few years ago I made what I call the 2x2 Block Conjecture for Hadamard matrices, which comes in two parts:  i) Every Hadamard matrix of order >2 can be partitioned into 2x2 rank 1 submatrices; ii) every Hadamard matrix of order >1 can be partitioned into 2x2 rank 2 submatrices.  If this is true, it will be the first essentially new universal property of Hadamard matrices to be established in over 100 years.  Any new structural fact like this, that can be established to hold for all Hadamard matrices, is likely to provide a critical key to the eventual solution of the Hadamard matrix problem.

In addition to existence and structural questions, there are questions of classification.  Before Hadamard, the English geometer and principal architect of the modern field of Linear Algebra, J. J. Sylvester, studied something he called inverse orthogonal matrices, which includes Hadamard matrices.    He attempted to establish a result saying that, if one of these matrices existed, then it was equivalent (after certain simple transformations) to one of a complete set of representatives that he produced.  Unfortunately, his reasoning was faulty, and his classification failed.   Here is how it works with Hadamard matrices:  we first observe that a Hadamard matrix remains Hadamard if its rows, or its columns, are permuted, or if all the entries in any row or column are negated.  We say that any two Hadamard matrices are equivalent if one can be transformed into the other by a series of such operations.  The set of all matrices equivalent to one Hadamard matrix is its equivalence class.   How many classes are there in each (known) order?  (The existence question simply asks for which orders this number is >0.)  It is known that there is a unique class in each of the orders 1,2,4,8 and 12.  There are 5 classes of order 16, 3 of order 20, 60 of order 24 and hundreds of order 28.  We know of thousands of classes of order 32, but so far have not completely decided on the classification.

The types of questions can be combined.  For example, not every Hadamard matrix is symmetric, but perhaps every Hadamard matrix is equivalent to a symmetric one?  Wallis and Lin showed that this is not the case.  They even showed that a Hadamard matrix may be equivalent to its transpose -- but not to a symmetric matrix!

Similarly, a PP(n) can have its rows or columns permuted, and it will remain a PP(n).  These are the equivalence operations for planes.  We say that a projective plane is cyclic not only if it (that is, its matrix) is circulant, but also if it is merely equivalent to a circulant matrix (that is because, from a geometrical perspective, the rows represent points and the columns represent lines -- or vice versa -- and these do not naturally have any particular ordering; all equivalent PP(n)'s represent the same geometrical plane).  As mentioned, we do not know if there are planes in orders other than prime powers.  But, of the known planes in these orders, how many inequivalent planes are possible?  There are many different classes of these planes, each with their own interesting properties.  The most "generic" of these exist in all known (finite) orders, and are called Desargesian planes.  These planes are cyclic.  There are also many known non-cyclic planes.  However, the only known plane in each prime (as opposed to prime power) order is the Desargesian plane.  Are prime orders special in that they have only one plane?  Even to this simple question we do not know the answer.

My fields of interest in CMT center around the Hadamard matrix question.  I study:

My interests range over many other fields.  In general I am interested in:

Publications

Some of My collaborators (besides students):


Email:
Dr. R. Craigen