HOMEPAGE
of
Dr. R.
Craigen
Welcome to my homepage. Comments welcome; it is always under
construction.
Interested in learning about
research this summer?
ABSTRACT: OUR RESEARCH ON ORTHOGONAL MATRICES
CURRENT COURSE WEB PAGES
Math
8510 Linear Representations of Groups (Graduate Course)
Math
3400 Combinatorics I (Geared for undergraduate Mathematics
Honours/Majors students)
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")
- Emerald (A.K.A "Emmy")
- Maple (A.K.A., well...just "Maple")
(can you see the
mathematical
connection in all three names? - 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
2002
- Factorizing sequences with zero autocorrelation
- circulant orthogonal matrices over the quaternion and dihedral
groups
- Robert Lecnik - half time RA
Summer 2002
- Exploration of Genetic Algorithm approaches to constructing
orthogonalmatrices
- Will Gibson - part time
research
assistant
2000-2003
- Smart search for sequences with zero autocorrelation using
affixes
andother
methods
- Affixes for Complex Golay Sequences
- 2x2 Block Hadamard conjecture
- 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
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) -- RichardBrualdi
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