°c 1998 Kluwer Academic Publishers. Manufactured in The Netherlands.
Bose-Mesner Algebras Related to Type II Matrices and Spin Models
FRANC¸ OIS JAEGER†
Laboratoire Leibniz, Institut IMAG, BP 53 38041 Grenoble cedex 9, France
MAKOTO MATSUMOTO matsumoto@math.keio.ac.jp
Faculty of Science and Technology, Keio University, Hiyoshi, Kohoku-ku, Yokohama, 223 Japan
KAZUMASA NOMURA nomura@tmd.ac.jp
College of Liberal Arts and Sciences, Tokyo Medical and Dental University, Kohnodai, Ichikawa, 272 Japan Received February 21, 1996; Revised March 18, 1996
Abstract. A type II matrix is a square matrix W with non-zero complex entries such that the entrywise quotient of any two distinct rows of W sums to zero. Hadamard matrices and character tables of abelian groups are easy examples, and other examples called spin models and satisfying an additional condition can be used as basic data to construct invariants of links in 3-space. Our main result is the construction, for every type II matrix W , of a Bose-Mesner algebra N(W), which is a commutative algebra of matrices containing the identity I , the all-one matrix J , closed under transposition and under Hadamard (i.e., entrywise) product. Moreover, if W is a spin model, it belongs to N(W). The transposition of matrices W corresponds to a classical notion of duality for the corresponding Bose-Mesner algebras N(W). Every Bose-Mesner algebra encodes a highly regular combinatorial structure called an association scheme, and we give an explicit construction of this structure. This allows us to compute N(W)for a number of examples.
Keywords: spin model, link invariant, association scheme, Bose-Mesner algebra
1. Introduction
The main motivation for the present work comes from the study of spin models for link invariants. Such a spin model can be viewed as a square matrix with complex entries which satisfies two equations, the type II and type III equations. Any solution to these equations yields an invariant of knots and links in 3-space via a construction due to V. Jones [21]
for symmetric matrices and generalized in [26] to arbitrary matrices. The problem of the classification of solutions to the type II and type III equations seems to be very difficult, and it was soon realized (see [17]) that it is deeply related with a classical topic in algebraic combinatorics, namely the study of association schemes.
Roughly speaking, an association scheme on a (finite) set X is a partition of X×X into relations which exhibits nice regularity properties. A standard example is given by distance-regular graphs (see [7]): X is the vertex-set and the relations correspond to the possible values of the distance function. Another standard example is given by transitive actions of finite groups on X (see [5]): the relations are the orbits of the corresponding
action on X×X . The regularity properties of the relations are conveniently described in terms of their adjacency matrices: they span an algebra of matrices with unit I closed under transposition. This algebra is called the Bose-Mesner algebra of the association scheme. It is also an algebra with unit J (the all-one matrix) for the Hadamard (i.e., entrywise) product of matrices. We always assume here that the ordinary matrix product is commutative. In this case, Bose-Mesner algebras and association schemes are equivalent concepts.
In October 1994 the first author proved, using the topological interpretation of the type II and type III equations, that every symmetric solution W to these equations belongs to some Bose-Mesner algebra [20]. Moreover, this algebra has a duality, i.e., a linear automorphism which, up to multiplication by a scalar, exchanges the ordinary and Hadamard product, and whose square is a scalar multiple of the transposition map. This duality has a nice expression in terms of W , or equivalently W is given by a solution to the so-called modular invariance equation corresponding to this duality (see [4]).
Immediately afterwards, the third author gave a purely algebraic proof that any symmetric matrix W satisfying the type II equation defines some Bose-Mesner algebra N(W), which will contain W if the type III equation is also satisfied [31]. This approach is obviously more general than that of [20], and this is particularly significant since solutions to the type II equation (which we call type II matrices) are of great interest in the theory of Von Neumann algebras and of some natural generalizations (see [1, 23]). Another advantage of this ap- proach is that it can be generalized to non-symmetric matrices, and such a generalization is the main content of the present paper.
To sum up, we shall generalize both the results of [20, 31] by associating with every type II matrix W a Bose-Mesner algebra N(W), which contains W when this matrix also satisfies the type III equation. The Bose-Mesner algebra N (tW ), wheretW denotes the transpose of W , is dual to N(W), which means that there is a linear isomorphism from N(W)to N (tW ) which converts the ordinary (respectively: Hadamard) product in N(W) into the Hadamard (respectively: ordinary) product of N (tW ). In particular, if W can be transformed into a symmetric matrix by multiplying row and columns by non-zero scalars (this occurs for instance if the type III equation holds), N(W)=N (tW ) has a duality.
We give also a direct and explicit construction of the association scheme corresponding to N(W), and of its symmetrization, in terms of certain graphs associated with W . This allows us to study effectively the tensor product construction for type II matrices, and a number of examples: character tables of abelian groups, Hadamard matrices of size 16, type II matrices of size 4, spin models for the Kauffman polynomial of links (see [17]), and the spin models defined on Hadamard graphs by the third author (see [29]).
2. Preliminaries
2.1. Association schemes and Bose-Mesner algebras
For more details concerning this section, the reader is referred to [5, 6, 8–10, 32].
Let X be a non-empty finite set. A d-class association scheme on X is a partition of X×X into d+1 non-empty relations Ri, i =0, . . . ,d, such that the following properties hold.
(1) R0= {(x,x)|x∈ X}.
(2) For every i∈ {0, . . . ,d}there exists i0∈ {0, . . . ,d}such that{(y,x)|(x,y)∈Ri} =Ri0. (3) There exist intersection numbers pki j(i,j,k∈ {0, . . . ,d}) such that, for every(x,y)∈
Rk,|{z∈ X |(x,z)∈ Ri, (z,y)∈ Rj}| =pki j. (4) pki j= pkj ifor every i,j,k∈ {0, . . . ,d}.
Remark Since all association schemes which appear in the present work satisfy property (4), we have incorporated this property in our definition. Thus, we agree with the termi- nology of [10], and our association schemes are commutative in the terminology of [5].
We denote by MX the set of square matrices with rows and columns indexed by X and entries in C. The(x,y)-entry of A∈ MXis denoted by A(x,y). We denote by I the identity matrix, by J the matrix with all entries equal to 1, bytA the transpose of A, and by A B the (ordinary) matrix product of A and B. The Hadamard product of A and B is denoted by A◦B and defined by(A◦B)(x,y)= A(x,y)B(x,y).
For every i in {0, . . . ,d}, let Ai ∈ MX be defined by: Ai(x,y)=1 if (x,y) ∈ Ri, Ai(x,y)=0 otherwise.
The facts that the Ai have entries 0 or 1 and that the Ri form a partition of X×X into non-empty relations are translated as follows.
(5) Ai 6=0, Ai◦Aj =δ(i,j)Ai (whereδis the Kronecker symbol).
(6) Pd
i=0Ai= J.
Properties (1), (2), (3) and (4) now become (7) A0=I .
(8) tAi =Ai0.
(9) AiAj =AjAi=Pd
k=0pki jAk.
LetAbe the C-linear span of{Ai |i =0, . . . ,d}. By (5) and (6),Ais a (commutative) algebra under Hadamard product, with unity element J , and {Ai | i = 0, . . . ,d} is a basis of orthogonal idempotents for this algebra. By (7) and (9),Ais also a commutative algebra under matrix product, with unity element I . Finally, (8) means thatAis closed under transposition. The vector subspaceAof MX is called the Bose-Mesner algebra of the association scheme{Ri|i =0, . . . ,d}on X .
Conversely, it is not difficult to show that every vector subspace of MXcontaining I and J , closed under transposition, which is a commutative algebra under Hadamard product and also under matrix product, is the Bose-Mesner algebra of some association scheme on X . The only non-trivial step is the existence of a basis of orthogonal idempotents for the Hadamard product, for which the reader is referred to [7], Theorem 2.6.1 (i) (the proof given there obviously works for non-symmetric matrices as well).
A Bose-Mesner algeberaA(or the corresponding association scheme) is symmetric if every matrix inAis symmetric. For every Bose-Mesner algebraA, its symmetrization A˜ is the set of symmetric matrices inA. Clearly,A˜ is a symmetric Bose-Mesner algebra. Its Hadamard idempotents are the Aifor all i with i =i0and the Ai+Ai0for all i with i6=i0.
LetAbe a Bose-Mesner algebra on X with basis of Hadamard idempotents {Ai|i = 0, . . . ,d}.
Since the Ai are real matrices,Ais closed under complex conjugation, and hence also under conjugate transposition. Then the commutativity of the matrix product onAimplies the existence of a unitary matrix U such that U−1AU consists of diagonal matrices. Note that on this algebra the ordinary matrix product and the Hadamard product coincide. It follows that Ahas a basis{Ei | i = 0, . . . ,d}such that the diagonal matrices1i = U−1EiU satisfy the identity1i◦1j =δ(i,j)1i (see again [7] Theorem 2.6.1 (i)), or equivalently 1i1j =δ(i,j)1i. Thus{Ei |i =0, . . . ,d}is a basis of orthogonal idempotents for the matrix product:
(10) EiEj =δ(i,j)Ei. Since I belongs toA, (11) Pd
i=0Ei =I .
Since J A=A J is a scalar multiple of J for all A inA, one easily shows that (1/|X|) J ∈ {Ei|i=0, . . . ,d}, and the notation is chosen so that
(12) E0= |X1|J .
Since the1i have entries 0 or 1, the Ei are Hermitian matrices, and the uniqueness of the basis of orthogonal idempotents shows that
(13) For every i in{0, . . . ,d}there existsˆi in{0, . . . ,d}such thattEi = ¯Ei =Eˆi. Finally the fact thatAis closed under Hadamard product implies the existence of numbers qi jk (i,j,k∈ {0, . . . ,d}) called the Krein parameters such that
(14) Ei◦Ej =|X1|Pd
k=0qi jkEk.
We now introduce several notions of isomorphism for association schemes and Bose- Mesner algebras.
Two association schemes{Ri |i =0, . . . ,d}and{Si |i=0, . . . ,d}on X are isomorphic if there exist permutations ρ : X → X and σ : {0, . . . ,d} → {0, . . . ,d} such that (ρ(x), ρ(y))belongs to Sσ (i)if and only if(x,y)belongs to Ri.
Two Bose-Mesner algebras A andB in MX are combinatorially isomorphic if there exists a permutation matrix P in MX such thatB= P−1AP. It is easy to see thatAand Bare combinatorially isomorphic if and only if the corresponding association schemes are isomorphic.
ForAandBas above, a Bose-Mesner isomorphism fromAtoBis a linear isomorphism ϕ :A→ Bsuch thatϕ(A A0)=ϕ(A)ϕ(A0)andϕ(A◦ A0)=ϕ(A)◦ϕ(A0)for every A, A0inA. In particular, for every permutation matrix P, settingϕ(A) = P−1A P defines a combinatorial Bose-Mesner isomorphism fromAto P−1AP. However, a Bose-Mesner
isomorphism need not be combinatorial. For instance, a 2-class symmetric association scheme(R0,R1,R2)is determined by the strongly regular graph corresponding to the rela- tion R1, and the Bose-Mesner algebras of two non-isomorphic strongly regular graphs with the same parameters (i.e., intersection numbers) such as the Shrikhande graph and the lattice graph L2(4)(see [7]) will be related by a non-combinatorial Bose-Mesner isomorphism.
A duality from Ato B is a linear isomorphism 9 : A → B such that 9(A A0) = 9(A)◦9(A0)and9(A◦ A0)=(1/|X|)9(A)9(A0)for every A, A0inA. If there exists a duality9fromAtoB,Bis called a dual toA. Then one easily shows that|X|9−1is a duality fromBtoA, and consequentlyAis a dual toB. We shall say that(A,B)is a dual pair.
Remarks
(i) For the sake of simplicity, we have adopted a non-standard terminology: if there exists a duality9 fromAtoB, one usually says thatB is “formally dual” toA. This is to distinguish the following situation corresponding to an “actual duality”: X is an abelian group, andAis contained in the Bose-Mesner algebra AX of X (the set of matrices A in MX such that, writing X additively, A(i+x,j+x)= A(i,j)for all i,j,x in X ). It is well known (see Section 5.1) that there exist dualities9:AX →AX, and, for any such duality9,(A, 9(A))is a dual pair.
(ii) Not every Bose-Mesner algebraAadmits a dual Bose-Mesner algebraB. Indeed a duality from A toB sends the basis of ordinary idempotents ofA to the basis of Hadamard idempotents of B. By comparing (9) and (14) one sees that the Krein parameters of Amust correspond to the intersection numbers of B, and hence be integers, which is not true in general.
(iii) It is clear from (5), (7), (8) and (9) that pi j0 6=0 iff j=i0. It easily follows that every Bose-Mesner isomorphism commutes with the transposition map. Similarly, since the trace of EiEj equals the sum of entries of Ei ◦ tEj, and the sum of entries of Ei is δ(i,0)|X|by (12), we obtain from (13) and (14) that qi j0 6=0 iff j = ˆi . This implies that every duality commutes with the transposition map.
Finally, let9 :A→ Abe a duality. To conform to the standard terminology, we shall call it a duality ofAonly if92= |X|τA, whereτAis the transposition map onA. We shall say thatAis self-dual if it has a duality in this sense.
Remark We do not know any example of a Bose-Mesner algebraAwhich is not self-dual but has a duality9:A→A. The question of the existence of such examples is raised by A. Munemasa in [16].
2.2. Spin models for link invariants
In [21], Vaughan Jones has introduced a construction of invariants of links in 3-space based on the statistical mechanical concept of spin model. The main idea is to represent every link by a connected plane diagram whose regions are colored black or white in such a
way that adjacent regions receive different colors. Then one defines states of the diagram as mappings from the set of black regions to some fixed finite set X of spins. There are two types of crossings, positive and negative, and each one is assigned a weight matrix W+or W−in MX. For every stateσ and crossingvincident with the black regions r , r0, lethσ | vi = W±(σ (r), σ (r0))be the local weight ofσ atv. Lethσi = Q
vhσ | vibe the weight ofσ, where the product is over all crossings. Then the partition function Z is P
σhσi, where the sum is over all states.
It is shown in [21] that if the matrices W+, W−satisfy certain invariance equations, then, after suitable normalization, Z defines a link invariant. The construction in [21] assumes that W+, W−are symmetric. This restriction was removed in [26], which gives the following invariance equations:
(15) (i) W+◦I =a I , J W+=W+J=Da−1J . (ii) W−◦I =a−1I , J W−=W−J =Da J . (16) W+W− = |X|I , W+◦ tW−=J .
(17) For everyα,β,γ in X , X
x∈X
W+(x, α)W+(x, β)W−(γ,x)=DW+(α, β)W−(β, γ )W−(γ, α),
where a∈C∗and D2= |X|.
Remarks
(i) When W+, W−are symmetric, this reduces to the invariance equations in [21].
(ii) Assuming (16), Eq. (17) is equivalent to other similar equations usually chosen to define spin models (see [26], Proposition 2.1).
(iii) (16) and (17) imply that (15) holds for some a∈C∗.
We shall also refer to (15), (16) and (17) as the type I, type II and type III conditions respectively, since they correspond to Reidemeister moves of these types (see [21, 26]).
The types also correspond to the degrees of the equations in terms of the entries of W+, W−. It will be convenient to reformulate the above equations in terms of W=W+alone.
In particular, we shall say that a matrix W in MX with non-zero entries is a type II matrix if it satisfies one of the following conditions, each of which is equivalent with (16) for W+=W :
(18) (i)P
x∈X W(b,x)
W(c,x) = |X|δ(b,c) for all(b,c)in X , (ii)P
x∈X W(x,b)
W(x,c) = |X|δ(b,c) for all(b,c)in X .
2.3. Spin models and commuting squares
Let DXconsist of all diagonal matrices in MX and let W be an invertible matrix in MX. We consider the following square
DX ⊂ MX
∪ ∪
C ⊂W−1DXW
which is a diagram of inclusions of algebras under the matrix product (here C is identified with the algebra of scalar matrices). MXis endowed with the normalized trace tr : MX →C, with tr(A) = (1/|X|)Trace(A). Then the above square is commuting (we describe here a particular case of a very general object—see [12, 1]) if tr(A B)=tr(A)tr(B)for every A∈ DX, B∈W−1DXW . This situation can also be described in terms of orthogonal pairs of algebras (see [14], Section 1.5 of [27, 28]). An easy computation shows that the square is commuting if and only if W−1(i,j)W(j,i)=(1/|X|)for all i,j in X , that is if and only if W is a type II matrix.
The case when W is unitary is of special importance for the study of subfactors in the theory of Von Neumann algebras (see [1, 12, 23]). This occurs exactly when all entries of W have absolute value 1/√
n, where n= |X|. 3. A dual pair of Bose-Mesner algebras
3.1. Construction of the dual pair
Let W be a type II matrix in MX. We introduce for each pair(b,c)∈ X×X two column vectors Ybcand Ybc0 indexed by X and defined as follows:
(19) Ybc(x)= WW((xx,,bc)), (20) Ybc0(x)= WW((bc,,xx)). Let
N(W)= {A∈ MX |Ybcis an eigenvector of A for all b,c∈ X}, and
N0(W)= {A∈MX |Ybc0 is an eigenvector of A for all b,c∈ X }.
Note that N0(W)=N(tW). In the sequel we write N for N(W), N0for N0(W). For every A in N , let9(A)∈ MX be defined by
(21) AYbc =(9(A))(b,c)Ybcfor all(b,c)∈X×X .
Similarly, for every A0in N0, we define90(A0)∈ MX by (22) A0Ybc0 =(90(A0))(b,c)Ybc0 for all(b,c)∈ X×X .
We denote byτN(respectively,τN0) the restriction of the transposition map to N (respec- tively, N0).
Theorem 1 N and N0are Bose-Mesner algebras. Moreover, 9(N)=N0, 90(N0)=N, and9 : N → N0, 90 : N0 → N are dualities such that909 = |X|τN, 990 = |X|τN0. Hence (N,N0)is a dual pair of Bose-Mesner algebras. Moreover when N = N0 and 9 =90,N is a self-dual Bose-Mesner algebra.
Proof: It is clear from (21) that N is a vector subspace of MX and that9 : N → MX is a linear map. We observe that
(23) For every c in X ,{Ybc|b∈ X}is a basis of column vectors.
Indeed, the matrix with (x,b)-entry equal to Ybc(x)is 1W , where 1 = Diag[1/W (x,c)]x∈X, and both1and W are invertible.
It follows that9is injective.
Note that I belongs to N , with9(I)= J .
Moreover, the type II property (18(ii)) can be written J Ybc = |X|δ(b,c)1, where 1 is the all-one column vector. Since Ybb =1 for every b in X , this means that J belongs to N , with9(J)= |X|I .
Let now A, B be two matrices in N . It is immediate from (21) that, for every(b,c)in X×X ,
A BYbc=B AYbc=(9(A))(b,c)(9(B))(b,c)Ybc.
This, together with (23), shows that N is a commutative algebra under matrix product, and that9(A B)=9(A)◦9(B).
We now show that9(N)⊆N0.
For A in N and a, b, c in X the a -entry of9(A)Ybc0 is (9(A)Ybc0 )(a)=X
x∈X
(9(A))(a,x)W(b,x) W(c,x).
By (21),(9(A))(a,x)Yax =AYax, and by considering c-entries we obtain (9(A))(a,x)W(c,a)
W(c,x) =X
y∈X
A(c,y)W(y,a) W(y,x) and hence
(9(A))(a,x)W(b,x) W(c,x) =X
y∈X
A(c,y)W(y,a)W(b,x) W(c,a)W(y,x).
It follows that
(9(A)Ybc0 )(a)=X
y∈X
A(c,y)W(y,a) W(c,a)
ÃX
x∈X
W(b,x) W(y,x)
!
=X
y∈X
A(c,y)W(y,a)
W(c,a)|X|δ(b,y) (by (18)(i))
= |X|A(c,b)W(b,a)
W(c,a) = |X|A(c,b)Ybc0 (a).
Thus9(A)Ybc0 = |X|A(c,b)Ybc0 .
This shows that9(A)∈N0with90(9(A))= |X|tA.
Replacing W bytW , we see that all results obtained so far are also valid if we interchange N and N0. Let us sum up these results.
(i) N , N0are vector subspaces of MX containing I , J . (ii) 9 : N → N0and90: N0→N are linear injective maps.
(iii) N , N0are commutative algebras under matrix product,9(A B)=9(A)◦9(B)( A, B in N ), and90(A0B0)=90(A0)◦90(B0)( A0, B0in N0).
(iv) 90(9(A))= |X|tA for A in N ,9(90(A0))= |X|tA0for A0in N0. By (ii), both9and90are bijective.
Let A, B belong to N . There exists A0, B0in N0such that A=90(A0), B =90(B0). By (iv) we have9(A)= |X|tA0,9(B)= |X|tB0. Now, by (iii), A◦ B=90(A0)◦90(B0)= 90(A0B0)belongs to N . Thus N (and similarly N0) is closed under Hadamard product.
Also note that by (iv) tA= |X|−190(9(A))belongs to N . Thus N (and similarly N0) is closed under transposition.
It follows that N and N0are Bose-Mesner algebras. By (iv),909 = |X|τN,990 =
|X|τN0. Finally,
9(A◦B)=9(90(A0B0))= |X|t(A0B0)= |X|t(B0A0)
= 1
|X|(|X|tA0)(|X|tB0)= 1
|X|9(A)9(B)
shows, together with (iii), that9 (and similarly90) is a duality. Thus(N, N0)is a dual pair. If N =N0and9 =90,92= |X|τN and N is self-dual. 2 Remarks
(i) We do not know if N =N0is a sufficient condition for the self-duality of N (see the remark at the end of Section 2.1).
(ii) The idea of the construction of Theorem 1 comes from [31]. Actually, Theorem 1 generalizes the main result of [31] which states that (for symmetric W ) the set of symmetric matrices in N(W)is a symmetric Bose-Mesner algebra.
(iii) The algebra N0has an interesting interpretation in the context of commuting squares.
A commuting square associated with a type II matrix has a certain Markovian property which allows the application of the basic construction to this square. This construction produces an infinite grid of commuting squares, with the initial square situated in the left and lowest corner. Our algebra N0can be described in terms of this initial square and the adjacent one on its right:
DX =A1,0 ⊂ MX =A1,1 ⊂ A1,2
∪ ∪ ∪
C=A0,0 ⊂ W−1DXW =A0,1 ⊂ A0,2
The second relative commutant associated with the initial square is the algebra A01,0∩A0,2= {a∈ A0,2|ab=ba for all b∈ A1,0}
(note that ab and ba are well defined elements of A1,2). It is shown in [1] that this second relative commutant can be identified with the subalgebra N0 = N0(W)of MX via some appropriate isomorphism. As a consequence, some of the results and examples to follow may have some interest in the study of towers of algebras and subfactors (see [23]).
3.2. Equivalences and the symmetric case
If W is a type II matrix and1,10are invertible diagonal matrices in MX, clearly1W10is also a type II matrix, and we shall say that this matrix is obtained from W by scaling.
In the sequel, W1and W2are type II matrices.
Proposition 2 If W2is obtained from W1by scaling,N(W2)= N(W1)and N0(W2)= N0(W1).
Proof: The effect of scaling on each vector Ybc or Ybc0 defined by (19) and (20) is a
multiplication by a non-zero scalar. 2
Now if P, P0are permutation matrices in MX, P W P0is also a type II matrix, and we shall say that it is obtained from W by permutation.
Proposition 3 If W2 is obtained from W1 by permutation, N(W2) is combinatorially isomorphic to N(W1)and N0(W2)is combinatorially isomorphic to N0(W1).
Proof: There exist permutations α, β of X such that W2(x,y) = W1(α(x), β(y)). For all x, b, c in X , let
Ybci (x)= Wi(x,b)
Wi(x,c), (i =1,2).
Thus Ybc2(x)=Yβ(1b)β(c)(α(x)). Hence there exists a permutation matrix P such that
©Ybc2 ¯¯(b,c)∈X×Xª
=©
PYbc1 ¯¯(b,c)∈X×Xª .
It follows that N(W2) = P N(W1)P−1, so that N(W2)is combinatorially isomorphic to N(W1). Working with tW1 andtW2 we also obtain that N0(W2)is combinatorially
isomorphic to N0(W1). 2
Remarks
(i) The equivalence of type II matrices generated by scaling and transposition corresponds to a natural notion of isomorphism of commuting squares [12]. Propositions 2 and 3 give only a special case of the result that higher relative commutants are invariants of commuting squares [12].
(ii) If W has entries±1, it is a Hadamard matrix. It is easy to see that in this case the equivalence generated by scaling and permutation corresponds to the usual notion of Hadamard equivalence. Hence the combinatorial types of N(W)and N0(W)are invariants of Hadamard matrices W under Hadamard equivalence.
Assume now that W is a symmetric type II matrix. Thus Ybc=Ybc0 for every b, c in X . Hence N = N0 and9 = 90. As a consequence of Theorem 1 and of the proof of Proposition 2, we obtain:
Proposition 4 If a type II matrix W is obtained from some symmetric matrix by scaling, N(W)=N0(W)is a self-dual Bose-Mesner algebra.
A matrix W is symmetrizable if it can be obtained from some symmetric matrix by scaling (this definition is clearly equivalent to the one given in Section 2.1 of [24]). It is easy to see that a matrix is symmetrizable iff it can be obtained from its transpose by some scaling (which must be conjugation by a diagonal matrix).
3.3. Graph descriptions of the dual pair
Let W be a type II matrix in MX. The following idea was first introduced by Vaughan Jones [22]. We shall associate with W two undirected graphs G and H on the vertex set X×X and use them to describe the dual pair(N,N0). These graphs will have no multiple edges (but possibly loops) and two vertices (possibly equal) will be said to be adjacent if they are joined by an edge.
Given two column vectors T , T0indexed by X , we writehT, T0ifor their usual scalar productP
x∈XT(x)T0(x), andhhT,T0iifor their Hermitian productP
x∈XT(x)T0(x)= hT,T0i.
Two vertices (b,c),(d,e)will be adjacent in G (respectively, H ) iffhYbc,Ydei 6= 0 (respectively,hhYbc,Ydeii 6=0). Thus H has a loop incident with every vertex, and G may have loops incident with some vertices. We denote by G2the (proper) squared graph of G:
two vertices are adjacent in G2if there is a vertex to which they are both adjacent in G (this implies the existence in G2of a loop incident with every non-isolated vertex of G).
Let C1,. . ., Cp(respectively, K1,. . ., Kq; L1,. . ., Lr) be the connected components of G (respectively, G2; H ).
Let A(Ci)(respectively, A(Ki); A(Li)) be the matrix in MX with(b,c)-entry equal to 1 if(b,c)∈Ci(respectively, Ki; Li) and to 0 otherwise.
Let V(Ci)(respectively, V(Ki); V(Li)) be the C -linear span of the set of vectors Ybc such that(b,c)belongs to Ci(respectively, Ki; Li). We denote by V the space of column vectors indexed by X .
Theorem 5
(i) V = ⊕ip=1V(Ci). Let E(Ci) (i =1, . . . ,p)be the matrices in MX,which represent the projections V →V(Ci)in the canonical basis of V . Then{E(Ci)|i =1, . . . ,p} is the basis of ordinary idempotents of N˜,and{A(Ci)|i=1, . . . ,p}is the basis of Hadamard idempotents ofN˜0.
(ii) V = ⊕qi=1V(Ki). Let E(Ki) (i =1, . . . ,q)be the matrices in MX which represent the projections V →V(Ki)in the canonical basis of V . Then{E(Ki)|i =1, . . . ,q} is the basis of ordinary idempotents of N,and{A(Ki)|i =1, . . . ,q}is the basis of Hadamard idempotents of N0.
(iii) V = ⊕ri=1V(Li). Let E(Li) (i = 1, . . . ,r)be the matrices in MX which represent the projections V →V(Li)in the canonical basis of V . Then{E(Li)|i=1, . . . ,r} is the basis of ordinary idempotents of N,and{A(Li)|i =1, . . . ,r}is the basis of Hadamard idempotents of N0.
As a consequence,q =r≥ p with full equality if and only if N is symmetric.
Proof: By (23),{Ybc|(b,c)∈X×X}spans V , and hence V =
Xp i=1
V(Ci)= Xq
i=1
V(Ki)= Xr
i=1
V(Li).
Let us show that these sums are direct. Note that by definition the V(Ci)are mutually orthogonal with respect to the usual scalar product, and the V(Li)are mutually orthogonal with respect to the Hermitian product. Since these products are non-degenerate,
V(Ci)∩X
j6=i
V(Cj)= {0} and V(Li)∩X
j6=i
V(Lj)= {0}
for all i , and hence V = ⊕ip=1V(Ci)= ⊕ri=1V(Li).
Let us now relate the connected components of G2with those of G.
If a connected component of G is non-bipartite (this occurs for instance if some vertex is incident with a loop), any two of its vertices can be joined in G by a path of even length (possibly with repeated vertices and edges) and hence it also defines a connected component of G2.
On the other hand, a bipartite connected component of G splits into two connected components of G2, each one corresponding to an independent set in G. Let Ki, Kj be
two connected components of G2corresponding in this way to a bipartition of a connected component Ck of G. Since Ki is independent in G, V(Ki)is orthogonal to itself with respect to the usual scalar product, and similarly for V(Kj). Hence, V(Ki)∩V(Kj)is orthogonal to V(Ck), and also to⊕`6=kV(C`). It follows that V(Ki)∩V(Kj)= {0}and V(Ck)=V(Ki)⊕V(Kj). We conclude that V = ⊕qi=1V(Ki).
It is clear from their definition that the E(Ci) (respectively, E(Ki); E(Li)) are orthogonal idempotents in MX. These idempotents belong to N , since E(Ci)Ybc = Ybc if(b,c) ∈ Ci, E(Ci)Ybc = 0 otherwise, and similarly for E(Ki)and E(Li). This also shows that 9(E(Ci)) = A(Ci), 9(E(Ki)) = A(Ki), 9(E(Li)) = A(Li). Then, in view of Theorem 1, the proof of Theorem 5 will be completed if we show that each of {E(Ki)|i =1, . . . ,q}and{E(Li)|i=1, . . . ,r}spans N , and that{E(Ci)|i=1, . . . ,p} spans N (the equality˜ 9(N˜)= ˜N0comes from the equality9τN =τN09 which follows immediately from Theorem 1—see also Remark (iii) in Section 2.1).
Note that
hYbc, Ycbi =X
x∈X
W(x,b)
W(x,c)· W(x,c)
W(x,b) = |X| 6=0
for every(b,c)in X×X and hence each A(Ci)is symmetric. It follows that E(Ci)∈ ˜N for i =1, . . . ,p (using again the equality9τN =τN09).
If(b,c)and(d,e)are adjacent vertices of G, for every matrix A in N , 9(A)(b,c)hYbc,Ydei = hAYbc,Ydei = hYbc,tAYdei
=(9(tA))(d,e)hYbc,Ydei
implies that9(A)(b,c)=9(tA)(d,e).
In particular, if A∈ ˜N ,9(A)(b,c)=9(A)(d,e)whenever(b,c)and(d,e)belong to the same connected component of G. It follows that9(A)belongs to the linear span of the A(Ci), i=1, . . . ,p, and hence A belongs to the linear span of the E(Ci), i=1, . . . ,p.
In general, 9(A)(b,c) = 9(A)(d,e)whenever(b,c)and(d,e)belong to the same connected component of G2. Then the same argument shows that every matrix A in N belongs to the linear span of the E(Ki), i=1, . . . ,q.
Finally, if(b,c)and(d,e)are adjacent vertices in H , for every matrix A in N , 9(A)(b,c)hhYbc,Ydeii = hhAYbc,Ydeii = hhYbc,tAYdeii
=(9(tA))(d,e)hhYbc,Ydeii
implies that9(A)(b,c)=9(tA)(d,e). Now9(tA)=9(A)for every A in N , as can be easily checked by expressing A in the basis of ordinary idempotents and using (13) and the fact that Hadamard idempotents are real.
It follows that9(A)(b,c)=9(A)(d,e)whenever(b,c)and(d,e)belong to the same connected component of H . Hence A belongs to the linear span of the E(Li), i=1, . . . ,r . 2
It is clear from the above proof that N is non-symmetric if and only if some component of G splits into two components of G2, or equivalently into two components of H . Moreover in such a splitting there exist b, c in X such that(b,c)is in one of the new components and (c,b)is in the other. Hence we obtain the following result.
Proposition 6 N is non-symmetric if and only if G has a bipartite connected component.
Moreover,if N is non-symmetric,there exist b,c in X such that the following properties hold:
(i) X
x∈X
W(x,b)2
W(x,c)2 =0, X
x∈X
W(x,c)2 W(x,b)2 =0 (ii) X
x∈X
W(x,b)W(x,c) W(x,c)W(x,b)=0
Consequently,if W is a real matrix,N is symmetric.
Proof:
(i) is equivalent tohYbc,Ybci = hYcb,Ycbi =0, i.e., to the fact that there is no loop in G incident to(b,c)or(c,b). This must hold if(b,c)and(c,b)are not adjacent in G2, since they are adjacent in G.
(ii) is equivalent tohhYbc,Ycbii =0, i.e., to the fact that(b,c)and(c,b)are not adjacent in
H . 2
Remark When all entries of W have the same absolute values (i.e., W is unitary up to a factor) (i) and (ii) are equivalent.
Remark As suggested by one of the referees, we might have defined type II matrices with different sets of rows and columns. However, the type III condition can be defined only if we identify these sets. For the sake of simplicity, we choose the same set X for both rows and columns. Here we state briefly what occurs if we distinguish the set X of rows and the set X0of columns with the same cardinality. We regard W as a linear map from C[X ] to C[X0], where C[X ] denotes the vector space with basis X . Then, the type II condition becomes the existence of W−∈Hom(C[X0],C[X ])such that
W ◦ tW−= J ∈Hom(C[X ],C[X0]) W W−=n·I ∈Hom(C[X0],C[X0]).
Now N(W) is a subalgebra of Hom (C[X0],C[X0]) and N0(W) is a subalgebra of Hom(C[X ], C[X ]), which are dual to each other. Every result in Sections 3 and 4 that uses only the type II condition for W is still valid. On the contrary, any statement con- cerning the type I, III conditions or symmetricity of W , like Propositions 4, 8–10, 12, and Theorem 11, requires an identification of X and X0.
4. Some applications
4.1. Tensor products
Given two finite sets X1, X2, we consider the bilinear map from MX1×MX2 to MX1×X2 which associates with A1∈ MX1, A2∈MX2their Kronecker product A1⊗A2defined by:
A1⊗A2((x1,x2), (y1,y2))=A1(x1,y1)A2(x2,y2) for all x1,y1∈X1,x2,y2∈X2. This establishes an isomorphism of vector spaces between MX1×X2and the tensor product MX1 ⊗MX2 and legitimates the use in what follows of the symbol ⊗for the Kronecker product of matrices as well as for the tensor product of vector spaces of matrices.
We note that ifA1,A2are Bose-Mesner algebras in MX1, MX2respectively, thenA1⊗A2
(which is the linear span of the matrices A1⊗A2, A1 ∈ A1, A2 ∈A2) is a Bose-Mesner algebra in MX1×X2since(A1⊗A2)(B1⊗B2)=(A1B1)⊗(A2B2),(A1⊗A2)◦(B1⊗B2)= (A1◦B1)⊗(A2◦B2)andt(A1⊗A2)=tA1⊗tA2for every A1, B1inA1and A2, B2inA2. Let now W1 ∈ MX1, W2 ∈ MX2 be two type II matrices. It is easy to check that W =W1⊗W2is also a type II matrix.
Using formula (19), we associate with W , W1, W2 the vectors Y(b1,b2)(c1,c2), Yb1
1c1, Yb2
2c2
respectively, for all b1, c1in X1and b2, c2in X2. Proposition 7
(i) N(W)=N(W1)⊗N(W2).
(ii) Ng(W)6=Ng(W1)⊗Ng(W2)if and only if both N(W1)and N(W2)are non-symmetric.
Proof: It follows immediately from (19) that Y(b1,b2)(c1,c2)((x1,x2))=Yb1
1c1(x1)Yb2
2c2(x2).
Hence, for every A1∈ N(W1), A2∈N(W2), Y(b1,b2)(c1,c2)is an eigenvector of A1⊗A2. This implies that N(W1)⊗N(W2) ⊆ N(W)andNg(W1)⊗Ng(W2)⊆ Ng(W). Let G, H be the graphs associated with W as in Section 3.3 and let Gi, Hi (i = 1,2) be the corresponding graphs for W1, W2. Clearly
Y(b1,b2)(c1,c2),Y(d1,d2)(e1,e2)®
= Yb1
1c1,Yd1
1e1
®Yb2
2c2,Yd2
2e2
® and similarly for the Hermitian producthh,ii.
Hence((b1,b2), (c1,c2)),((d1,d2), (e1,e2))are adjacent in G (respectively, H ) if and only if (b1,c1), (d1,e1)are adjacent in G1 (respectively, H1) and (b2,c2), (d2,e2) are adjacent in G2(respectively, H2).
If we identify each vertex((b1,b2), (c1,c2))of G with the pair((b1,c1), (b2,c2))formed with one vertex of G1and one vertex of G2we see that G is the categorical product G1·G2 of G1and G2(see [34]). Similarly H =H1·H2.
We shall need the following graph-theoretical result (see [34]): the categorical product of two connected graphs is disconnected if and only if each of these graphs is bipartite. From
