Type II Matrices and Their Bose-Mesner Algebras

Type II Matrices and Their Bose-Mesner Algebras

RIE HOSOYA [email protected]

Graduate School of Natural Science and Technology, Kanazawa University, Kakuma-machi, Kanazawa-shi, Ishikawa 920-1192, Japan

HIROSHI SUZUKI^∗ [email protected]

Department of Mathematics, International Christian University, 10-2, Osawa 3-chome, Mitaka-shi Tokyo 181-8585, Japan

Received October 24, 2000; Revised July 16, 2002

Abstract. Type II matrices were introduced in connection with spin models for link invariants. It is known that a pair of Bose-Mesner algebras (called a dual pair) of commutative association schemes are naturally associated with each type II matrix. In this paper, we show that type II matrices whose Bose-Mesner algebras are imprimitive are expressed as so-called generalized tensor products of some type II matrices of smaller sizes. As an application, we give a classification of type II matrices of size at most 10 except 9 by using the classification of commutative association schemes.

Keywords: type II matrix, spin model, Bose-Mesner algebra

1. Introduction

Throughout this paperM[i,j] denotes the (i,j)-entry of a matrixM andu[h] denotes the h-th entry of a vectoru.Let M be an m×n matrix whose entries are all nonzero. We associate ann×mmatrixM⁻defined by the following.

M⁻[i,j]= 1 M[j,i].

LetIdenote the identity matrix and let Jdenote the all 1 square matrix of suitable size.

Let Matn(C) denote the set ofn×n complex matrices. W ∈ Matn(C) is said to be a type II matrixifWW⁻ =nI. It is clear that ifW is a type II matrix, then the transpose^tW of the matrix andW⁻are type II matrices as well. Hence for a matrixW ∈Matn(C) whose entries are nonzero, we have the following.

WW⁻=n·I ⇔ n h=1

W[i,h]

W[j,h] =δi,j·n for all 1≤i,j ≤n

⇔ n h=1

W[h,i]

W[h,j] =δi,j·n for all 1≤i,j ≤n

⇔W⁻W =n·I.

∗This research was partially supported by the Grant-in-Aid for Scientific Research (No. 12640039), Japan Society of the Promotion of Science.

The definition of type II matrices was first introduced explicitly in the study ofspin models. See [1, 3, 4, 6–9, 13] for details.

Example 1.1

(1) Letζ be a primitiven-th root of 1. Then the matrixW =W(Zn)∈Matn(C) defined byW[i,j]=ζ^{(i−1)(j−1)}is a type II matrix.W(Zn) is called acyclic type II matrixof sizen.

(2) Letαbe a root of the quadratic equationt²+nt+n=0. Then the matrixW ∈Matn(C) defined byW[i,j]=1+δi,jαis a type II matrix.W is called aPotts type II matrixof sizen.

LetW ∈Matn(C) be a type II matrix. IfS,S∈Matn(C) are permutation matrices and D,D ∈ Matn(C) are nonsingular diagonal matrices, then it is easy to see thatSDWDS is also a type II matrix (See Section 2). We say that two type II matricesW andWare type II equivalentifW=SDWDSfor suitable choices of permutation matricesS,Sand diagonal matrices D,D. It is clear that this defines an equivalence relation on the set of type II matrices.

For a type II matrixW ∈ Matn(C) and for 1 ≤ i,j ≤ n, we define ann-dimensional column vectoru^W_i,j by the following.

u_i^W_,j[h]= W[h,i] W[h,j]. Let

N(W)=

M ∈Matn(C)u_i^W_,jis an eigenvector forMfor all 1≤i,j≤n . It is known thatN(W) is the Bose-Mesner algebra of a commutative association scheme.

N(W) is called aNomura algebra. Moreover, there exists a duality map from N(W) to N(^tW).N(^tW) is called thedualofN(W). We often sayN(W) has a dual (See Section 2).

We are interested in determining type II matrices of small sizes. Type II matrices at most size 5 have been completely determined (See [7, 14]). We are also interested in the Bose- Mesner algebras which appear as the Nomura algebras of type II matrices. Type II matrices whose Nomura algebras are Span(I,J) are difficult to determine. On the other hand, in the classification of spin models, we do not need to determine type II matrices of this case [15].

In this paper we consider the caseN(W)=Span(I,J).

