In a primitive symmetric association scheme, why does $E_j$ occur in some power of $E_i$ for each $i,j$?

Question

I am having some trouble in the proof of the Absolute Bound Condition for primitive symmetric association Schemes in the book Algebraic Combinatorics I by Bannai and Ito (Chapter 2, Section 4, Theorem 9):

Let $\chi=(X,\lbrace{R_i\rbrace}_{0\leq i \leq d})$ be a primitive symmetric association scheme of class $d$. Let the $\lbrace E_i\rbrace_{0\leq i\leq d}$ be the primitive idempotents of the adjacency algebra of $\chi$. Denote by $E_i^h$ to be the Hadamard product $\circ$ of $E_i$ with itself $h$ times. Since $\chi$ is primitive, we have for any $j$ and $i$ an $0\leq h \leq d$ such that $E_j$ occurs in the linear decomposition of $E_i^h$ with respect to the basis $E_0,\ldots,E_d.$

I do not understand how the emboldened statement is justified. It says in the book that this is because imprimitivity is a equivalent to there being a suitable rearrangement of indices $1,\ldots,d$ and an index $0<t<d$ such that the Hadamard product $E_i \circ E_j$ is a linear combination of $E_0,E_1,\ldots,E_t$ for all $0\leq i,j \leq t.$

To get an idea, I tried to show this by contradiction on the special case when $d=3$ and the assumption that $E_2$ does not occur in the decomposition of $E_1^h$ for $0\leq h \leq 3.$ With this assumption, we get $q_{11}^2=0$ so \begin{align*} E_1^2 = &q_{11}^0 E_0 + q_{11}^1 E_1 + q_{11}^3E_3,\\ E_1^3 =&q_{11}^0(q_{01}^0 E_0 + q_{01}^1 E_1 + q_{01}^2 E_2 + q_{01}^3 E_3) + q_{11}^1(q_{11}^0 E_0 + q_{11}^1 E_1 + q_{11}^2 E_2 + q_{11}^3 E_3)\\ &+q_{11}^3(q_{13}^0 E_0 + q_{13}^1 E_1 + q_{13}^2 E_2 + q_{13}^3 E_3). \end{align*} Since $E_2$ does not occur in $E_1^3$, the latter gives us $q_{11}^0q_{01}^2 + q_{11}^1 q_{11}^2 + q_{11}^3q_{13}^2 = 0.$ Since $q_{01}^2=0=q_{11}^2,$ we obtain $q_{11}^3q_{13}^2=0.$

If $q_{11}^3=0$, then since $q_{11}^2=0$, we have the linear span of $E_0,E_1$ as a subalgebra of the adjacency algebra, violating primitivity. However, I no longer know what to do when $q_{13}^2=0.$ If I could show $q_{33}^2=0$, then the linear span of $E_0,E_1,E_3$ would form a subalgebra of the adjacency algebra and would violate primitivity. However, I don't know how to show $q_{33}^2=0.$

Answer 1

A Schur polynomial in the matrix $E$ is a linear combination of Schur powers of $E$. If $p(t)$ is a polynomial, write $p\circ E$ to denote the corresponding Schur polynomial in $E$.

If $E_i$ is a spectral idempotent of an association scheme and $p\circ E_i$ is invertible, then $p\circ E_i$ is a linear combination of the Schur idempotents with no coefficient in the linear combination equal to zero.

Now suppose $E$ is a spectral idempotent and there is no polynomial $p$ such that $p\circ E$ is invertible. We aim to show the scheme is primitive. Let $W$ be the subspace of the Bose-Mesner algebra of the scheme spanned by the Schur powers of $E$. Note that $A_i(p\circ E)$ is a Schur polynomial in $E$ (because $p\circ E$ is a linear combination of spectral idempotents and so $A(p\circ E)$ must be a linear combination of a subset of these). Therefore $W$ is invariant under the full Bose-Mesner algebra. In particular $W$ is closed under matrix multiplication.

Since $W$ is Schur-closed, it has a basis of Schur idempotents. Let $B$ denote their sum. Then $B$ is the adjacency matrix of a graph and, since the powers of $B$ all lie in $W$, this graph is not connected. Therefore the scheme is imprimitive.

[Obviously the claim that Bannai and Ito are making is not trivial. It is dual to the fact that if $A_i$ is connected then there is a polynomial $p$ in $A_i$ such that $p(A_i)\circ A_j\ne0$ for all $j$.]

Answer 2

The following supplement is mainly due to Dr. Godsil's excellent answer.

We give a direct way of showing that if for some $0\leq i,j\leq d$ we have that $E_j$ does not occur in the decomposition of any $E_i^h$ for any $0\leq h\leq d$, then it follows that $\chi$ is an imprimitive association scheme. To do this, we will show that there exists a reindexing of the indices $1,\ldots,d$ and an index $0<t<d$ such that the Hadamard product $E_i\circ E_j$ is a linear combination of $E_0,E_1,\ldots,E_t$ for all $0\leq i,j\leq t$.

Without loss of generality, we assume that $E_d$ does not occur in the decomposition of any power $0\leq h\leq d$ of $E_1$. Let $S$ be the set of indices $0\leq j \leq d$ such that $E_j$ occurs in the linear decomposition of some power $0\leq h\leq d$ of $E_1$. Observe that $S$ always contains $0$ and $1$ and never contains $d$. Without loss of generality, we may rearrange the indices such that the indices that occur in $S$ are precisely the first $t<d$ indices $0,1,\ldots,t$ where $t=|S|-1$. It remains to show that if $i,j \in S$ and $k\notin S$, then $q_{ij}^k=0.$ We prove this by contradiction.

Suppose that there exist $i,j \in S$ and $k \notin S$ with $q_{ij}^k>0$. Let $a,b$ be nonnegative integers such that $E_1^a=\sum_r \alpha_rE_r$ and $E_1^b=\sum_r \beta_rE_r$ where $\alpha_i,\beta_j>0$; i.e., such that $E_i$ and $E_j$ respectively occur in $E_1^a$ and $E_1^b$. By multiplying these, we see that $E_1^{a}E_1^b$ contains a term of the form $\alpha_i\beta_j E_i\circ E_j.$ By expanding this, we see that the linear decomposition of $E_1^{a}E_1^{b}$ contains $\alpha_i \beta_j q_{ij}^k E_k$ where $\alpha_i\beta_j q_{ij}^k$ is nonzero. Since the Krein parameters are nonnegative, this term will not be cancelled out by considering the other coefficients of $E_k$ when expanding $E_1^{a}E_1^{b}$. In particular, this implies that $E_k$ occurs in the decomposition of $E^{a+b}.$ If $a+b\leq d$, we are done, for we obtain the contradiction that $k\in S$. If $a+b>d$, note that $E_1^0,\ldots,E_1^{d+1}$ are linearly dependent since the algebra is $d+1$ dimensional. Thus, any power of $E_1$ above $d$ is expressible as a linear combination of powers of $E_1$ at most $d$. Hence, $E_1^{a+b}$ is expressible as a linear combination of the $E_1^h$ where $0\leq h\leq d$. Since $E_k$ occurs in $E_1^{a+b}$, it must occur in some $E_1^h$ where $0\leq h\leq d$. Thus, $k \in S$ and we obtain a contradiction as before.