10th birthday of MSG

Another event last week was the 10th anniversary talk in the Mathematics Study Group at South Bank University.

This group was set up by Carrie Rutherford, whose photo is below (as well as a mathematician at South Bank, she is a volunteer on the Markfield beam engine near Tottenham).

Carrie Rutherford

Carrie learned how to run a study group as a member of the Combinatorics Study Group at Queen Mary. She set up her own at South Bank, and it has evolved its individual style, attracting a range of people from as far afield as Norwich and Portsmouth.

The first ever talk in the MSG was on Hadamard matrices, and when Carrie asked me if I could talk about Hadamard matrices I was happy to comply.

Hadamard asked the question:

How large can the determinant of an n×n real matrix be, if its entries all have absolute values at most 1?

There is a simple geometric argument. The determinant is the volume of the Euclidean paralleleliped spanned by the rows of the matrix. The Euclidean length of each row is at most n1/2, and the volume spanned by vectors of fixed length is maximised when the vectors are pairwise orthogonal; so the maximum determinant is nn/2. Equality is achieved if and only if all the entries in the matrix H are +1 or −1 and HHT = nI. Such a matrix is called a Hadamard matrix. (This is a nice example of how the solution to a continuous problem may plunge you into the discrete world.)

It is easy to show that the order of a Hadamard matrix must be 1, 2 or a multiple of 4. It is conjectured that every multiple of 4 is the order of a Hadamard matrix. This is one of the big open problems in discrete mathematics. I think that the first unsettled case is order 668. (The previous smallest, 428, was solved at the IPM in Tehran shortly after my visit there in 2005.)

There has been some interest in symmetric and skew Hadamard matrices. (A Hadamard matrix can’t really be skew, since a real skew matrix has zero diagonal; we abuse language by saying that a skew-Hadamard matrix is one with +1 on the diagonal and HI skew-symmetric.)

One could ask Hadamard’s question also for matrices with zero diagonal and off-diagonal entries with absolute value at most 1. The same argument shows that the determinant of such a matrix C is at most (n−1)n/2, with equality if and only if the off-diagonal entries of C are +1 or −1 and CCT = (n−1)I. A matrix meeting the bound is called a conference matrix. (The name comes from their occurrence in conference telephony in the 1950s.)

One of the most remarkable facts about conference matrices is that, essentially, such a matrix must be either symmetric or (genuinely) skew-symmetric:

Theorem: A conference matrix of order greater than 1 has even order, and is equivalent (under row and column sign changes) to a symmetric matrix if n is congruent to 2 (mod 4), or to a skew-symmetric matrix if n is congruent to 0 (mod 4).

It is easy to see that C is a skew conference matrix if and only if C+I is a skew-Hadamard matrix, so the existence conjecture in this case is that both types exist for all multiples of 4. In the symmetric case, however, van Lint and Seidel showed that a symmetric conference matrix of order n exists if and only if n−1 is the sum of two squares.

Symmetric conference matrices are obtained by bordering with 1s the Seidel adjacency matrices of Paley graphs. Now the South Bank University logo is a pentagon, and the Mathematics Study Group logo the 3×3 grid; these are the first two Paley graphs, so give rise to conference matrices of orders 6 and 10, the latter very fitting for the anniversary of the MSG!

A similar construction shows that skew-Hadamard matrices are obtained by suitably bordering the signed adjacency matrices of doubly regular tournaments. By coincidence, these arose in another piece of work I put on the arXiv recently, joint with statisticians from the UK, Germany and Poland on circular repeated-measurements designs.

Also from statistics is an intriguing conjecture by Denis Lin on the relation between maximum determinant of skew matrices with orders congruent to 2 (mod 4), similar to the relation H = C+I that we saw in the case where the order is congruent to 0 mod 4. However, for this, I will refer you to the slides, which are on the on the MSG webpage, or in the usual place.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition, history and tagged , , , , , . Bookmark the permalink.

One Response to 10th birthday of MSG

  1. I saw Paley’s grave on my recent visit to Banff, covered in deep snow: see
    https://cameroncounts.wordpress.com/2014/11/28/banff-days-4-and-5/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s