LetU1,U2, . . . ,Umbe square matrices of sizen, and letV1,V2, . . . ,Vnbe square matrices of sizem. Let ˜W =(U1,U2, . . . ,Um)⊗(V1,V2, . . . ,Vn) be a square matrix of sizemn such that the (i,j)-block ˜W[[i],[j]] is defined by the following.

W˜[[i],[j]]=i,jVj,

wherei,j[h,k] = δh,kUh[i,j] (i,j = 1, . . . ,n andh,k = 1, . . . ,m). We call ˜W the generalized tensor productofU1,U2, . . . ,UmandV1,V2, . . . ,Vn.In Lemma 4.1, we show

that ifU1,U2, . . . ,UmandV1,V2, . . . ,Vn are type II matrices, then ˜W is a type II matrix.

We are informed by K. Nomura that the special case of this result was already noticed by V.F.R. Jones. K. Nomura and U. Haagerup also considered some special cases of this result [5, 12].

Now we state our main result.

Theorem 1.1 Let W be a type II matrix of size mn.Let Jnbe the all1matrix of size n≥2, and let Imbe the identity matrix of size m≥2.Then the following are equivalent.

(i) There exists a permutation matrix S such that Jn⊗Im∈N(SW).

(ii) N(W)is an imprimitive Bose-Mesner algebra with a system of imprimitivity having blocks of size n.

(iii) W is type II equivalent to a generalized tensor product(U1,U2, . . . ,Um)⊗(V1,V2, . . . ,Vn),where U1,U2, . . . ,Umand V1,V2, . . . ,Vnare type II matrices of size n and m respectively.

According to the classification of commutative association schemes [11] and considering the fact thatN(W) has a dual, for type II matrices of size at most 10,one of the following holds.

(a) N(W) is a Bose-Mesner algebra of an imprimitive association scheme.

(b) dimN(W)=3 orpforW of size p=5,7,9.

(c) N(W)=Span(I,J).

Applying Theorem 1.1 to the case of (a),W is expressed as a generalized tensor product of type II matrices of size at most 5.Moreover, the following hold.

Theorem 1.2 Let W be a type II matrix of size at most8 or size10.Then one of the following holds.

(i) N(W)=Span(I,J).

(ii) W is type II equivalent to a cyclic type II matrix.

(iii) W is type II equivalent to a generalized tensor product of type II matrices of smaller sizes.

Recently, T. Matsumura [10] showed that there is no type II matrix W such that dimN(W) = 3.According to his result, the above theorem is true for the case of size 9.As for the results concerning small four-weight spin models, the reader is referred to [4, 15].

2. Preliminary results

LetWbe a type II matrix. Then we can define a mapping =WfromN(W) to Mat_n(C) by the following.

Mu^W_i,j=(M)[i,j]u^W_i,j forM ∈N(W),

i.e., the (i,j)-entry of(M) is the eigenvalue of M associated with the eigenvectoru^W_i,j. The mapis called theduality map.

Proposition 2.1 Let W be a type II matrix inMatn(C). Then the following hold.

(1) For all1≤i ≤n,the set of vectors{u^W_i,j |1≤ j ≤n}is linearly independent.

(2) N(W)is the Bose-Mesner algebra of a commutative association scheme.

(3) The duality map =W is a linear isomorphism fromN(W)toN(^tW)=N(W⁻) satisfying the following conditions.

(a) (I)= J and(J)=nI.

(b) (MN)=(M)◦(N)for all M,N ∈N(W).

(c) (M◦N)=(1/n)(M)(N)for all M,N ∈N(W).

(4) Let=^tW. Then for every M∈N(W),we have((M))=n^tM.

Proof: All assertions can be found in [7, Theorem 1]. (1) is the statement (23) in its proof.

✷ Let B denote the Bose-Mesner algebra of a commutative association scheme X = (X,{Ri}0≤i≤d). Then there are two canonical bases. One of them is the set ofadjacency(or associate)matrices{A0=I,A1, . . . ,Ad}satisfyingAi◦Aj =δi,jAi, and the other is the set ofprimitive idempotents{E0=(1/|X|)J,E1, . . . ,Ed}satisfyingEiEj=δi,jEi. Let

Ai = d

j=0

pi(j)Ej, Ei= 1

|X| d

j=0

qi(j)Aj.

