\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems

\usepackage{tikz}
\usepackage{mleftright} %%matrix with line

%\makeatletter
%\DeclareRobustCommand*\cal{\@fontswitch\relax\mathcal}
%\makeatother


\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\spanrm}{span}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\Row}{Row}
\DeclareMathOperator{\dgr}{dgr}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\summ}{sum}
\DeclareMathOperator{\trace}{tr}
\DeclareMathOperator{\spec}{sp}
\DeclareMathOperator{\row}{row}

\begin{DefTralics}
\newcommand{\Mat}{\mathrm{Mat}}
\newcommand{\spanrm}{\mathrm{span}}
\newcommand{\G}{\Gamma}
\newcommand{\A}{\mathcal{A}}
\newcommand{\CC}{\mathbb{C}}
\end{DefTralics}


\newcommand{\gras}[1]{{\upshape #1}}
\newcommand{\G}{\Gamma}
\newcommand{\A}{\mathcal{A}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\ds}{\displaystyle}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\D}{\mathcal{D}}

\newcommand{\N}{\mathcal{N}}
\newcommand{\F}{\mathcal{F}}

\def\ww{{\boldsymbol w}}
\def\tt{{\boldsymbol t}}
\def\pp{{\boldsymbol p}}
\def\jj{{\boldsymbol j}}
\def\O{{\boldsymbol O}}
\def\0{{\boldsymbol 0}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\T}{\mathcal{T}}


\newcommand{\wt}{\widetilde}
\newcommand{\As}{A^*}
\newcommand{\Es}{E^*}
\newcommand{\MX}{\mat_X(\CC)}
\newcommand{\MtX}{\mat_{\tilde{X}}(\CC)}
\newcommand{\la}{\langle}
\newcommand{\h}{\widehat}
\newcommand{\ra}{\rangle}
\newcommand{\ov}{\overline}
\def\P{\mathcal{P}}
\def\ol{\overline}



\newenvironment{problem}{\begin{enonce}{Problem}}{\end{enonce}}
\newenvironment{algorithm}{\begin{enonce}{Algorithm}}{\end{enonce}}
\newenvironment{comment}{\begin{enonce}{Comment}}{\end{enonce}}




%%%%%%%%% a placer avant \begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}


\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur

%%%1
\author{\firstname{Miquel} \middlename{A.} \lastname{Fiol}}

