Natural graph spectra Ziqing Xiang Abstract In 2003, van Dam and Haemers posed a fundamental question in spectral graph theory: does there exist a “sensible” matrix whose spectrum determines a random graph up to isomorphism? This paper introduces the class of natural graph matrices , which are matrices defined by applying a fixed sequence of elementary operations to the adjacency matrix. This class includes many standard matrices such as the adjacency matrix, the Seidel matrix, the Laplacian matrix, and the distance matrix. We give an affirmative answer to the question of van Dam and Haemers by proving the existence of a natural graph matrix whose spectrum determines random graphs up to isomorphism. The proof introduces a new algebraic framework called double algebras , which provides a simple sufficient condition for spectral determination. This sufficient condition is then shown to hold for random graphs. \DeclareDatamodelConstant [type=list]namepartsfamily,given,given-i 1 Introduction The extent to which a graph is determined by the spectrum of an associated matrix is a foundational problem in spectral graph theory. This problem dates back to the 1950s, initially studied by chemists in the context of the adjacency spectrum. Two comprehensive surveys by van Dam and Haemers in 2003 and 2009 [ 8 , 9 ] summarize the development of this problem. In [ 8 ] , they conjectured that almost all graphs are determined by their adjacency spectra. Moreover, they posed the question: for which “sensible” matrices does the spectrum determine the graph up to isomorphism? We refer to this as the Determined by Spectrum (DS) problem. The DS problem is naturally connected to the Graph Isomorphism (GI) problem because if a graph is determined by its spectrum, then one could test isomorphism by comparing spectra (provided the spectra can be computed efficiently). However, since GI is believed to be computationally hard, one cannot expect a simple spectrum to determine every graph. On the other hand, it is well-known that GI is easy for random graphs. Indeed, Babai, Erdős and Selkow [ 2 ] gave a linear-time algorithm for testing isomorphism of random graphs. This suggests that the DS problem might have a positive answer for random graphs with respect to some matrix spectra. There is a large body of work on various types of spectra, both on the DS problem specifically and in spectral graph theory more generally. Commonly studied spectra include those of the adjacency matrix [ 7 ] , the adjacency matrix of the complement [ 10 , 11 ] , Laplacian matrix, signless Laplacian matrix [ 4 ] , and distance matrix [ 1 ] , among others. These matrices are all considered to be “sensible”. However, it remains open whether any of these spectra can determine the structure of random graphs. The main difficulty is the lack of good sufficient conditions for a graph to be determined by a given spectrum, which in turn obstructs any probabilistic estimation. In this paper, we introduce a new class of spectral invariants, the natural graph spectra . The idea and justification for this concept are discussed first in Section 1.1 , and a rigorous definition is given in Definition 3.2 . The main result, Theorem 1.1 , is an affirmative answer to the DS problem. It shows the existence of a natural graph spectrum that determines the structure for a random graph. Theorem 1.1 . Let n be a natural number. There exists a natural graph spectrum (which may depend on n ) such that for the Erdős-Rényi random graph G(n,\frac{1}{2}) , the spectrum determines G up to isomorphism asymptotically almost surely. Theorem 1.1 follows from Theorems 1.2 and 1.3 in Section 1.3 , which may be of independent interest. Theorem 1.2 gives a simple sufficient condition for a graph to be determined by a certain natural graph spectrum. The sufficient condition involves a new algebraic structure called double algebras . Theorem 1.3 shows that this double algebra sufficient condition is satisfied by random graphs. 1.1 Natural graph matrices Our approach begins by rigorously defining what constitutes a “sensible” matrix. We define a natural graph matrix to be a matrix obtained from the adjacency matrix by a “fixed sequence” of operations: (1) linear combinations, (2) ordinary matrix multiplication \bullet , and (3) Hadamard (entry-wise) product \circ . The requirement of a “fixed sequence” ensures that the same sequence is applied to every graph, so the matrix is defined uniformly. For example, using adjacency matrices for some graphs and Laplacian matrices for some other graphs is not natural. A natural graph spectrum is the spectrum, over the algebraic closure of the base field, of a natural graph matrix. The operations of linear combinations and matrix multiplication are natural to consider because if we know the spectrum of a matrix, then we know the spectrum of any polynomial in that matrix. The inclusion of Hadamard product is justified by several considerations. (i) Hadamard product is computationally easy, even easier than ordinary matrix multiplication. (ii) The Hadamard product is defined independently of any specific graph. In other words, the process (not the result) of calculating a natural spectrum does not depend on the values of the adjacency matrices. (iii) The theory of association schemes, or more generally the theory of coherent configurations, is built on the three operations. Association schemes and coherent configurations have numerous applications in design theory, coding theory, graph theory, and so on. In particular, coherent configurations are already used in the study of GI problem. (iv) The known examples of “sensible” matrices are natural. For instance, the adjacency matrix A_{G} is trivially natural. The adjacency matrix of the complement has the expression \overline{A}_{G}=A_{G}^{\circ 0}-A_{G}^{\bullet 0}-A_{G} , where -^{\circ 0} and -^{\bullet 0} mean taking the zeroth power with respect to \circ and \bullet , respectively. In particular, A_{G}^{\circ 0}=J is the all-one matrix, and A_{G}^{\bullet 0}=I is the identity matrix. The Laplacian matrix and the signless Laplacian matrix have the expressions L_{G}=(A_{G}\bullet A_{G})\circ A_{G}^{\bullet 0}-A_{G} and Q_{G}=(A_{G}\bullet A_{G})\circ A_{G}^{\bullet 0}+A_{G} , respectively. For graphs with a fixed number of vertices, the distance matrix is also natural. Since the formula for the distance matrix is more complicated, we postpone it to Example 3.1 . (v) Known examples of “non-sensible” matrices, such as those in [ 8 , 6 ] , are not natural. Proofs that these matrices are not natural are postponed to Section 5 . (vi) Natural graph spectra cannot determine the structure of all graphs. Although this might seem to be a defect of natural graph spectra, this is exactly what we expect and it must be the case. Had they been able to determine the structure of all graphs, we could use them to solve the GI problem, which implies that the spectra would be extremely complicated, unless the GI problem could be solved much more efficiently than currently known [ 3 ] . More on this is discussed in Section 5 . 1.2 Double algebras To give a solid foundation for the notion of a “fixed sequence” of operations and to analyze natural graph spectra, we introduce double algebras . Roughly speaking, a double algebra is a vector space equipped with two multiplications, \bullet and \circ . For a graph G with n vertices, we associate the double algebra \FF\langle\langle A_{G}\rangle\rangle generated by its adjacency matrix over a field \FF . This is a (double) subalgebra of the matrix (double) algebra M_{n}(\FF) . The theory of double algebras is developed in Section 2 . Using double algebras allows us to define natural graph matrices and natural graph spectra rigorously in Definition 3.2 . 1.3 Sufficient conditions We prove Theorem 1.1 by first establishing a simple sufficient condition for a certain natural graph spectrum to determine the graph. This condition resolves the key difficulty in previous studies of the DS problem. Theorem 1.2 . Let \FF be a field, and let n be a natural number. There exists a natural graph spectrum \Spec:\{\text{$n$-vertex graphs}\}\to\{\text{multisets}\} , such that for every n -vertex graph G satisfying \FF\langle\langle A_{G}\rangle\rangle=M_{n}(\FF) , the spectrum \Spec G determines G up to graph isomorphism. Theorem 1.2 is proved in Section 3 . This theorem only establishes the existence of a natural graph spectrum. Although one could trace through the proof to construct an explicit natural graph spectrum, the resulting spectrum is quite complicated. The reason is that the proof uses the existence of a so-called universal involution-closed \circ -idempotent basis. It is possible to get around this general result and give a simpler explicit spectrum directly, but we do not pursue it in this paper. Theorem 1.3 shows that the sufficient condition \FF\langle\langle A_{G}\rangle\rangle=M_{n}(\FF) in Theorem 1.2 is asymptotically almost surely satisfied for random graphs. Theorem 1.3 . Let \FF be a field, and let n be a natural number. For random graphs G with n vertices, \FF\langle\langle A_{G}\rangle\rangle=M_{n}(\FF) asymptotically almost surely. Theorem 1.3 is proved in Section 4 . The main result, Theorem 1.1 , follows immediately from Theorems 1.2 and 1.3 . We believe in general that the more “complicated” a natural graph spectrum is, the more graphs it can determine. In this sense, it is a very interesting question to find a natural graph spectrum which is closer to the classical spectra, such as adjacency spectrum and Laplacian spectrum, while still determining the structure of random graphs. 1.4 Structure of the paper The rest of the paper is organized as follows. Section 2 develops the theory of double algebras. Its focus is the existence of a universal involution-closed \circ -idempotent basis. Section 3 applies this theory to natural graph spectra, and proves Theorem 1.2 . Section 4 analyzes the double algebra of random graphs, and prove Theorem 1.3 . Section 5 discusses the dimensions of double algebras of graphs. 2 Double algebras In this section, we develop the general theory of double algebras. The primary example is square matrices equipped with matrix multiplication, the Hadamard product, and the transpose. The main technical goal is Section 2.6 , which establishes the existence of a universal involution-closed \circ -idempotent basis. It is a key tool for our spectral constructions in Section 3 . 2.1 Basics Let \FF be a field. A double algebra R over \FF is a vector space V over \FF equipped with two maps \bullet_{R}\from V\otimes V\to V and \circ_{R}\from V\otimes V\to V . If we focus on only \bullet_{R} , or only on \circ_{R} , we obtain two ordinary algebras, denoted by R^{\bullet} and R^{\circ} , respectively. The subscripts R will be omitted if it is clear from the context. We call the double algebra an associative (resp. commutative, semisimple) double algebra if both R^{\bullet} and R^{\circ} are associative (resp. commutative, semisimple). We always assume the existence of an identity element in an associative algebra. For associative double algebras, there exist identity elements 1^{\bullet} and 1^{\circ} for \bullet and \circ , respectively. All the double algebras are assumed to be associative in this paper. If we combine the two multiplications \bullet and \circ , then we obtain a map (\bullet,\circ)\from V\otimes V\to V\oplus V . Note that the notion of double algebra we use differs from some algebraic structure with the same name in some literature, where the structure map is a map V\otimes V\to V\otimes V instead. Sometimes, double algebras are equipped with involutions. An involution of a double algebra R is a linear map \sigma:V\to V such that \sigma(\sigma(a))=a , \sigma(a\bullet b)=\sigma(b)\bullet\sigma(a) and \sigma(a\circ b)=\sigma(b)\circ\sigma(a) for all a,b\in R . The primary example, which is also the one used throughout the paper, is the following. Example 2.1 . Let M_{n}(\FF) be the set of n\times n matrices over \FF . It is equipped with matrix multiplication \bullet and entry-wise multiplication \circ . The \bullet -identity 1^{\bullet} is the identity matrix, and the \circ -identity is the all-one matrix. The matrix transpose a\mapsto a^{\top} is an involution. The two multiplications \bullet and \circ play an fundamental role in the theory of association schemes [ 5 ] . The Bose-Mesner algebra of an association scheme, with \bullet and \circ equipped, is actually a double subalgebra of M_{n}(\FF) . Another example comes from group representation theory. Example 2.2 . Let G be a finite group, and \FF G be the group algebra over \FF . We equip it with a new multiplication g\circ h:=\begin{cases}g,&g=h,\\ 0,&g\neq h.\end{cases} The \bullet -identity 1^{\bullet} is 1 , and the \circ -identity 1^{\circ} is \sum_{g\in G}g . The inverse map on group elements g\mapsto g^{-1} induces an involution. This \circ multiplication, while natural, is typically used implicitly in group representation theory and seldom appears as an explicit operation. With this double algebra viewpoint, it is possible to treat a portion of group representation theory, in particular, character table, as a special case of the representation theory of double algebras. We will discuss more on this in a separate paper. 2.2 Free algebras To formalize “fixed sequences” of operations, we require an analogue of polynomial rings. This is provided by free double algebras. The free (associative) algebra in x over \FF with multiplication \bullet (resp. \circ ) is denoted by \FF\langle x\rangle^{\bullet} (resp. \FF\langle x\rangle^{\circ} ). The elements are simply (not necessarily commutative) polynomials over \FF with multiplication \bullet (resp. \circ ). As with ordinary algebras, a free double algebra in x over \FF exists, and it is denoted by \FF\langle\langle x\rangle\rangle . The elements are like polynomials over \FF with the caveat that we use two multiplications instead of one. We call the elements in \FF\langle\langle x\rangle\rangle double polynomials in x over \FF . For example, (x\bullet x)\circ x+x is a double polynomial in x . The free double algebra admits a standard involution. Let \sigma_{x}:\FF\langle\langle x\rangle\rangle\to\FF\langle\langle x\rangle\rangle be given by \sigma_{x}(x)=x , \sigma_{x}(p_{1}\circ p_{2}):=\sigma_{x}(p_{2})\circ\sigma_{x}(p_{1}) , and \sigma_{x}(p_{1}\bullet p_{2}):=\sigma_{x}(p_{2})\bullet\sigma_{x}(p_{1}) for p_{1},p_{2}\in\FF\langle\langle x\rangle\rangle . Let R be a double algebra, and a\in R an element. The element a generates a double subalgebra of R , that is, the smallest double subalgebra of R containing a , denoted by \FF\langle\langle a\rangle\rangle . Extending the notion of evaluation p\mapsto p(a) for ordinary polynomial p at a , we have a natural evaluation map for double polynomials \displaystyle{\rm eval}_{a}\from\FF\langle\langle x\rangle\rangle \displaystyle\to\FF\langle\langle a\rangle\rangle\subseteq R \displaystyle x \displaystyle\mapsto a. We often use the abbreviation p(a):={\rm eval}_{a}(p) for a double polynomial p\in\FF\langle\langle x\rangle\rangle . For example, for p=(x\bullet x)\circ x+x\in\FF\langle\langle a\rangle\rangle , p(a)=(a\bullet a)\circ a+a\in R . 2.3 Idempotents Starting from this subsection, we will mainly discuss notions and results for \circ for simplicity. The \bullet -version can be obtained by interchanging \circ and \bullet . In a double algebra, the idempotents with respect to \circ , namely the elements x\in R such that x\circ x=x , are called \circ -idempotents . It is clear that 0 and 1^{\circ} are \circ -idempotents. Similar to the algebra case, we call the nonzero \circ -idempotents primitive if they cannot be written as the sum of two nonzero orthogonal \circ -idempotents. We call a basis \{b_{i}:\ i\in I\} of R a \circ -idempotent basis if the basis elements b_{i} are all primitive \circ -idempotents. We have the following basic facts about the existence of a \circ -idempotent basis. It follows directly from the Wedderburn-Artin theorem, and its proof is omitted. Lemma 2.3 . Let R be a finite dimensional double algebra. Assume that R^{\circ} is commutative and split semisimple, then R admits a \circ -idempotent basis. Note that, for noncommutative R^{\circ} , we cannot expect the existence of a \circ -idempotent basis. It is possible to get some analogous result involving idempotents and nilpotent elements using Wedderburn principal theorem though. Since \circ -idempotent basis and its universal version in Section 2.5 is good enough for our purpose, we only consider the commutative R^{\circ} . 2.4 Spectrum and projection For a matrix a\in M_{n}(\FF) , its spectrum over \FF , as a set, is the collection of all \lambda\in\FF such that \lambda I-a is not an invertible matrix. This concept of spectrum has been generalized to any associative algebra, and we use it for double algebras. For a\in R , the \circ -spectrum of a over \FF is \Spec^{\circ}_{\FF}a:=\{\lambda\in\FF:\ \text{$a-\lambda$ is not invertible in $R^{\circ}$}\}. When R is finite dimensional over \FF , the \circ -spectrum \Spec^{\circ}_{\FF}a is a finite set for every a\in R . Let \Lambda\subseteq\FF be a finite subset, and for \lambda\in\Lambda , consider the projection polynomial {\rm proj}^{\circ}_{\Lambda,\lambda}:=\sideset{}{{}^{\circ}}{\prod}_{\mu\in\Lambda\setminus\{\lambda\}}\frac{x-\mu 1^{\circ}}{\lambda-\mu}\in\FF\langle x\rangle^{\circ}, (2.1) where \sideset{}{{}^{\circ}}{\prod} denotes products with respect to \circ . The reason why it is called a projection polynomial is that it is related to the projection to the “ \lambda -eigenspace” if we treat \lambda\in\Spec^{\circ}_{\FF}a as an “eigenvalue”. This will be illustrated in Example 2.4 first, and then be proved in Lemma 2.5 . Example 2.4 . Let M_{n\times m}(\FF) be the collection of all n\times m matrices over \FF equipped with Hadamard product \circ . Let a\in M_{n\times m}(\FF) be a matrix whose entries are in a finite subset \Lambda\subseteq\FF . Then, \Spec^{\circ}_{\FF}a consists of all entries of a . Moreover, for every \lambda\in\Lambda , by a direct calculation, \left({\rm proj}^{\circ}_{\Lambda,\lambda}(a)\right)_{ij}=\begin{cases}1,&a_{ij}=\lambda,\\ 0,&a_{ij}\neq\lambda.\end{cases} In other words, {\rm proj}^{\circ}_{\Lambda,\lambda}(a) extracts the locations where the entries of a are \lambda . Example 2.4 can be generalized in a setting of commutative split semisimple R^{\circ} , as to be shown in Lemma 2.5 . Lemma 2.5 . Let R^{\circ} be a finite dimensional commutative split semisimple algebra over \FF . Let \Lambda\subseteq\FF be a finite subset. Then, for every a\in R^{\circ} such that \Spec^{\circ}_{\FF}a\subseteq\Lambda , a=\sum_{\lambda\in\Lambda}\lambda\ {\rm proj}^{\circ}_{\Lambda,\lambda}(a), and the summand {\rm proj}^{\circ}_{\Lambda,\lambda}(a) is a \circ -idempotent. Proof. Since R^{\circ} is finite dimensional commutative split semisimple over \FF , R^{\circ}\cong\FF^{\dim_{\FF}R^{\circ}} . Thus, it suffices to prove the result for \FF^{n} . The projection {\rm proj}^{\circ}_{\Lambda,\lambda} works by projecting a vector a\in\FF^{n} to the locations where the entries are \lambda , just like in Example 2.4 . The result follows directly from this interpretation (with m=1 in Example 2.4 ). ∎ 2.5 Universal idempotent basis A subalgebra of a commutative split semisimple algbera is again commutative split semisimple. Hence by Lemma 2.3 , we know that every subalgebra of R^{\circ} admits a \circ -idempotent basis. It turns out that it is possible to give a “universal” basis for any finite family of subalgebras. Definition 2.6 . Let R_{a} be a family of \circ -subalgebras of R^{\circ} indexed by a\in A , where A\subseteq R is a subset. A universal \circ -idempotent basis with respect to this family is a subset B\subseteq\FF\langle\langle x\rangle\rangle such that the following statements hold for every a\in A . (i) The nonzero elements of b(a) ’s for b\in B are distinct. (ii) The nonzero elements of \{b(a):\ b\in B\} form a \circ -idempotent basis of R_{a} . If (ii) holds, but (i) does not necessarily hold, then we call B a weak universal \circ -idempotent basis . The goal of this subsection is to establish the existence of a universal \circ -idempotent basis for families of double subalgebras. We first prove the existence for families of \circ -subalgebras of R^{\circ} in Lemma 2.7 . Lemma 2.7 . Assume that R^{\circ} is commutative, split semisimple, and finite dimensional over \FF . Let A\subseteq R be a finite subset, and B\subseteq\FF\langle\langle x\rangle\rangle a finite subset. Consider the family R_{a}:=\FF\langle b(a):\ b\in B\rangle^{\circ} for a\in A . Then, the family has a finite universal \circ -idempotent basis. Proof. Let \ast denote the (associative) composition of double polynomials in \FF\langle\langle x\rangle\rangle . Put in other words, (f\ast g)(x):=f(g(x)) for f,g\in\FF\langle\langle x\rangle\rangle . For a\in A , (f\ast g)(a)=f(g(a)). (2.2) Let \Lambda:=\bigcup_{a\in A}\bigcup_{b\in B}\Spec^{\circ}_{\FF}b(a) , which is a finite set. Consider the following finite set of compositions of double polynomials: C:=\{{\rm proj}^{\circ}_{\Lambda,\lambda}\ast b:\ \lambda\in\Lambda,b\in B\}, (2.3) where {\rm proj}^{\circ}_{\Lambda,\lambda}\in\FF\langle x\rangle^{\circ}\subseteq\FF\langle\langle x\rangle\rangle is the projection polynomial defined in Eq. 2.1 . For a subset X\subseteq C , let d_{X}:=\sideset{}{{}^{\circ}}{\prod}_{c\in C}\begin{cases}1^{\circ}-c,&c\in X,\\ c,&c\notin X.\end{cases} (2.4) Let D:=\{d_{X}:\ X\subseteq C\} . We claim that D is a desired universal \circ -idempotent basis. Fix an a\in A . We first prove that for every d\in D , d(a) is a \circ -idempotent. By Lemma 2.5 , for every b\in B , {\rm proj}^{\circ}_{\Lambda,\lambda}(b(a)) is a \circ -idempotent. So, from the construction of C in Eq. 2.3 , for every c\in C , c(a) is a \circ -idempotent. Since (1^{\circ}-c)(a) and c(a) are both \circ -idempotents for all c\in C , for every X\subseteq C , the product d_{X}(a) is a \circ -idempotent by Eq. 2.4 . Next, we prove that nonzero elements of d(a) ’s for d\in D are distinct and form a basis of R_{a} . Note that c=\sum_{c\notin X\subseteq C}d_{X} (2.5) We proceed with the following calculation. \displaystyle R_{a}= \displaystyle\FF\langle b(a):\ b\in B\rangle^{\circ} \displaystyle= \displaystyle\FF\langle{\rm proj}^{\circ}_{\Lambda,\lambda}(b(a)):\ \lambda\in\Lambda,b\in B\rangle^{\circ} (by Lemmas 2.5 and 2.1 ) \displaystyle= \displaystyle\FF\langle c(a):\ c\in C\rangle^{\circ} (by Eqs. 2.2 and 2.3 ) \displaystyle= \displaystyle\FF\langle d_{X}(a):\ X\subseteq C\rangle^{\circ} (by Eqs. 2.4 and 2.5 ) \displaystyle= \displaystyle\FF\langle d(a):\ d\in D\rangle^{\circ}. \displaystyle(\text{by the definition of $D$}) For every c\in C , since c(a) is \circ -idempotent, we know that (1^{\circ}-c)(a) and c(a) are orthogonal. Therefore, for subsets X,Y\subseteq C , by Eq. 2.4 and the commutativity of \circ , d_{X}(a)\circ d_{Y}(a)=\begin{cases}d_{X}(a),&X=Y,\\ 0,&X\neq Y.\end{cases} (2.6) So, nonzero elements of d(a) ’s for d\in D are distinct. Moreover, since \Span_{\FF}\{d(a):\ d\in D\} is closed under \circ , nonzero elements of \{d(a):\ d\in D\} is a basis of \FF\langle d(a):\ d\in D\rangle^{\circ}=R_{a} . At the end, since nonzero elements of \{d(a):\ d\in D\} are orthogonal \circ -idempotents and form a basis of R_{a} , they are all primitive \circ -idempotents. ∎ Now, we are ready to prove the existence of a universal \circ -idempotent basis for double subalgebras. Proposition 2.8 . Assume that R^{\circ} is commutative, split semisimple and finite dimensional over \FF . Let A\subseteq R be a finite subset, and consider the family R_{a}:=\FF\langle\langle a\rangle\rangle for a\in A . Then, the family has a finite universal \circ -idempotent basis. Proof. We build the universal basis inductively, using Lemma 2.7 to refine a universal basis for each step in a family of filtrations R_{a}^{(i)} of \circ -subalgebras of R_{a} . For each a\in A , let R_{a}^{(0)}:=\FF\langle 1^{\bullet},a\rangle^{\circ}\subseteq R^{\circ}, and for each positive i , let R_{a}^{(i)}:=\FF\langle R_{a}^{(i-1)}\bullet R_{a}^{(i-1)}\rangle^{\circ}. They form a filtration R_{a}^{(0)}\subseteq R_{a}^{(1)}\subseteq R_{a}^{(2)}\subseteq\dots with \bigcup_{i\in\NN}R_{a}^{(i)}=R_{a} . Since \dim_{\FF}R_{a}^{(i)}\leq\dim_{\FF}R_{a}\leq\dim_{\FF}R\lt\infty , we have R_{a}^{(\dim_{\FF}R)}=R_{a} for every a\in A . Let B^{(0)}:=\{1^{\bullet},x\} . Then, by the definition of R_{a}^{(0)} , R_{a}^{(0)}=\FF\langle b(a):\ b\in B^{(0)}\rangle^{\circ}. Applying Lemma 2.7 to R_{a}^{(0)} and B^{(0)} , we have a finite \circ -idempotent basis C^{(0)} of R_{a}^{(0)} . Let B^{(1)}:=\{c\bullet c^{\prime}:\ c,c^{\prime}\in C^{(0)}\} . Then, by the definition of R_{a}^{(1)} , R_{a}^{(1)}=\FF\langle R_{a}^{(0)}\bullet R_{a}^{(0)}\rangle^{\circ}=\FF\langle c(a)\bullet c^{\prime}(a):\ c,c^{\prime}\in C^{(0)}\rangle^{\circ}=\FF\langle b(a):\ b\in B^{(1)}\rangle^{\circ}. Again by applying Lemma 2.7 to R_{a}^{(1)} and B^{(1)} , we have a finite \circ -idempotent basis C^{(1)} of R_{a}^{(1)} . We repeat this process by induction, and we obtain a finite \circ -idempotent basis C^{(i)} of R_{a}^{(i)} for each natural number i . Therefore, C^{(\dim_{\FF}R)} is a finite \circ -idempotent basis of R_{a}^{(\dim_{\FF}R)}=R_{a} . Since the construction of C^{(\dim_{\FF}R)} is independent of the choice of a , it is a desired universal \circ -idempotent basis. ∎ We finish this subsection by showing that a weak universal basis can be converted to a universal basis. This will be used in Section 2.6 . Lemma 2.9 . Assume that R^{\circ} is commutative, split semisimple and finite dimensional over \FF . Let A\subseteq R be a finite subset, and R_{a} a family of subalgebras of R^{\circ} for a\in A . If the family has an ordered weak universal \circ -idempotent basis, then it has an ordered universal \circ -idempotent basis. Proof. Let B\subseteq\FF\langle\langle x\rangle\rangle be a weak universal \circ -idempotent basis. We order the elements in B as b_{1},\dots,b_{n} . For each 1\leq i\leq n , we define c_{i} inductively: c_{i}:=b_{i}-\sum_{j\lt i}b_{i}\circ c_{j}. Then, an induction shows that for every a\in A , c_{i}(a)=\begin{cases}b_{i}(a),&\text{$b_{i}(a)\neq b_{j}(a)$ for $j\lt i$},\\ 0,&\text{otherwise}.\end{cases} Thus, C:=\{c_{1},\dots,c_{n}\} is a universal \circ -idempotent basis. ∎ 2.6 Involution We study double algebras with involutions in this subsection. Our goal is to show the existence of a universal \circ -idempotent basis that is compatible with the involution. If R admits a \circ -idempotent basis, then by the defining property, the involution preserves the property of being primitive \circ -idempotent. Thus, the involution on R induces an involution on the \circ -idempotent basis. Theorem 2.10 below gives a universal version of this statement, whose proof requires some extra work. Theorem 2.10 . Let R be a double algebra equipped with an involution \sigma . Assume that R^{\circ} is commutative, split semisimple and finite dimensional over \FF . Let A\subseteq R^{\sigma} be a finite subset, where R^{\sigma} is the \sigma -fixed points of R . Consider the family of double subalgebras R_{a}:=\FF\langle\langle a\rangle\rangle\subseteq R for a\in A . Then, there exists a finite universal \circ -idempotent basis B closed under involution in the sense that for some involution \sigma_{B}\from B\to B on the set B , \sigma(b(a))=\sigma_{B}(b)(a) for all a\in A . Proof. The strategy is to start with a universal basis from Proposition 2.8 , extend it to a weak basis closed under some involution, and then apply the process of Lemma 2.9 . Let B\subseteq\FF\langle\langle x\rangle\rangle be a finite universal \circ -idempotent basis for the family R_{a} for a\in A guaranteed by Proposition 2.8 . We order the elements of B as b_{1},\dots,b_{n} . The universal \circ -idempotent basis b_{1},\dots,b_{n} extends to an ordered weak universal \circ -idempotent basis B^{\prime} b_{1}\circ\sigma_{x}(b_{1}),\dots,b_{n}\circ\sigma_{x}(b_{n}),b_{1},\sigma(b_{1}),b_{2},\sigma_{x}(b_{2}),\dots,b_{n},\sigma_{x}(b_{n}), where \sigma_{x} is the standard involution in \FF\langle\langle x\rangle\rangle . We define a set involution \sigma^{\prime}:B^{\prime}\to B^{\prime} on this weak universal \circ -idempotent basis by restricting \sigma_{x} to B^{\prime} : \displaystyle\sigma^{\prime}(b_{i}\circ\sigma_{x}(b_{i})) \displaystyle:=\sigma_{x}(b_{i}\circ\sigma_{x}(b_{i}))=b_{i}\circ\sigma_{x}(b_{i}), \displaystyle\sigma^{\prime}(b_{i}) \displaystyle:=\sigma_{x}(b_{i}), \displaystyle\sigma^{\prime}(\sigma_{x}(b_{i})) \displaystyle:=\sigma_{x}(\sigma_{x}(b_{i}))=b_{i}. Therefore, \sigma(b^{\prime}(a))=\sigma^{\prime}(b^{\prime})(\sigma(a))=\sigma^{\prime}(b^{\prime})(a) for b^{\prime}\in B^{\prime} and a\in A . Applying Lemma 2.9 to B^{\prime} , we convert this weak basis to an ordered universal basis c_{1},\dots,c_{3n} . Then, by the constructions of c_{1},\dots,c_{3n} , the following statements hold for every a\in A : (i) \sigma(c_{i}(a))=c_{i}(a) for 1\leq i\leq n , (ii) \sigma(c_{n+2i-1}(a))=c_{n+2i}(a) for 1\leq i\leq n , (iii) \sigma(c_{n+2i}(a))=c_{n+2i-1}(a) for 1\leq i\leq n . Similar to the arguments for B^{\prime} , the standard involution \sigma_{x} restricts to an involution on c_{1},\dots,c_{3n} , and it is compatible with \sigma . Thus, c_{1},\dots,c_{3n} is a universal \circ -idempotent basis closed under involution. ∎ 3 Natural graph spectrum The goal of this section is to define natural graph spectra, and prove Theorem 1.2 . To do this, we need to give a construction of a specific natural graph spectrum, and demonstrate how it is related to the structure of the graph. We fix the field \FF and the number of vertices n . A graph matrix is an assignment of a matrix over \FF for each n -vertex graph G . Typical examples include adjacency matrix, adjacency matrix of the complement, Laplacian matrix, signless Laplacian matrix, distance matrix, and so on. Example 3.1 . The typical matrices are all related to adjacency matrix via certain double polynomials. (i) The adjacency matrix is A_{G}=x(A_{G}) . (ii) The adjacency matrix of the complement is \overline{A}_{G}=(1^{\circ}-1^{\bullet}-x)(A_{G}) . (iii) The Laplacian matrix is L_{G}=((x\bullet x)\circ 1^{\bullet}-x)(A_{G}) . (iv) The signless Laplacian matrix is Q_{G}=((x\bullet x)\circ 1^{\bullet}+x)(A_{G}) . (v) The distance matrix is {\rm Dist}_{G}=p(A_{G}) , where p:=\frac{1}{N!}\sum_{d=0}^{n-1}\left(\sideset{}{{}^{\circ}}{\prod}_{i=1}^{N}(i1^{\circ}-(x+1^{\bullet})^{\bullet d})\right) and N is sufficiently large compared with n . Note that there might be many different double polynomials associated to the same graph matrix. For example, we also have A_{G}=(x\circ x)(A_{G}) , since A_{G} is a \{0,1\} -matrix. Moreover, the double polynomial for {\rm Dist}_{G} above is probably not the simplest one. The “fixed sequence” of operations mentioned in Section 1 could be defined rigorously by using double polynomials. This leads to the precise definition of natural matrices, given in terms of double algebras defined in Section 2 . Definition 3.2 . A graph matrix \displaystyle M_{-}\from\{\text{graphs with $n$ vertices}\} \displaystyle\to\{\text{$n\times n$ matrices}\}, \displaystyle G \displaystyle\mapsto M_{G}, is called natural if there exists some double polynomial p\in\FF\langle\langle x\rangle\rangle such that M_{G}=p(A_{G}) for all graphs G with n vertices. A natural graph spectrum is the spectrum of graphs with respect to a natural graph matrix over the algebraic closure \overline{\FF} of \FF . By Example 3.1 , the adjacency spectrum, Laplacian spectrum, A_{\alpha} spectrum and distance spectrum are all natural graph spectra. 3.1 The strong spectrum In the study of DS problems, a common used trick is to combine the knowledge of multiple spectra. For example, the generalized spectrum is just a combination of the adjacency spectrum and the adjacency spectrum of the complementary graph. We also employ this idea for natural graph spectra. There are infinitely many natural graph spectra, indexed by the associated double polynomial. The collection of all of them is called the strong natural spectrum . Definition 3.3 . Let G be a graph with n vertices. The strong natural spectrum of G , denoted by \SSpec G , is the map \displaystyle\SSpec G:\FF\langle\langle x\rangle\rangle\to \displaystyle{\rm MultiSet}, \displaystyle p\mapsto \displaystyle\Spec_{\overline{\FF}}p(A_{G}), where {\rm MultiSet} is the collection of all multisubsets over the algebraic closure \overline{\FF} of \FF , and \Spec_{\overline{\FF}} is the operation to take the spectrum of a square matrix over \overline{\FF} . The strong natural spectrum clearly contains no less information than any specific natural graph spectrum. We will first analyze what information that strong natural spectrum has, and then try to consider a set of natural spectra (i.e. the strong natural spectrum restricted to a small set of double polynomials). 3.2 Graph of double subalgebras Let V be a finite set, and let M_{V}(\FF) be the double algebra of V\times V matrices over \FF equipped with the involution given by matrix transpose. The algebra M_{V}(\FF)^{\circ} is finite dimensional commutative split semisimple, satisfying the requirements of Theorem 2.10 . Let A\subseteq M_{V}(\FF) be the collection of the symmetric \{0,1\} -matrices with zeros on the diagonal, which is a finite set. We consider the finite family \FF\langle\langle a\rangle\rangle for a\in A . By Theorem 2.10 , there exists a universal involution-closed \circ -idempotent basis B for \FF\langle\langle a\rangle\rangle . With the help of B , we can reconstruct graphs from double algebras. The idea is to interpret diagonal idempotents as vertices and certain products as potential edges. For each a\in A , we construct a directed graph G_{a} with the vertex set V_{a}:=\{b\in B:\ \text{$b(a)$ is a nonzero diagonal matrix}\}, and the arc set \{(s,t)\in V_{a}\times V_{a}:\ (s\bullet x\bullet t)(a)\neq 0\}. Now, we can obtain a double algebra of a graph by considering the double subalgebra generated by its adjacency matrix. Conversely, we can obtain a (directed) graph from a double subalgebra. Proposition 3.4 shows that under some assumptions, these two procedures are inverses to each other. Proposition 3.4 . Let G be a graph with vertex set V , and a\in M_{V}(\FF) its adjacency matrix. If |V_{a}|=|V| , then G_{a}\cong G . Proof. For every b\in V_{a} , b(a) is a nonzero diagonal \{0,1\} -matrix, since b(a) is a \circ -idempotent. Since 1^{\bullet}(a) is the identity matrix, which is a \circ -idempotent, it must be a sum of diagonal primitive \circ -idempotent, hence 1^{\bullet}=\sum_{b\in V_{a}}b(a) . Since |V_{a}|=|V| , each b(a) contains a unique 1 . Therefore, there exists a unique bijection \displaystyle f\from V_{a} \displaystyle\to V, \displaystyle b \displaystyle\mapsto\text{the unique $v\in V$ such that $(b(a))_{v,v}=1$}. Let A be the adjacency matrix of G_{a} . A direct calculation shows that for s,t\in V_{a} , A_{v,w}=((s\bullet x\bullet t)(a))_{v,w}=\delta_{f(s),v}\delta_{f(t),w}a_{s,t}. Therefore, the adjacency matrix of G_{a} and that of G are the same up to the permutation of indices by f , hence G\cong G_{a} . ∎ A priori, the condition |V_{a}|=|V| may not be easy to verify. We give in Corollary 3.5 an alternative condition that looks simpler. Actually, it is possible to prove that the condition \FF\langle\langle a\rangle\rangle=M_{n}(\FF) in Corollary 3.5 is equivalent to |V_{a}|=|V| , but we will only prove that the former implies the latter in Corollary 3.5 . Corollary 3.5 . Let C:=\{b\bullet x\bullet b^{\prime}\in\FF\langle\langle x\rangle\rangle:\ b,b^{\prime}\in B\} . Let G be a graph with n vertices and a its adjacency matrix. If \FF\langle\langle a\rangle\rangle=M_{n}(\FF) , then the knowledge of whether c(a) is zero or not for each c\in C determines G up to graph isomorphism. Proof. Since \FF\langle\langle a\rangle\rangle=M_{n}(\FF) and B a universal \circ -idempotent basis, \{b(a):b\in B\} contains all \{0,1\} -matrices with exactly one 1 . Therefore, |V_{a}|=|V| . The result follows from the construction of G_{a} and Proposition 3.4 . ∎ Now, we can extract some double polynomials from the construction of the graph G_{a} . These double polynomials give finitely many natural spectra which can determine the structure of the graph under the assumption that \FF\langle\langle a\rangle\rangle=M_{n}(\FF) . Proposition 3.6 . There exists some finite subset D\subseteq\FF\langle\langle x\rangle\rangle such that the following statement holds. For every graph G with \FF\langle\langle A_{G}\rangle\rangle\cong M_{n}(\FF) , where A_{G} is the adjacency matrix of G (up to some vertex ordering), d(A_{G}) is a \circ -idempotent for every d\in D and (\SSpec G)|_{D} determines G up to graph isomorphism. Proof. Let G be a graph with \FF\langle\langle A_{G}\rangle\rangle\cong M_{n}(\FF) . For every b,b^{\prime}\in B , the matrix (b\bullet x\bullet b^{\prime})(A_{G}) is a \{0,1\} -matrix with zero diagonal and with at most one entry being 1 . Therefore, the spectrum of (b\bullet x\bullet b^{\prime})(A_{G}) determines whether (b\bullet x\bullet b^{\prime})(A_{G}) is zero or not. More precisely, (b\bullet x\bullet b^{\prime})(A_{G}) is nonzero if and only if it has a nonzero eigenvalue. Let D:=\{c+\sigma_{x}(c)\in\FF\langle\langle x\rangle\rangle:\ c\in C\} , where C is the finite set defined in Corollary 3.5 , and \sigma_{x} is the standard involution. For every c\in C , the matrix (c+\sigma_{x}(c))(A_{G}) is a symmetric \{0,1\} matrix with zero diagonal and with either zero or two entries being 1 . The spectrum of the former one consists of n many of 0 ’s, and that of the latter one consists of one -1 , one 1 , and n-2 many of 0 ’s. Therefore, the spectrum of (c+\sigma_{x}(c))(A_{G}) determines whether (c+\sigma_{x}(c))(A_{G}) is zero or not. Now, the result then follows from Corollary 3.5 . ∎ 3.3 Merging spectra Proposition 3.6 shows that only a finite number of natural spectra is needed to determine the structure of a graph under certain assumptions. To obtain a single natural spectrum, we now show how to encode multiple natural graph spectra into one. For a matrix A\in M_{n}(\FF) , let \trSpec A be the tuple of traces of powers of A : \trSpec A:=(\tr A,\tr A^{2},\dots,\tr A^{n}). Then, \trSpec A and \Spec_{\overline{\FF}}A determine each other. Proposition 3.7 . Let m,b be natural numbers. There exist positive integers a_{1},\dots,a_{m} (which depend on m and b ) such that the following statement holds. Let A_{1},\dots,A_{m} be a finite family of n\times n matrices over \ZZ with \|A_{i}\|_{\infty}\leq b , where \|A_{i}\|_{\infty} is the largest absolute value of the entries of A_{i} . Then, \Spec_{\overline{\FF}}\left(a_{1}A_{1}+\dots+a_{m}A_{m}\right) determines \Spec_{\overline{\FF}}A_{i} for all 1\leq i\leq m . Proof. It suffices to prove the m=2 , since the result for general m follows from an induction using m=2 case. Now, assume that m=2 . Let z be a sufficiently large positive integer. For every 1\leq k\leq n , \tr A_{1}^{k} is the remainder of \tr(A_{1}+zA_{2})^{k} modulo z , and \tr A_{2}^{k} is the closest integer to \frac{1}{z^{k}}\tr(A_{1}+zA_{2})^{k} . Thus, the \trSpec(A_{1}+zA_{2}) determines \trSpec A_{1} and \trSpec A_{2} . Due to the equivalence between \trSpec and \Spec , the spectrum of A_{1}+zA_{2} determines those of A_{1} and A_{2} . ∎ With the technical result Proposition 3.7 , we can combine natural spectra indexed by a set into a single natural spectrum. Proposition 3.8 . Let D\subseteq\FF\langle\langle x\rangle\rangle be a finite subset. There exists a p\in\FF\langle\langle x\rangle\rangle such that the following statement holds. For every graph G such that d(a) is a \circ -idempotent for all d\in D , (\SSpec G)(p) determines (\SSpec G)|_{D} . Proof. Note that the \circ -idempotents in M_{n}(\FF) are just \{0,1\} -matrices. The result follows from Proposition 3.7 for m:=|D| and b=1 . ∎ Now, we can prove the first main result. Proof of Theorem 1.2 . By Proposition 3.6 , there exists some finite subset D\subseteq\FF\langle\langle x\rangle\rangle such that for every G with \FF\langle\langle A_{G}\rangle\rangle\cong M_{n}(\FF) , (i) d(A_{G}) is a \circ -idempotent for every d\in D , (ii) (\SSpec G)|_{D} determines G up to graph isomorphism. The (i) makes sure that Proposition 3.8 is applicable to D . Thus there exists a p\in\FF\langle\langle x\rangle\rangle such that (\SSpec G)(p) determines (\SSpec G)|_{D} . Consider the natural spectrum \Spec G:=(\SSpec G)(p)=\Spec_{\overline{\FF}}p(A_{G}) . Combined with (ii) , we know that \Spec G determines G up to isomorphism for all G with \FF\langle\langle A_{G}\rangle\rangle\cong M_{n}(\FF) . ∎ 4 Double algebra of random graphs Having established in Theorem 1.2 that the condition \FF\langle\langle A_{G}\rangle\rangle=M_{n}(\FF) is sufficient in Section 3 , we now prove Theorem 1.3 , which says the sufficient condition is satisfied by random graphs. Theorems 1.2 and 1.3 together complete the proof of our main theorem Theorem 1.1 . Let n be a fixed natural number, and let G be an Erdős-Rényi random graph G(n,\frac{1}{2}) . Let r:=\lfloor 3\log_{2}n\rfloor . Let v_{1},\dots,v_{n} be a vertex ordering such that d_{1}\geq\dots\geq d_{n} , where d_{i} is the degree of vertex v_{i} . Consider the adjacency matrix A of G with respect to this vertex order. Let w_{j}:=(A_{i,j}:\ 1\leq i\leq r)\in\{0,1\}^{r} . Theorem 4.1 ( [ 2 , Theorem 1.2] ) . We have d_{1}>\dots>d_{r}>d_{r+1} , and w_{j}\neq w_{k} for distinct j,k\in[r+1,n] asymptotically almost surely. The operations of extracting high degree vertices and identifying w_{j} can be implemented in \FF\langle\langle A\rangle\rangle . This idea leads to a proof of Theorem 1.3 . Proof of Theorem 1.3 . By Theorem 4.1 , it suffices to prove that d_{1}>\dots>d_{r}>d_{r+1} and w_{j}\neq w_{k} for distinct j,k\in[r+1,n] implies that \FF\langle\langle A_{G}\rangle\rangle=M_{n}(\FF) . For each 1\leq i\leq r , define b_{i}\in\FF\langle\langle A\rangle\rangle by b_{i}:={\rm proj}^{\circ}_{\{0,1,\dots,n-1\},d_{i}}\left((A\bullet A)\circ I\right). Then, b_{i} is a diagonal \{0,1\} -matrix. Moreover, (b_{i})_{k,k}=1 if and only if d_{k}=d_{i} . Since d_{1}>\dots>d_{r}>d_{r+1} , b_{i} has a unique entry being 1 , the (i,i) -th entry. Let J be the n\times n all-one matrix. For each r+1\leq j\leq n , define b_{j}\in\FF\langle\langle A\rangle\rangle by b_{j}:=\left(\sum_{i=1}^{r}\left(A_{i,j}A+(1-A_{i,j})(J-I-A)\right)\bullet b_{i}\bullet J\right)\circ\left(I-\sum_{i=1}^{r}b_{i}\right). Then, b_{j} is a diagonal \{0,1\} -matrix. Moreover, (b_{j})_{k,k}=1 if and only if r+1\leq k\leq n and w_{k}=w_{j} . Since w_{j}\neq w_{k} for distinct j,k\in[r+1,n] , b_{j} has a unique entry being 1 , specifically at the (j,j) -position. Therefore, b_{1},\dots,b_{n} runs over all diagonal \{0,1\} -matrices with exactly one entry being 1 . The products b_{s}\bullet J\bullet b_{t}\in\FF\langle\langle A\rangle\rangle is the \{0,1\} -matrices with (s,t) -entry being 1 and all other entries 0 . Thus, M_{n}(\FF)\subseteq\Span_{\FF}\{b_{s}\bullet J\bullet b_{t}:\ 1\leq s,t\leq n\}\subseteq\FF\langle\langle A\rangle\rangle\subseteq M_{n}(\FF).\qed We note, though, that the results in [ 2 ] , such as Theorem 4.1 , cannot be used directly to prove Theorem 1.1 , since they are not natural in the sense of Section 3 . In particular, Theorem 4.1 needs to order the vertices in G by degrees, and this operation depends on the graph G . It is Theorem 1.2 , more precisely, the universal \circ -idempotent basis, that “converts” the idea of [ 2 ] to a natural spectrum. 5 Dimensions of double algebras of graphs As shown in Theorem 1.2 , the double algebra \FF\langle\langle A_{G}\rangle\rangle of a graph G can be used in a key sufficient condition. It is very interesting to give a more precise description of \FF\langle\langle A_{G}\rangle\rangle for a general graph G , and to investigate what would happen if \FF\langle\langle A_{G}\rangle\rangle\neq M_{n}(\FF) . Let G be a connected graph with n vertices, and let A_{G} be its adjacency matrix and {\rm diam}(G) its diameter. Since the distance matrix is in the double algebra \mathbb{F}\langle\langle A_{G}\rangle\rangle by Example 3.1 , we have natural bounds {\rm diam}(G)+1\leq\dim\mathbb{F}\langle\langle A_{G}\rangle\rangle\leq n^{2}. If the upper bound n^{2} is achieved, then Theorem 1.2 shows that some natural spectrum, which is independent of the choice of G , determines the structure of G . The lower bound {\rm diam}(G)+1 is achieved if and only if \mathbb{F}\langle\langle A_{G}\rangle\rangle is the Bose-Mesner algebra of a P-polynomial association scheme. In other words, the lower bound is achieved if and only if G is a distance-regular graph. For a connected strongly regular graph G , the double algebra admits a basis I,A_{G},J-I-A_{G} . Therefore, the strong natural spectrum of G consists of all information of linear combinations of I , A_{G} and J-I-A_{G} . In other words, knowing the strong spectrum of a strongly regular graph is equivalent to knowing the type of the strongly regular graph. Similar arguments work for connected distance-regular graphs. Knowing the strong natural spectrum of a distance regular graph is equivalent to knowing the intersection array of the graph. Therefore, for connected distance-regular graphs, any natural spectrum contains no more information than the intersection array, hence cannot be used to distinguish different distance-regular graphs with the same intersection array. This limitation can be used to prove rigorously that certain matrices in [ 8 , Section 2.5] are not natural.