The base change matrices P withP[i,j]= pj(i) andQwithQ[i,j]=qj(i) are called the first eigenmatrix andthe second eigenmatrixrespectively. For the general theory of commutative association schemes and that of Bose-Mesner algebras, the reader is referred to the excellent monograph [2].

LetW ∈Matn(C) be a type II matrix. We use the following notation. LetX (resp.X) be a commutative association scheme with the Bose-Mesner algebraN(W) (resp.N(^tW)).

Let A0,A1, . . . ,Ad be the adjacency matrices inN(W), and let E0,E1, . . . ,Ed be the primitive idempotents. By the previous proposition, the dimensions ofN(W) andN(^tW) are equal. Let A₀,A₁, . . . ,A_dbe the adjacency matrices inN(^tW), and letE₀,E₁, . . . ,E_d be the primitive idempotents. Let =W and=^tW.

Corollary 2.2 Let W∈Matn(C)be a type II matrix. Then,by a suitable arrangement of indices,the following hold.

(1) (Ai)=nE_iand(Ei)= A_i. (2) (E_i)=^tAi and(A_i)=n^tEi.

(3) The first eigenmatrix P of X is the second eigenmatrix Q of X and the second eigenmatrix Q ofXis the first eigenmatrix PofX.

Remarks In this paper, we use the above ordering of the idempotents so that P = Q, although it is customary to use the standard ordering of them so thatP =Q¯.

Proposition 2.3 Let W be a type II matrix inMatn(C),let∈Matn(C)be a nonsingular diagonal matrix,and let S be a permutation matrix such that S[x,y]=δσ(x),y,whereσis a permutation on X = {1,2, . . . ,n}. Then the following hold.

(1) u^W_x,y=u_x,^W_y = ^[y_[x^,_,^y]_x]u^W_x,y.

(2) u^{W S}_x,y =u^W_{σ−1(x),σ−1(y)},andu_x^SW_,y =Su^W_x,y. (3) W,W,SW and WS are type II matrices.

(4) N(W)=N(W)=N(W)=N(WS)and SN(W)^tS=N(SW).

(5) WS(M)=^tSW(M)S for M ∈N(WS)=N(W).

Proof: Straightforward. See also [7, Section 3.2]. ✷ Remarks Two Bose-Mesner algebrasBandBin Matn(C) arecombinatorially isomor- phicif there exists a permutation matrixSin Mat_n(C) such thatB=SB^tS.Hence by (4) in the above proposition the Bose-Mesner algebrasN(W),N(W),N(W),N(WS) and N(SW) are all combinatorially isomorphic.

3. Type II matrices

In this section, we prove several results which will be useful to determine type II matrices W when a Bose-Mesner algebra contained inN(W) is given.

Proposition 3.1 Let W ∈Matn(C)be a type II matrix. LetBbe the Bose-Mesner algebra of a commutative association scheme contained inN(W),and let A0,A1, . . . ,Ad be its adjacency matrices and E0,E1, . . . ,Ed be its primitive idempotents, which satisfy the conditions(1)–(3)in Corollary2.2. Let V =Cⁿand Vi =EiV . Suppose

Ai = d h=0

pi(h)Eh, Ei = 1 n

d h=0

qi(h)Ah.

Then the following hold.

(1) Let=⁽_i^j)= {h|u^W_h,j∈Vi}. If Al[s,t]=1,then W[t,j]

W[s,j]

h∈

W[s,h]

W[t,h] =n·Ei[s,t]=qi(l).

(2) Let=i^(j)= {h | Ai[h,j]=1}and let =W. Ifu^W_s,t∈Vl,then W[j,s]

W[j,t]

h∈

W[h,t]

W[h,s] =(Ai)[s,t]= pi(l). (3) Let^tEi=Eˆı. Thenu^W_s,t ∈Vi if and only ifu^W_t,s∈Vˆı.

Lemma 3.2 Let =W be the duality map fromN(W)toN(^tW). Then the following hold.

(1) u^t_s^W_,t =u^W_t,s⁻for every1≤s,t ≤n.

(2) Eiu^W_s,t=u_s^W_,t if and only if(Ei)[s,t]=1.

(3) (Ai)u^t_s^W_,t =nu^t_s^W_,tif and only if Ai[t,s]=1.

(4) For M∈N(W),(^tM)=^t(M).

Proof: All of the assertions are clear from the definitions and Corollary 2.2. The last assertion is a consequence of the following.

(^tM)= 1

n(((M))=^t(M),

by Corollary 2.2. ✷

Proof of Proposition 3.1: Let =W and=^tW.

(1) Since((^tEi))=n·Ei, we compute(^tEi)u^t_s^W_,t. Note that(^tEi) is a (0,1) matrix as it is an idempotent with respect to a ◦-product. (^tEi)[j,h] = ^t(Ei)[j,h] = 1 if and only if(Ei)[h,j] = 1. On the other hand,(Ei)[h,j] = 1 if and only if Eiu^W_h,j =u^W_h,j,i.e.,(Ei)[h,j]=1 if and only ifh ∈⁽i^j) =.Hence, we have the following.

n·Ei[s,t]W[s,j]

W[t,j] = _t

Ei

u^t_s^W_,t [j]

= n h=1

_t Ei

[j,h]u^t_s^W_,t[h]

= n h=1

_t Ei

[j,h]W[s,h]

W[t,h]

=

h∈

W[s,h]

W[t,h]. This proves (1).

(2) Since((^tAi))=n·AiandAi[h,j]=1 if and only ifh∈, we have the following.

h∈

W[h,t]

W[h,s] = n h=1

Ai[h,j]W[h,t] W[h,s]

= n h=1

tAi[j,h]W[h,t] W[h,s]

= 1 n

n h=1

((Ai))[j,h]W[h,t] W[h,s]

= 1 n

((Ai))u_t^W_,s [j]

= 1

n(((Ai)))[t,s]W[j,t]

W[j,s]

=^t(Ai)[t,s]W[j,t]

W[j,s]

=(Ai)[s,t]W[j,t] W[j,s].

Now it remains to show that(Ai)[s,t]= pi(l). This follows from the following.

(Ai)[s,t]u_s^W_,t =Aiu^W_s,t= d h=0

pi(h)Ehu_s^W_,t = pi(l)u_s^W_,t,

asu_s^W_,t ∈Vl=ElV. This proves (2).

(3) Since(^tEi)=^t(Ei), we have the following.

u^W_s,t∈Vi ⇔1=(Ei)[s,t]=^t_t Ei

[s,t]=_t Ei

[t,s]

⇔u_t^W_,s∈Vˆı. ✷

Lemma 3.3([15]) Let W be a type II matrix inMatn(C),and E0 = _n¹J,E1, . . . ,Ed be orthogonal idempotents ofN(W)expressing I as a sum,i.e.,

EiEj =δi,jEi, for0≤i,j ≤d, and I =E0+E1+ · · · +Ed.

Then W is type II equivalent to a matrix U =[U0,U1, . . . ,Ud]with the following properties.

(1) U0= j,where j denotes the all ones column vector.

(2) Uiis an n×mimatrix with ones in the first row and no zero entries,where mi=rankEi. (3) The column space of Ui equals the column space of Ei.In particular,the columns of

each Ui are linearly independent.

(4) N(W)=N(U).

Proof: Since all entries ofW are nonzero, there exist nonsingular diagonal matrices D andDsuch thatDW Dhasjas the first column and the entries of the first row are all ones.

LetW=DWD=[w1,w2, . . . ,wn].Sincew1 = j,u_i^W_,1 =wifori =1,2, . . . ,n.Since N(W)=N(DWD)=N(W),the set of column vectors ofWforms a basis of common eigenvectors of Span(E0,E1, . . . ,Ed).Since Ei’s are idempotents, the eigenvalues are 1 or 0.HenceEiwj =wjor 0.Sincewj =Iwj =E0wj+E1wj+ · · · +Edwj,eachwj

is contained in exactly one column space ofEi’s. Hence by a suitable rearrangement of the order of the vectorsw1,w2, . . . ,wn,we have a matrixUwith the properties (1)–(3). Since U is obtained by multiplying a permutation matrix S toWfrom the right,U =WS = DWDSand it is type II equivalent toW andN(W)=N(U) as desired. ✷ In the light of the previous lemma and Corollary 2.2, we consider the following situation.

LetW ∈Matn(C) be a type II matrix. LetX =(X,{Ri}0≤i≤d) be a commutative association scheme with the Bose-Mesner algebraB⊂N(W). Let A0,A1, . . . ,Ad be the adjacency matrices inB, and letE0,E1, . . . ,Ed be the primitive idempotents inB.LetB=(B).

