Graph spectrum 引理：对于二分图G,如果a是A(G)的一个特征值，且重数为k,那么-α也是A(G)的一个特征值，重数也是k U V 证明：把A表示为U[0B1 假设()是A的一个特征向量，对应特征值为a: ()=[g81G)=a) 因此B'x=ay,By=ax。再考虑() A()g81()()-(）=-(） 因此-α也是A的特征值 最后，注意到：α的重数为k一存在k个线性无关的特征向量对应的特征值α 对每一个分别取反后依然是线性无关的，因此-α的重数也为k 8
Graph spectrum 引理：对于二分图�，如果�是� � 的一个特征值，且重数为�，那么−�也是� � 的一个特征值，重数也是� 证明：把�表示为 � � � � 0 � �! 0 假设 " # 是� 的一个特征向量，对应特征值为�： �� �!� = 0 � �! 0 � � = � � � 因此 �!� = ��, �� = ��。再考虑 " $# � � −� = 0 � �! 0 � −� = −�� �!� = −�� �� = −� � −� 因此 −�也是� 的特征值 最后，注意到：�的重数为 � ⇔ 存在 �个线性无关的特征向量对应的特征值� 对每一个分别取反后依然是线性无关的，因此−�的重数也为 � 8
Graph spectrum 事实上，引理的反方向也是对的。 引理：设A(G)的特征值为a1≥a2≥…≥an,如果i,a:=-an-i+1, 那么G一定是二分图 证明：首先证明：对于任意奇数k,∑=0 A的特征值为a1,a2,,an则Ak的特征值为a,a吃，，a,因此对于任意奇数k, trace(a)=∑=0 组合含义：(4*)=长度为k的从到的行走方案的数目 trae(4)=∑a)u=0,又因为a)u≥0，所以(4a=0 即，对于任意奇数k,长度为k的环路不存在。因此，一定是二分图 9
Graph spectrum 事实上，引理的反方向也是对的。 引理：设� � 的特征值为�/ ≥ �0 ≥ ⋯ ≥ �1，如果∀�, �% = −�&$%'(，那么�一定是二分图 证明：首先证明：对于任意奇数�, ∑2 �2 3 = 0 � 的特征值为�(, �), … , �&则 �3 的特征值为�/ 3, �0 3, … , �1 3，因此对于任意奇数k， ����� �3 = : 2 �2 3 = 0 组合含义: �3 2,4 = 长度为k的从�到�的行走方案的数目 ����� �3 = : 2 �3 2,2 = 0，又因为 �3 2,2 ≥ 0，所以 �3 2,2 = 0 即，对于任意奇数k ，长度为k的环路不存在。因此，一定是二分图 9