talk/dsscintuition.tex

   1 \begin{block}{From Theory}
   2 Find all the $2^n\times 2^n$ matrices $M=\dfrac{1}{n}.\hat{M}$ such that:
   3 \begin{enumerate}
   4 \item $\hat{M}_{ij}=0$ if $j$ is not a neighbor of $i$
   5 %, \textit{i.e.},  there is no edge from $i$ to $j$ in the $n$-cube.
   6 \item $0 \le \hat{M}_{ii} \le n$: the number of loops around $i$ is lesser than $n$
   7 \item Otherwise $\hat{M}_{ij}=1$ if the edge from $i$ to $j$ is kept and 0 otherwise
   8 \item For any index of line $i$, $1 \le i\le 2^n$, $n = \sum_{1 \le j\le 2^n} \hat{M}_{ij}$:
   9   the matrix is right stochastic
  10 \item For any index of column $j$,
  11   $1 \le j\le 2^n$, $n = \sum_{1 \le i\le 2^n} \hat{M}_{ij}$:
  12   the matrix is left stochastic
  13 \item All the values of $\sum_{1\le k\le 2^n}\hat{M}^k$ are strictly positive: the induced graph is strongly connected
  14 \end{enumerate}
  15 \end{block}
  16
  17
  18