ThenBis a Bose-Mesner algebra of a commutative association schemeXwhich is dual toX. LetA_i=(Ei) andE_i= ¹_n(Ai). ThenA₀,A₁, . . . ,A_dare the adjacency matrices inB, andE₀,E₁, . . . ,E_dare the primitive idempotents inB.

For a matrix M∈Matn(C) and the set of indices = {i1,i2, . . . ,ik} and = {j1,j2, . . . ,jm}, letM[, ] denote the submatrix ofMconsisting of the rowsi1,i2, . . . ,ik

and the columnsj1,j2, . . . ,jm. LetW =[w1,w2, . . . ,wn]. Assumew1= jand the entries in the first row ofW are 1. Assume the following.

1. i = {h| Ai[h,1]=1}.

2. j = {h |Ejwh =wh}.

As an application of Proposition 3.1, the following hold.

Proposition 3.4 Let W be a type II matrix satisfying the condition above. Let Ws,t = W[s, t]. Let jdenote the all one vector of appropriate size. Then the following hold.

(1) Wi,hj=qh(i)j. (2) ^tjWi,h =pi(h)^tj. (3) (Wj,h)⁻j = pj(h)j. (4) ^tj(Wj,h)⁻=qh(j)^tj.

(5) Wi,h(Wj,h)⁻=n·Eh[i, j].

We define two matricesSandT of sizen×(d+1) and (d+1)×n. S[h,j]=

1 ifh ∈j

0 otherwise, T[i,h]=

1 ifh∈i

0 otherwise.

Corollary 3.5 Under the hypothesis of Proposition3.4,the following hold.

(1) WS=SQ.

(2) TW=^tPT .¯ (3) W^−tT =^tTP.

(4) ^tSW⁻=^tQ¯^tS.

Proof: The matrix equations are direct consequences of the assertions (1)–(4) in

Proposition 3.4. ✷

4. Generalized tensor products

In this section we give some properties of generalized tensor products and the proof of Theorem 1.1.

Lemma 4.1 Let U1,U2, . . . ,Um be square matrices of size n, and V1,V2, . . . ,Vn be square matrices of size m. Let W be a generalized tensor product of U1,U2, . . . ,Umand V1,V2, . . . ,Vn. Then the following are equivalent.

(1) W is a type II matrix.

(2) U1,U2, . . . ,Um,V1,V2, . . . ,Vnare type II matrices.

Proof: (1)⇒(2).SinceW is a type II matrix, n

j=1

m y=1

W[m(h−1)+x,m(j−1)+y]

W[m(i−1)+x,m(j−1)+y] =mnδh,i, for 1≤h,i ≤nand 1≤x≤m.

LHS= n

j=1

m y=1

h,jVj[x,y]

i,jVj[x,y]

= n

j=1

m y=1

Ux[h,j]Vj[x,y]

Ux[i,j]Vj[x,y]

= n

j=1

Ux[h,j] Ux[i,j]

m y=1

Vj[x,y]

Vj[x,y]

=m n

j=1

Ux[h,j] Ux[i,j]. Hence

n j=1

Ux[h,j]

Ux[i,j] =nδh,i,

i.e.,Uxis a type II matrix of sizenfor 1≤x≤m.

Similarly, sinceW is a type II matrix, n

h=1

m x=1

W[m(h−1)+x,m(i−1)+y]

W[m(h−1)+x,m(i−1)+z] =mnδy,z,

for 1≤i ≤nand 1≤ y,z ≤m.By computing the left hand side of the above equation, we have the following.

m x=1

Vi[x,y]

Vi[x,z] =mδy,z,

i.e.,Viis a type II matrix of sizemfor 1≤i ≤n.

(2)⇒(1).

n h=1

m x=1

W[m(h−1)+x,m(i−1)+y]

W[m(h−1)+x,m(j−1)+z] = n h=1

m x=1

h,iVi[x,y]

h,jVj[x,z]

= n h=1

m x=1

Ux[h,i]Vi[x,y]

Ux[h,j]Vj[x,z]

= m x=1

n h=1

Ux[h,i] Ux[h,j]

Vi[x,y]

Vj[x,z]

=nδi,j

m x=1

Vi[x,y]

Vj[x,z]

=nδi,j

m x=1

Vi[x,y]

Vi[x,z]

=mnδi,jδy,z. ✷

