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
- Math
3360 Combinatorics II (Fall 2016)
- Math 3380 Introduction to Projective Geometry (Fall 2016
not live)
- Math 8510/4920 Combinatorial Design Theory (Winter 2017
not live yet)
- Math 1300 Linear Algebra and Vector Geometry (Winter 2017
not live yet)
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
- Born 1959
- High School: Columnneetza Sr. High, Williams Lake B.C. 1977
- Undergrad: BSc. at UBC (Hon. Math, 1st class) 1981
- Master's: MMath in Pure Math at University of Waterloo
1988
- Doctorate: PhD in Pure Math at University of Waterloo
1991
- Work history:
- NSERC Postdoctoral Fellow 91-93 University of Lethbridge
(Lethbridge, Alberta)
- Asst Professor 93-95 University of Lethbridge
- Asst Professor 95-99 Fresno Pacific University (Fresno,
California)
- Asst Professor 99-02 University of Manitoba (Winnipeg,
Manitoba)
- Assoc Professor 02- University of Manitoba
- In 1994 I was one of the two recipients of the Kirkman Medal
in its inaugural year, for my work in Combinatorics in the first
few years after my PhD.
- Math Co-curricular activities:
- Math Club
- Coach for U of M Putnam and NCS/MAA teams.
(co-coaches: K.Kopotun
and D.Gunderson)
- High School enrichment/mentoring projects
- Manitoba Mathematics Museum
- Married to Karen (nee Bell), June
30, 1984
- Children:
- Christopher (March 1988)
- Lisa (July 1991 -- a graduation present!)
- Cats:
Archimedes (A.K.A. "Archie") RIP 2013
Emerald (A.K.A "Emmy") RIP 2011
- Maple (A.K.A., well...just "Maple")
- Sashi
- Winnie (Ther Poosy)
- Church Affiliation: Member of Fort Garry MB Church,
Winnipeg, MB
- Some of my perspective on Mathematics
and Christianity
Recent
Student Undergraduate Research Assistants
- Roger Woodford - NSERC
SRA scholar Summer 2002 (Currently a grad student at UBC)
- Classification of Butson Hadamard matrices and Unit Hadamard
matrices
- Boolean complementary pairs
- Development of the new theory of Power Hadamard matrices
- Manon Mireault - half
time RA Summer 2004
- Factorizing sequences with zero autocorrelation
- circulant orthogonal matrices over the quaternion and
dihedral groups
- Robert Lecnik - half time
RA Summer 2004
- Exploration of Genetic Algorithm approaches to constructing
orthogonalmatrices
- Will Gibson - part time
research assistant 2000-2004 and 2011
- Smart search for sequences with zero autocorrelation using
affixes andother methods
- Affixes for Complex Golay Sequences
- 2x2 Block Hadamard conjecture
- Gabriel Faucher (2004, 2006)
- Dave Gabrielson (2006)
- Mike Himbeault (2006, 2008)
- Trevor Wares (2006)
- Mark Nagelberg (2010)
- Colin Desmarais (2013)
- Glendon Klassen (2013)
- Pat Naylor (2013)
- Ted Eaton (2013)
- YOU? In Summer 2004, depending on funding, I may hire
1-4 undergraduate students for research time. Check the
box outside my office door for application forms.
Graduate Students
- Michelle Davidson (PhD)-
Structure of Projective Planes
- Golwyn Millar (MSc)
- Ivan Livinskyi (MSc)
- Rahim Taghikhani (MSc)
- Angel Barria Comicheo (PhD co-supervisor with Khodr
Shamseddine)
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 {x_{1},...,x_{n},-x_{1},...,-x_{n}},
where
x_{1},...,x_{n} 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 n^{2}+n+1
such
that AA^{t}=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 3^{3}=27,
or 5^{2}=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 2^{t}p, 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 2^{T} is about the order of
magnitude of p^{2}. However, in my result, T can be
taken to be considerably less than p^{1/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:
- Hadamard matrices
- weighing matrices
- orthogonal designs
- many kinds of generalized Hadamard, weighing and orthogonal
designs
- Butson type: these have entries that are (zero or)
complex roots of unity
- Signed group type: These have entries (zero
or) in a signed group (a group with a central element of
order 2, denoted -1), with algebra performed over a ring I
call the signed group ring
- Group type: The (nonzero) entries of these
are elements of a group, all algebra is performed over the
group ring, and the sum of the group elements is taken to be 0
(i.e., we are actually working in an appropriate quotient
ring)
- Unit type: these have entries that are (zero
or) complex units (points on the unit circle)
- Inverse-orthogonal: These are an odd
twist--there is no restriction on the (complex) entries, but
orthogonality is defined in terms of multiplying not by the
Hermitian adjoint of the matrix, but by the matrix obtained by
transpose followed by reciprocation of every nonzero
entry. For unit type matrices, there is no difference.
- Various sequences with zero autocorrelation:
Golay sequences, ternary complementary pairs, complex Golay
sequences, Boolean complementary pairs, normal, near normal
sequences, and so on. These are used to construct
orthogonal matrices of various types; they also form an
algebraic object with inherently interesting orthogonal
structure.
- Combinatorial designs: such as block designs,
BIBD's, SBIBD's, etc. I am a bit odd in that I view all
such objects purely as matrices. I get the impression
that this is the minority approach among design theorists.
- Power Hadamard matrices: These were
introduced by my student, Roger Woodford, and me during our
work in the summer of 2002. The entries of these matrices are
powers of an indeterminate x, the algebra is done in a
polynomial ring, and orthogonality is modulo some polynomial.
My interests range over many other fields. In general I am
interested in:
- Combinatorics
- Linear Algebra
- Abstract algebra (especially associative rings)
- Group theory
- p-adic analysis
- problem solving and heuristics
- Philosophy of Mathematics
- Complex analysis
- Functional equations
- Mathematical approaches to questions about wider subjects like
cosmology and consciousness
- Information theory, quantum information theory and quantum
computation
Publications
- The Associativity Equation Revisited (with Z. Pales), Aequationes
Mathematicae,37 (1989) 306--312.
- The Range of the Determinant Function on the Set of n x n
(0,1)-Matrices, Journal of Combinatorial Mathematics and
Combinatorial Computing, 8 (1990) 161--171.
- Embedding Rectangular Matrices in Hadamard Matrices, Linear
and
Multilinear
algebra,
29 (1991) 91--92.
Equivalence of Inverse Orthogonal and Unit Hadamard Matrices, Bulletin
of
the Australian Mathematical Society, 44#1 (1991) 109--115.
- A New Class of Weighing Matrices with Square Weights, Bull.
ICA,3 (1991) 33--42.
- Weighing Matrices from Generalized Hadamard Matrices by
2-Adjugation}, JCMCC,10 (1991) 193--200.
- Constructing Hadamard Matrices with Orthogonal Pairs, Ars
Comb.
33 (1992) 57--64.
- Product of Four Hadamard Matrices, (with J. Seberry and X.
Zhang), J. Comb. Th. (Ser. A), 59#2 (1992)
318--320.
- Matrices Equivalent to their Transpose by Permutations, Congressus
Numerantium,86 (1992) 33--41.
- A Generalization of Belevitch's Construction, Congressus
Numerantium, 87 (1992) 43--50.
- On the Nonexistence of Hermitian Circulant Complex Hadamard
Matrices, (with H. Kharaghani) Australasian J.
Combinatorics,7 (1993) 225--227.
- The Craft of Weaving Matrices, Congressus Numerantium,
92 (1993) 9--28.
- The Structure of Weighing Matrices having Large Weights, Designs,
Codes
and
Cryptography,5 (1995), 199--216.
- Regular Conference Matrices and Complex Hadamard Matrices, Utilitas
Mathematica, 45 (1994) 65--69.
- Trace, Symmetry and Orthogonality}, Canadian
Mathematical Bulletin, 37 (1994), 461--467
- Complex Golay Sequences}, Journal of Combinatorial
Mathematics and Combinatorial Computing, 15
(1994) 161--169.
- Hadamard Matrices: 1893--1993, (with W. D. Wallis)
Congressus Numerantium,97 (1993) 99--129.
- A Direct Approach to Hadamard's Inequality}, Bulletin of
the Institute of Combinatorics and its Applications, 12
(1994) 28--32.
- On the Existence of Regular Hadamard Matrices}, Congressus
Numerantium,99 (1994) 277--283.
- Improved Model of Temperature Dependent Development by
Arthropods} (with Derek J. Lactin, N. J. Holliday and D. L.
Johnson), Environ. Entomol.,24(1), 68--75.
- Constructing Weighing Matrices by the Method of Weaving, Journal
of
Combinatorial
Designs,3 (1995) 1--13
- Signed Groups, Sequences and the Asymptotic Existence of
Hadamard Matrices}, Journal of Combinatorial Theory, 71
(1995) 241--254.
- On the Asymptotic Existence of Complex Hadamard Matrices
(with W. H. Holzmann and H. Kharaghani), Journal of
Combinatorial Designs, 5 (1996) 319--327.
- A Combined Approach to the Construction of Hadamard Matrices
(with H. Kharaghani), Australasian Journal of
Combinatorics, 3 (1996) 89--107.
- Hadamard Matrices from Weighing Matrices via Signed Groups,
Designs, Codes and Cryptography,12 (1997)
49--58.
- A Theory of Ternary Complementary Pairs, (with C.
Koukouvinos), J. Combinatorial Theory, Ser. A96
(2001) 358--375.
- Complex Golay Sequences: Structure and
Applications (with W. Holzmann and H. Kharaghani), Discrete
Mathematics 252 (2002) 73--89.
- Boolean and Ternary complementary Pairs, to appear in J.
Combinatorial Theory, Ser. A.
- Weaving Hadamard matrices with large excess, to appear in
JCD, with H. Kharaghani
- Non-refereed publications:
- Orthogonal Sets and Orthogonal Designs, Tech. Rep. CORR \#
90-19, University of Waterloo (1990).
- The Method of Weaving: A New Way to Construct Weighing
Matrices}, Tech. Rep. TR-MA-01-92, University of Lethbridge
(1992).
- A PreCalculus Workbook} (with summer student, H. Pinto).
Comprehensive self-tutorial book to prepare students with a
weak background for the mathematical requirements of Calculus
and otherintroductory University courses in Mathematics
(approx. 100 pages;prepublication release, Sept. 1994).
Note: as of 2002, this book has never been put into
final form...a summer project for a motivated student
assistant, perhaps?
- Articles in the Explorations series (Explorations is
a regular feature of the Lethbridge Herald, the local daily
paper, in which researchers describe aspects of their work at
a level accessible to the general public, and whose goal is
broadening public interest in, and awareness of, research):
- Error-correcting Codes and Pictures from Saturn (about an
application of Hadamard matrices), The Lethbridge
Herald, Tues., Feb. 18, 1992, C8
- Looking for Strings of Pearls (on the subject of symbolic
dynamics) The Lethbridge Herald, Tues., Nov. 8, 1994, B11
- Three sections to CRC Handbook of Combinatorial Designs
(Ed's J. Dinitz and C. Colburn, CRC Press, 1996):
- Weighing Matrices and Weighing Designs
- Orthogonal Designs (with J. Seberry)
- Hadamard Matrices.
- Articles in Manitoba Math Links (the Quarterly Newsletter of
the U of M Mathematics Department, aimed at High School
Students and Math Teachers. My contributions are
generally devoted to encouraging the reader to pursue a
mathematical exploration, using elementary tools, and leading
to interesting and nontrivial destinations -- mathematical
adventures, if you will. I look for topics that will be
new to most readers, and not beyond a grade 10 level. I
make an attempt add non-mathematical layers to the experience
such as interesting background information, a story line, or
some philosophical meandering):
- Parse-o-grams, 1#1 (2000) p. 7
- Infigers, 1#2 (2001) 6--7
- The Woman at the Well, 1#3 (2001) p. 1,3
- Mathletics at U of M 2#5 (2002) 3--4 (not part of my usual
"series"; a report on math competitions)
- When Bad Sums Happen to Good Fractions, 2#5 (2002)
6--7
- Submitted for publication or in preparation:
- On the structure ofmultiphase complementary pairs, (in
progress) with W. Holzmann and H. Kharaghani)
- ICW$(n,s^2)$ classification for small $n$ and unrestricted
weight (in progress) with Y. Strassler
- An anatomy of Hadamard matrices (a revision of my master's
essay, for eventual distribution by request, not for
publication)
- Classification of some Unit Hadamard matrices (in
progress) with Roger Woodford
- The Group of Odd-weight Boolean complementary Pairs (in
progress) with Roger Woodford
- Classification of some Butson Hadamard matrices (in
progress) with Tim Nikkel and Roger Woodford
- Zero patterns of ternary complementary pairs (in progress)
- Signed groups, projective representations, and cocyclic
Hadamard matrices (in progress) -- an explanation of my
contention that signed group development of Hadamard matrices
and cocyclic development are essentially the same thing; there
appears to be some resistance to this idea among those who
study cocyclic development, and I feel a careful exposition of
the connection should clear up this point. This is for
distribution, but may or may not eventually be published.
- Further explorations into Ternary Complementary Pairs (in
progress) with W. Gibson, S. Georgiou and C. Koukouvinos
- Affixes of TCP's (in progress) with W. Gibson
- On products of Complementary Pairs (in progress)
- The 2x2 Block Conjecture for Hadamard Matrices (in progress)
- Modulus 3 Ternary Complementary Pairs (in progress)
- Dissections of Ternary Complementary Pairs (in progress)
- A Recursive Construction for Orthogonal Designs (in
progress) with H. Kharaghani
- Power hadamard matrices (for submission to the J. Seberry
birthday issue of Discrete Mathematics) with R. Woodford
Some of My collaborators
(besides students):
- H. Kharaghani (U. Lethbridge): Hadamard matrices, block
sequences, orthogonal designs, excess, complex sequences, 1991--
(ongoing)
- W. Holzmann (U. Lethbridge): same topics as for H. Kharaghani
- W. deLauney (Cryptomathematics Res. Grp., Def. Sci. Tech.
Org., Australia): Generalized Hadamard matrices, 1992 (some
unfinished projects...)
- J. Seberry (U. Wollongong, Australia): Hadamard, Weighing
matrices, OD's 1989-- (more unfinished projects...)
- W. D. Wallis (South. Ill. U. at Carbondale, Ill.): Hadamard
matrices, 1993
- D. J. Lactin (Agriculture Canada Research Station,
Lethbridge): consulting for project modeling insect development,
1993--94
- Y. Strassler (Bar-Ilan University, Israel): Orthogonal
circulant matrices, 1995--
- K. Arasu (Wright State University, Ohio): Special
weighing matrices and block designs, 1996-- (unfinished
projects...)
- C. Koukouvinos (National Technical University of Athens,
Greece): Ternary complementary sequences, 1998-- (ongoing)
Email:
Dr.
R. Craigen