Average Mixing


Let $A$ be the adjacency matrix of a graph, with the spectral decomposition \[A = \sum_r \theta_r E_r.\] The continuous quantum walk is \[U(t) = \exp(itA) = \sum_r e^{i\theta_r t} E_r.\] The probability distributions of the walk are given by the mixing matrix \[M(t) = U(t) \circ U(-t).\] In general this does not converge. However, the average over time \[\frac{1}{T} \int_0^T M(t) dt\] does converge to the average mixing matrix \[\widehat{M} = \sum_r E_r \circ E_r.\] The average mixing matrix is symmetric and doubly stochastic, so each column is a probability distribution. We compute the entropy of each column and sum them up. This sum measures how far $\widehat{M}$ is from being flat.

The following is our data in .sobj format on trees and connected graphs.

  1. The entropy sum for trees on up to 14 vertices. data
  2. The entropy sum for connected graph on up to 8 vertices. data

There are graphs with the same entropy sum. Here are some examples.