上海理工大学学报  2022, Vol. 44 Issue (5): 497-501 PDF

A vertex weighted zeta function of a digraph
YANG Wenling, ZHU Lin
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Given a digraph $G$ , a weight was assigned to each vertex. For this digraph, a vertex weighted zeta function was defined, the weight of which was associated with the weights of the cycles in $G$ , induced by the vertex weights given above. Two determinant expressions of the vertex weighted zeta function were provided, using Amitsur identity and some techniques in linear algebra. When the digraph was symmetric, the existing results were natural corollaries of our results. Finally, an example was given and the specific form of the vertex weighted zeta function was calculated.
Key words: zeta function     symmetric digraph     weighted matrix
1 问题的提出

$P = ({e_1},{e_2}, \cdots ,{e_r})$ 在有向图中，如果对任意的 $i = 1, 2,\cdots ,r$ ，有 ${e_i} \in D(G)$ ，且对任意的 ${e_i}$ $i = 1,2, \cdots ,r - 1$ ，有 $t({e_i}) = o({e_{i + 1}})$ ，则 $P = ({e_1}, {e_2},\cdots ,{e_r})$ $G$ 中的一条路，并且称路 $P$ 的长度 $|P| = r$ 。若在路 $P$ 中存在一个 ${e_i}(i = 1,2, \cdots ,r - 1)$ ，有 ${e_{i + 1}} = e_i^{ - 1}$ ，则称路 $P$ 是有回路的。且对上述路 $P$ ，若进一步有 $t({e_r}) = o({e_1})$ ，则称 $P$ 为一个圈。为了方便，本文统一用 $C$ 表示圈。 ${C^s}$ $C$ 的幂，其中， ${C^s}$ 表示 $C$ 绕自己 $s$ 圈。若 $C$ 不能表示成更小圈的幂，则 $C$ 是素圈。

 $Z(G,u) = \prod\limits_{[C]} {{{\left(1 - {u^{|C|}}\right)}^{ - 1}}}$

 $Z{(G,u)^{ - 1}} = {(1 - {u^2})^{m - n}}{\text{det}}({{\boldsymbol{I}}_n} - u{\boldsymbol{A}}(G) + {u^2}({{\boldsymbol{D}}_G} - {{\boldsymbol{I}}_n}))$

 ${A}_{uv}=\left\{\begin{array}{ll}1, & (u,v)\in E(G) \\ 0, & 其他 \end{array} \right.$

Foata等[6]运用Lyndon字和Amitsur恒等式给出了图的Ihara zeta函数的行列式表达式的一个新的证明。给定一个有限全序集 $X$ ，考虑 $X$ 上的所有字组成的集合 ${X^*}$ ，且 ${X^*}$ 上有自然的字典序，它由 $X$ 上的全序诱导。全序集 $X$ 中的Lyndon字 $\pi$ ${X^*}$ 中的一个非空字，满足在其循环重排类中最小且 $\pi$ 不能写成更短的字的幂次。

${{\boldsymbol{M}}_1},{{\boldsymbol{M}}_2},\cdots,{{\boldsymbol{M}}_k}$ 是阶数相同的方阵， $L$ $\{ 1, 2,\cdots,k\}$ 上所有Lyndon字的集合。对于 $L$ 中的每个Lyndon字 $\pi = {i_1}{i_2} \cdots {i_p}$ ，记 ${{\boldsymbol{M}}_\pi } = {{\boldsymbol{M}}_{{i_1}}}{{\boldsymbol{M}}_{{i_2}}} \cdots {{\boldsymbol{M}}_{{i_p}}}$ ，那么，Amitsur恒等式为[14]

 ${\text{det}}({\boldsymbol{I}} - ({{\boldsymbol{M}}_1} + {{\boldsymbol{M}}_2} +\cdots + {{\boldsymbol{M}}_k})) = \prod\limits_{\pi \in L} {{\text{det}}} ({\boldsymbol{I}} - {{\boldsymbol{M}}_\pi })$

${\boldsymbol{M}} = ({m_{ij}})$ $n \times n$ 阶矩阵，且 $L$ 是在 $\{ 1,2, \cdots ,n\}$ 上的所有Lyndon字的集合。根据Amistur恒等式可得

 ${\text{det}}({\boldsymbol{I}} - {\boldsymbol{M}}) = \prod\limits_{\pi \in L} {(1 - {m_\pi })}$

2 有向图的顶点加权zeta函数

$G$ 是有向图， $|V(G)| = n$ $|D(G)| = m$ ${G_1}, {G_2}$ $G$ 的完全非对称部分和对称部分，记 $|D({G_1})| = {m_1},|D({G_2})| = {m_2}$ $t = \dfrac{{{m_2}}}{2}$ 。定义顶点权重函数 $\omega$ $V(G) \to \mathbb{C}$ 。设圈 $C = ({e_1},{e_2}, \cdots ,{e_r})$ ，定义 $C$ 的权重 $\omega (C)$

 $\omega (C) = \omega {(t({e_1}))^2}\omega {(t({e_2}))^2} \cdots \omega {(t({e_r}))^2} = \prod\limits_{i = 1}^r \omega {(t({e_i}))^2}$

 ${\zeta _\omega }(G,u) = \prod\limits_{[C]} \left(1 - \omega ( C){u^{|C|}}\right)^{ - 1}$

 $\begin{split}& {{{B}}}_{ef}=\left\{\begin{array}{ll}\omega {(t(e))}^{2}, & t(e)=o(f) \\ 0, & 其他 \end{array} \right. \\& {{{J}}}_{ef}=\left\{\begin{array}{ll}\omega {(t(e))}^{2}, & f={e}^{-1} \\ 0, & 其他 \end{array}\right. \end{split}$

 $\begin{split}& {a}_{uv}=\left\{\begin{array}{ll}1, & (u,v)\in D(G) \\ 0, & 其他 \end{array} \right.\\& {d}_{uv}=\left\{\begin{array}{ll}\left|\right\{e\in D({G}_{2}):t(e)=u\left\}\right|, & u=v \\ 0,\quad 其他 \end{array}\right. \end{split}$

 ${\zeta _\omega }{(G,u)^{ - 1}} = {\text{det}}({{\boldsymbol{I}}_m} - u({\boldsymbol{B}} - {\boldsymbol{J}}))$

 ${\text{det}}({\boldsymbol{I}} - {\boldsymbol{M}}) = \prod\limits_{\pi \in L} {(1 - {m_\pi })}$

 ${\text{det}}({{\boldsymbol{I}}_m} - u({\boldsymbol{B}} - {\boldsymbol{J}})) = {\text{det}}({{\boldsymbol{I}}_m} - u{\boldsymbol{M}}) = \prod\limits_{\pi \in L} {(1 - {u^{|\pi |}}{m_\pi })}$

 ${m}_{\pi }=\left\{\begin{array}{ll}\omega (C), & C=({i}_{1},{i}_{2},\cdots ,{i}_{p})\text{ }是G中的素圈 \\ 0, & 其他 \end{array} \right.$

 ${\text{det}}({{\boldsymbol{I}}_m} - u({\boldsymbol{B}} - {\boldsymbol{J}})) = \prod\limits_{[C]} {(1 - \omega (} C){u^{|C|}})$

 ${A}_{xy}=\left\{\begin{array}{ll}\omega (x)\omega (y), & (x,y)\in D({G}_{1}) \\ \dfrac{\omega (x)\omega (y)}{1-{u}^{2}\omega {(x)}^{2}\omega {(y)}^{2}}, & (x,y)\in D({G}_{2}) \\ 0, & 其他 \end{array}\right.$
 ${\bar d_{xy}} = \left\{ {\begin{array}{*{20}{l}} { \displaystyle \sum\limits_{o(e) = x,\;e \in D({G_2})}\dfrac{{ \omega {{(x)}^2}\omega {{(t(e))}^2}}}{{1 - {u^2}\omega {{(x)}^2}\omega {{(t(e))}^2}}}},&{\;x = y}\\ 0,&其他{\;} \end{array}} \right.$

 $\begin{split} {\zeta _\omega }{(G,u)^{ - 1}} =& \prod\limits_{j = {m_1} + 1}^{{m_1} + t} {(1 - {u^2}\omega (} o({e_j}){)^2}\omega {(t({e_j}))^2})\cdot\\&{\text{det}}({{\boldsymbol{I}}_n} - u\overline {\boldsymbol{A}} + {u^2}\overline {\boldsymbol{D}} ) \end{split}$

 $\begin{split}& {{\boldsymbol{S}}}_{ev}=\left\{\begin{array}{ll}\omega (t(e)), & t(e)=v \\ 0, & 其他 \end{array} \right. \\& {{\boldsymbol{T}}}_{ev}=\left\{\begin{array}{ll}\omega (o(e)), & o(e)=v \\ 0, & 其他 \end{array}\right. \end{split}$

 ${\boldsymbol{B}} = {\boldsymbol{S}}{{\boldsymbol{T}}}^{\rm{T}}$

 $\begin{split}& {\zeta }_{\omega }{(}{G,\;u)^{-1}}=\text{det}({{\boldsymbol{I}}}_{m}-u({\boldsymbol{B}}-{\boldsymbol{J}}))=\\& \quad \text{det}({{\boldsymbol{I}}}_{m}-u({\boldsymbol{S}}{}^{t}{\boldsymbol{T}}-{\boldsymbol{J}}))=\\& \quad \text{det}({{\boldsymbol{I}}}_{m}-u{\boldsymbol{S}}{}^{t}{\boldsymbol{T}}{(}{{{\boldsymbol{I}}_{m}+u{\boldsymbol{J}}}})\text{det}({\boldsymbol{I}}_{m}+u{\boldsymbol{J}}) \end{split}$

 ${\text{det}}({{\boldsymbol{I}}_m} - {\boldsymbol{PQ}}) = {\text{det}}({{\boldsymbol{I}}_n} - {\boldsymbol{QP}})$

 ${\zeta _\omega }{(G,u)^{ - 1}} = {\text{det}}({{\boldsymbol{I}}_n} - u{\;^t}{\boldsymbol{T}}{({{\boldsymbol{I}}_m} + u{\boldsymbol{J}})^{ - 1}}{\boldsymbol{S}})\;{\text{det}}({{\boldsymbol{I}}_m} + u{\boldsymbol{J}})$

 ${\text{det}}({{\boldsymbol{I}}_m} + u{\boldsymbol{J}}) = \sum\limits_{j = {m_1} + 1}^{{m_1} + t} {(1 - {u^2}\omega (} o({e_j}){)^2}\omega {(t({e_j}))^2})$

${x_{{e_j}}} = {x_j} = 1 - {u^2}\omega {(o({e_j}))^2}\omega {(t({e_j}))^2}$ ${m_1} + 1 \leqslant j \leqslant {m_1} + t, \;t = \dfrac{{{m_2}}}{2}$ ，则

 ${({{\boldsymbol{I}}_m} + u{\boldsymbol{J}})^{ - 1}} = \left[ {\begin{array}{*{20}{c}} 1& \cdots &0&0&0& \cdots &0 \\ \vdots & & \vdots & \vdots & \vdots & & \vdots \\ 0& \cdots &1&0&0& \cdots &0 \\ 0& \cdots &0&{\dfrac{1}{{{x_{{m_1} + 1}}}}}&{\dfrac{{ - u\omega {{(t({e_{{m_1} + 1}}))}^2}}}{{{x_{{m_1} + 1}}}}}& \cdots &0 \\ 0& \cdots &0&{\dfrac{{ - u\omega {{(o({e_{{m_1} + 1}}))}^2}}}{{{x_{{m_1} + 1}}}}}&{\dfrac{1}{{{x_{{m_1} + 1}}}}}& \cdots &0 \\ \vdots & & \vdots & \vdots & \vdots & & \vdots \\ 0& \cdots &0&0&0& \cdots &{\dfrac{1}{{{x_{{m_1} + t}}}}} \end{array}} \right]$

 ${{(}{\boldsymbol{T}^{\rm{T}}}{({{\boldsymbol{I}}}_{m}+u{\boldsymbol{J}})}^{-1}{\boldsymbol{S}})}_{uv}=\left\{\begin{array}{ll}\omega (u)\omega (v), \qquad \quad(u,v)\in D({G}_{1}) \\ \dfrac{\omega (u)\omega (v)}{1-{u}^{2}\omega {(u)}^{2}\omega {(v)}^{2}},\; (u,v)\in D({G}_{2}) \end{array} \right.$

 ${{\boldsymbol{T}}^{\rm{T}}{({{\boldsymbol{I}}_{2m}} + u{\boldsymbol{J}})^{ - 1}}{\boldsymbol{S}})_{vv}} = - u \displaystyle \sum\limits_{o(e) = v,\; e\in D({G_2})} \frac{{\omega {{(v)}^2}\omega {{(t(e))}^2}}}{{1 - {u^2}\omega {{(v)}^2}\omega {{(t(e))}^2}}}$

 ${\zeta _\omega }{(G,u)^{ - 1}} = \prod\limits_{j = {m_1} + 1}^{{m_1} + t} { (1 - {u^2}\omega (} o({e_j}){)^2}\omega {(t({e_j}))^2}){\text{det}}({{\boldsymbol{I}}_n} - u\overline {\boldsymbol{A}} + {u^2}\overline {\boldsymbol{D}} )$

 ${\zeta _\omega }{(G,u)^{ - 1}} = \prod\limits_{j = 1}^{m/2} {(1 - {u^2}\omega (} o({e_j}){)^2}\omega {(t({e_j}))^2}){\text{det}}({{\boldsymbol{I}}_n} - u\overline {\boldsymbol{A}} + {u^2}\overline {\boldsymbol{D}} )$

 ${\zeta _\omega }{(G,u)^{ - 1}} = {\text{det}}({{\boldsymbol{I}}_n} - u\overline {\boldsymbol{A}} (G))$

 $Z{(G,u)^{ - 1}} = {(1 - {u^2})^{t - n}}{\text{det}}[{{\boldsymbol{I}}_n} - u{\boldsymbol{A}}(G) + {u^2}({{\boldsymbol{D}}_G} + u{\boldsymbol{A}}({G_1}) - {{\boldsymbol{I}}_n})]$

 $\begin{gathered} \overline {\boldsymbol{A}} (G) = {\boldsymbol{A}}({G_1}) + \frac{1}{{1 - {u^2}}}{\boldsymbol{A}}({G_2}) \\ \overline {\boldsymbol{D}} (G) = \frac{1}{{1 - {u^2}}}{{\boldsymbol{D}}_G} \\ \end{gathered}$

 $\begin{split}& Z(G, u)^{-1} =\zeta_{\omega=1}(G, u)^{-1} =\\ &\quad \left(1 - u^{2}\right)^{t-n} \operatorname{det}\left[{\boldsymbol{I}}_{n} - u\left(\boldsymbol{A}\left(G_{2}\right) + \left( 1 - u^{2} \right) \boldsymbol{A}\left( G_{1} \right) \right) + u^{2}\left( \boldsymbol{D}_{G} - {\boldsymbol{I}}_{n} \right) \right]=\\ & \quad \left(1-u^{2}\right)^{t-n} \operatorname{det}\left[{\boldsymbol{I}}_{n}-u \boldsymbol{A}(G)+u^{2}\left(\boldsymbol{D}_{G}+u \boldsymbol{A}\left(G_{1}\right)-{\boldsymbol{I}}_{n}\right)\right] \end{split}$

a.[4] $G = {G_2}$ ，即 $G$ 是对称有向图，则 $G$ 的Ihara zeta函数 $Z(G,u)$ 有如下的行列式表达式：

 $Z{(G,u)^{ - 1}} = {(1 - {u^2})^{m/2 - n}}{\text{det}}[{{\boldsymbol{I}}_n} - u{\boldsymbol{A}}(G) + {u^2}({{\boldsymbol{D}}_G} - {{\boldsymbol{I}}_n})]$

b.[11] $G = {G_1}$ ，此时 $G$ 是完全非对称有向图，则 $G$ 的Ihara zeta函数 $Z(G,u)$ 有如下的行列式表达式：

 $Z{(G,u)^{ - 1}} = {\text{det}}({{\boldsymbol{I}}_n} - u{\boldsymbol{A}}(G)) 。$
3 例　子

 图 1 有向图 $G$ Fig. 1 Digraph $G$
 $\overline {\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} 0 & {\dfrac{{{\omega _1}{\omega _2}}}{{1 - {u^2}\omega _1^2\omega _2^2}}} & 0 & {{\omega _1}{\omega _4}} \\ {\dfrac{{{\omega _1}{\omega _2}}}{{1 - {u^2}\omega _1^2\omega _2^2}}} & 0 & {\dfrac{{{\omega _2}{\omega _3}}}{{1 - {u^2}\omega _2^2\omega _3^2}}} & 0 \\ 0 & {\dfrac{{{\omega _2}{\omega _3}}}{{1 - {u^2}\omega _2^2\omega _3^2}}} & 0 & {{\omega _3}{\omega _4}} \\ 0 & {{\omega _2}{\omega _4}} & 0 & 0 \end{array}} \right]$
 $\overline {\boldsymbol{D}} = \left[ {\begin{array}{*{20}{c}} {\dfrac{{\omega _1^2\omega _2^2}}{{1 - {u^2}\omega _1^2\omega _2^2}}} & 0 & 0 & 0 \\ 0 & {\dfrac{{\omega _1^2\omega _2^2}}{{1 - {u^2}\omega _1^2\omega _2^2}} + \dfrac{{\omega _2^2\omega _3^2}}{{1 - {u^2}\omega _2^2\omega _3^2}}} & 0 & 0 \\ 0 & 0 & {\dfrac{{\omega _2^2\omega _3^2}}{{1 - {u^2}\omega _2^2\omega _3^2}}} & 0 \\ 0 & 0 & 0 & 0 \end{array}} \right]$

 $\begin{split}& {\zeta _\omega }{(G,u)^{ - 1}}{\text{ = }}\prod\limits_{j = 4}^5 {(1 - {u^2}\omega (} o({e_j}){)^2}\omega {(t({e_j}))^2}){\text{det}}({{\boldsymbol{I}}_n} - u\overline {\boldsymbol{A}} + {u^2}\overline {\boldsymbol{D}} )=(1 - {u^2}\omega _1^2\omega _2^2)(1 - {u^2}\omega _2^2\omega _3^2)\cdot \\&\quad{\text{det}}\left[ {\begin{array}{*{20}{c}} {1 + {u^2}\dfrac{{\omega _1^2\omega _2^2}}{{1 - {u^2}\omega _1^2\omega _2^2}}}&{\dfrac{{ - u{\omega _1}{\omega _2}}}{{1 - {u^2}\omega _1^2\omega _2^2}}}&0&{ - u{\omega _1}{\omega _4}} \\ {\dfrac{{ - u{\omega _1}{\omega _2}}}{{1 - {u^2}\omega _1^2\omega _2^2}}}&{1 + {u^2}\dfrac{{\omega _1^2\omega _2^2}}{{1 - {u^2}\omega _1^2\omega _2^2}} + {u^2}\dfrac{{\omega _2^2\omega _3^2}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&{\dfrac{{ - u{\omega _2}{\omega _3}}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&0 \\ 0&{\dfrac{{ - u{\omega _2}{\omega _3}}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&{1 + {u^2}\dfrac{{\omega _2^2\omega _3^2}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&{ - u{\omega _3}{\omega _4}} \\ 0&{ - u{\omega _2}{\omega _4}}&0&1 \end{array}} \right]=\\&\quad (1 - {u^2}\omega _1^2\omega _2^2)(1 - {u^2}\omega _2^2\omega _3^2)\cdot \\&\quad {\text{det}}\left[ {\begin{array}{*{20}{c}} {\dfrac{1}{{1 - {u^2}\omega _1^2\omega _2^2}}}&{\dfrac{{ - u{\omega _1}{\omega _2}}}{{1 - {u^2}\omega _1^2\omega _2^2}}}&0&{ - u{\omega _1}{\omega _4}} \\ {\dfrac{{ - u{\omega _1}{\omega _2}}}{{1 - {u^2}\omega _1^2\omega _2^2}}}&{\dfrac{1}{{1 - {u^2}\omega _1^2\omega _2^2}} + {u^2}\dfrac{{\omega _2^2\omega _3^2}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&{\dfrac{{ - u{\omega _2}{\omega _3}}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&0 \\ 0&{\dfrac{{ - u{\omega _2}{\omega _3}}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&{\dfrac{{\omega _2^2\omega _3^2}}{{1 - {u^2}\omega _2^2\omega _3^2}}}&{ - u{\omega _3}{\omega _4}} \\ 0&{ - u{\omega _2}{\omega _4}}&0&1 \end{array}} \right]=\\&\quad 1 - {u^3}\omega _1^2\omega _2^2\omega _4^2 - {u^3}\omega _2^2\omega _3^2\omega _4^2 \end{split}$

 [1] IHARA Y. On discrete subgroups of the two by two projective linear group over p-adic fields[J]. Journal of the Mathematical Society of Japan, 1966, 18(3): 219-235. [2] SUNADA T. L-functions in geometry and some applications[M]//Curvature and Topology of Riemannian Manifolds. Berlin, Heidelberg: Springer-Verlag, 1986: 266–284. [3] SUNADA T. Fundamental groups and laplacians[M]//Geometry and Analysis on Manifolds. Berlin, Heidelberg: Springer-Verlag, 1988: 248–277. [4] BASS H. The Ihara-Selberg zeta function of a tree lattice[J]. International Journal of Mathematics, 1992, 3(6): 717-797. [5] STARK H M, TERRAS A A. Zeta functions of finite graphs and coverings[J]. Advances in Mathematics, 1996, 121(1): 124-165. [6] FOATA D, ZEILBERGER D. A combinatorial proof of Bass's evaluations of the Ihara-Selberg zeta function for graphs[J]. Transactions of the American Mathematical Society, 1999, 351(6): 2257-2274. [7] KOTANI M, SUNADA T. Zeta functions of finite graphs[J]. Journal of Mathematical Sciences (University of Tokyo), 2000, 7(1): 7-25. [8] MIZUNO H, SATO I. Zeta functions of digraphs[J]. Linear Algebra and its Applications, 2001, 336(1/3): 181-190. [9] MIZUNO H, SATO I. Weighted zeta functions of digraphs[J]. Linear Algebra and its Applications, 2002, 355(1/3): 35-48. [10] MIZUNO H, SATO I. Weighted zeta functions of graphs[J]. Journal of Combinatorial Theory, Series B, 2004, 91(2): 169-183. [11] HORTON M D. Ihara zeta functions of digraphs[J]. Linear Algebra and its Applications, 2007, 425(1): 130-142. [12] KONNO N, MITSUHASHI H, MORITA H, et al. A new weighted Ihara zeta function for a graph[J]. Linear Algebra and its Applications, 2019, 571: 154-179. [13] ZHU L. A vertex weighted Bartholdi zeta function for a graph[J]. Linear Algebra and its Applications, 2021, 621: 254-271. [14] AMITSUR S A. On the characteristic polynomial of a sum of matrices[J]. Linear and Multilinear Algebra, 1980, 8(3): 177-182. [15] SATO I. Bartholdi zeta functions of group coverings of digraphs[J]. Far East Journal of Mathematical Sciences, 2005, 18(3): 321-339.