The following lemma is well known. See also [2].

Lemma 4.2 Let M∈Matmn(C).Suppose M satisfies the following.

(1) M◦I =I.

(2) M =M◦M. (3) m M=M M.

(4) ^tM=M.

Then there exists a permutation matrix S such that^tSMS=In⊗Jm.

Lemma 4.3 Let W∈Matmn(C)with nonzero entries. Then the following are equivalent.

(i) W =(U1, . . . ,Um)⊗(V1, . . . ,Vn)for some matrices U1, . . . ,Umand V1, . . . ,Vn of sizes n and m respectively.

(ii) For1≤i,h≤n and1≤x,y,z≤m, W[x,m(i−1)+y]

W[x,m(i−1)+z] = W[m(h−1)+x,m(i−1)+y]

W[m(h−1)+x,m(i−1)+z].

Proof: (i)⇒(ii) is obtained by the direct computation. Assume (ii). We have the following.

W[m(h−1)+x,m(i−1)+y]

W[x,m(i−1)+y] = W[m(h−1)+x,m(i−1)+z]

W[x,m(i−1)+z]

for 1≤i,h≤nand 1≤x,y,z≤m.

The above equation implies that the ratio ofW[m(h−1)+x,m(i−1)+y] toW[x,m(i− 1)+y] does not depend on the choice of yfor 1≤ y≤m.

Fixy=1. Set

t_h^x_,i= W[m(h−1)+x,m(i−1)+1]

W[x,m(i−1)+1] , where 1≤h,i ≤nand 1≤x≤m.

Define square matricesVjof sizembyVj=W[[1],[j]] for 1≤ j ≤n,andUxof size nbyUx[i,j]=t_i^x_,jfor 1≤x≤mand 1≤i,j≤n.

Then we can verifyW =(U1, . . . ,Um)⊗(V1, . . . ,Vn). ✷

Lemma 4.4 Let U1,U2, . . . ,Um be type II matrices of size n and let V1,V2, . . . ,Vn be type II matrices of size m. Let W be a generalized tensor product of U1,U2, . . . ,Umand V1,V2, . . . ,Vn.If M ∈N(Vi)for1≤i ≤n,then Jn⊗M∈N(W).

Proof: Letvⁱy^,,^jzbe a column vector ofW defined as follows.

vⁱ_y^,_,^j_z[m(h−1)+x]= h,iVi[x,y]

h,jVj[x,z]. where 1≤h,i,j ≤nand 1≤x,y,z≤m.

The following hold.

(Jn⊗M)vⁱ_y^,_,^j_z

[m(h−1)+x]

=

h

x

(Jn⊗M)[m(h−1)+x,m(h−1)+x]vⁱ_y^,_,^j_z[m(h−1)+x]

=

h

x

M[x,x]h,iVi[x,y]

h,jVj[x,z]

=

h

x

M[x,x]Ux[h,i]Vi[x,y]

Ux[h,j]Vj[x,z]

=

x

M[x,x]

h

Ux[h,i]

Ux[h,j]

Vi[x,y]

Vj[x,z]

=nδi,j

x

M[x,x]Vi[x,y]

Vj[x,z]

=nδi,j

Mu^V_y,ⁱ_z [x]

SinceM belongs toN(Vi),the following hold.

(Jn⊗M)vⁱ_y^,_,^j_z=αδi,jvⁱ_y^,_,^j_z

whereα∈C.HenceJn⊗M ∈N(W). ✷

Proof of Theorem 1.1: (i)⇒(ii). Suppose that there exists a permutation matrixSsuch that Jn⊗Im∈N(SW).LetA0, . . . ,Adbe the basis of Hadamard idempotents ofN(SW), whereA0=I andA0+ · · · +Ad = J. By a suitable arrangement of indices, there exists a permutation matrixSsuch that

A0+ · · · + As =S(Im⊗Jn)^tS∈N(SW)

for some s with 1 ≤ s ≤ d −1. HenceN(W) is an imprimitive Bose-Mesner algebra whose imprimitive equivalence class is of sizen.By Proposition 2.3,N(W) andN(SW) are combinatorially isomorphic. Therefore we obtain (i)⇒(ii). For the detail see [2].

(ii) ⇒(i). SupposeN(W) is an imprimitive Bose-Mesner algebra, whose imprimitive equivalence class is of sizen. There exists a permutation matrixSsuch that

