Conference matrix

From Wikipedia, the free encyclopedia

In mathematics, a conference matrix (also called a C-matrix) is a square matrix C with 0 on the diagonal and +1 and −1 off the diagonal, such that C^TC is a multiple of the identity matrix I. Thus, if the matrix has order n, C^TC = (n−1)I.

Conference matrices arose in several independent ways. One original source is a problem in telephony (Belevitch 1950). Another is statistics (Raghavarao 1959). Still another is elliptic geometry (van Lint and Seidel 1966).

For n > 1, there are two kinds of conference matrices. Let us normalize C by negating any row or column whose first entry is negative. (This does not change whether a matrix is a conference matrix.) Thus, a normalized conference matrix has all 1's in its first row and column, except for a 0 in the top left corner. Let S be the matrix that remains when the first row and column of C are removed. Then either n is a multiple of 4, and S is antisymmetric (as is C if the first row is negated), or n is congruent to 2 (modulo 4) and S is symmetric (as is C).

[edit] Symmetric conference matrices

If C is a symmetric conference matrix of order n > 1, then not only must n be congruent to 2 (mod 4) but also n − 1 must be a sum of two square integers (Belevich 1950; there is a clever proof by elementary matrix theory in van Lint and Seidel 1966).

Given a symmetric conference matrix, the matrix S can be viewed as the Seidel adjacency matrix of a graph. The graph has n − 1 vertices, corresponding to the rows and columns of S, and two vertices are adjacent if the corresponding entry in S is negative. This graph is strongly regular of the type called (after the matrix) a conference graph.

The existence of conference matrices of orders n allowed by the above restrictions is known only for some values of n. For instance, if n = q + 1 where q is a prime power congruent to 1 (mod 4), then the Paley graphs provide examples of symmetric conference matrices of order n, by taking S to be the Seidel matrix of the Paley graph. The first few possible orders of a symmetric conference matrix are n = 2, 6, 10, 14, 18, (not 22, since 21 is not a sum of two squares), 26, 30, (not 34 since 33 is not a sum of two squares), 38, 42, 46, 50; for every one of these, it is known that a symmetric conference matrix of that order exists. Order 54 seems to be an open problem. (See Sloane, Sequence A000952.)

[edit] Antisymmetric conference matrices

Antisymmetric conference matrices can also be produced by the Paley construction. Let q be a prime power with residue 3 (mod 4). Then there is a Paley digraph of order q which leads to an antisymmetric conference matrix of order n = q + 1. The matrix is obtained by taking for S the q × q matrix that has a +1 in position (i,j) and −1 in position (j,i) if there is an arc of the digraph from i to j, and zero diagonal. Then C constructed as above from S, but with the first row all negative, is an antisymmetric conference matrix.

This construction solves only a small part of the problem of deciding for which values of n, multiples of 4, there exist antisymmetric conference matrices of order n.

[edit] References

Belevitch, V. (1950), Theorem of 2n-terminal networks with application to conference telephony. Electr. Commun., vol. 26, pp. 231-244.

Goethals, J.M., and Seidel, J.J. (1967), Orthogonal matrices with zero diagonal. Canadian Journal of Mathematics, vol. 19, pp. 1001-1010.

van Lint, J.H., and Seidel, J.J. (1966), Equilateral point sets in elliptic geometry. Indagationes Mathematicae, vol. 28, pp. 335-348.

Raghavarao, D. (1959), Some optimum weighing designs. Annals of Mathematical Statistics, vol. 30, pp. 295-303.

Seidel, J.J. (1991), ed. D.G. Corneil and R. Mathon, Geometry and Combinatorics: Selected Works of J.J. Seidel. Boston: Academic Press. Several of the articles are related to conference matrices and their graphs.