\address{Departament de Matem{\`a}tiques\\
Universitat Polit{\' e}cnica de Catalunya\\
Barcelona Graduate School of Mathematics\\
Institut de Matem{\`a}tiques de la UPC-BarcelonaTech (IMTech)\\
Catalonia, Spain}

\email{miquel.angel.fiol@upc.edu}



%%%2
\author{\firstname{Safet} \lastname{Penji{\'c}}}
\address{University of Primorska\\
Andrej Maru{\v s}i{\v c} Institute\\
Muzejski trg 2\\
6000 Koper, Slovenia}

\email{Safet.Penjic@iam.upr.si}

\thanks{This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The second author acknowledges the financial support from the Slovenian Research Agency (research program P1-0285 and research project J1-1695).}


%%%%% Sujet

\keywords{Symmetric association scheme, adjacency algebra, quotient-polynomial graph, intersection diagram.}
 

\subjclass{05E30, 05C50}


%%%%% Titre et résumé
\title[On symmetric association schemes and associated QPG]{On symmetric association schemes and associated quotient-polynomial graphs}

\begin{abstract}
Let $\G$ denote an undirected, connected, regular graph with vertex set $X$, adjacency matrix $A$, and ${d+1}$ distinct eigenvalues. Let $\A=\A(\G)$ denote the subalgebra of $\Mat_X(\CC)$ generated by $A$. We refer to $\A$ as the \emph{adjacency algebra} of $\G$. In this paper we investigate algebraic and combinatorial structure of $\G$ for which the adjacency algebra $\A$ is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) $\A$ has a standard basis $\{I,F_1,\ldots,F_d\}$; (ii) for every vertex there exists identical distance-faithful intersection diagram of $\G$ with $d+1$ cells; (iii) the graph $\G$ is quotient-polynomial; and (iv) if we pick $F\in \{I,F_1,\ldots,F_d\}$ then $F$ has $d+1$ distinct eigenvalues if and only if $\spanrm\{I,F_1,\ldots,F_d\}=\spanrm\{I,F,\ldots,F^d\}$. We describe the combinatorial structure of quotient-polynomial graphs with diameter $2$ and $4$ distinct eigenvalues. 
As a consequence of the techniques used in the paper, some simple algorithms allow us to decide whether $\G$ is distance-regular or not and, more generally, which distance-$i$ matrices are polynomial in $A$, giving also these polynomials.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
\maketitle

\section{Introduction}
\label{1a}

A matrix algebra is a vector space of matrices which is closed with respect to matrix multiplication. Let $X$ denote a finite set and $\Mat_X(\CC)$ the set of complex square matrices with rows and columns indexed by $X$ (or full algebra denoted by $\CC_{|X|}$). The subalgebras of $\Mat_{X}(\CC)$ that are closed under (elementwise) Hadamard multiplication, and containing the all-ones matrix $J$, are known as coherent algebras. The concept was developed independently by Weisfeiler and Lehman in~\cite{WL} and by Higman in~\cite{Hcc, Hca}. A good introduction to the topic may be found in~\cite{KMMZ}. In the literature, a rich theory has been built up around this concept, and much more can be found in~\cite{IJR, JKM, KCG, Swa, SAD, ST, SS, XB}. It is well known that every coherent algebra $\C$ is semisimple (see, for example, \cite[Section~2]{FS}) and that has a standard basis $\{N_0,N_1,\ldots,N_r\}$ consisting of the primitive idempotents of $\C$ viewed as a subalgebra of $\Mat_X(\CC)$ with respect to Hadamard multiplication (see~\cite{Hca}). Each \emph{basis matrix} $N_i$ of a coherent algebra $\C=\langle N_0, N_1,\ldots, N_r\rangle$ can be regarded as the adjacency matrix $A=A(\G_i)$ of a graph $\G_i=(X,R_i)$. Then $\G_i$ and $R_i$ are called a \emph{basis graph} and a \emph{basis relation}, respectively, of the coherent algebra $\C$. The basis relations of a coherent algebra give rise to a \emph{coherent configuration} in the sense of~\cite{Hcc}.

A special subfamily of coherent configurations are commutative association schemes also known as homogeneous coherent configurations~\cite{EP}. Let $\R=\{R_0,R_1,\ldots,R_n\}$ denote a set of nonempty subsets of $X\times X$. For each $i$, let $A_i\in\Mat_X(\CC)$ denote the adjacency matrix of the (in general, directed) graph $(X,R_i)$. The pair $(X,\R)$ is an \emph{association scheme} with $n$ classes if the following holds.
\begin{enumerate}[label=(AS\arabic*),leftmargin=1.5cm]
\item\label{enumAS1}
$A_0=I$, the identity matrix.
\item\label{enumAS2}
$\ds{\sum_{i=0}^n A_i=J}$, the all-ones matrix.
\item\label{enumAS3}
${A_i}^\top\in\{A_0,A_1,\ldots,A_n\}$ for $0\le i\le n$.
\item\label{enumAS4}
$A_iA_j$ is a linear combination of $A_0,A_1,\ldots,A_n$ for $0\le i,j\le n$.
\end{enumerate}
By~\ref{enumAS1} and~\ref{enumAS4} the vector space $\M$ spanned by the set $\{A_0,A_1,\ldots,A_n\}$ is an algebra; this is the \emph{Bose--Mesner algebra} of $(X,\R)$. We say that $(X,\R)$ is \emph{commutative} if $\M$ is commutative, and that $(X,\R)$ is \emph{symmetric} if the matrices $A_i$ are symmetric. A symmetric association scheme is commutative. The concept of (symmetric) association schemes can also be viewed as a purely combinatorial generalization of the concept of finite transitive permutation groups (famously said as a ``group theory without groups''~\cite{BI}). The Bose--Mesner algebra was introduced in~\cite{BM}, and the monumental thesis of Delsarte~\cite{Daa} proclaimed the importance of commutative association schemes as a unifying framework for coding theory and design theory. There are a number of excellent articles and textbooks on the theory of (commutative) association schemes and Delsarte's theory; see, for instance, \cite{BRA, BCN, DL, FT, HS, MT}. The following are some of the books which include accounts on commutative association schemes:~\cite{CL, Gac, MWS, LW}. As an example of a commutative association scheme, let $\G$ denote a distance-regular graph of diameter $D$. It is well known (not hard to prove) that the vector space spanned by the distance-$i$ matrices $A_0,A_1,\ldots,A_D$ of $\G$, is closed under both ordinary multiplication $(A,B)\mapsto AB$ and Hadamard multiplication $(A,B)\mapsto A\circ B$ (see, for example, \cite[Chapter~III]{BI} or~\cite[Chapter~4]{BCN}). This is one of the main reasons why the theory of distance-regular graphs is so rich in the study of algebraic and combinatorial structures.

In this paper we consider the following problem (we always assume that our graphs are finite, simple, and connected; see Section~\ref{2a} for formal definitions).

\begin{problem}
\label{1b}
Let $\G$ denote a regular graph with vertex set $X$. Using the algebraic or combinatorial structure of $\G$, find, if possible, a set $\mathcal{F}=\{F_0,F_1(=F),\ldots,F_d\}$ of mutually disjoint $(0,1)$-matrices satisfying the following properties: 
\hypertarget{prob1.1_i}{\upshape (i)} the sum of some (respectively all) of these matrices gives $I$ (respectively $J$); \hypertarget{prob1.1_ii}{\upshape (ii)} for each $i\in \{0,\ldots,d\}$, the transpose of $F_i$ belongs to $\mathcal{F}$; \hypertarget{prob1.1_iii}{\upshape (iii)} the vector space spanned by $\mathcal{F}$ is closed under both ordinary and Hadamard multiplication; and \hypertarget{prob1.1_iv}{\upshape (iv)} each $F_i$ is a polynomial (not necessarily of degree $i$) in $F$.
\end{problem}
A basis $\{F_0,F_1,\ldots,F_d\}$ of some subalgebra $\C\subset \Mat_{X}(\CC)$ satisfying all the properties of Problem~\ref{1b} is known as the \emph{standard basis} of $\C$.
In particular, property~\ref{enumAS4} holds and there exist \emph{intersection numbers} $p^h_{ij}$ $(0\le i,j,h\le d)$ such that $\textstyle F_iF_j=\sum_{i=0}^d p^h_{ij} F_h$.

The contents and main results of the paper are as follows.
In Section~\ref{2a} we recall some notation and definitions.
In Section~\ref{3a} we give a new and algorithmic proof of a known result~\cite[Theorem~2.6.1]{BCN}. Namely, if the adjacency algebra $\A=\{p(A) \mid p\in \RR[x] \}$ of a graph $\G$ is closed under Hadamard multiplication, then $\A$ is a symmetric association scheme (see Theorem~\ref{1c}). We also recall a simple procedure to find the number of different eigenvalues of a Hermitian matrix without computing them, and propose a simple algorithm to check distance-regularity.
%\item

The next question we want to answer is what is the combinatorial structure of $\G$ for which the vector space $\A$ is closed under Hadamard multiplication.
This is studied in Section~\ref{7a}, where we show that, if the adjacency algebra $\A$, with $\dim(\A)=d+1$, of a regular graph is an association scheme, then there exists a common intersection diagram with $d+1$ cells for every vertex $x$ that corresponds to a distance-related equitable partition (see Theorem~\ref{1g}).
%\item

For the converse of Theorem~\ref{1g}, see Theorem~\ref{1f}. The first author in~\cite{FQ} defined quotient-polynomial graphs, as graphs for which the adjacency matrices of a walk-regular partition belong to the adjacency algebra $\A$. In Section~\ref{go} we recall some old, and prove some new, properties of such graphs. We also consider graphs which have the same distance-faithful intersection diagram around every vertex, and we propose a method for deciding if their distance-$i$ matrices $A_i$ are polynomial in $A$. In Section~\ref{gn} we give an algorithm which computes the polynomial $p_i(t)$ so that $A_i=p_i(A)$ (if such a polynomial exists).
%\item

In Theorem~\ref{1d} of Section~\ref{4a} we establish a connection between the structure of $\G$ and Problem~\ref{1b}. Namely, it is shown that the adjacency algebra of $\G$ is closed under the Hadamard product if and only if $\G$ is a quotient-polynomial graph (see Theorem~\ref{1d}).
As a corollary of Theorem~\ref{1d}, if the number of distinct entries of $A^d$ is greater than the number $d+1$ of distinct eigenvalues, then the adjacency algebra $\A$ is not closed under Hadamard multiplication (see also Section~\ref{go}).
In Theorem~\ref{1h} we consider quotient-polynomial graphs with diameter $2$, and $4$ distinct eigenvalues. Quotient-polynomial graphs with diameter $2$, and $3$ distinct eigenvalues are known as strongly regular graphs.
Note the similarity between~\cite[Theorem~5.1]{ED} and Theorem~\ref{1h}.
Moreover, we prove that a regular graph $\G$ with diameter $2$ and $4$ distinct eigenvalues is quotient-polynomial if and only if either any two nonadjacent (respectively, adjacent) vertices have a constant number of common neighbours, and the number of common neighbours of any two adjacent (respectively, nonadjacent) vertices takes precisely two values (see Theorem~\ref{1h}).
In Section~\ref{5a} we give a necessary and sufficient condition for the existence of an idempotent generator (see Theorem~\ref{1e}). This corresponds to condition \hyperlink{prob1.1_iv}{(iv)} of Problem~\ref{1b}.
Globally, note that Theorems~\ref{1c},~\ref{1d} and~\ref{1e} give a solution to our problem.
Finally, in the last Section~\ref{6a} we propose some open problems.




\section{Definitions and preliminaries}
\label{2a}

A \emph{graph} (or an \emph{undirected graph}) $\G$ is a pair $(X, R)$, where $X$ is a nonempty set and $R$ is a collection of two element subsets of $X$. The elements of $X$ are called the \emph{vertices} of $\G$, and the elements of $R$ are called the \emph{edges} of $\G$. When $xy\in R$, we say that vertices $x$ and $y$ are \emph{adjacent}, or that $x$ and $y$ are \emph{neighbors}.
A graph is \emph{finite} if both its vertex set and edge set are finite. 
%%If we allow for an edge to start and to end at the same vertex, then an edge with identical ends is called a \emph{loop}, and a graph is \emph{simple} if it has no loops and no two of its edges join the same pair of vertices. 
By our definition for an edge it is not allowed to start and end at the same vertex, so we can say a graph is \emph{simple} if no two of its edges join the same pair of vertices.
For any two vertices $x, y \in X$, a \emph{walk} of length $h$ from $x$ to $y$ is a sequence $x_0,x_1,x_2,\ldots,x_h$ $(x_i\in X,\, 0\le i\le h)$ such that $x_0 = x$, $x_h = y$, and $x_i$ is adjacent to $x_{i+1}$ $(0\le i\le h-1)$. We say that $\G$ is \emph{connected} if for any $x, y\in X$, there is a walk from $x$ to $y$. From now on, we assume that $\G$ is finite, simple and connected.


For any $x, y\in X$, the \emph{distance} between $x$ and $y$, denoted $\dist(x, y)$, is the length of the shortest walk from $x$ to $y$. The \emph{diameter} $D = D(\G)$ is defined to be $
D = \max\{\dist(u,v)\,|\,u, v\in X\}$.
We say $\G$ is \emph{regular with valency} $k$, or {$k$-regular}, if each vertex in $\G$ has exactly $k$ neighbours.
Recall also that a graph $\G$ is \emph{distance-regular} if its distance relations
(or distance matrices) form an association scheme.
A \emph{strongly regular graph}, different from the complete graph or its complement, is a distance-regular graph with diameter $D=2$. For more information about distance-regular graphs, we refer the reader to~\cite{DKT}. Some excellent articles that contain algebraic approach to the theory of distance-regular graphs are~\cite{ADF, ADF2, MF, FGG, AN, T2}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


A \emph{partition around} $x$ of $\G$, is a partition $\{\P_0=\{x\},\P_1,\ldots,\P_s\}$ of the vertex set $X$, where $s$ is a positive integer.
The \emph{eccentricity} of $x$, denoted by $\varepsilon(x)$, is the maximum distance between $x$ and any other vertex $y$ of $\G$.
A \emph{distance partition around} $x$, is a partition $\{\G_0(x),\G(x),\ldots,\G_{\varepsilon(x)}(x)\}$ of $X$.
An \emph{$x$-distance-faithful partition} $\{\P_0,\P_1,\ldots,\P_s\}$ with $s\ge\varepsilon(x)$ is a refinement of the distance partition around $x$.
An \emph{equitable partition} of a graph $\G$ is a partition $\pi = \{\P_1, \P_2, \dots, \P_s\}$ of its vertex set into nonempty cells such that for all integers $i,j$ $(1 \le i,j \le s)$ the number $c_{ij}$ of neighbours, which a vertex in the cell $\P_i$ has in the cell $\P_j$, is independent of the choice of the vertex in $\P_i$. We call the $c_{ij}$'s the \emph{corresponding parameters}. The \emph{intersection diagram} of an equitable partition $\pi$ of a graph $\G$ is the collection of circles indexed by the sets of $\pi$ with lines between them. If there is no line between $\P_i$ and $\P_j$, then it means that there is no edge $yz$ for any $y\in\P_i$ and $z\in\P_j$. If there is a line between $\P_i$ and $\P_j$, then a number on the line near a circle $\P_i$ denotes corresponding parameter $c_{ij}$. A number above or below a circle $\P_i$ denotes the corresponding parameter $c_{ii}$ (see Figure~\ref{2e} for an example).

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=.31]
\draw [line width=.8pt] (-7.04,-0.01)-- (0,2.53);
\draw [line width=.8pt] (0,2.53)-- (-0.02,-2.51);
\draw [line width=.8pt] (-0.02,-2.51)-- (6.98,-0.99);
\draw [line width=.8pt] (6.98,-0.99)-- (6.98,1.01);
\draw [line width=.8pt] (6.98,1.01)-- (1,-5.51);
\draw [line width=.8pt] (1,-5.51)-- (1.02,5.51);
\draw [line width=.8pt] (1.02,5.51)-- (-7.04,-0.01);
\draw [line width=.8pt] (1,-5.51)-- (-7.04,-0.01);
\draw [line width=.8pt] (-7.04,-0.01)-- (-0.02,-2.51);
\draw [line width=.8pt] (-0.02,-2.51)-- (6.98,1.01);
\draw [line width=.8pt] (6.98,1.01)-- (1.02,5.51);
\draw [line width=.8pt] (1.02,5.51)-- (0,2.53);
\draw [line width=.8pt] (0,2.53)-- (6.98,-0.99);
\draw [line width=.8pt] (6.98,-0.99)-- (1,-5.51);
\draw [fill=black] (0,2.53) circle [radius=0.2];
\draw [fill=black] (-0.02,-2.51) circle [radius=0.2];
\draw [fill=black] (6.98,-0.99) circle [radius=0.2];
\draw [fill=black] (6.98,1.01) circle [radius=0.2];
\draw [fill=black] (1,-5.51) circle [radius=0.2];
\draw [fill=black] (1.02,5.51) circle [radius=0.2];
\draw [fill=black] (-7.04,-0.01) circle [radius=0.2];
{\tiny
\node at (-7.54,-0.01) {$0$};
\node at (0.5,2.53) {$1$};
\node at (-0.07,-3.01) {$2$};
\node at (7.48,-0.99) {$3$};
\node at (7.48,1.01) {$4$};
\node at (1.5,-5.51) {$5$};
\node at (1.52,5.51) {$6$};
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{tikzpicture}\qquad\qquad
{\small
\begin{tikzpicture}[scale=.4]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\draw (-7.04,-0.01) -- (0,4.01);
\draw (-7.04,-0.01) -- (0.006,-4.014);
%%\draw (-7.04,-0.01) -- (7.024,-0.01);
\draw (0,4.01) -- (0.006,-4.014);
\draw (0,4.01) -- (7.024,-0.01);
\draw (0.006,-4.014) -- (7.024,-0.01);
\draw [fill=white] (-7.04,-0.01) circle [radius=1.1];
\draw [fill=white] (0,4.01) circle [radius=1.1];
\draw [fill=white] (0.006,-4.014) circle [radius=1.1];
\draw [fill=white] (7.024,-0.01) circle [radius=1.1];
\node at (-7.04,-0.01) {$\P_0$};
\node at (0,4.01) {$\P_1$};
\node at (0.006,-4.014) {$\P_2$};
\node at (7.024,-0.01) {$\P_3$};
%%\node at (-8.04,0.99) {$\P_0$};
\node at (-6.04,0.99) {$2$};
\node at (-6.04,-1.01) {$2$};
\node at (-7.04,-1.51) {--};
%%\node at (-1,5.01) {$\P_1$};
\node at (0,5.51) {$1$};
\node at (1.3,3.41) {$1$};
\node at (-1.3,3.41) {$1$};
\node at (0.3,2.51) {$1$};
%%\node at (-1.3,-4.71) {$\P_2$};
\node at (1.3,-3) {$2$};
\node at (-1.3,-3) {$1$};
\node at (0.006,-5.51) {--};
\node at (0.3,-2.51) {$1$};
%%\node at (8.524,-0.01) {$\P_3$};
\node at (7.024,-1.51) {$1$};
\node at (5.624,0.9) {$1$};
\node at (5.624,-0.7) {$2$};
\end{tikzpicture}
}
\caption{Cayley graph $\mbox{Cay}(\ZZ_{7};\{1,2\})$ and its intersection diagram (around vertex $0$). The adjacency algebra of this graph is closed with respect to Hadamard multiplication (this follows from Theorems~\ref{1f} and~\ref{1d}; or independently from Theorem~\ref{1h}).}
\label{2e}
\end{center}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The adjacency algebra}
\label{2f}

Let $\CC$ denote the complex number field, and let $\G$ denote a graph with vertex set $X$ and diameter $D$. For $0 \le i \le D$ let $A_i$ denote the matrix in $\Mat_X(\CC)$ with $(x,y)$-entry
\begin{equation}
\label{2g}
 (A_i)_{x y} = \begin{cases}
 1 & \hbox{if } \dist(x,y)=i, \\
 0 & \hbox{if } \dist(x,y) \ne i \end{cases} \qquad (x,y \in X).
\end{equation}
We call $A_i$ the \emph{distance-$i$ matrix} of $\G$. We abbreviate $A\coloneqq A_1$ and call this the \emph{adjacency matrix} of $\G$. Observe that $A_0 = I$, $\sum_{i=0}^D A_i = J$, $\overline{A_i} = A_i \;(0 \le i \le D)$, and $A_i^\top = A_i \;(0 \le i \le D)$, where $I$ denotes the identity matrix (respectively, all-ones matrix) in $\Mat_X(\CC)$, ``$^\top$'' denotes transpose, and ``$\overline{\phantom{A}}$'' denotes complex conjugation.

Let $\V=\CC^X$ denote the vector space over $\CC$ consisting of column vectors whose coordinates are indexed by $X$ and whose entries are in $\CC$. We call $\V$ the \emph{standard module}. We endow $\V$ with the Hermitian inner product $\langle \cdot , \cdot \rangle_{\V}$ that satisfies $\langle u,v \rangle_{\V} = u^\top\overline{v}$ for $u,v \in V$. Moreover, 
\[
\langle u, Bv \rangle_{\V} = \langle \overline{B}^\top u, v \rangle_{\V}
\]
for $u,v\in \V$ and $B \in \Mat_X(\CC)$.

We observe that $\Mat_X(\CC)$ acts on $\V$ by left multiplication, and since $A$ is a real symmetric matrix, $A$ can be interpreted as a self-adjoint operator on $\V$. This yields that $\V$ has an orthogonal basis consisting of eigenvectors of $A$ (see, for example, \cite[Chapter~7]{AS}). Assume that $\G$ has $d+1$ distinct eigenvectors. For each eigenvalue $\lambda_i$ $(0\le i\le d)$ of $\G$ let $U_i$ be the (real) matrix whose columns form an orthonormal basis of its eigenspace $\V_i \coloneqq \ker(A-\lambda_iI)$, and let $m_i\coloneqq \dim(\V_i)$. The \emph{primitive idempotents} of $A$ are the matrices
\[
E_i \coloneqq U_iU_i^\top\qquad(0\le i\le d).
\]
Some well-known properties of the primitive idempotents are the following:
\begin{enumerate}[label=(e-\roman*),leftmargin=1.5cm]
\item\label{enume-i}
$p(A)=\sum\limits_{i=0}^d p(\lambda_i) E_i$, for every polynomial $p\in\CC[t]$.
In particular, $E_0+E_1+\cdots+E_d=I$ and $A^h=\sum_{i=0}^d \lambda_i^h E_i$ $(h\in\NN)$.
\item\label{enume-ii}
$\trace(E_i)=m_i$ $(0\le i\le d)$.
\item\label{enume-iii}
$E_i^\top=E_i$ $(0\le i \le d)$.
\item\label{enume-iv}
$\G$ regular and connected $\Rightarrow$ $E_0=|X|^{-1}J$.
\item\label{enume-v}
$E_iE_j=\delta_{ij} E_i$ $(0\le i,j\le D)$.
\item\label{enume-vi}
$E_iA=AE_i=\lambda_i E_i$ $(0\le i\le d)$.
\item\label{enume-vii}
$\ds{E_i=\frac{1}{\pi_i}\prod_{\stackrel{j=0}{j\not=i}}^d(A-\lambda_jI)}$ $(0\le i\le d)$, where $\pi_i=\prod_{j=0(j\not=i)}^d(\lambda_i-\lambda_j)$.
\item\label{2j}
$E_i$ is the orthogonal projector onto $\V_i=\ker(A-\lambda_iI)$ $(0\le i \le d)$. Moreover, $\im(E_i)=\ker(A-\lambda_iI)$ and $\ker(E_i)=\im(A-\lambda_iI)$.
\end{enumerate}
Proofs of properties~\ref{enume-i}--\ref{2j} can be found, for example, in~\cite[Chapter~2]{SP}. Recall that, the number of walks of length $\ell\ge 0$ between vertices $u$ and $v$ of $\G$ is the $(u,v)$-entry of $A^\ell$, and that the eigenvalues of a real symmetric matrix are real numbers (see, for example, \cite{PT}). From this fact, together with~\ref{enume-iv} and~\ref{2j}, we have the following result:

\begin{coro}[{Hoffman polynomial, \cite[Theorem~1]{AJH}}]
\label{2h}
A graph $\G$ is regular and connected if and only if there exists a polynomial $H\in\RR[t]$ such that $J=H(A)$.
\end{coro}

Now, using the above notation, the vector space
\[
\A=\RR_d[A]=\spanrm\{I,A,A^2,\ldots,A^d\}
\]
is an algebra, with the ordinary product of matrices and orthogonal basis $\{E_0,E_1,\ldots,E_d\}$, called the \emph{adjacency algebra}. Moreover, the vector space
\[
\D=\spanrm\{I,A,A_2,\ldots,A_D\}
\]
forms an algebra with the Hadamard product ``$\circ$'' of matrices, defined by $(M\circ N)_{uv}=(M)_{uv}(N)_{uv}$. We call $\D$ the {\em distance $\circ$-algebra}. Note that, when $\G$ is regular, $I,A,J\in \A\cap\D$, and thus $\dim(\A\cap\D)\ge 3$ assuming that $\G$ is neither a complete graph (in which case, $J=I+A$) nor the empty graph. In this algebraic context, an important result is that $\G$ is distance-regular if and only if $\A = \D$, which is therefore equivalent to $\dim(\A\cap \D) = d + 1$ (and hence $d = D$); see, for example, \cite{NB, BCN, RP}. A related concept was introduced by Weichsel~\cite{PW2}: a graph
is called {\em distance-polynomial} if $\D \subset \A$, that is, if each distance matrix is a polynomial in $A$. In other words, a
graph with diameter $D$ is distance-polynomial if and only if $\dim(\A \cap \D) = D + 1$.


In general the algebras $\A$ and $\D$ are different from the algebra $\N=(\langle A_0,A_1,\ldots,$ $A_D \rangle,+,\cdot)$ generated by the set of distance-$i$ matrices $\{ A_0,A_1,\ldots, A_D\}$ with respect to the ordinary product of matrices. Figure~\ref{2i} shows a diagram with some inclusion relationships when $\A$ is closed under Hadamard multiplication.

\begin{figure}[t]
\centering
\begin{tikzpicture}[scale=0.98]
\node (30) at (0,-4.5) {$(\langle I,A,\ldots,A^d\rangle,+,\circ)$};
\node (41) at (3,-6) {$(\D,+,\circ)$};
\node (42) at (-3,-6) {$(\A,+,\cdot)$};
\node (50) at (0,-7.5) {$\{I,A,J\}$};
\draw (30) -- (41);
\draw (30) -- (42);
\draw (41) -- (50);
\draw (42) -- (50);
\end{tikzpicture}
\caption{Inclusion diagram when the adjacency algebra $\A$ is closed under Hadamard multiplication. A line segment that goes upward from $M$ to $N$ means that $N$ contains $M$. In case when $\G$ is a distance-regular graph we have $\A=\D$.}
\label{2i}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The symmetric association scheme}
\label{3a}

In this section we give a new and algorithmic proof of a known result (see~\cite[Theorem~2.6.1]{BCN}).
With this aim,
let us call two $(0,1)$-matrices $B$, $C$ disjoint if $B\circ C=0$. For the moment, let $\F$ denote the vector space of symmetric $n\times n$ matrices. In~\cite[Theorem~2.6.1(i)]{BCN} it was proved that $\F$ has a basis of mutually disjoint $(0,1)$-matrices if and only if $\F$ is closed under Hadamard multiplication. In~\cite[Theorem~2.6.1(iii)]{BCN} it was proved that $\F$ is the Bose--Mesner algebra of an association scheme if and only if $I,J\in\F$ and $\F$ is closed under both ordinary and Hadamard multiplication. Thus, as commented, our next theorem is a re-proof of~\cite[Theorem~2.6.1]{BCN} using a different (algorithmic) approach.
We emphasize that the notation and technique used in our proof is important for the application in Section~\ref{3c}, as well as for the rest of the paper.

\begin{theorem}
\label{1c}
Let $\G$ denote a regular graph with $d+1$ distinct eigenvalues. If the vector space $\A=\spanrm\{I,A,\ldots,A^d\}$ is closed under Hadamard multiplication $(A,B)\rightarrow A\circ B$, then there exists a unique basis $\{F_0,F_1,\ldots,F_d\}$ of $\A$ such that the following hold.
\begin{enumerate}[label=(\roman*)]
\item\label{Theo3.1_i}
$F_i$'s $(0\le i\le d)$ are nonzero $(0,1)$-matrices, such that $F_i\circ F_j=\delta_{ij}F_i$ $(0\le i,j\le d)$.
\item\label{Theo3.1_ii}
There exist $m\in\{0,1,\ldots,d\}$ such that $F_m=I$, the identity matrix.
\item\label{Theo3.1_iii}
$\ds{\sum_{i=0}^d F_i=J}$, the all-ones matrix.
\item\label{Theo3.1_iv}
${F_i}^\top=F_i$ %and $\ol{F_i}=F_i$
$(0\le i\le d)$.
\item\label{Theo3.1_v}
$F_iF_j$ is a linear combination of $F_0,F_1,\ldots,F_d$ for $0\le i,j\le d$.
\end{enumerate}
\end{theorem}

\begin{proof}
Let $X$ denote the vertex set of $\G$ and let $b_i$ $(0\le i\le d)$ denote the row vectors, obtained from $A^i$ $(0\le i\le d)$ as concatenation of the rows of $A^i$. That is, if
\[
A^i=
\left(
\begin{matrix}
d^i_{11} & d^i_{12} & \ldots & d^i_{1,|X|}\\
d^i_{21} & d^i_{22} & \ldots & d^i_{2,|X|}\\
\vdots & \vdots &~ & \vdots\\
d^i_{|X|,1} & d^i_{|X|,2} & \ldots & d^i_{|X|,|X|}\\
\end{matrix}
\right)
\]
then
\[
b_i=\left(
\begin{matrix}
d^i_{11} & d^i_{12} & \ldots & d^i_{1,|X|} &
d^i_{21} & \ldots & d^i_{|X|,1} & d^i_{|X|,2} & \ldots & d^i_{|X|,|X|}
\end{matrix}
\right).
\]
Define $B$ as the $d\times|X|^2$ matrix constructed from the row set $\{b_0,b_1,\ldots,b_d\}$,
\[
B=\left(
\begin{matrix}
- & b_{0} & - \\
- & b_{1} & - \\
~ & \vdots &~ \\
- & b_{d} & - \\
\end{matrix}
\right).
\]
It is not hard to see that the vector space $\A$ is isomorphic to the vector space %$\C\coloneqq \Row(C)=\Row(B^\top)=$,
\[
\C\coloneqq \Row(B^\top)=\{\gamma_0b_0^\top+\gamma_1b_1^\top+\ldots+\gamma_db_d^\top\,|\,\gamma_0,\gamma_1,\ldots,\gamma_d\in\RR\}.
\]
Using elementary row operation on $B$, we compute $C$ as the reduced row echelon form of the matrix $B$. That is,
\[
B\stackrel{\row}{\sim}C=
\left(
\begin{matrix}
1 & * & 0 & 0 & * & * & 0 & * & * & \ldots \\
0 & 0 & 1 & 0 & * & * & 0 & * & * & \ldots \\
0 & 0 & 0 & 1 & * & * & 0 & * & * & \ldots \\
\vdots &~ &~ &~ & \vdots &~ & 0 & * &~ & \vdots \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & * & * & \ldots \\
\end{matrix}
\right)=
\left(
\begin{matrix}
- & c_{0} & - \\
- & c_{1} & - \\
~ & \vdots &~ \\
- & c_{d} & - \\
\end{matrix}
\right).
\]
Note that the set of nonzero vectors $c_i$ $(0\le i\le d)$ are linearly independent. Finally, we can use row vectors $\{c_i\}_{i=0}^d$ to construct our matrices $F_i$ in the following way. If
\[
c_i=
\left(
\begin{matrix}
c^i_{11} & c^i_{12} & \ldots & c^i_{1,|X|} &
c^i_{21} & \ldots & c^i_{|X|,1} & c^i_{|X|,2} & \ldots & c^i_{|X|,|X|}
\end{matrix}
\right).
\]
then
\[
F_i=
\left(
\begin{matrix}
c^i_{11} & c^i_{12} & \ldots & c^i_{1,|X|}\\
c^i_{21} & c^i_{22} & \ldots & c^i_{2,|X|}\\
\vdots & \vdots &~ & \vdots\\
c^i_{|X|,1} & c^i_{|X|,2} & \ldots & c^i_{|X|,|X|}\\
\end{matrix}
\right).
\]
We claim that the set $\{F_0,F_1,\ldots,F_d\}$ has the required properties. By construction, it is routine to show that the matrices $F_0,F_1,\ldots,F_m$ are linearly independent.

%\medskip
\ref{Theo3.1_i} Pick $F_i$ for some $i$ $(0\le i\le d)$. Since $\{F_0,F_1,\ldots,F_d\}$ is a basis of the vector space $\A$, which is closed under both ordinary multiplication and Hadamard multiplication, there exists scalars $\alpha_0,\ldots,\alpha_d$ such that $F_i\circ F_i=\sum_{h=0}^d \alpha_h F_h$. Now pick $F_j$ (where $j\ne i$) and consider the $(x,y)$-entry of $F_j$ which corresponds to the first nonzero entry of the row vector $c_j$. We have $(F_j)_{xy}=1$ and $(F_h)_{xy}=0$ $(0\le h\le d,~h\ne j)$. This yields that if $\alpha_j \ne 0$ then $(F_i\circ F_i)_{xy}=\alpha_j\ne 0$, a contradiction (because $(F_i)_{xy}=0$). Thus $F_i\circ F_i=\alpha_iF_i$. To show that $\alpha_i=1$, pick $(u,v)$-entry of $F_i$ which corresponds to the first nonzero entry of the row vector $c_i$. We have $(F_i)_{uv}=1$ and with that $1=(F_i\circ F_i)_{uv}=(\alpha_iF_i)_{uv}=\alpha_i$.

This yields $F_i\circ F_i= F_i$, and with that all entries of $F_i$ $(0\le i\le d)$ are zeros and ones. In a similar way as above, we can show that $F_i\circ F_j=\boldsymbol{O}$, for $i\ne j$. The result follows.

%\medskip
\ref{Theo3.1_ii} Since $I\in\A=\spanrm\{F_0,F_1,\ldots,F_d\}$ and the set $\{F_0,F_1,\ldots,F_d\}$ is a basis of $\circ$-idempotents, there exists an index set $\Omega$ such that $\sum_{\alpha\in\Omega} F_{\alpha}=I$. If $|\Omega|>1$ then we can pick $\alpha\in\Omega$, $y,z\in X$, such that $(I_\alpha)_{yy}=1$ and $(I_\alpha)_{zz}=0$. For an algebra $\A$ we have that for any $B,C\in\A$, $BC=CB$, and since $J\in\A$ we have $I_\alpha J=JI_\alpha$. If we compute $(y,z)$-entry of $I_\alpha J$ and $JI_\alpha$ we get $(I_\alpha J)_{yz}=1$, $(JI_\alpha)_{yz}=0$, a contradiction. The result follows.

%\medskip
\ref{Theo3.1_iii} Since $\G$ is a regular connected graph we have $J\in\A$. On the other hand, by~\ref{Theo3.1_i} the set $\{F_0,F_1,\ldots,F_d\}$ is a basis of $\circ$-idempotents. The result follows.

%\medskip
%(iv) 
\ref{Theo3.1_iv} Since the $F_i$ $(0\le i\le d)$ are real symmetric matrices, the result follows.

%\medskip
%(v) 
\ref{Theo3.1_v} Note that $\{F_0,F_1,\ldots,F_d\}$ is a basis of $\A$.

%\medskip
This completes the proof.
\end{proof}

Note that, as a consequence, if the adjacency algebra $\A$ of $\G$ is closed under Hadamard multiplication, then it produces a symmetric association scheme. The property~\ref{Theo3.1_ii} of Theorem~\ref{1c} tell us that if we want to get property~\hyperlink{prob1.1_i}{(i)} of Problem~\ref{1b}, for $|\Omega|>1$, we should consider a directed graph $\G$. By Theorem~\ref{1c}\ref{Theo3.1_iv}, we also need a directed graph to get non-symmetric $F_i$'s. Using the technique from the proof of Theorem~\ref{1c}, 
 it is not hard to figure out an algorithm which yields the number of distinct eigenvalues of $A$ without computing them.


%{\bf \textit{Question}.}
%Let $A$ denote a Hermitian matrix. Is there some easy method how $A$ without computing them? Moreover can we find the number of such eigenvalues using only two operations, like matrix multiplication and elementary row operation?
%\medskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%---------- Forwarded message ---------
%From: Akihiro Munemasa via <mersenne@listes.mathdoc.fr>
%Date: Mon, May 10, 2021 at 2:12 PM
%Subject: [ALCO] Editor Decision
%To: Miguel Angel Fiol <miguel.angel.fiol@upc.edu>, Safet Penjic <safet.penjic@iam.upr.si>
%
%
%Dear Miguel Angel Fiol, Safet Penjic,
% 
% We have reached a decision regarding your submission to Algebraic Combinatorics, "On symmetric association schemes and associated quotient-polynomial graphs".
% 
% Our decision is: Revisions Required--Editor's comments:Please consider removing Subsection 3.1. It gives an "algorithm" to find the number of distinct eigenvalues of a Hermitian matrix. An elementary linear algebra says that every Hermitian matrix is diagonalizable, so the number of distinct eigenvalues coincides with the degree of the minimal polynomial. Finding the degree of the minimal polynomial of a Hermitian (or more generally, diagonalizable) matrix is nothing but finding the smallest positive integer k such that A^{k+1} is in the linear span of A^0,A^1,...,A^k. In general, such a problem is reduced to whether a system of homogeneous linear equations has a nontrivial solution. A more efficient 'algorithm' is to compute the projection of A^{k+1} onto the span of A^0,A^1,...,A^k, which is conveniently done by the Gram-Schmidt orthogonalization process. Algorithm 3.2 is exactly this procedure, so there is nothing new. The only difference from the standard orthonormalization is to avoid square roots to stay in the rational field. 
%In conclusion, the contents of Subsection 3.1 is worth only a few sentences, noting that the Gram-Schmidt orthonormalization can be done within the rational if we do not orthonormalize but just orthogonalize.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Checking the number of distinct eigenvalues and distance-regula\-rity}
\label{3c}


%As shown in this subsection, the technique used in the proof of Theorem~\ref{1c} can be used to find the number of distinct eigenvalues of a symmetric (or Hermitian) matrix.
%The motivation for this algorithm is that, for the solution of some problems that deal with eigenvalues, we only need to know the number of different ones.
%%In other words, sometimes values of eigenvalues are not so important as number of them.
%Moreover, if we have a large matrix (or a set of large matrices), computing all the eigenvalues is time consuming.
%
%Also there is problem of distinct two different eigenvalues when we work with computer programs. All computers work only with rational numbers. So, if we deal with a large number of eigenvalues, even when we compute them in the usual way, we always have the problem of distinguishing two of them, because their values are often close to each other, up to some decimal place. Our method can avoid this.
%
%Our method is especially applicable in algebraic and spectral graph theory, since symmetric $(0,1)$-matrix represent adjacency matrix of a graph. Also, for example, see Corollary~\ref{gs}. For more information about algebraic and spectral graph theory we recommend \cite{NB,PT}.
%Moreover, idea for one part of our solution we found in \cite{MF}.


As before, let $X$ denote a set with $|X|=n$ elements, $\Mat_X(\CC)$ the set of $n\times n$ matrices over $\CC$ with rows and columns indexed by $X$, and $A\in\Mat_X(\CC)$ a Hermitian matrix. 
Then, to find the number $d+1$ of distinct eigenvalues of $A$ (without computing them),
it suffices to find the dimension of the vector space $\A$ spanned by the powers of~$A$.
With this aim, we can
consider the set $\{A^0,A^1,\ldots,A^k\}$ for some positive integer $k$. Then, as in the proof of Theorem~\ref{1c}, we construct the matrix $B$ and compute $C=(c_{ij})_{(d+1)\times n^2}$ as its reduced row echelon form (here both~$B$ and~$C$ are matrices from the proof of Theorem~\ref{1c}). 
Then, note that the set of nonzero row vectors $c_i$ $(0\le i\le k)$ are linearly independent. Thus,
we only need to find the smallest $k$ so that $c_k\neq 0$ to conclude that $A$ has $d+1=k+1$ different eigenvalues. The problem with this approach is that to decide what initial number $k$ to pick. Of course, $k=n$ will always work, but, in this case, we need to compute all $A^i$ $(0\le i\le n)$ which is not the best choice if the number of distinct eigenvalues is small compared with $n$.

To overcome the above problem, we can use the Gram--Schmidt method with inner scalar product
\begin{equation}
\label{ip}
\langle A,B\rangle_{\CC_n} \coloneqq \frac{1}{n} \trace (A B)=\frac{1}{n}\summ (A\circ \overline{B}), \qquad A,B\in \Mat_X(\CC),
\end{equation}
where $\summ(M)$ denotes the sum of all entries of $M$ (the term $\frac{1}{n}$ is a normalization factor to get $\|I\|_{\CC_n}=1$) .
Then, if we apply the method from the matrices $I,A,A^2,\ldots$, we get a sequence $A_0,A_1,\ldots$, where $A_i$ is a polynomial of degree $i$ in $A$, for $i=0,\ldots,d$, the matrices $A_0,\ldots,A_{d}$ are orthogonal, and $A_i=0$ for $i>d$. Consequently, we only need to apply the process until we reach the first zero matrix.
Moreover, notice that if, when computing $A_{k+1}$, instead of the power $A^{k+1}$, we use $A_{k}A$, we have
$\langle A_{k}A, A_i \rangle_{\CC_n}=\langle A_{k}, A_i A\rangle_{\CC_n}=0$ for each $i<k-1$ (since $A_iA$ is a polynomial in $A$ of degree less than $k$). 
Moreover,
the Gram--Schmidt orthonormalization can be done within the rational field if we do not orthonormalize but just orthogonalize.


Thus, if $A$ is a Hermitian matrix such that $\A=\spanrm\{A^0,A,\ldots,A^d\}$ is closed under Hadamard product,
we can use the above procedure to compute the standard basis $\{F_0,F_1,\ldots, F_d\}$ of $\A$ by following the proof of Theorem~\ref{1c}\ref{Theo3.1_i}. Just apply the algorithm to get a set $\{A_0,A_1,\ldots,A_d\}$ of non-zero matrices such that $d+1$ is the number of distinct eigenvalues of $A$, and, starting from them, proceed as in the proof.


In fact, if $A$ is the adjacency matrix of a graph $\G$ with $d+1$ eigenvalues, the above inner product~\eqref{ip} is denoted as $\langle \cdot,\cdot\rangle_{\G}$, and the obtained matrices $A_0,A_1,\ldots,A_d$ coincide, up to a multiplicative constant, with the so-called {\em predistance} matrices of $\G$, see~\cite{FP}. In turn, such matrices are obtained by evaluating at $A$ the predistance polynomials $p_0,\ldots,p_d$, introduced in~\cite{fg97}.
In particular, if $\G$ is distance-regular, the predistance polynomials and predistance matrices are, respectively, the distance polynomials and distance matrices of $\G$.
If $\G$ has spectrum $\spec(\G) = \spec (A) = \{\lambda_0^{m_0},\lambda_1^{m_1},\dots,
\lambda_d^{m_d}\}$,
where $\lambda_0>\lambda_1>\cdots >\lambda_d$,
the {\em predistance polynomials}
$p_0,p_1,\ldots,p_d$
constitute an orthogonal sequence of polynomials ($\dgr (p_i)=i$) with respect to the scalar product

\begin{equation}\label{ip2}
\langle f, g\rangle_{\G} \coloneqq \frac{1}{n} \sum_{i=0}^d m_i f(\lambda_i) g(\lambda_i)= \frac{1}{n}\trace (f(A)g(A)) = \langle f(A), g(A)\rangle_{\G},
\end{equation}
normalized in such a way that
$\|p_i\|_{\G}^2=p_i(\lambda_0)$ (we know that $p_i(\lambda_0)>0$ for every $i=0,\ldots,d$).

As every sequence of orthogonal polynomials, the predistance polynomials satisfy a three-term recurrence of the form
\begin{equation}
\label{recur}
xp_{i}=b_{i-1}p_{i-1}+a_ip_i+c_{i+1}p_{i+1}\qquad (0\le i\le d),
\end{equation}
where the constants $b_{i-1}$, $a_i$, and $c_{i+1}$ are the Fourier coefficients of $xp_i$ in terms of $p_{i-1}$, $p_i$, and $p_{i+1}$, respectively (and $b_{-1}=c_{d+1}=0$).
Moreover, $p_0+p_1+\cdots+p_d=H$, the Hoffman polynomial of Corollary~\ref{2h}. Hence, if $\G$ is $k$-regular, we can apply the above algorithm, based on the Gram--Schmidt method, 
 to obtain the predistance matrices if we normalize each $A_i$, for $i=0,\ldots,d$, in such a way that $\|A_i\|_{\G}^2=\langle A_i,J \rangle_{\G}$, which satisfy
\begin{equation}
\label{sum-p=J}
A_0+A_1+\cdots + A_d = p_0(A)+p_1(A)+\cdots +p_d(A)=H(A)=J.
\end{equation}

Some recent characterizations of distance-regularity in terms of the predistance polynomials and distance matrices $A_d$ and $A_{d-1}$ are the following:
A regular graph $\G$ with $d + 1$ distinct eigenvalues, diameter $D = d$, is distance-regular if and only if either
\begin{enumerate}[label=(DR\arabic*),leftmargin=1.5cm]
\item\label{enumDR1} $A_d\in\A$,
\item\label{enumDR2} $A_d = p_d(A)$,
\item\label{enumDR3} $A_i = p_i(A)$ for $i=d-2,d-1$.
\end{enumerate}
Each of the above conditions assures the existence of all the distance matrices $A_0(=I), A_1(=A),A_2,\ldots,A_d$, which is a well-known characterization of distance-regularity. More generally, in~\cite{DDF}, a graph $\G$ is said to be {\em $k$-partially distance-regular},
for some $k<d$, if there exist the distance matrices $A_i$ for $i=0,\ldots,k$.
For more details, see~\cite{DDF, EvD, Fpdr, FGY}.

Now, as another possible application of the algorithm given by the Gram--Schmidt method,
%\ref{3d} 
we have the following result.
\begin{prop}
\label{propo1}
Let $\G$ be a regular graph with diameter $D$, and $d+1$ different eigenvalues. Let $A_i$ be the matrices obtained by applying the Gram--Schmidt method,
% Algorithm~\ref{3d}, 
and normalizing them so that $\|A_i\|_{\G}^2=\langle A_i,J \rangle_{\G}$, for $i=0,1\ldots$, that is,
$A_i \leftarrow \frac{\langle A_i, J\rangle_{\G}}{\|A_i\|_{\G}^2}A_i$. If the following conditions hold:
\begin{enumerate}[label=(\roman*)]
\item\label{prop3.2_i}
$A_{D+1}=0$ and $A_D\neq 0$,
\item\label{prop3.2_ii}
$A_D$ is a $(0,1)$-matrix,
\item\label{prop3.2_iii}
$A_i$, $i=0,\ldots,D-1$, are nonnegative matrices,
\end{enumerate}
then $\G$ is a distance-regular graph.
\end{prop}

\begin{proof}
We will prove that $A_d$ is the distance-$d$ matrix of $\G$.
First, as we have already seen,~\ref{prop3.2_i}~implies that $D=d$.
Then, if $u,v\in X$ are two vertices at distance $\dist(u,v)=d$, we have that
$(A_d)_{uv}=(p_d(A))_{uv}=(H(A))_{uv}=(J)_{uv}=1$.
Otherwise, assume that $\dist(u,v)=\ell<d$ and $(A_d)_{uv}=1$. Then, from~\eqref{sum-p=J}
and~\ref{prop3.2_iii}, it should be $(A_{\ell}+\cdots+A_{d-1})_{uv}=0$. In particular,
$(A_{\ell})_{uv}=0$, a contradiction since $A_{\ell}=p_{\ell}(A)$, with $\dgr(p_{\ell})=\ell$ and so $p_{\ell}$ has leading nonzero coefficient.
Then, if $\dist(u,v)<d$, then $(A_d)_{uv}=0$. Consequently, $A_d$ is as claimed, and~\ref{enumDR2} gives the result.
\end{proof}

Notice that, in fact, if $\G$ is indeed distance-regular, all the normalized matrices $A_0,A_1,\ldots$ obtained by the algorithm must be the corresponding distance matrices. This provides an obvious procedure to decide whether a regular graph is distance-regular or not.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\section{Proof of Theorem~\ref{1g}}
\section{The distance-faithful intersection diagrams}
\label{7a}

In this section we prove that, if the adjacency algebra $\A=\{I,A,\ldots,A^d\}$ of a regular graph is closed under Hadamard multiplication, then there exists a common $x$-distance-faithful intersection diagram of an equitable partition with $d+1$ cells for every vertex $x$.

\begin{theorem}
\label{1g}
Let $\G$ denote a regular graph with $d+1$ distinct eigenvalues. If the vector space $\A=\spanrm\{I,A,\ldots,A^d\}$ is closed under Hadamard multiplication, then, for every vertex $x$, there exists an $x$-distance-faithful intersection diagram of an equitable partition with $d+1$ cells. Moreover, this intersection diagram is the same around every vertex.
\end{theorem}

\begin{proof}
Since $\G$ is a regular graph, by Theorem~\ref{1c} $\A$ has the standard basis $\{F_0,F_1,\ldots,F_d\}$. Let $X$ denote the vertex set of $\G$. Given $x\in X$, we define the partition
\[
\pi_x=\{\P_0(x),\P_1(x),\ldots,\P_d(x)\},
\quad\mbox{ where }\quad
\P_i(x)=\{z\mid (F_i)_{xz}=1\}~(0\le i\le d),
\]
To prove the claim, we need to show that the following~\ref{proof_Theo4.1_i}--\ref{proof_Theo4.1_iii} hold.
\begin{enumerate}[label=(\roman*)]
\item\label{proof_Theo4.1_i}
All vertices in $\P_i(x)$ are at the same distance from $x$.
\item\label{proof_Theo4.1_ii}
$|\P_i(x)|=|\P_i(u)|$ $(0\le i\le d)$ for every $x,u\in X$.
\item\label{proof_Theo4.1_iii}
There exist numbers $c_{ij}$ $(0\le i,j\le d)$ such that, for every $x\in X$, $\pi_x$ is equitable partition of $\G$ with corresponding parameters $c_{ij}$ (which do not depend on $x$).
\end{enumerate}

%\medskip
\ref{proof_Theo4.1_i} We first show that for any $z,w\in\P_i(x)$ we have $(A^\ell)_{xz}=(A^\ell)_{xw}$ $(0\le \ell\le d)$. That is, the number of walks of length $\ell$ from $x$ to $z$ is the same as the number of walks of length $\ell$ from $x$ to $w$. Since $\{F_h\}_{h=0}^d$ is a basis of $\A$ there exist scalars $\alpha_{ij}$ $(0\le i,j\le d)$ such that
\[
A^\ell=\sum_{j=0}^d \alpha_{\ell j} F_j
\qquad
(0\le \ell\le d).
\]
Since $z,w\in\P_i(x)$ we have $(F_i)_{xz}=(F_i)_{xw}=1$ and $(F_j)_{xz}=(F_j)_{xw}=0$ for $j\ne i$. This yields $(A^\ell)_{xz}=\alpha_{\ell i}=(A^\ell)_{xw}.$
Now we prove the claim~\ref{proof_Theo4.1_i} by contradiction. Assume that $z,w\in\P_i(x)$ and that $\dist(x,z)>\dist(x,w)=\ell$. Then, we have $(A^{\ell})_{xw}\ne 0$ but $(A^{\ell})_{xz}= 0$, a contradiction.

%\medskip
\ref{proof_Theo4.1_ii} This follows from the fact that every matrix in $A$ has constant row sums, so $F_i$ does too. Indeed, since $\G$ is a regular graph of valency $k$, $A\jj=k\jj$ (where $\jj$ is all-ones column vector). This yields $E_0\jj=\jj$ and $E_j\jj=\0$ for $1\le j\le d$ (see property~\ref{2j} in Subsection~\ref{2f}). Now, since $F_i\in\A=\spanrm\{E_0,E_1,\ldots,E_d\}$, there exist scalars $\beta_{h}$ $(0\le h\le d)$ such that
\[
F_i=\sum_{h=0}^d \beta_h E_h \qquad (0\le i\le d).
\]
This implies $F_i\jj=\beta_0 E_0\jj = \beta_0 \jj$. That is, the sum of row entries is the same for every vertex. Therefore, $|\P_i(x)|=\sum_{z\in X} (F_i)_{xz}=\beta_0=\sum_{w\in X} (F_i)_{uw}=|\P_i(u)|$.

%\medskip
\ref{proof_Theo4.1_iii} Since $AF_i\in\spanrm\{F_0,F_1,\ldots,F_d\}$, there exist scalars $c_{ij}$ $(0\le i,j\le d)$ such that
\begin{equation}
\label{7b}
AF_i=\sum_{h=0}^d c_{ih} F_h
\qquad(0\le i\le d).
\end{equation}
Now, for any given $x\in X$ and $y\in\P_j(x)$, from the left side of~\eqref{7b} we have
\[
(AF_i)_{yx}=\sum_{z\in X} (A)_{yz} (F_i)_{zx} = |\G(y)\cap \P_i(x)|,
\]
and from the right side of~\eqref{7b} we have
\[
(AF_i)_{yx}=\left(\sum_{h=0}^d c_{ih} F_h\right)_{yx}= c_{ij} (F_j)_{yx} = c_{ij}.
\]
Thus, $\pi_x$ is an equitable partition of $\G$ with corresponding parameters $c_{ij}$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The quotient-polynomial graphs}
\label{go}

In this section we recall some old, and prove some new, properties of quotient-polynomial graphs, a concept introduced by the first author in~\cite{FQ}.

Recall that, for every $y,z\in X$, $(A^\ell)_{yz}$ $(0\le \ell\le d)$ is the number of walks of length $\ell$ between vertices $y$ and $z$.

\begin{defi}\label{gb}
Let $\G$ denote a graph with vertex set $X$ and $d+1$ distinct eigenvalues. The column vector $\ww(y,z)\in\CC^{d+1}$ is defined as
\[
\ww(y,z)=\Big( (A^0)_{yz}, (A^1)_{yz},\ldots,(A^d)_{yz} \Big)^{\top}.
\]
\end{defi}

Let $\R=\{R_0,R_1,\ldots,R_r\}$ denote a partition of $X\times X$ such that, for each $i$ $(0\le i\le r)$, the pairs $(y,z),(u,v)\in X\times X$ belong to $R_i$ if and only if $\ww(y,z)=\ww(u,v)$. Then, from the above definition, all pairs of vertices in a given $R_i$ are at the same distance.

\begin{rema}\label{gm}
If we have an equitable partition $\pi=\{\P_0,\P_1,\ldots,\P_r\}$ around $y$, $\P_0=\{y\}$,
with intersection numbers $b_{ij}$ we can compute the vector $\ww(y,z)$ $(y,z\in X)$ from its {\em quotient matrix} $B=(b_{ij})\in\Mat_{(r+1)\times (r+1)}(\CC)$, $(0\le i, j\le r)$.
The reason is that $\frac{1}{|\P_j|}(B^\ell)_{\P_j,\P_0}$ is the number of $\ell$-walks $(0\le\ell\le d)$ from $z$ to $y$ for any $z\in\P_j$ $(0\le j\le r)$ (see, for instance, \cite{DF}).
\end{rema}



\begin{defi}
\label{ga}
The \emph{walk-regular} partition $\R=\{R_0,R_1,\ldots,R_r\}$ of $X\times X$ is the partition satisfying that, for each $i$ $(0\le i\le r)$, the pairs $(y,z),(u,v)\in X\times X$ belong to $R_i$ if and only if $\ww(y,z)=\ww(u,v)$.
Let $M_i$ $(0\le i\le r)$ denote the $|X|\times|X|$ matrix, indexed by the vertices of $\G$, and defined by
\[
(M_i)_{yz}=\begin{cases}
 1 & \hbox{if } (y,z)\in R_i\,\\
 0 & \hbox{otherwise} \end{cases} \qquad (y,z \in X).
\]
The matrix $M_i$ is called the \emph{adjacency matrix of the equivalence class $R_i$.}
\end{defi}

Note that, since the walk-regular partition follows from the equivalence classes of $\ww$, it is unique up to ordering of the indices in $\R=\{R_0,R_1,\ldots,R_r\}$.
In other words, if necessary, and using the comment after Definition~\ref{gb}, we can define the walk-regular partition $\R$ by adding the following restriction: for any $i\le j$ and $(x,y)\in R_i$, $(u,v)\in R_j$ we have $\dist(x,y)\le\dist(u,v)$.
Moreover, by the same comment, the following lemma is immediate.
\begin{lemma}
\label{gd}
Let $\G$ be a graph with vertex set $X$ and a walk-regular partition $\R$ of $X\times X$.
Let $A_i$ $(0\le i\le D)$ denote the distance-$i$ matrix of $\G$, and let $M_i$ $(0\le i\le r)$ denote the adjacency matrices of the corresponding equivalence classes $R_i$. Then there exists an index set $\Phi_i\subset \{0,\ldots,r\}$ such that
$A_i=\sum_{j\in\Phi_i} M_j$.
\end{lemma}

\begin{defi}
\label{gk}
Let $\G$ denote a graph with vertex set $X$, $d+1$ distinct eigenvalues, and adjacency algebra $\A$. Let $\R=\{R_0,R_1,\ldots,R_r\}$ be the walk-regular partition of $X\times X$ and let $M_i$ $(0\le i\le r)$ denote the adjacency matrices of the equivalence classes $R_i$ $(0\le i\le r)$. A graph $\G$ is {\em quotient-polynomial} if $M_i\in\A$ $(0\le i\le r)$.
\end{defi}

From Lemma~\ref{gd} and Definition~\ref{gk} it follows that every distance-$i$ matrix of a quotient-polynomial graph $\G$ belongs to its adjacency algebra $\A$.

\begin{exam}
\label{gp}
Let $B\otimes C$ denote the Kronecker tensor product of matrices $B$ and $C$ (for the definition and properties of Kronecker tensor product see, for example, \cite[Chapter~13]{AL} or~\cite[Chapter~4]{HF}). Let $A$ and $A'$ denote the adjacency matrices of the graphs $\G$ and $\G'$ respectively. The Kronecker product, $\G\otimes\G'$, is that graph with adjacency matrix $A\otimes A'$ (see~\cite{PW}).

\looseness-1
Let $T_4$ be the triangular graph
 %with vertex set $X'=\{0,1,2,3,4,5\}$, and edge set $R'=\{01,02,03,05,12,13,14,24,25,34,35,45\}$
 (that is, the line graph of the complete graph $K_4$, or $K_6$ minus a matching). The distinct eigenvalues of $T_4$ are $\{-2,0,4\}$, and the distinct eigenvalues of the complete graph $K_2$ are $\{-1,1\}$. Consider the graph $\G=K_2\otimes T_4$, the bipartite double of $T_4$.
From~\cite[Theorem~13.12]{AL}, the distinct eigenvalues of $\G$ are $\{-4,-2,0,2,4\}$, and from~\cite[Theorem~1]{PW}, $\G$ is connected.
Moreover, $\G$ is a quotient-polynomial graph. The adjacency algebra of $\G$ is closed with respect to the Hadamard product, and has the standard basis $\{F_0,F_1,F_2,F_3,F_4\}$, where $F_i\coloneqq p_i(A)$ $(0\le i\le 4)$ and
\[
p_0(t)=1,\qquad
p_1(t)=t,\qquad
p_2(t)=-\frac{t^4}{32}+\frac{5t^2}{8}-1,
\]
\[
p_3(t)=\frac{t^4}{16}-\frac{3 t^2}{4},\qquad
p_4(t)=\frac{t^3}{8}-\frac{3t}{2}.
\]
(The above polynomials can be obtained by the process explained in Definition~\ref{gl}.)
For the corresponding intersection diagram of $\G$ see Figure~\ref{gq}.
\end{exam}

\begin{figure}[htb]\centering
{\small
\begin{tikzpicture}[scale=.3]
\draw [line width=.8pt] (5.98,-2.51)-- (12.02,-0.55);
\draw [line width=.8pt] (5.98,-2.51)-- (-0.02,1.53);
\draw [line width=.8pt] (5.98,-2.51)-- (-0.04,0.47);
\draw [line width=.8pt] (5.98,-2.51)-- (11.98,0.55);
\draw [line width=.8pt] (6,3.99)-- (-0.04,-0.47);
\draw [line width=.8pt] (6,3.99)-- (-0.02,1.53);
\draw [line width=.8pt] (6,3.99)-- (-0.04,0.47);
\draw [line width=.8pt] (6,3.99)-- (-0.02,-1.53);
\draw [line width=.8pt] (6,-5.53)-- (-0.04,-0.47);
\draw [line width=.8pt] (6,-5.53)-- (12.02,-0.55);
\draw [line width=.8pt] (6,-5.53)-- (-0.02,-1.53);
\draw [line width=.8pt] (6,-5.53)-- (11.98,0.55);
\draw [line width=.8pt] (5.98,-4.49)-- (-0.04,-0.47);
\draw [line width=.8pt] (5.98,-4.49)-- (12.02,-0.55);
\draw [line width=.8pt] (5.98,-4.49)-- (-0.02,-1.53);
\draw [line width=.8pt] (5.98,-4.49)-- (11.98,0.55);
\draw [line width=.8pt] (6,-3.49)-- (12.02,-0.55);
\draw [line width=.8pt] (6,-3.49)-- (-0.02,1.53);
\draw [line width=.8pt] (6,-3.49)-- (-0.04,0.47);
\draw [line width=.8pt] (6,-3.49)-- (11.98,0.55);
\draw [line width=.8pt] (-6.06,-0.03)-- (-0.04,-0.47);
\draw [line width=.8pt] (-6.06,-0.03)-- (-0.02,1.53);
\draw [line width=.8pt] (-6.06,-0.03)-- (-0.04,0.47);
\draw [line width=.8pt] (-6.06,-0.03)-- (-0.02,-1.53);
\draw [fill=black] (5.98,-2.51) circle [radius=0.2];
\draw [fill=black] (6,3.99) circle [radius=0.2];
\draw [fill=black] (6,-5.53) circle [radius=0.2];
\draw [fill=black] (5.98,-4.49) circle [radius=0.2];
\draw [fill=black] (6,-3.49) circle [radius=0.2];
\draw [fill=black] (-6.06,-0.03) circle [radius=0.2];
\draw [fill=black] (-0.04,-0.47) circle [radius=0.2];
\draw [fill=black] (12.02,-0.55) circle [radius=0.2];
\draw [fill=black] (-0.02,1.53) circle [radius=0.2];
\draw [fill=black] (-0.04,0.47) circle [radius=0.2];
\draw [fill=black] (-0.02,-1.53) circle [radius=0.2];
\draw [fill=black] (11.98,0.55) circle [radius=0.2];
\end{tikzpicture}
\qquad
\begin{tikzpicture}[scale=.31]
\draw (-6.06,-0.03)-- (0,-0.01);
\draw (6.02,4.01)-- (0,-0.01);
\draw (6.02,-3.99)-- (0,-0.01);
\draw (6.02,-3.99)-- (12.02,-0.01);
\draw [fill=white] (-6.06,-0.03) circle (1.5cm);
\draw [fill=white] (0,-0.01) circle (1.5cm);
\draw [fill=white] (6.02,4.01) circle (1.5cm);
\draw [fill=white] (6.02,-3.99) circle (1.5cm);
\draw [fill=white] (12.02,-0.01) circle (1.5cm);
\node at (-6.06,-0.03) {$\P_0$};
\node at (0,-0.01) {$\P_1$};
\node at (6.02,4.01) {$\P_2$};
\node at (6.02,-3.99) {$\P_3$};
\node at (12.02,-0.01) {$\P_4$};
\node at (-6.06,-2.03) {--};
\node at (0,-2.01) {--};
\node at (6.02,2.01) {--};
\node at (6.02,-5.99) {--};
\node at (12.02,-2.01) {--};
\node at (-4.1,0.5) {$4$};
\node at (-2,0.5) {$1$};
\node at (1.4,1.4) {$1$};
\node at (1.4,-1.4) {$2$};
\node at (4.2,3.3) {$4$};
\node at (4.2,-3.4) {$2$};
\node at (7.8,-3.4) {$2$};
\node at (10.5,-1.5) {$4$};
\end{tikzpicture}
\caption{The quotient-polynomial graph $\G\coloneqq K_2\otimes T_4$ and its intersection diagram. The adjacency algebra of $\G$ is closed with respect to the Hadamard product. If $\{F_0,F_1,F_2,F_3,F_4\}$ is the standard basis from Remark~\ref{gp}, then for a fixed vertex $x$ of $\G$ we have $\P_i=\{z \mid (F_i)_{xz}=1\}$ $(0\le i\le d)$.}
\label{gq}
}\end{figure}

\begin{defi}\label{gl}
Let $\G$ denote a graph with $d+1$ distinct eigenvalues. Given the walk-regular partition $\R=\{R_0,R_1,\ldots,R_r\}$ of $X\times X$, let $w_{ij}$ be the common value of the number of $i$-walks $(0\le i\le d)$ from $y$ to $z$ for any $y,z\in R_j$ $(0\le j\le r)$. Define the matrices $W$ and $Z$, and the polynomials $p_i(t)$ $(0\le i\le d)$ as follows:
\[
[W |\tt]=
\renewcommand\arraystretch{1.3}
\mleft[
\begin{array}{cccc|c}
w_{00} & w_{01} & \ldots & w_{0r} & 1\\
w_{10} & w_{11} & \ldots & w_{1r} & t\\
w_{20} & w_{21} & \ldots & w_{2r} & t^2\\
\vdots & \vdots & \, & \vdots & \vdots\\
w_{d0} & w_{d1} & \ldots & w_{dr} & t^d
\end{array}
\mright]
\stackrel{\row}{\sim}
\mleft[
\begin{array}{ccccccccc|c}
1 & * & 0 & 0 & \hdots&0& *&\hdots&*& p_1(t)\\
0 & 0 & 1 & 0 & \hdots&0& *&\hdots&*& p_1(t)\\
0 & 0 & 0 & 1 & \hdots&0& *&\hdots&*& p_2(t)\\
\vdots & \vdots & \vdots & \vdots &~& \vdots& \vdots &~ & \vdots & \vdots\\
0 & 0 & 0 & 0 & \hdots&1& *&\hdots&* & p_d(t)
\end{array}
\mright]=
[Z |\pp(t)],
\]
that is, the matrix $[Z|\pp(t)]$ is the reduced row-echelon form of $[W|\tt]$.
(As we will see in the next proof, $\rank(W)=d+1$.)
\end{defi}

\begin{theorem}
\label{gf}
Let $\G$ be a graph with vertex set $X$, $d+1$ distinct eigenvalues, and let $\R=\{R_0,R_1,\ldots,R_r\}$ denote a walk-regular partition of $X\times X$. Then,
\[
d\le r.
\]
Furthermore, let $Z$ denote the matrix of Definition~\ref{gl}, and define
\[
\W\coloneqq \left\{\ww(y,z) \mid y,z\in X \right\}.
\]
 Then the following are equivalent.
\begin{enumerate}[label=(\roman*)]
\item\label{Theo5.8_i} 
$d=r$.
\item\label{Theo5.8_ii}
$Z=I$.
\item\label{Theo5.8_iii}
$|\W|=d+1$.
\item\label{Theo5.8_iv}
$\W$ is a linearly independent set.
\item\label{Theo5.8_v}
$\G$ is a quotient-polynomial graph.
\end{enumerate}
\end{theorem}

\begin{proof}
Let $M_j$ denote the adjacency matrix of the relation $R_j$ $(0\le j\le r)$. Since $\R$ is a walk-regular partition, for the scalars $w_{ij}$ $(0\le i\le d,~0\le j\le r)$ of Definition~\ref{gl}, we have
\begin{align*}
 I & = w_{00} M_{0} + w_{01} M_1 + \cdots + w_{0r} M_r,\\
 A & = w_{10} M_{0} + w_{11} M_1 + \cdots + w_{1r} M_r,\\
 A^2 & = w_{20} M_{0} + w_{21} M_1 + \cdots + w_{2r} M_r,\\
&\phantom{{}={}} \vdots\\
A^d & = w_{d0} M_{0} + w_{d1} M_1 + \cdots + w_{dr} M_r.
\end{align*}
This yields $\spanrm\{I,A,\ldots,A^d\}\subseteq \spanrm\{M_0,M_1,\ldots,M_r\}$ as vector spaces, and hence $d\le r$.

Let $W$ denote the matrix from Definition~\ref{gl}. Note that the elements of the set $\W$ are columns of the matrix $W$, and since $\R$ is a walk-regular partition, $\W$ has exactly $r+1$ elements.

Also note that
\begin{equation}
\label{gu}
\rank(W)\ge d+1.
\end{equation}
Otherwise, if $\rank(W)<d+1$, applying elementary row operations on the above system, we get $A^d\in\spanrm\{I,A,\ldots,A^{d-1}\}$, a contradiction.

To prove equivalences between~\ref{Theo5.8_i}--\ref{Theo5.8_v}, we show the following chain of implications.


%\medskip
\ref{Theo5.8_i} $\Rightarrow$~\ref{Theo5.8_ii},~\ref{Theo5.8_v}.
If $d=r$ then $\rank(W)= d+1 = r+1$, which means that $Z=I$ and for every $M_i$ we have $M_i=p_i(A)$. This yields $M_i\in\A$, and $\G$ is a quotient-polynomial graph.

%\smallskip
\ref{Theo5.8_ii} $\Rightarrow$~\ref{Theo5.8_i},~\ref{Theo5.8_iii},~\ref{Theo5.8_iv}. If $Z=I$, since $Z$ is a $(d+1)\times(r+1)$ matrix, we have $r=d$. Moreover, we also have that $\rank(W)=d+1$. This yields $|\W|=d+1$ and $\W$ is a linearly independent set.

%\smallskip
\ref{Theo5.8_iii} $\Rightarrow$~\ref{Theo5.8_i},~\ref{Theo5.8_iv}.
If $|\W|=d+1$ then $d=r$ (since $\W$ has $r+1$ elements). If $\W$ is a linearly dependent set, then $\rank(W)<d+1$, which is a contradiction with~\eqref{gu}.

%\smallskip
\ref{Theo5.8_iv} $\Rightarrow$~\ref{Theo5.8_i}.
If $\W$ is a linearly independent set, then $\rank(W)\ge r+1$. On the other hand, since $d\le r$, and $W$ is $(d+1)\times(r+1)$ matrix, we have $\rank(W)\le d+1$. This yields $d=r$.


%\smallskip
\ref{Theo5.8_v} $\Rightarrow$~\ref{Theo5.8_i}.
If $\G$ is a quotient-polynomial graph then $M_i\in\A$ $(0\le i\le r)$. Then as vector spaces $\spanrm\{M_0,M_1,\ldots,M_r\}\subseteq\spanrm\{I,A,\ldots,A^d\}$, which yield $r\le d$. On the other hand, since $d\le r$, the result follows.
\end{proof}


\begin{coro}
\label{gs}
Let $\G$ denote a graph with $d+1$ distinct eigenvalues, and $x$-distance-faithful intersection diagram $\pi$ with $r+1$ cells. If $\G$ has the same $x$-distance-faithful intersection diagram around every vertex $x$, then $\G$ has at most $r+1$ eigenvalues. Moreover, if $r=d$ then $\G$ is a quotient-polynomial graph.
\end{coro}

\begin{proof}
The same intersection diagram around every vertex corresponds to a walk-regular partition of $X\times X$ with $r+1$ cells. The result now follows from Theorem~\ref{gf}.
\end{proof}

From the end of the proof of Theorem~\ref{gf}, the number of distinct entries of $A^i$ $(0\le i\le d)$ is important in deciding when $\G$ is not a quotient-polynomial graph.

\begin{coro}
\label{gs2}
Let $\G$ denote a graph with vertex set $X$ and $d+1$ distinct eigenvalues. If, for $i\in \{0,\ldots,d\}$, the matrix $A^i$ has more than $d+1$ distinct entries, then $\G$ is not a quotient-polynomial graph.
\end{coro}

\begin{proof}
Under the hypothesis, $A^i$ cannot be written as a linear combination of some $d+1$ $\circ$-idempotent $(0,1)$-matrices in $\{F_0,\ldots, F_d\}$ and, hence, $\A$ does not have a standard basis.
\end{proof}

\begin{comment}
\label{gr}
If $\G$ is a quotient-polynomial graph then the polynomials $p_i$ $(0\le i\le r)$ from Definition~\ref{gl} are orthogonal with respect to the scalar product~\eqref{ip2}, as happens with the distance polynomials of a distance-regular graph.
%$\langle f,g\rangle=\frac{1}{|X|}\trace(f(A){\ol{g(A)}}^\top)$.
Indeed, for every $i,j$ $(0\le i,j\le d)$, we have
\[
\langle p_i,p_j\rangle_{\G}= \langle p_i(A),p_j(A) \rangle_{\G}= \langle M_i,M_j \rangle_{\G}
%\frac{1}{|X|}\sum\limits_{u\in X}(M_i\ol{M_j}^\top)_{uu}
%=\frac{1}{|X|}\sum\limits_{u\in X}\sum\limits_{v\in X}(M_i)_{uv}(\ol{M_j})_{uv}
=\frac{1}{|X|}\sum\limits_{u,v\in X}(M_i\circ \ol{M_j})_{uv}
=0.
\]
Also, for the same polynomials $p_i$ $(0\le i\le r)$, we have that $\G$ is a regular and connected graph if and only if $\sum_{i=0}^r p_i(A)=J$.
\end{comment}

\begin{theorem}
\label{1f}
Let $\G$ denote a graph with vertex set $X$, $x$-distance-faithful intersection diagram $\pi_x$, and assume that $\pi_x$ has $r+1$ cells $\P_i$ with $\P_0=\{x\}$: $\pi_x=\{\P_0,\P_1,\ldots,\P_r\}$. Let $w_{ij}$ denote the number of $i$-walks $(0\le i\le r)$ from $y$ to $x$ for any $y\in\P_j$ $(0\le j\le r)$. Let $P=[w_{ij}]_{0\le i,j\le r}$ denote $(r+1)\times(r+1)$ matrix with entries $w_{ij}$. If $\G$ has the same $x$-distance-faithful intersection diagram around every $x\in X$ then $\G$ has exactly $\rank(P)$ distinct eigenvalues. Moreover, if $\rank(P)=r+1$ then $\G$ is a quotient-polynomial graph.
\end{theorem}

\begin{proof}
Using the intersection diagram $\pi_x=\{\P_0,\P_1,\ldots,\P_r\}$ around $x$, we can consider the column vectors
\begin{equation}
\label{gt}
\ww_0=\left(\begin{matrix}
w_{00}\\w_{10}\\w_{20}\\ \vdots\\w_{r0}\\
\end{matrix}\right),
\ww_1=\left(\begin{matrix}
w_{01}\\w_{11}\\w_{21}\\ \vdots\\w_{r1}\\
\end{matrix}\right),
\ldots,
\ww_r=\left(\begin{matrix}
w_{0r}\\w_{1r}\\w_{2r}\\ \vdots\\w_{rr}\\
\end{matrix}\right),
\end{equation}
where $w_{ij}$ denote the number of $i$-walks $(0\le i\le r)$ from $z$ to $x$ for any $z\in\P_j$ $(0\le j\le r)$. Note that we do not know whether it is $\ww_i\ne\ww_j$ for every $0\le i,j\le r$ or not. Now, pick a vertex $u\in X$ $(u\ne x)$, consider the intersection diagram $\pi_u=\{\P_0(u),\P_1(u),\ldots,\P_r(u)\}$, and let $\ww'_{ij}(u,v)$ denote the number of $i$-walks $(0\le i\le r)$ from $v$ to $u$ for any $v\in\P_j(u)$ $(0\le j\le r)$. Then, since $\G$ has the same intersection diagram around every vertex, the set of vectors
\[
\ww'_0(u,v),
\ww'_1(u,v),
\ldots,
\ww'_r(u,v),
\]
is the same as in~\eqref{gt}. That is, for every $i$ $(0\le i\le r)$ there exists exactly one $h$ $(0\le h\le r)$ such that $\ww_i=\ww'_h(u,v)$. Now we can define the matrices $M_i\in\Mat_{(r+1)\times(r+1)}(\CC)$ in the following way:
\[
(M_i)_{zy} =
\begin{cases}
1 & \hbox{if } \ww'_h(z,y)=\ww_i \hbox{ for some } h, \\
0 & \hbox{otherwise } \;
\end{cases}
\qquad (z,y \in X).
\]
This definition of $M_i$ yields that
\begin{equation}
\label{gw}
A^i=w_{i0}M_0+w_{i1}M_1+\cdots+w_{ir}M_r
\qquad(0\le i\le r).
\end{equation}
Also, since $\G$ has the same distance-faithful intersection diagram around every vertex, using this intersection diagram we can construct a walk-regular partition of $X\times X$ with $r+1$ basis relations $R_i$. So, by Theorem~\ref{gf}, $d\le r$. By assumptions
\[
P=
\mleft[
\begin{array}{cccc}
w_{00} & w_{01} & \ldots & w_{0r}\\
w_{10} & w_{11} & \ldots & w_{1r}\\
w_{20} & w_{21} & \ldots & w_{2r}\\
\vdots & \vdots & \, & \vdots\\
w_{r0} & w_{r1} & \ldots & w_{rr}
\end{array}
\mright].
\]
Now using~\eqref{gw} and the fact that $\dim(\A)=d+1$, it follows $\rank(P)=d+1$. If $\rank(P)=r+1$ the result follows from Theorem~\ref{gf}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Algorithmic approach for deciding whether \texorpdfstring{$A_i$}{Ai} is a polynomial in \texorpdfstring{$A$}{A} or not}
\label{gn}

In this subsection we give an algorithm which, for a given graph $\G$, decides whether $A_i$ $(0\le i\le D)$ is a polynomial (not necessarily of degree $i$) in $A$ or not. If the answer is in the affirmative, then the algorithm also computes that polynomial. Note that this procedure can be seen as a refinement of the mentioned
procedure to check distance-regularity, since it allows also to decide whether $\G$ is distance-polynomial ($A_i\in \A$ for every $i=0,\ldots,D$) or not.

\begin{algorithm}
\label{gi}
Let $A$ denote the adjacency matrix of $\G$ with $d+1$ distinct eigenvalues and diameter $D$. Considering only the matrix $Z$ (from Definition~\ref{gl}) we can determine which distance-$i$ matrix is a polynomial in $A$ (see Example~\ref{gh}).

\smallskip
\noindent
\gras{Input:} The adjacency matrix $A$ of $\G$, or intersection diagrams around every vertex.\\
\noindent
\gras{Output:} A polynomial $p_i$ such that $A_i=p_i(A)$ (if such a polynomial exists).
\begin{enumerate}[label=\arabic*.]
\item %[{\bf 1.}]
Using the adjacency matrix $A$ of $\G$ (or using intersection diagrams around every vertex), compute the vectors $\ww(y,z)$ for every $y,z\in X$ (see Definition~\ref{gb} and Remark~\ref{gm}).
\item %[{\bf 2.}]
Find the matrices $[W\mid\tt]$, $[Z\mid\pp(t)]$, and the polynomials $p_i(t)$ $(0\le i\le d)$ from Definition~\ref{gl}.
\item %[{\bf 3.}]
The columns of the matrices $W$ and $Z$ are indexed by the sets $\{R_0,R_1,\ldots,R_r\}$ (where $\R=\{R_0,R_1,\ldots,R_r\}$ is the walk-regular partition of $X\times X$). Let $R_{i_1},R_{i_2},\ldots,R_{i_k}$ denote the equivalence classes for which all pair of vertices in any $R_{i_h}$ $(0\le h\le k)$ are at the same distance. These relations represent the columns $i_h$ $(0\le h\le k)$ in $[W|\tt]$ and $[Z| \pp(t)]$. Let $p_{j_1},p_{j_2},\ldots,p_{j_m}$ denote the polynomials which have nonzero entry in the columns ${i_h}$ $(0\le h\le k)$ of $Z$.
\item %[{\bf 4.}]
If the sum of the rows ${j_1},{j_2}, \ldots, {j_m}$ of $Z$ is a $(0,1)$-row vector for which the nonzero entry is only in columns $R_{i_1}, R_{i_2}, \ldots, R_{i_k}$, and vice versa, then the adjacency matrix $A_i$ is polynomial in $A$, and we have $A_i=p_{j_1}(A)+p_{j_2}(A)+\cdots+p_{j_m}(A)$. Otherwise, $A_i$ is not polynomial in $A$.
\end{enumerate}
\end{algorithm}


\begin{figure}[!ht]\centering
{%%\tiny
\small
%\begin{center}
\begin{tikzpicture}[scale=.3]
\fill (5.437550622520739,3.686217782649107) circle [radius=0.2];
\fill (6.221332839871632,6.4437684051698465) circle [radius=0.2];
\fill (5.521332839871632,9.223768405169846) circle [radius=0.2];
\fill (3.5251150572225267,11.281319027690586) circle [radius=0.2];
\fill (0.7675644347017866,12.065101245041479) circle [radius=0.2];
\fill (-2.0124355652982127,11.36510124504148) circle [radius=0.2];
\fill (-4.069986187818953,9.368883462392375) circle [radius=0.2];
\fill (-4.853768405169847,6.611332839871634) circle [radius=0.2];
\fill (-4.153768405169848,3.831332839871636) circle [radius=0.2];
\fill (-2.157550622520742,1.7737822173508944) circle [radius=0.2];
\fill (0.6,0.99) circle [radius=0.2];
\fill (3.38,1.69) circle [radius=0.2];
\draw (-2.0124355652982127,11.36510124504148)-- (5.521332839871632,9.223768405169846);
\draw (3.5251150572225267,11.281319027690586)-- (5.437550622520739,3.686217782649107);
\draw (0.7675644347017866,12.065101245041479)-- (-4.853768405169847,6.611332839871634);
\draw (-4.069986187818953,9.368883462392375)-- (-2.157550622520742,1.7737822173508944);
\draw (6.221332839871632,6.4437684051698465)-- (0.6,0.99);
\draw (3.38,1.69)-- (-4.153768405169848,3.831332839871636);
\draw (-2.0124355652982127,11.36510124504148)-- (-4.069986187818953,9.368883462392375);
\draw (-4.069986187818953,9.368883462392375)-- (-4.853768405169847,6.611332839871634);
\draw (-4.853768405169847,6.611332839871634)-- (-4.153768405169848,3.831332839871636);
\draw (-4.153768405169848,3.831332839871636)-- (-2.157550622520742,1.7737822173508944);
\draw (-2.157550622520742,1.7737822173508944)-- (0.6,0.99);
\draw (0.6,0.99)-- (3.38,1.69);
\draw (3.38,1.69)-- (5.437550622520739,3.686217782649107);
\draw (5.437550622520739,3.686217782649107)-- (6.221332839871632,6.4437684051698465);
\draw (6.221332839871632,6.4437684051698465)-- (5.521332839871632,9.223768405169846);
\draw (5.521332839871632,9.223768405169846)-- (3.5251150572225267,11.281319027690586);
\draw (3.5251150572225267,11.281319027690586)-- (0.7675644347017866,12.065101245041479);
\draw (0.7675644347017866,12.065101245041479)-- (-2.0124355652982127,11.36510124504148);
\end{tikzpicture}
\qquad
\begin{tikzpicture}[scale=.6]
\draw (1,3) circle [radius=0.6];
\node at (1,3) {{\small$\P_0$}};
\node at (1.5,3.75) {$2$};
\node at (1.5,2.25) {$1$};
%%\node at (0.8,3.8) {{\small$\P_0$}};
\node at (1,2.2) {{\small --}};


\draw (3,1) circle [radius=0.6];
\node at (3,1) {{\small$\P_2$}};
\node at (2.25,1.5) {$1$};
\node at (3.75,0.75) {$2$};
%%\node at (3,1.8) {{\small$\P_2$}};
\node at (3,0.2) {{\small --}};

\draw (3,5) circle [radius=0.6];
\node at (3,5) {{\small$\P_1$}};
\node at (2.25,4.5) {$1$};
\node at (3.5,4.25) {$1$};
\node at (3.75,5.25) {$1$};
%%\node at (3,5.8) {{\small$\P_1$}};
\node at (3,4.2) {{\small --}};

\draw (7,1) circle [radius=0.6];
\node at (7,1) {\small$\P_4$};
\node at (6.25,0.75) {$1$};
\node at (6.5,1.75) {$1$};
\node at (7.75,0.75) {$1$};
%%\node at (7,1.8) {{\small$\P_4$}};
\node at (7,0.2) {{\small --}};

\draw (7,5) circle [radius=0.7];
\node at (7,5) {{\small$\P_3$}};
\node at (6.25,5.25) {$1$};
\node at (7.75,5.25) {$1$};
\node at (7.5,4.25) {$1$};
%%\node at (7,5.8) {{\small$\P_3$}};
\node at (7,4.2) {{\small --}};

\draw (11,1) circle [radius=0.6];
\node at (11,1) {{\small$\P_6$}};
\node at (10.25,0.75) {$1$};
\node at (10.5,1.75) {$1$};
\node at (11.75,1.5) {$1$};
%%\node at (11,1.8) {{\small$\P_6$}};
\node at (11,0.2) {{\small --}};

\draw (11,5) circle [radius=0.6];
\node at (11,5) {\small$\P_5$};
\node at (10.25,5.25) {$2$};
\node at (11.75,4.5) {$1$};
%%\node at (11,5.8) {{\small$\P_5$}};
\node at (11,4.2) {{\small --}};

\draw (13,3) circle [radius=0.6];
\node at (13,3) {\small$\P_7$};
\node at (12.5,3.75) {$1$};
\node at (12.5,2.25) {$2$};
%%\node at (13.2,3.8) {{\small$\P_7$}};
\node at (13,2.2) {{\small --}};
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\draw (1.43,2.57)--(2.57,1.43);
\draw (1.43,3.43)--(2.57,4.57);

\draw (3.6,1)--(6.4,1);
\draw (3.6,5)--(6.4,5);
\draw (3.43,4.57)--(6.57,1.43);

\draw (7.6,1)--(10.4,1);
\draw (7.43,4.57)--(10.57,1.43);
\draw (7.6,5)--(10.4,5);

\draw (11.43,1.43)--(12.57,2.57);
\draw (11.43,4.57)--(12.57,3.43);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{tikzpicture}
\caption{``Chordal ring'' $(12,4)$ and its intersection diagram. This graph has the same intersection diagram around every vertex and adjacency algebra $\A$ is not closed with respect to Hadamard product. If $\R=\{R_0,R_1,\ldots,R_7\}$ is the walk-regular partition and $F_i$ $(0\le i\le 7)$ are adjacency matrices of $R_i$ $(0\le i\le 7)$, then for a fixed vertex $x$ of $\G$ we have $\P_i=\{z \mid (F_i)_{xz}=1\}$ $(0\le i\le 7)$.}
\label{gg}
%\end{center}
}
\end{figure}

\begin{exam}
\label{gh}
Assume that $\G$ is the graph from Figure~\ref{gg}. Using the intersection diagram we can compute the adjacency matrix $B\in\Mat_{8\times 8}(\CC)$ of intersection diagram, and using $B$, we can compute the numbers $w_{ij}$ from Definition~\ref{gl} (for example, a number $(B^\ell)_{\P_3,\P_0}$ is the number $w_{\ell 3}$ $(0\le\ell\le 7)$). Since we do not know the number of distinct eigenvalues, using Corollary~\ref{gs} we know that $\G$ will not have more then $8$ of them. So we can compute the matrices $W$ and $Z$ with $8$ rows and $8$ columns. We have
\[
\underbrace{\left(\begin{array}{cccccccc|c}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & t\\
3 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & t^2\\
0 & 6 & 7 & 0 & 0 & 2 & 3 & 0 & t^3\\
19 & 0 & 0 & 11 & 16 & 0 & 0 & 8 & t^4\\
0 & 46 & 51 & 0 & 0 & 30 & 35 & 0 & t^5\\
143 & 0 & 0 & 111 & 132 & 0 & 0 & 100 & t^6\\
0 & 386 & 407 & 0 & 0 & 322 & 343 & 0 & t^7
\end{array}\right)}_{=[W|\tt]}
\stackrel{\row}{\sim}
\underbrace{
\left(\begin{array}{cccccccc|c}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & p_0(t)\\
0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & p_1(t)\\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & p_2(t)\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & p_3(t)\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & p_4(t)\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & p_5(t)\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & p_6(t)\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & *
\end{array}\right)
}_{=[Z\mid\pp(t)]}
\]
where polynomials $p_i(t)$ $(0\le i\le 6)$ are
\begin{gather*}
p_0(t)=1,\qquad
p_1(t)=\frac{1}{10}t^5 - \frac{3}{2} t^3 + \frac{27}{5} t,\qquad
p_2(t)=-\frac{1}{10} t^5 + \frac{3}{2}t^3 - \frac{22}{5} t,\qquad
\\
p_3(t)=\frac{2}{15}t^6 - \frac{5}{3}t^4 + \frac{68}{15}t^2 - 1,\qquad
p_4(t)=-\frac{1}{15}t^6 + \frac{5}{6}t^4 - \frac{53}{30}t^2 - 1,%\qquad
\\
p_5(t)=\frac{1}{20}t^5 - \frac{1}{4}t^3 - \frac{4}{5}t,\qquad
p_6(t)=-\frac{1}{20} t^6 + \frac{3}{4} t^4 - \frac{27}{10} t^2 + 1.
\end{gather*}
Since $\rank(W)=7$, $\G$ has $7$ distinct eigenvalues, which imply that the polynomial $p_7(t)$ is not important. Note that $A_0=p_0(A)$, $A_1=p_1(A)+p_2(A)$, $A_2=p_3(A)+p_4(A)$, $A_3=p_5(A)$ and $A_4=p_6(A)$. Therefore, every distance-$i$ matrix can be written as a polynomial in $A$ and $\sum_{i=0}^6 p_i(t)$ is the Hoffman polynomial. Thus, by Theorem~\ref{gf}, $\G$ is not a quotient-polynomial graph.
\end{exam}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\section{Proof of Theorem~\ref{1d}}
\section{Some characterizations of quotient-polynomial graphs}
\label{4a}

%In this section we prove Theorems~\ref{1d} and~\ref{1h}.
%First we prove Theorem~\ref{1d}.
%(The adjacency algebra of $\G$ is closed under Hadamard product if and only if $\G$ is a quotient-polynomial graph).

For the moment assume that $\G$ is a distance-regular graph with diameter $D$. Note that intersection diagram of a distance partition around $x$ of $\G$ has $D+1$ cells, and is the same for every $x\in X$ (also it is $x$-distance-faithful). So as an immediate corollary of Theorem~\ref{1f}, the number of distinct eigenvalues of a distance-regular graph $\G$ is $\le D+1$. Also note that the nonnegative integer $w_{ij}$ from the Theorem~\ref{1f} can be computed from the $x$-distance-faithful intersection diagram.

The following result follows from~\cite[Theorem~4.1]{FQ}. Here we give an alternative proof for completeness and clarity. It establishes a connection between the structure of $\G$ and Problem~\ref{1b}.

\begin{theorem}
\label{1d}
Let $\G$ denote a regular graph with $d+1$ distinct eigenvalues. Then, the vector space $\A=\spanrm\{I,A,\ldots,A^d\}$ is closed under Hadamard multiplication if and only if $\G$ is a quotient-polynomial graph.
\end{theorem}
\begin{proof}
Assume that $\G$ is a quotient-polynomial graph. Let $F_i$ $(0\le i\le d)$ denote the adjacency matrix of the equivalence class $R_i$ $(0\le i\le d)$ of a walk-regular partition $\R=\{R_0,R_1,\ldots,R_d\}$ of $X\times X$.
By definition, $\{I=F_0,F_1,\ldots,F_d\}$ is a linearly independent set such that $F_i\circ F_j=\delta_{ij}F_i$, and $\sum_{i=0}^d F_i=J$. Moreover since $F_i\in\A$ we have $\spanrm\{F_0,F_1,\ldots,F_d\}\subseteq \A$. Thus, the vector space $\A$ is closed under both ordinary and Hadamard multiplication.

Conversely, assume that the vector space $\A$ is closed under both ordinary and Hadamard multiplication. By Theorem~\ref{1c}, since $\G$ is a regular graph, the algebra $\A$ has the standard basis $\{I=F_0,F_1,\ldots,F_d\}$. Then, there exists scalars $\alpha_{ij}$ $(0\le i,j\le d)$ such that
\begin{equation}
\label{4b}
A^\ell = \sum_{j=0}^d \alpha_{\ell j} F_j \qquad (0\le\ell\le d).
\end{equation}
Now, by~\eqref{4b}, if $u,v,y,z\in X$ are vertices such that $(F_i)_{uv}=1$ and $(F_i)_{yz}=1$ $(0\le i\le d)$, then the number of walks of length $\ell$ from $u$ to $v$, is equal to the number of walks of length $\ell$ from $y$ to $z$ $(0\le\ell\le d)$. This implies that the matrices $F_i$ correspond to the basis relations $R_i$ $(0\le i\le d)$, and that $\R=\{R_0,R_1,\ldots,R_d\}$ is a walk-regular partition of $X\times X$. Since $F_i\in\A$ the result follows.
\end{proof}

\begin{coro}
Let $\G$ be a graph with adjacency matrix $A$ and $d+1$ distinct eigenvalues. If some matrix in $\{A^2,\ldots,A^d\}$ has more than $d+1$ distinct entries, then $\A$ is not closed under Hadamard product.
\end{coro}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\section{Proof of Theorem~\ref{1h}}
%\label{4d}

Now we prove Theorem~\ref{1h}.
(A regular graph $\G$ with diameter $2$ and $4$ distinct eigenvalues is quotient-polynomial if and only if either
any two nonadjacent (respectively, adjacent) vertices have a constant number of common neighbours, and the number of common neighbours of any two adjacent (respectively, nonadjacent) vertices takes precisely two values.)

The proof can be seen as a very nice application of the walk-regular partition from Section~\ref{go}.

\begin{theorem}
\label{1h}
Let $\G$ denote a regular connected graph with diameter $2$ and $4$ distinct eigenvalues. Then the vector space $\A=\spanrm\{I,A,A^2,A^3\}$ is closed under Hadamard multiplication if and only if either~\ref{Theo6.3_i} or~\ref{Theo6.3_ii} below hold.
\begin{enumerate}[label=(\roman*)]
\item\label{Theo6.3_i} %[{\rm (i)}]
Any two nonadjacent vertices have a constant number of common neighbours, and the number of common neighbours of any two adjacent vertices takes precisely two values.
\item\label{Theo6.3_ii} %[{\rm (ii)}]
Any two adjacent vertices have a constant number of common neighbours, and the number of common neighbours of any two nonadjacent vertices takes precisely two values.
\end{enumerate}
\end{theorem}

\begin{proof} %\ \\*[-1.2em]
%\begin{itemize}
%\item[
$(\Rightarrow)$ %]
Assume that the vector space $\A=\spanrm\{I,A,A^2,A^3\}$ is closed under Hadamard multiplication. By Theorem~\ref{1c}, $\A$ has the standard basis $\{F_0,F_1,F_2,F_3\}$ consisting of $\circ$-idempotents. For every $\ell$ $(0\le\ell\le 3)$ there exist scalars $\alpha_{\ell i}$ $(0\le i\le 3)$ such that
\[
A^\ell=\alpha_{\ell 0} F_0 +\alpha_{\ell 1} F_1 +
\alpha_{\ell 2} F_2 + \alpha_{\ell 3} F_3.
\]
This implies that if $(F_i)_{yz}\ne 0$ then $(A^\ell)_{yz}=\alpha_{\ell i}$. Thus, for every $y,z,u,v\in X$, if $(F_i)_{yz}\ne 0$ and $(F_i)_{uv}\ne 0$ then
\[
(A^\ell)_{yz}=(A^\ell)_{uv}
\qquad
(0\le \ell\le 3).
\]
Now, we can obtain a walk-regular partition $\R=\{R_0,R_1,R_2,R_3\}$ (see Definition~\ref{ga}) in the following way:
\[
(z,y)\in R_i
\qquad\Leftrightarrow\qquad
(F_i)_{zy}\ne 0
\qquad(0\le i\le 3).
\]
By the paragraph after Definition~\ref{gb}, all pairs of vertices in a given $R_i$ are at the same distance. This implies that if $(F_i)_{zy}\ne 0$ and $(F_i)_{uv}\ne 0$ then $\dist(z,v)=\dist(u,v)$ for every $z,y,u,v\in X$. Permute indices of the set $\{F_0,F_1,F_2,F_3\}$ so that $F_0=I$, and, for any $i\le j$ and $(F_i)_{zy}\ne 0$, $(F_j)_{uv}\ne 0$ we have $\dist(z,y)\le \dist(u,v)$. Since $\G$ is a graph of diameter $2$, $(F_3)_{zy}\ne 0$ implies $\dist(z,y)=2$. Since there exist scalars $\beta_i$ $(0\le i\le 3)$ such that
\[
A=\beta_0 I + \beta_1 F_1 + \beta_2 F_2+ \beta_3 F_3
\]
and since $A$ is a $(0,1)$-matrix, we have $\beta_0=0$ and only one of the following two cases are possible: $A=F_1+F_2$ or $A=F_1$.

%\medskip
%\begin{itemize}
%\item[\emph{Case 1.}]
\begin{enonce*}[remark]{Case 1}
Assume that $A=F_1+F_2$. This yields $F_3=A_2$. Now, it is not hard to see that there exists scalars $k,\lambda_1,\lambda_2,\mu$ such that
\[
A^2= k I + \lambda_1 F_1 + \lambda_2 F_2 + \mu F_3,
\]
and the result follows.
\end{enonce*}

%\item[\emph{Case 2.}]
\begin{enonce*}[remark]{Case 2}
Assume that $A=F_1$. This yields $F_2+F_3=A_2$. Now, there exists scalars $k,\lambda,\mu_1,\mu_2$ such that
\[
A^2= k I + \lambda F_1 + \mu_1 F_2 + \mu_2 F_3,
\]
and the result follows.
\end{enonce*}
%\end{itemize}

%\item[
$(\Leftarrow)$ %]
Assume that $\G$ has the property~\ref{Theo6.3_i}, that is any two vertices at distance two have exactly $\mu$ common neighbours, and for every adjacent $x,y\in X$ we have $|\G(x)\cap\G(y)|\in\{\lambda_1,\lambda_2\}$. Define the matrices $\{F_0,F_1,F_2,F_3\}$ as $F_0\coloneqq I$, $F_1+F_2=A$ where
\[
(F_1)_{xy}=1
\qquad\mbox{if and only if}\qquad
\dist(x,y)=1 \mbox{ and } |\G(x)\cap\G(y)|=\lambda_1
\qquad (x,y\in X),
\]
and let $F_3=A_2$. Since $\G$ is regular $J\in\A$. Note that $I+A+A_2=J$ yields $A_2\in\A$, and with that $F_3\in\A$. Let $k$ denote the valency of $\G$. Computing $A^2$ we have
\[
A^2=kI+\lambda_1F_1+\lambda_2F_2+\mu A_2=
kI+\lambda_1F_1+\lambda_2(A-F_1)+\mu A_2
\]
which yields $F_1\in\A$. Since $F_2=A-F_1$ we also have $F_2\in\A$. By construction the set $\{F_0,F_1,F_2,F_3\}$ is linearly independent set consisting of $\circ$-idempotents. Thus we showed that $\spanrm\{F_0,F_1,F_2,F_3\}\subseteq\A$. The result follows.


If we assume that $\G$ has the property~\ref{Theo6.3_ii}, the proof is similar as above (consider the set of $(0,1)$-matrices $\{I,A,F_2,F_3\}$ where $F_2+F_3=A_2$, and $(F_2)_{xy}=1$ if and only if $\dist(x,y)=2$ and $|\G(x)\cap\G(y)|=\mu_1$).\qedhere%\vspace{-7mm}
%\end{itemize}
\end{proof}

%\medskip
The two families of graphs from Theorem~\ref{1h} are in fact a subfamily of quasi-strongly regular graphs (see~\cite{Gol}).
Indeed, note that if $\G$ is a graph for which property~\ref{Theo6.3_i} of Theorem~\ref{1h} holds, then the distance-$2$ matrix of $\G$ is the adjacency matrix of $\ol{\G}$ (complement of $\G$, which have the property that any two adjacent vertices have a constant number of common neighbours, and the number of common neighbours of any two nonadjacent vertices takes precisely two values). With this in mind, it follows a result of Van Dam from~\cite{ED}:

\begin{theorem}[{\cite[Theorem~5.1]{ED}}]
\label{4f}
Let $\G$ be a connected regular graph with four distinct eigenvalues and diameter $2$. Then $\G$ is one of the relations of a $3$-class association scheme if and only if any two adjacent vertices have a constant number of common neighbours, and the number of common neighbours of any two nonadjacent vertices takes precisely two values.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The existence of an idempotent generator}
\label{5a}

Now we prove that a given $F\in \{F_0,F_1,\ldots,F_d\}$ has $d+1$ distinct eigenvalues if and only if $\langle F_0,F_1,\ldots,F_d \rangle=\langle I,F,\ldots,F^d\rangle$.

\begin{theorem}
\label{1e}
Let $\G$ denote a quotient-polynomial graph with $d+1$ distinct eigenvalues, and let $\{I,F_1,\ldots,F_d\}$ denote the standard basis of the adjacency algebra $\A$. Pick $F\in\{F_0,F_1,\ldots,F_d\}$. Then $F$ has $d+1$ distinct eigenvalues if and only if $\spanrm\{F_0,F_1,\ldots,F_d\}=\spanrm\{I,F,\ldots,F^d\}$.
\end{theorem}

%%{\em Proof. }
\begin{proof}
We already know that, for any real symmetric matrix $B$ with $s+1$ distinct eigenvalues, the set $\{I,B,\ldots,B^s\}$ is a basis of the algebra $\{p(B)\mid p\in\RR[t]\}$.

%\begin{itemize}
%\item[
$(\Leftarrow)$ %]
Assume that $\A=\spanrm\{I,F,\ldots,F^d\}$. This yield that $\{I,F,\ldots,F^d\}$ is also a basis of $\A$, that is, it is maximal linearly independent set. Thus $F$ have $d+1$ distinct eigenvalues.

%\item[
$(\Rightarrow)$ %]
 Now assume that $F$ has $d+1$ distinct eigenvalues, and let $\F$ denote the algebra generated by the set $\{I,F^1,\ldots,F^d\}$. Since $\{I,F_1,\ldots,F_d\}$ is a basis of $\A$ we have that $F^i\in\A$ for every $i\in\NN$. This yields $\F\subseteq\A$, that is $\dim(\F)\le d+1$. Now since $F$ has $d+1$ distinct eigenvalues, $\dim(\F)=d+1$, and the result follows. %\vspace{-7mm}
%%\hfill$\hbox{\rule{3pt}{6pt}}$
%\end{itemize}
\end{proof}

\begin{exam}
Let $\G$ denote the bipartite $2$-walk-regular graph with diameter $4$ and $6$ distinct eigenvalues from~\cite[Theorem~2]{JK}. By such a theorem, $\G$ generates an association scheme with $5$ classes. Let $\{A_0,A_1,\ldots,A_5\}$ denote the adjacency matrices of this association scheme. Considering its first eigenmatrix $P$~\cite[Section~3]{JK}, we can conclude that $A_1$ and $A_3$ have 6 different eigenvalues. Thus, both of these matrices generate the algebra $\A$ of $\G$, which is closed under Hadamard multiplication.
\end{exam}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Further directions}
\label{6a}


Let $\G$ denote a quotient-polynomial graph with vertex set $X$, $d+1$ distinct eigenvalues, and let $\{I,F_1,\ldots,F_d\}$ be the standard basis of the adjacency algebra $\A$ of $\G$.


Since $\{E_0,E_1,\ldots,E_d\}$ is also a basis of $\A$, there exist numbers $q^h_{ij}$ such that
\begin{equation}
\label{6b}
E_i\circ E_j=\frac{1}{|X|}\sum_{h=0}^d q^h_{ij} E_h
\qquad(0\le i,j\le d).
\end{equation}
The numbers $q^h_{ij}$ are called the \emph{Krein parameters} for $\G$ with respect to the ordering $E_0,E_1,\ldots,E_d$ of its basis of primitive idempotents. An ordering $E_0,E_1,\ldots,E_d$ is a \emph{cometric ($Q$-polynomial\/) ordering} if the following conditions are satisfied:
\begin{enumerate}[label=(Q\arabic*)]
\item
$q^h_{ij}=0$ whenever any one of the indices $i,j,h$ exceed the sum of the remaining two, and
\item
$q^h_{ij}>0$ when $0\le i,j,h\le d$ and any one of the indices equals the sum of the remaining two.
\end{enumerate}
We say that $\G$ is a \emph{cometric} (or \emph{$Q$-polynomial}) quotient-polynomial graph when such an ordering exists. In the future, we plan to study algebraic and combinatorial properties of cometric quotient-polynomial graphs. This $Q$-polynomial concept is taken from the theory of commutative association schemes. A good introduction to the topic of $Q$-polynomial structures for association schemes and distance-regular graphs can be found in~\cite{GD}. For a new technique (and approach) about computations in Bose--Mesner algebras, which also deals with $Q$-polynomial case, we recommend~\cite[Section~3]{WMS}.


Fix a ``base vertex'' $x\in X$. For each $i$ $(0\le i\le D)$ let $F^*_i=F^*_i(x)$ denote the diagonal matrix in $\Mat_X(\CC)$ with $(y,y)$-entries $(F^*_i)_{yy}=(F_i)_{xy}$. The \emph{Terwilliger} (or \emph{subconstituent}) algebra $\T=\T(x)$ of $\G$ with respect to $x$ is the subalgebra of $\Mat_X(\CC)$ generated by $\{I,F_1,\ldots,F_d,F^*_0,F^*_1,\ldots,F^*_D\}$. By a $T$-{\em module} we mean a subspace $\W$ of $\V=\CC^X$ such that $B\W \subseteq \W$ for all $B \in \T$. Let $\W$ denote a $T$-module. Then $\W$ is said to be {\em irreducible} whenever $\W$ is nonzero and $\W$ contains no $T$-modules other than $0$ and $\W$. In the future we plan to study irreducible $T$-modules of quotient-polynomial graph $\G$. This $T$-module concept is also taken from the theory of commutative association schemes~\cite{T1, T3, T4}. For most recent research on the use of Terwilliger algebra in the study of $P$-polynomial association schemes (that is, using the Terwilliger algebra to study distance-regular graphs) see~\cite{CW, MM1, MM2, MMP1, MMP2, MSq, MJV, MX, PS}.

Another possible line of research would be the study of ``pseudo-quotient-polynomial graphs'', defined by using weighted regular partitions,
see~\cite{Fei}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


At the end, let $\G$ denote $k$-regular graph with adjacency matrix $A$. We are interested in finding which ``known'' family of polynomials $\{q_i(x)\}_{i=0}^d$ will produce the standard basis $\{q_i(A)\}_{i=0}^d$ of $\mathcal{A}$, and in connections between ``known'' families of polynomials with our polynomials from Definition~\ref{gl}. For example, it would be nice to use our polynomials in a similar way as it is done in~\cite{f21}. 
 %[https://doi.org/10.1016/j.disc.2020.112235].
In that paper, the author studied polynomials $\{G_{i,k}(x)\}_{i=0}^d$ defined by $G_{k,0}(x)=1$, $G_{k,1}(x)=x+1$, and
\[
G_{k,i+2}(x)=xG(k,i+1)-(k-1)G_{k,i}(x) \quad\mbox{ for } i\ge 0,
\]
to give a lower bound for the discriminant of the polynomials $\{G_{i,k}(x)\}_{i=0}^d$. As explained in
\cite[p.~2]{f21},
% [https://doi.org/10.1016/j.disc.2020.112235, page 2],
the $(x,y)$-entry of $G_{k,i}(A)$ counts the number of paths of length $i$ joining the vertices $x$ and $y$. For example, one question can be what happens if, in our algorithms, we replace our polynomials by the family $\{G_{i,k}\}_{i=0}^d$ or by the family $\{F_{k,i}(x)\}_{i=0}^d$, where $\{F_{k,i}(x)\}_{i=0}^d$ are defined by $F_{k,0}(x)=1$, $F_{k,1}(x)=x$, $F_{k,2}(x)=x^2-k$, and
\[
F_{k,i+2}(x)=xF_{k,i+1}(x)-(k-1)F_{k,i}(x) \quad\mbox{ for } i\ge 1
\]
(see~\cite{f21}). Also, one line of research could be to find out what kind of graphs we get if, for example, the set of matrices $\{G_{i,k}(A)\}_{i=0}^d$ is orthogonal with respect to the inner product~\eqref{ip2}.
%{\small
%\bibliographystyle{references}
%\bibliography{symAssSchRegGRaph}
%}




 
\longthanks{The authors thank the anonymous reviewers for helpful and constructive comments that contributed to improving the final version of the paper.}


\nocite{*}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Fiol_507}
\end{document}