A0+ · · · + As =^tS(Im⊗Jn)S

for adjacency matrices A0, . . . ,As, where 1≤s≤d−1 by [2, Theorem 9.3]. Hence Im⊗Jn∈ SN(W)^tS =N(SW).

SinceW andSWare type II equivalent, We have (ii).

(i)⇒(iii). LetW be a type II matrix of sizemn satisfying the condition (i). We may assume Jn⊗Im∈N(W).ThenW(Jn⊗Im)∈N(^tW).LetM =W(¹_nJn⊗Im) and let M=_n¹Jn⊗Im.Then the following hold.

(1) MJ =J.

(2) M=MM. (3) _n¹M=M◦M. (4) ^tM=M.

Next, we consider the duality. By Proposition 2.1(3) and Lemma 3.2(4), the following hold.

(1) W(M)◦W(J)=W(J). (2) W(M)=W(M)◦W(M). (3) ¹_nW(M)= _mn¹ W(M)W(M).

(4) ^tW(M)=W(M).

It is clear thatM =W(M)=W(¹_nJn⊗Im) satisfies the conditions (1)–(4) in Lemma 4.2.

Hence there exists a permutation matrixSof sizemnsuch thatWS(Jn⊗Im)=^tSW(Jn⊗ Im)S =n In⊗Jm.Hencen In⊗Jm∈N(^t(WS)) (See Proposition 2.3(3)). SinceN(WS)= N(W), we replaceW byWSif necessary. Therefore we assume thatW satisfies

W(Jn⊗Im)=n In⊗Jm.

Leta=m(i−1)+yandb=m(i−1)+zfor 1≤i ≤n,1≤ y,z≤m.Compare the (m(h−1)+x) entry of the both sides of

(Jn⊗Im)u^W_a,b=W(Jn⊗Im)[a,b]u_a^W_,b, for 1≤h≤n,1≤x ≤m.The left hand side is

mn k=1

(Jn⊗Im)[m(h−1)+x,k]u^W_a,b[k]= n

j=1

W[m(j−1)+x,a]

W[m(j−1)+x,b]. The right hand side is

n(In⊗Jm)[a,b]u^W_a,b[m(h−1)+x]=nW[m(h−1)+x,a]

W[m(h−1)+x,b].

Hence we get n

j=1

W[m(j−1)+x,a]

W[m(j−1)+x,b] =nW[m(h−1)+x,a]

W[m(h−1)+x,b].

Observe that the left hand side does not depend onh. Hence the right hand side is also independent of the choice of h. Therefore we have (ii) of Lemma 4.3, and thus W = (U1, . . . ,Um)⊗(V1, . . . ,Vn) for some matricesU1, . . . ,UmandV1, . . . ,Vnof sizesnand mrespectively. By Lemma 4.1,U1, . . . ,UmandV1, . . . ,Vnare type II matrices. This shows thatW satisfies (iii) in Theorem 1.1.

(iii)⇒(i).By Lemma 4.4, it is clear. ✷

Remarks K. Nomura illustrated generalized tensor products by functions as follows.

Fix nonempty finite setsX,Y. For functions:

f : X×Y ×X −→C, g:Y ×X×Y −→C,

we define their generalized tensor product f ⊗g:X×Y ×X×Y −→C by

(f ⊗g)(x1,y1,x2,y2)= f(x1,y1,x2)g(y1,x2,y2). 5. Examples of generalized tensor products

5.1. Generalized tensor products of size 2m

In this section, we describe the method to express type II matrices as generalized tensor products. We use the same notation fori,jas in the previous section.

IfU1 =U2 = · · · = Um =U we writeU⊗(V1,V2, . . . ,Vn) instead of (U1,U2, . . . , Um)⊗(V1,V2, . . . ,Vn).

Proposition 5.1 Let U1,U2, . . . ,Um be type II matrices of size2and let V1,V2be type II matrices of size m.Then the generalized tensor product(U1,U2, . . . ,Um)⊗(V1,V2)is type II equivalent to the generalized tensor product U⊗(V1,V₂)where U =[¹₁−¹¹],and V₂=⁻¹1112V2.

Proof: Straightforward. ✷

For type II matricesW,Wof the same size, we say W isright type II equivalent to W if there exist a nonsingular diagonal matrix Dand a permutation matrix S such that W=WDS.

