1
$\begingroup$

Let $G_n$ be the graph obtained from the $n-$cube graph $C_n$ by adding one extra edge between each vertex and its antipode (vertex whose label has all $0$'s and $1$'s switched)
Note: The $C_n$ graph is constructed by labelling each vertex with a string of $n$ symbols consisting only of $0$'s and $1$'s
Find the number of closed walks in $G_n$ which begin and hence end at the origin $\textbf{0}=(0,0,...,0)$

Using Radon transforms and the associated matrices, I already know that the number of walks of length $l$ associated with a vertex $u$ is given by $$\frac{1}{2^n} \sum_{i=0}^{n} \binom{n}{i}(n-2i)^l$$

I also understand that this means that all diagonal entries of $A^l$ are given by the same formula as above (no $u$ dependence)

Also notice that we want to find any one of the diagonal entries of the matrix $(A+B)^l$ with $$B=\begin{bmatrix} 0 & 0 & 0 & \dots & 0 & 1 \\ 0 & 0 & 0 & \dots & 1 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 0 & \dots & 0 & 0 \\ 1 & 0 & 0 & \dots & 0 & 0 \end{bmatrix}$$

Note: I considered the adjacency matrix of the graph by ordering the vertices in a dictionary order with $0<1$ and hence we have that if $A$ is the adjacency matrix of $C_n$, then $A+B$ is the adjacency matrix of $G_n$

So now it boils down to figuring out the $(1,1)-$th entry of $(A+B)^l$ where the $(1,1)-$th entry of $A^l$ is known

How do I proceed ? The two matrices don't commute and binomial is hence not applicable :(

There has got to be some other way is what I'm guessing

$\endgroup$

1 Answer 1

1
$\begingroup$

I'll start by giving a more elementary, combinatorial answer (because that's what I did first). At the end, I finish off your proof with the matrices. By the way, they do commute!

The first question was essentially "Consider the vector space $\Bbb F_2^n$ and the set $S = \{e_1, \dotsc, e_n\}$. How many sequences of elements of $S$ of length $l$ sum to $0$?" The new question is the same, but if you instead consider $S' = S \cup \{v\}$, where $v = (1, 1, \dotsc, 1)^{\mathsf T}$ is the antipode of $0$. It shouldn't be too hard to get a double sum expression by thinking about it this way: if $v$ appears an even number of times, the remainder must sum to $0$ - ie each $e_i$ appears an even number of times. If $v$ appears an odd number of times, each $e_i$ must appear an odd number of times.

In more detail - let's say the number of paths of length $l$ from $0$ to $0$ is $a_l$ (which you've calculated already) and the number of paths from $0$ to $v$ is $b_l$ (we're considering $n$ to be fixed). By similar reasoning to this, $b_l$ is the coefficient of $x^l/l!$ in \begin{align*} \biggl(\sum_{k=0}^\infty \frac{x^{2k + 1}}{(2k + 1)!}\biggr)^{n} &= \left(\frac{e^x - e^{-x}}{2}\right)^n \\ &= 2^{-n} \sum_{k = 0}^n \binom nk (-1)^k e^{(n - k)x} e^{-kx} \\ &= 2^{-n} \sum_{k = 0}^n \binom nk (-1)^k e^{(n - 2k)x}, \end{align*} so \begin{equation*} b_l = 2^{-n} \sum_{i = 0}^n \binom ni (-1)^i (n - 2i)^l \end{equation*} Then by pure combinatorics, summing over the possible number of appearances of $v$ in the path, the number of paths from $0$ to $0$ in $G_n$ of length $l$ is \begin{equation*} \sum_{\text{$k \le l$ even}} \binom lk a_{l - k} + \sum_{\text{$k \le l$ odd}} \binom lk b_{l - k} \end{equation*} Now we might observe that this does actually recombine into one double sum, because the expressions for $a_l$ and $b_l$ are so similar. Then we can make some more simplifications: \begin{align*} 2^{-n} \sum_{k = 0}^l \binom lk \sum_{i = 0}^n (-1)^{ik} \binom ni (n - 2i)^{l - k} &= 2^{-n} \sum_{i = 0}^n \binom ni \sum_{k = 0}^l \binom lk (-1)^{ik} (n - 2i)^{l - k} \\ &= 2^{-n} \sum_{i = 0}^n \binom ni ((-1)^i + n - 2i)^l \end{align*} This nice form would certainly seem to suggest there is some sort of simpler argument :)


Indeed, we know that the eigenvalues of $A$ are $n - 2j$, with multiplicity $\binom nj$. I'll treat the cube as the powerset of $[n]$ for this part. Let's work in the free vector space (over your favourite field of characteristic other than $2$) on the vertices of the cube, with basis $\{e_X : X \subseteq [n]\}$.

For any subset $Y \subseteq [n]$, consider the vector $u_Y = \sum_X \varepsilon_{YX} e_X$, where $\varepsilon_{YX}$ is $1$ if $|X \cap Y|$ is even, and $-1$ otherwise. As discussed here, these form a basis of eigenvectors for $A$, with $u_Y$ having eigenvalue $n - 2|Y|$.

Now let's think about eigenvectors of $B$. The action of $B$ on the basis is quite straightforward, since $B$ is a permutation matrix and a product of tranpositions - we have $B e_X = e_{[n] \setminus X}$. In particular, $B$ has eigenvalues $\pm 1$, and corresponding eigenspaces spanned by vectors of the form $e_X + e_{[n] \setminus X}$ (the $1$-eigenspace) and $e_X - e_{[n] \setminus X}$ (the $-1$-eigenspace) respectively.

In particular - observe that if $|Y|$ is even, then $\varepsilon_{YX} = \varepsilon_{Y,[n] \setminus X}$, because $Y$ is partitioned into $Y \cap X$ and $Y \cap ([n] \setminus X)$, so they have the same parity. Hence, if $|Y|$ is even, then $u_Y$ lies in the $1$-eigenspace of $B$.

Similarly, if $|Y|$ is odd, then $u_Y$ lies in the $-1$-eigenspace of $B$.

Therefore, the $u_Y$ are still a basis of eigenvectors for $A + B$, now with eigenvalues $n - 2|Y| + (-1)^{|Y|}$. (Indeed, this implies that $A$ and $B$ do commute :). I'm not sure why you thought they didn't. It should be fairly intuitive that they do, since $B$ is an involutive automomorphism of the graph. The $(i, j)$ entry of $AB$ represents whether there's an edge from vertex $i$ to vertex $Bj$, and the $(i, j)$ entry of $BA$ represents whether there's one from $Bi$ to $j$). Anyway, now we could use the binomial theorem to get some type of double sum.

But having the eigenvalues (and their multiplicities) in hand, it's quite easy to compute the trace of $(A + B)^l$ - it's \begin{equation*} \sum_{i = 0}^n \binom ni ((-1)^i + n - 2i)^l \end{equation*} This of course over-counts by a factor of $2^n$.

$\endgroup$
1
  • $\begingroup$ Beautiful ! Thats quite nice !! Though now that I think about it, the last two lines would suffice for $\textit{me}$ because trace is actually sum $l-$th powers of the eigen values ! $\endgroup$
    – Snowflake
    Oct 24, 2023 at 23:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .