On Hoffman polynomials of $\lambda$-doubly stochastic irreducible matrices and commutative association schemes

Abstract

Let $\Gamma$ denote a finite (strongly) connected regular (di)graph with adjacency matrix $A$. The {\em Hoffman polynomial} $h(t)$ of $\Gamma =\Gamma (A)$ is the unique polynomial of smallest degree satisfying $h(A)=J$, where $J$ denotes the all-ones matrix. Let $X$ denote a nonempty finite set. A nonnegative matrix $B\in{\mbox{Mat}}_X({\mathbb R})$ is called {\em $\lambda$-doubly stochastic} if ${\sum }_{z\in X}(B{)}_{yz}={\sum }_{z\in X}(B{)}_{zy}=\lambda$ for each $y\in X$. In this paper we first show that there exists a polynomial $h(t)$ such that $h(B)=J$ if and only if $B$ is a $\lambda$-doubly stochastic irreducible matrix. This result allows us to define the Hoffman polynomial of a $\lambda$-doubly stochastic irreducible matrix. Now, let $B\in{\mbox{Mat}}_X({\mathbb R})$ denote a normal irreducible nonnegative matrix, and $\mathcal{B}=\{p(B)\mid p\in \mathbb{C}[t]\}$ denote the vector space over $\mathbb{C}$ of all polynomials in $B$. Let us define a $01$-matrix $\hat{A}$ in the following way: $(\hat{A}{)}_{xy}=1$ if and only if $(B{)}_{xy}>0$ $(x,y\in X)$. Let $\Gamma =\Gamma (\hat{A})$ denote a (di)graph with adjacency matrix $\hat{A}$, diameter $D$, and let $A_D$ denote the distance-$D$ matrix of $\Gamma$. We show that $\mathcal{B}$ is the Bose--Mesner algebra of a commutative $D$-class association scheme if and only if $B$ is a normal $\lambda$-doubly stochastic matrix with $D+1$ distinct eigenvalues and $A_D$ is a polynomial in $B$.