Proposition 5.2 Let U =[¹₁−¹¹],and let V1,V2,V₁and V₂be type II matrices of size m.

Let W =U⊗(V1,V2).Then the following hold.

(i) If V₁is type II equivalent to V1,then W is type II equivalent to U⊗(V₁,L)for a type II matrix L of size m.

(ii) If V₂is right type II equivalent to V2,then W is type II equivalent to U⊗(V1,V₂).

Proof: Straightforward. ✷

5.2. Examples

LetW be a type II matrix such thatN(W)=Span(I,J).RecallN(W) has a dual.

5.2.1. The case of size 6. LetWbe a type II matrix of size 6.According to the classification of association schemes of size 6 [11], it is easy to see thatN(W) is imprimitive. Hence by Theorem 1.1,W is type II equivalent to a generalized tensor product of type II matrices of size 2 and those of size 3.

Let

U = 1 1

1 −1

, V1=





1 1 1

1 w w²

1 w² w



, V2=





1 1 1

a aw aw² b bw² bw



,

wherew³ =1, w =1 anda,b∈ C− {0}.By Proposition 5.1 and Proposition 5.2,W is type II equivalent toU⊗(V1,V2).

Remarks LetCn ∈Matn(C) denote a permutation matrix defined byCn[i,j]=δi+1,j, where indices are regarded as elements inZn.For type II matricesW of size 6 one of the following holds.

(i) N(W)=Span(I,J).

(ii) W is type II equivalent to a cyclic type II matrixW(Z6) and there is a permutation matrixS∈Matn(C) such that

SN(W)^tS =N(SW)=Span(I,C,C², . . . ,C⁵), whereC =C6.

(iii) W or ^tW is type II equivalent to U ⊗(V1,V2), where (a,b) is not a member of {(±1,±1),(±w,±w²),(±w²,±w)}.Moreover, there are permutation matricesS,T∈ Matn(C) such that

SN(W)^tS=N(SW)=Span(I,C+C³+C⁵,C²,C⁴), TN(^tW)^tT =N(T^tW)=Span(I,C+C⁴,C²+C⁵,C³), whereC =C6.

The statement (iii) implies the existence of the generalized tensor product which is essen- tially different from an ordinary tensor product sinceN(U⊗(V1,V2))=N(U)⊗N(Vi)= N(U⊗Vi)=N(W(Z6)) fori =1,2,whereU,V1,V2are the matrices defined above and (a,b) satisfies the condition in the statement (iii).

5.2.2. The case of size 8. LetWbe a type II matrix of size 8.According to the classification of association schemes of size 8 [11], it is clear that N(W) is imprimitive. Hence by Theorem 1.1,W is type II equivalent to a generalized tensor product of type II matrices of size 2 and those of size 4.

Let

U = 1 1

1 −1

, V1=







1 1 1 1

1 −1 λ −λ

1 1 −1 −1

1 −1 −λ λ





, V2=







1 1 1 1

1 −1 µ −µ

1 1 −1 −1

1 −1 −µ µ





,

whereλ, µ∈C− {0}.By Proposition 5.1 and Proposition 5.2,W is type II equivalent to U⊗(V1,SDV2) whereS is a permutation matrix of size 4 and Dis a diagonal matrix of size 4.

5.2.3. The case of size 10. LetWbe a type II matrix of size 10.According to the classifi- cation of association schemes of size 10 [11], it is clear thatN(W) is imprimitive. Hence by Theorem 1.1,W is type II equivalent to a generalized tensor product of type II matrices of size 2 and those of size 5.

Let

U = 1 1

1 −1

, V1=











1 1 1 1 1

1 η η² η³ η⁴ 1 η² η⁴ η η³ 1 η³ η η⁴ η² 1 η⁴ η³ η² η











, V2=











α 1 1 1 1

1 α 1 1 1

1 1 α 1 1

1 1 1 α 1

1 1 1 1 α









 ,

whereη⁵ =1, η=1,andαsatisfies the equationα+α⁻¹+3 =0.By Proposition 5.1 and Proposition 5.2,W is type II equivalent to one of the following.

(i) U⊗(V1,SDV1), (ii) U⊗(V1,SDV2), (iii) U⊗(V2,SDV1), (iv) U⊗(V2,SDV2),

whereSis a permutation matrix of size 5 andDis a nonsingular diagonal matrix of size 5.

See also [14].